So sánh phương pháp tham lam và quy hoạch động trong xây dựng thuật toán để ứng dụng bồi dưỡng học sinh giỏi

1. Mở đầu:
1.1. Lí do chọn đề tài:
	Tin học là một môn học mới trong các trường trung học phổ thông (THPT), được đưa vào giảng dạy chính thức trong các trường THPT từ năm 2006 – 2007. Tuy nhiên trong thực tế môn Tin học đã được đưa vào tham gia thi học sinh giỏi cấp tỉnh, cấp quốc gia từ rất lâu.
Như chúng ta đã biết, trong các kỳ thi học sinh giỏi thì các lớp bài toán về tối ưu hóa luôn được ưu tiên lựa chọn trong các đề thi vì tính ứng dụng vào thực tiễn cao. Để giải quyết lớp các bài toán tối ưu đó, có rất nhiều phương pháp như: phương pháp nhánh cận, phương pháp quy hoạch động, phương pháp tham lam...Tuy nhiên lại chưa có các tài liệu nghiên cứu nào chuyên sâu về vấn đề này, đồng nghiệp, nhà trường chưa có nhiều kinh nghiệm để giải quyết, khắc phục. Vậy “Có phải tất cả các bài toán tối ưu đều có thể áp dụng được tất cả các phương pháp để giải không?; “Làm thế nào để nhận dạng được bài toán có thể áp dụng phương pháp nào?; “Làm thế nào có thể giải một bài toán bằng các phương pháp đó?”;
Chính vì những lý do trên mà trong nội dung của sáng kiến kinh nghiệm lần này tôi xin giới thiệu một chuyên đề mới trong công tác bồi dưỡng học sinh giỏi của mình đó là: “So sánh phương pháp tham lam và quy hoạch động trong xây dựng thuật toán để ứng dụng bồi dưỡng học sinh giỏi.”
1.2. Mục đích nghiên cứu:
Nhằm nâng cao chất lượng giảng dạy cũng như học tập của học sinh trong quá trình bồi dưỡng học sinh giỏi từ đó nâng cao chất lượng giải trong các kỳ thi học sinh giỏi Tin học.
1.3. Đối tượng nghiên cứu:
Học sinh đội tuyển khối 10 và khối 11.
1.4. Phương pháp nghiên cứu:
Trong phần này tôi sẽ đưa ra phương pháp nghiên cứu xây dựng cơ sở lý thuyết tổng quan hai phương pháp tham lam, quy hoạch động và giới thiệu thêm một số phương pháp khác, từ đó đưa ra một số ví dụ cụ thể có sử dụng hai phương pháp trên để có cơ sở so sánh, nhằm giúp học sinh nhận biết và vận dụng vào các loại bài toán cụ thể.
1.5. Những điểm mới của sáng kiến kinh nghiệm:
	Trong sáng kiến kinh nghiệm này, tôi có rút ra ưu điểm cũng như hạn chế của cả 2 phương pháp tham lam và quy hoạch động, từ đó đưa ra hướng giải quyết, cách vận dụng nhằm giúp học sinh vận dụng linh hoạt với từng loại bài toán giúp đạt hiểu quả tối ưu nhất.
2. Nội dung của sáng kiến kinh nghiệm:
2.1. Cơ sở lý luận:
Để giải quyết một bài toán tối ưu trong công tác bồi dưỡng học sinh giỏi thì có rất nhiều phương pháp để giải quyết bài toán này, ví dụ như phương pháp Tham lam, phương pháp Quay lui, phương pháp tìm Nhánh cận, phương pháp Quy hoạch động, ... Tuy nhiên, làm thế nào để nhận dạng được bài toán có thể áp dụng phương pháp nào?, phương pháp nào thì tối ưu hơn?... Vậy tôi đưa ra hai phương pháp tham lam và quy hoạch động để tìm hiểu kỹ hơn làm rõ các câu hỏi trên.
2.2. Thực trạng vấn đề:
Xuất phát từ thực tế, trong các kỳ thi học sinh giỏi tin học thì các lớp bài toán về tối ưu hóa luôn được ưu tiên lựa chọn trong các đề của các kỳ thi học sinh giỏi Tỉnh, các kỳ thi Olympic, các kỳ thi Quốc gia, ví dụ như: đề thi HSGQG Tin học năm học 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019; đề thi Olympic Tin học 30/4 hầu hết các năm; đề thi HSG Tin học Tỉnh Thanh Hóa hầu hết các năm.
Hơn thế nữa, học sinh thường không nắm rõ phải sử dụng phương pháp nào khi giải các lớp bài toán tối ưu hóa.
2.3. Các giải pháp .
2.3.1. Phương pháp quy hoạch động
2.3.1.1. Khái niệm về phương pháp quy hoạch động
a. Khái niệm
Phương pháp quy hoạch động (Dynamic Programming) là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu toàn bộ hay một phần kết quả tính toán tại mỗi bước trước đó với mục đích sử dụng lại.
Như vậy, Quy hoạch động = Chia để trị + Mảng (lưu lại kết quả).
Phương pháp quy hoạch động do nhà toán học người Mỹ Richard Bellman (1920-1984) phát minh năm 1953. Phương pháp này dùng để giải các bài toán tối ưu có bản chất đệ quy, tức là tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con.
Điểm khác nhau cơ bản giữa quy hoạch động và phương pháp đệ quy là:
Phương pháp đệ quy giải quyết bài toán theo hướng top-down, nghĩa là để giải bài toán ban đầu, ta phải đi giải tất cả các bài toán con của nó. Đây là một phương pháp hay, tuy nhiên phương pháp này sẽ gặp hạn chế về mặt thời gian, tốc độ do phải tính đi tính lại nhiều lần một số bài toán con giống nhau nào đó.
Phương pháp quy hoạch động sử dụng nguyên lý bottom-up, nghĩa là "đi từ dưới lên". Đầu tiên, ta sẽ phải giải các bài toán con đơn giản nhất, có thể tìm ngay ra nghiệm. Sau đó kết hợp các bài toán con này lại để tìm lời giải cho bài toán lớn hơn và cứ như thế cho đến khi giải được bài toán yêu cầu. Với phương pháp này, mỗi bài toán con sau khi giải xong đều được lưu trữ lại và đem ra sử dụng nếu cần. Do đó tiết kiệm bộ nhớ và cải thiện được tốc độ.
b. Đặc điểm chung của quy hoạch động
Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).
Quy hoạch động cần phải có bảng phương án.
Ý tưởng cơ bản của phương pháp quy hoạch động là tránh tính toán lại các bài toán con đã xét, nói cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ.
Tóm lại: 
+ Quy hoạch động dùng để giải quyết bài toán tối ưu theo nguyên lý “chia để trị” nhưng thực chất là một phương pháp cải tiến hơn của phương pháp giải quyết bài toán theo hướng đệ quy.
+ Quy hoạch động làm giảm độ phức tạp, giảm thời gian giải quyết bài toán.
+ Quy hoạch động thường tiếp cận theo hướng từ dưới lên (Bottom-up).
c. Các yêu cầu của một bài toán tối ưu sử dụng được phương pháp quy hoạch động
Một bài toán tối ưu muốn giải được bằng phương pháp quy hoạch động khi bài toán tối ưu đó có các đặc điểm dưới đây:
i. Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn.
ii. Vì quy hoạch động là đi giải tất cả các bài toán con nên nếu không đủ không gian vật lý lưu trữ kết quả (bộ nhớ, đĩa) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được.
iii. Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước.
2.3.1.2 Các bước giải bài toán tối ưu bằng phương pháp quy hoạch động
Bước 1: Lập công thức truy hồi
Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tương quan quyết định của bước đang xử lý với các bước đã xử lý trước đó. Hoặc tìm cách phân rã bài toán thành các “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thước đã cho với kết quả của các “bài toán con” cùng kiểu có kích thước nhỏ hơn của nó nhằm xây dựng phương trình truy toán (dạng hàm hoặc thủ tục đệ quy). 
Bước 2: Tổ chức dữ liệu và chương trình
Tổ chức dữ liệu sao cho đạt các yêu cầu sau: 
Dữ liệu được tính toán dần theo các bước. 
Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại. 
Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập. 
Cụ thể: 
Các giá trị tối ưu của bài toán thường được lưu trữ trong một bảng (mảng một chiều hoặc hai, ba, v.v chiều). 
Cần lưu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang giải. 
Dựa vào công thức và các giá trị đã có trong bảng để tìm dần các giá trị còn lại của bảng. 
Ngoài ra còn cần mảng lưu trữ nghiệm tương ứng với các giá trị tối ưu trong từng gian đoạn. 
Dựa vào bảng lưu trữ nghiệm và bảng giá trị tối ưu trong từng giai đoạn đã xây dựng, tìm ra kết quả bài toán.
Bước 3: Truy vết, tìm nghiệm của bài toán dựa vào bảng phương án
Làm tốt thuật toán bằng cách thu gọn hệ thức truy hồi và giảm kích thước miền nhớ. Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước. 
Trong một số trường hợp có thể thay mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0, 1 bởi mảng hai chiều mới bằng cách dùng kỹ thuật quản lý bit.
2.3.1.3. Ưu điểm và hạn chế của phương pháp quy hoạch động
 a. Ưu điểm
Tiết kiệm được thời gian thực hiện vì không cần phải tính đi tính lại nhiều lần một số bài toán con giống nhau.
Chương trình thực hiện nhanh do không phải tốn thời gian giải lại một bài toán con đã được giải.
Kỹ thuật quy hoạch động có thể vận dụng để giải các bài toán tối ưu, các bài toán có công thức truy hồi.
b. Hạn chế
Số lượng các bài toán con cần giải quyết và lưu giữ kết quả là rất lớn.
Sự kết hợp lời giải của các bài toán con chưa chắc cho ta lời giải của bài toán ban đầu.
Việc tìm công thức truy hồi hoặc tìm cách phân rã bài toán nhiều khi đòi hỏi sự phân tích tổng hợp rất công phu, dễ sai sót, khó nhận ra như thế nào là thích hợp, đòi hỏi nhiều thời gian suy nghĩ. Đồng thời không phải lúc nào kết hợp lời giải của các bài toán con cũng cho kết quả của bài toán lớn hơn.
Khi bảng lưu trữ đòi hỏi mảng hai, ba chiều thì khó có thể xử lý dữ liệu với kích cỡ mỗi chiều lớn đến hàng trăm.
Có những bài toán tối ưu không thể giải được bằng quy hoạch động.
Tóm lại: Không phải lúc nào việc kết hợp các bài toán con cũng cho ta kết quả của bài toán lớn hơn. Hay nói cách khác là việc tìm kiếm "công thức truy hồi" rất khó khăn. Ngoài ra, số lượng các bài toán con cần lưu trữ có thể rất lớn, không chấp nhận được vì dữ liệu và bộ nhớ máy tính không cho phép.
2.3.1.4. Bài toán balo 0-1
a. Phát biểu bài toán
Cho một cái ba lô có thể đựng một trọng lượng M và n đồ vật, mỗi đồ vật i có một trọng lượng wi và một giá trị vi. (M, wi và vi là số nguyên dương) Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá M và tổng giá trị là lớn nhất. 
b. Thuật giải
 Xây dựng công thức
Bài toán con: F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các đồ vật {1, 2, , i} với giới hạn trọng lượng j. 
Tham số: 2 tham số i và j, i = 0..n, j = 0..M;
Công thức truy hồi:
Với giới hạn trọng lượng j, việc chọn tối ưu trong số các đồ vật {1, 2, , i-1, i} để có giá trị lớn nhất sẽ có hai khả năng:
 + Nếu trọng lượng hiện tại của ba lô là j nhỏ hơn trọng lượng của đồ vật i là wi (j<wi) thì ba lô không thể chứa đồ vật thứ i. Khi đó F[i, j] là giá trị lớn nhất có thể chọn bằng cách chọn trong số các đồ vật {1, 2, , i-1) với giới hạn trọng lượng j, tức là: 
F[i, j] = F[i-1, j]
 + Nếu trọng lượng hiện tại của ba lô là j lớn hơn hoặc bằng trọng lượng của đồ vật i là wi (j≥wi) thì ba lô có thể chứa đồ vật thứ i. Khi đó xảy ra hai trường hợp:
Nếu chỉ cần sử dụng các đồ vật {1, 2, , i-1) mà cho tổng giá trị ba lô lớn nhất thì không cần sử dụng đồ vật thứ i.
Sử dụng đồ vật thứ i nếu cho tổng giá trị lớn nhất thì F[i, j] bằng giá trị đồ vật thứ i là vi cộng với giá trị lớn nhất có thể có được bằng các chọn trong số các đồ vật {1, 2, , i-1) với giới hạn trọng lượng j-wi. Tức là về mặt giá trị thu được: 
F[i, j] = vi + F[i-1, j-wi]
Theo cách xây dựng F[i, j] là giá trị lớn nhất có thể nên tra sẽ lấy giá trị lớn nhất trong hai trường hợp trên:
F[i, j] = max(F[i-1, j], vi + F[i-1, j-wi] 
Như vậy công thức truy hồi tính F[i, j] là:
	0 nếu i = 0 hoặc j = 0
F[i, j] = F[i-1, j] nếu j < wi 	
 max(F[i-1, j], vi + F[i-1, j-wi]) nếu j ≥ wi
Điều kiện đầu: F[0, j] = 0, j = 1..M
 F[i, 0] = 0; i = 1..n
 Tổ chức dữ liệu
Xây dựng mảng hai chiều F[0..n, 0..M] để lưu lại các giải pháp của các bài toán con với F[i, j] là giá trị lớn nhất có thể có bằng cách chọn trong các đồ vật {1, 2, , i} với giới hạn trọng lượng j. 
 Truy vết
Bảng phương án gồm n+1 dòng, M+1 cột. Trước tiên ta điền cơ sở quy hoạch động đó là dòng 0 gồm toàn số 0, sau đó sử dụng công thức truy hồi để tính dòng 1 trên cơ sở dòng 0 đã có, dùng dòng 1 để tính dòng 2,, đến khi tính hết dòng n. Sau khi tính xong bảng phương án thì giá trị F[n, M] thu được chính là giá trị lớn nhất khi chọn trong các n đồ vật với giới hạn trọng lượng M.
Nếu F[n, M] = F[n-1, M] thì tức là không chọn đồ vật thứ n, ta truy tiếp F[n-1, M].
Nếu F[n, M] ≠ F[n-1, M] thì ta thông báo rằng phép chọn tối ưu có chọn đồ vật thứ n và truy tiếp F[n-1, M-wn].
Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.
Như vậy, thuật toán quy hoạch động cho bài toán cái ba lô như sau:
Procedure BALO_qhd;
Begin
 Fillchar(F[0],sizeof(F[0]),0);
 For i:=1 to n do
 For j:=1 to M do
 begin
 F[i,j]:=F[i-1,j];
 if (j>=w[i]) and (F[i,j] < F[i-1,j-w[i]]+v[i]) then
 F[i,j]:=F[i-1,j-w[i]]+v[i];
end;
End;
c. Độ phức tạp thuật toán 
Thuật toán tính mảng n x M phần tử bởi hai vòng lặp lồng nhau nên độ phức tạp là O(nM).
d. Ví dụ
Ta có một ba lô có trọng lượng là 5 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng bên. 
Bảng 2.1. Thông số các đồ vật
Loại đồ vật
Trọng lượng
Giá trị
1
2
3
2
3
4
3
4
5
4
5
6
Dựa vào công thức truy hồi ta tính các giá trị F[i, j] thu được bảng phương án như sau:
Theo bảng phương án thì F[4, 5] = 7, chính là giá trị lớn nhất khi chọn trong 4 đồ vật.
Ta thấy F[4, 5] = F[3, 5], tức là ta không chọn đồ vật thứ 4
F[3, 5] = F[2, 5], tức là ta không chọn đồ vật thứ 3
Truy tiếp, ta thấy F[2, 5] ≠ F[1, 5] nên ta thông báo chọn đồ vật thứ 2 và truy tiếp F[n-1, M-wn] chính là F[1, 2].
Tiếp theo, ta thấy F[1, 2] ≠ F[0, 2] nên ta thông báo chọn đồ vật thứ 1, truy tiếp đến F[0, 0] thì dừng.
Như vậy loại đồ vật được sử dụng là loại 1 và 2 với tổng giá trị lớn nhất là 7.
2.3.1.5. Bài toán đổi tiền
a. Phát biểu bài toán
Cho n loại tiền giấy có mệnh giá là a1, a2, , an. Cần đổi số tiền S. Tìm phương án đổi S thành ít tờ nhất gồm các loại tiền trên. Mỗi phương án là một bộ (k1, k2, , kn), trong đó ki là số tờ mệnh giá ai, i = 1..n. Bài toán quy về tìm bộ (k1, k2, , kn) sao cho:
k1.a1 + k2.a2 + + kn.an = S 
và tổng k1 + k2 +  + kn nhỏ nhất. 
b. Thuật giải
 Xây dựng công thức
Bài toán con: L[i] là số tờ cần đổi trong cách đổi ít tờ nhất của số tiền i.
Tham số: 1 tham số i, với i = 0..S;
Công thức truy hồi:
L[i] = min{L[i - a[k]] + 1 | k = 1..n & i ≥ a[k]}
Điều kiện đầu: L[0] = 0;
 Tổ chức dữ liệu
Xây dựng mảng một chiều L[0..S] với L[i] là số tờ cần đổi trong cách đổi ít tờ nhất của số tiền i. Khi đó số tờ cần đổi trong cách đổi ít tờ nhất của số tiền S sẽ là L[S].
Xây dựng mảng a[0..n] để ghi nhận mệnh giá của các đồng tiền. Khi đó a[i] là mệnh giá đồng i.
Xây dựng mảng KQ[0..S] để ghi nhận lại loại tờ cần đổi
 Truy vết
Như vậy dãy L sẽ gồm S+1 ô. Trước tiên ta điền cơ sở quy hoạch động đó chính là ô đầu tiên sẽ là 0, sau đó ta sử dụng công thức truy hồi để tính tất cả các ô còn lại.
Sau khi tính xong dãy L thì giá trị L[S] thu được chính là số tờ cần đổi trong cách đổi ít tờ nhất của số tiền S.
Tại mỗi bước xây dựng dãy L, mỗi khi đặt L[i] := L[i - a[k]] + 1, ta đặt KQ[i] := k để lưu lại loại tờ tiền k cần chọn trong phương án đổi ít tờ nhất của số tiền i.
Sau khi tính dãy KQ, ta truy vết:
KQ[S] là loại tờ tiền đầu tiên được chọn,
KQ[S – a[KQ[S]]] là loại tờ tiền thứ hai được chọn,
Như vậy, thuật toán quy hoạch động cho bài toán đổi tiền như sau:
Procedure DOITIEN_qhd;
Begin
 Fillchar (L, sizeof(L), 0);
 Fillchar (KQ, sizeof(KQ), 0);
 For i:=1 to S do
 begin
 for k:=1 to n do
 if a[k] <= i then
 if (L[i] = 0) or (L[i-a[k]] +1 < L[i]) then
 begin
 L[i] := L[i-a[k]] + 1;
 KQ[i] := k;
 end;
 end;
End;
c. Đánh giá độ phức tạp 
Thuật toán sử dụng 2 vòng lặp lồng nhau. Vậy độ phức tạp O(Sn).
d. Ví dụ
Cho 3 loại tiền giấy lần lượt có mệnh giá là 1, 2, 4, Cần đổi số tiền S = 10. Tìm phương án đổi S thành ít tờ nhất gồm các loại tiền trên. 
Hai dãy L và KQ sau khi tính sẽ là:
 Bảng 2.3. Bảng phương án ví dụ đổi tiền
i
0
1
2
3
4
5
6
7
8
9
10
Số tờ (L[i])
0
1
1
2
1
2
2
3
2
3
3
Loại tờ (KQ[i])
0
1
2
1
3
1
2
1
3
1
2
Theo bảng phương án, ta thu được L[10] = 3 có nghĩa là với số tiền S = 10 thì ta cần đổi ít nhất là 3 tờ.
Ta có KQ[10] = 2, có nghĩa ta chọn tờ đầu tiên là loại tờ thứ 2 tương ứng với mệnh giá là 2 (a[2] = 2), như vậy số tiền cần đổi còn lại là 10 – 2 = 8.
Với KQ[8] = 3, ta sẽ chọn tờ thứ 2 là loại tờ thứ 3 tương ứng với mệnh giá là 4 (a[3] = 4), như vậy số tiền cần đổi còn lại là 8 – 4 = 4.
Với KQ[4] = 3, ta sẽ chọn tờ thứ 3 là loại tờ thứ 3 tương ứng với mệnh giá là 4 (a[3] = 4), như vậy số tiền cần đổi còn lại là 4 – 4 = 0.
Như vậy với số tiền S = 10 thì ta cần đổi ít nhất là 3 tờ gồm 1 tờ loại 2 và 2 tờ loại 3.
2.3.2. Phương pháp tham lam
2.3.2.1 Khái niệm về phương pháp tham lam
a. Khái niệm
Là một phương pháp dùng để giải quyết bài toán để tìm kiếm lựa chọn tối ưu ở mỗi bước với hy vọng tìm được tối ưu toàn cục.
b. Nội dung kĩ thuật tham lam
Tham lam theo cách hiểu dân gian là trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này chuyển sang món ngon thứ baKỹ thuật tham ăn thường được vận dụng giải bài toán tối ưu tổ hợp bằng cách xây dựng một phương án X. Phương án X được xây dựng bằng cách lựa chọn từng thành phần Xi của X cho đến khi hoàn chỉnh tức là đủ n thành phần. Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta không còn gì để chọn mà phải chấp nhận giá trị cuối cùng còn lại.
2.3.2.2. Tính chất của phương pháp tham lam
Thành phần then chốt trước tiên là tính lựa chọn tham lam, một giải pháp tối ưu toàn cục bằng cách lựa chọn tối ưu cục bộ khi có nhiều sự lựa chọn thì ta có thể lựa chọn phương án nào tốt nhất trong thời điểm hiện tại của bài toán hiện tại mà không cần quan tâm đến kết quả của giai đoạn sau.
Đây là chỗ khác nhau giữa các thuật toán tham lam và quy hoạch động. Trong quy hoạch động tại mỗi bước ta thực hiện một lựa chọn, nhưng sự lựa chọn phụ thuộc vào giải pháp cho bài toán con, do đó ta xử lý bài toán quy hoạch động từ dưới lên (Bottom - Up), nghĩa là xử lý những bài toán nhỏ hơn đến bài toán con lớn hơn. Đối với giải thuật tham lam ta lựa chọn phương án tốt nhất ngay lúc đó và giải quyết bài toán con sau khi lựa chọn được thực hiện. Việc lựa chọn bởi một thuật toán tham lam lựa chọn cho đến thời điểm hiện tại đó, nhưng nó không thể phụ thuộc bất kỳ trong tương lai hay những giải pháp cho các bài toán con. Vì vậy không giống như thuật toán quy hoạch giải quyết bài toán từ dưới lên, mà một thuật toán tham lam giải quyết bài toán từ trên xuống. Thuật toán tham lam thường đạt hiệu lực khi ta thực hiện lựa chọn trong bài toán con. Ví dụ trong bài toán chọn hoạt động, giả sử rằng ta có các hoạt động được sắp xếp sẵn theo thứ tự tăng dần của một thời điểm kết thúc, ta cần kiểm tra mỗi một hoạt động. Thường là nó đươc xử lí trước khi đưa vào hay sử dụng một cấu trúc dữ liệu thích hợp (thường là một hàng đợi ưu thế) nên ta có thể thực hiện lựa chọn tham lam một cách nhanh chóng . Vì vậy với việc lựa chọn đó sẽ đưa ra một thuật toán hiệu quả.
2.3.2.3. Đặc điểm chung của phương pháp tham lam
Mục đích xây dựng bài toán giải nhiều lớp bài toán khác nhau, đưa ra quyết định dựa ngay vào thuật toán đang có, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ. Vì vậy thuật toán dễ đề xuất, thời gian tính nhanh nhưng có một số bài toán không cho kết quả tối ưu.
Giải thuật tham lam có năm phần:
- Một tập hợp các ứng viên để từ đó tạo ra lời giải.
- Một hàm lựa chọn, theo đó để lựa chọn các ứng viên tốt nhất bổ sung vào lời giải.
- Một hàm khả thi, dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải.
- Một hàm mục tiêu, ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh.
- Một hàm đánh giá chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.
2.3.2.4. Ưu điểm và hạn chế của phương pháp tham lam
a. Ưu điểm
Áp dụng kĩ thuật tham lam sẽ cho một giải thuật thời gian đa thức. Hơn nữa việc thiết kế, cài đặt đơn giản.
b. Nhược điểm
Tuy nhiên, sử dụng