Bài giảng Giải thuật nâng cao - Giải thuật tham lam - Ngô Quốc Việt

GIẢI THUẬT THAM LAM 
TS. NGÔ QUỐC VIỆT 
2015 
Nội dung 
1. Giới thiệu 
2. Bài toán cây bao trùm tối thiểu (MST) 
3. Huffman coding 
4. Phủ tập hợp 
Giải thuật nâng cao-Lý thuyết số 2 
Giới thiệu 
• Thuật giải tham lam xây dựng giải pháp từng bước, 
trong đó chọn lời bước kế tiếp dựa trên tiêu chí có 
lợi & hiển nhiên nhất. 
• Cách tiếp cận có thể cho lời giải không đúng trong 
một số trường hợp, nhưng phần lớn đạt được kết 
quả tối ưu. 
• Bài giảng minh họa greedy với: MST, Huffman 
coding, phủ tập hợp. 
Giải thuật nâng cao-Lý thuyết số 3 
Cây bao trùm tối tiểu – Minimum spanning tree 
4 
• Cho đồ thị G liên thông vô hướng, cây bao trùm (cây 
khung) được định nghĩa là đồ thị con dạng cây 
(không có chu trình) có mọi đỉnh của G và mọi đỉnh 
liên thông nhau. Một đồ thị có thể có nhiều cây bao 
trùm. 
or or or 
Một số Spanning Trees từ A Graph A 
Cây bao trùm tối tiểu 
5 
• Số lượng cây bao trùm của đồ thị G 
𝑡 𝐺 = 
1 𝐺 𝑙à 𝑐â𝑦
𝑛 𝐺 đồ 𝑡ℎị 𝑣ò𝑛𝑔 𝐶𝑛
𝑛𝑛−2 𝐺 đồ 𝑡ℎị đầ𝑦 đủ 𝐾𝑛
• Đồ thị đầy đủ: mọi cặp đỉnh được nối bởi cạnh duy nhất. 
• Bigraph: tập đỉnh trong G chia thành hai tập rời nhau U, 
V. Mỗi cạnh chỉ nối giữa điểm trong U với điểm trong V. 
• Tìm cây bao trùm: theo chiều rộng, theo chiều sâu 
Cây bao trùm tối tiểu 
6 
• Cây bao trùm nhỏ nhất là cây bao trùm có tổng 
trọng số các cạnh nhỏ hơn tất cả các cây bao trùm 
khác 
• Thuật giải tìm MST trên đồ thị có hoặc không có 
trọng số: Prim, Kruskal, Boruvka. 
5 
7 
2 
1 
3 
4 
2 
1 
3 
Complete Graph Minimum Spanning Tree 
MST-Thuật giải Prim 
7 
• Tương tự thuật giải Dijkstra, với trọng số cạnh thay 
chiều dài đường đi 
1. Tạo cây ban đầu với đỉnh bất kỳ thuộc graph. 
2. Thêm cạnh vào cây : chọn cạnh có trọng số nhỏ 
nhất (chưa có trong cây đang tạo) nối với các 
đỉnh của cây và thêm vào cây 
3. Lặp lại (đến khi mọi đỉnh trong cây) 
MST-Thuật giải Prim 
8 
• Input: đồ thị trọng số không rỗng với tập đỉnh V và 
cạnh E (trọng số có thể âm). 
• Khởi tạo: Vnew = {x}, với x is là node bất kỳ(starting 
point) từ V, Enew = {} 
• Lặp đến khi Vnew = V: 
• Chọn cạnh {u, v} với minimal weight sao 
cho u thuộc Vnew và v không thuộc (nếu có nhiều cạnh 
cùng trọng số, chọn ngãu nhiên một cạnh) 
• Thêm v vào Vnew, và {u, v} to Enew 
• Output: Vnew và Enew chứa minimal spanning tree 
MST-Thuật giải Prim 
9 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
10 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
11 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
12 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
13 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
14 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
15 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
16 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
17 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim 
18 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
4 
1 
2 3 
2 1 
3 
5 
3 
4 
2 
5 6 
4 
4 
10 
A 
B C 
D 
E F 
G 
H 
I 
J 
MST-Thuật giải Prim-Phân tích 
19 
• Running Time: 𝑂(𝑚 + 𝑛 log 𝑛) (𝑚 =
 𝑒𝑑𝑔𝑒𝑠, 𝑛 = 𝑛𝑜𝑑𝑒𝑠) 
• Nếu không dùng heap, the run time sẽ là 𝑂(𝑛2). 
• Không cần sắp xếp theo trọng số cạnh trước. 
• Vì xét theo đỉnh  không cần xét khả năng tạo chu 
trình 
MST-Thuật giải Krusal 
20 
1. Sắp xếp tăng dần theo trọng số cạnh 
2. Chọn cạnh có trọng số nhỏ nhất. Kiểm tra nếu 
không tạo thành chu trình, chọn nó. Ngược lại 
chọn cạnh khác có trọng số nhỏ và không tạo chu 
trình. 
3. Lặp bước 2 đến khi có (𝑉 − 1) cạnh trong cây bao 
trùm 
MST-Thuật giải Krusal 
Giải thuật nâng cao-Lý thuyết số 21 
MST-Thuật giải Krusal 
22 
edge dv 
(D,E) 1 
(D,G) 2 
(E,G) 3 
(C,D) 3 
(G,H) 3 
(C,F) 3 
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
23 
edge dv 
(D,E) 1  
(D,G) 2 
(E,G) 3 
(C,D) 3 
(G,H) 3 
(C,F) 3 
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
24 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3 
(C,D) 3 
(G,H) 3 
(C,F) 3 
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
25 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3 
(G,H) 3 
(C,F) 3 
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
Accepting edge (E,G) would create a cycle 
MST-Thuật giải Krusal 
26 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3 
(C,F) 3 
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
27 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3 
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
28 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4 
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
29 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4  
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4 
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
30 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4  
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4  
(B,F) 4 
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
31 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4  
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4  
(B,F) 4  
(B,H) 4 
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
32 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4  
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4  
(B,F) 4  
(B,H) 4  
(A,H) 5 
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
33 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4  
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
3 
2 
4 
6 
3 
4 
3 
4 
8 
4 
3 
10 edge dv 
(B,E) 4  
(B,F) 4  
(B,H) 4  
(A,H) 5  
(D,F) 6 
(A,B) 8 
(A,F) 10 
MST-Thuật giải Krusal 
34 
edge dv 
(D,E) 1  
(D,G) 2  
(E,G) 3  
(C,D) 3  
(G,H) 3  
(C,F) 3  
(B,C) 4  
5 
1 
A 
H 
B 
F 
E 
D 
C 
G 
2 
3 
3 
3 
edge dv 
(B,E) 4  
(B,F) 4  
(B,H) 4  
(A,H) 5  
(D,F) 6 
(A,B) 8 
(A,F) 10 
Done 
Total Cost =  dv = 21 
4 
} 
MST-Thuật giải Krusal-Phân tích 
35 
• Running Time = O(m log n) (m = edges, n = 
nodes). QuickSort algorithm 
• Kiểm tra cạnh tạo ra chu trình có thể chậm. Tuy 
nhiên, sử dụng data structure “union-find” sẽ khắc 
phục nhược điểm. 
• Trong một số trường hợp (có đỉnh nối với cạnh dài 
nhất với đồ thị)  phải kiểm tra mọi cạnh. 
Phủ tập hợp-ví dụ 
• Một khu quy hoạch (có nhiều khu phố) cần xác định các 
vị trí xây trường với hai ràng buộc 
• Trường phải trong khu phố (town) 
• Không học sinh/phụ huynh nào phải đi qua xa (vd: 10km) từ 
nhà đến trường 
• Câu hỏi: cần xây tối thiểu bao nhiêu trường? 
• Yêu cầu trên có thể giải thông qua khái niệm phủ tập 
hợp. 
Giải thuật nâng cao-Lý thuyết số 36 
Các khu phố Khu phố trong 
phạm vi 10km 
Phủ tập hợp-định nghĩa 
• Cho tập phổ biến 𝑈 = 𝑢1, 𝑢2,  , 𝑢𝑛 
• Gọi 𝑆1, 𝑆2,  , 𝑆𝑘 ⊆ 𝑈 là các tập con có các trọng số 
tương ứng 𝑐1, 𝑐2,  , 𝑐𝑛 
• Mục tiêu: cần tìm 𝐼 = 1,2,  ,𝑚 sao cho cực tiểu 
 𝑐𝑖𝑖 và 𝑆𝑖𝑖 = 𝑈. 
• Hỏi: U, Si, ci trong bài toán xây các trường? 
• 𝑈 ={các town trong khu quy hoạch} 
• Với mỗi khu phố x, Sx là tập các town trong phạm vi 10km. 
Trường tại x sẽ phủ các town này 
• cx=1, x ? 
Giải thuật nâng cao-Lý thuyết số 37 
Phủ tập hợp-giải thuật greedy 
• Chọn Si chứa nhiều town nhất chưa được phủ 
• Lặp lại cho đến khi các Si được chọn phủ U. 
• Ví dụ xây trường 
• Chọn Sa, Sa chứa a, b, d, e, k, i, h. 
• Chọn Sf hoặc Sg, vì chứa f, g. 
• Chọn Sc và Sj chứa chính nó. 
• 𝑐𝑖𝑖 = 4. 
• Nhận xét: có thể chọn giải pháp tốt hơn? 
• Xây trường tại b, e, và i là giải pháp tốt hơn 
Giải thuật nâng cao-Lý thuyết số 38 
Phủ tập hợp-giải thuật greedy 
1. 𝐶 = *+ 
2. While 𝐶 ≠ 𝑈 
 Tìm tập S có cost nhỏ nhất 
 Đặt 𝛼 =
𝑐(𝑆)
𝑆−𝐶
 Với mỗi 𝑒 ∈ 𝑆\C, đặt 𝑝𝑟𝑖𝑐𝑒(𝑒) = 𝛼 
 𝐶 = 𝐶 ∪ 𝑆 
3. Ouput C 
Giải thuật nâng cao-Lý thuyết số 39 
Phủ tập hợp-giải thuật greedy-ví dụ 
• Cho 𝑈 = *1,2,3,4,5+, 𝑆 = *𝑆1, 𝑆2, 𝑆3+, 𝑆1 = *4,1,3+,
 𝐶𝑜𝑠𝑡(𝑆1) = 5, 𝑆2 = *2,5+, 𝐶𝑜𝑠𝑡(𝑆2) = 10, 𝑆3 =
 *1,4,3,2+, 𝐶𝑜𝑠𝑡(𝑆3) = 3. Minh họa với Greedy 
• Lần lặp 1: 𝑆1 = 𝐶𝑜𝑠𝑡(𝑆1)/|𝑆1 – 𝐶| = 5/3; 𝑆2 =
 𝐶𝑜𝑠𝑡(𝑆2)/|𝑆2 – 𝐶| = 10/2; 𝑆3 = 𝐶𝑜𝑠𝑡(𝑆3)/
|𝑆3 – 𝐶| = ¾  chọn S3. 
• Lần lặp 2: S1 = Cost(S1)/|S1 – C| = 5/0; S2 = 
Cost(S2)/|S2 – C| = 10/1  chọn S2. 
• Trường hợp này greedy có nghiệm tối ưu 
Giải thuật nâng cao-Lý thuyết số 40 
Phủ tập hợp-giải thuật greedy-ví dụ 
• 𝑈 = *1,2,3,4,5,6,7,8,9,10,11,12,13+; S1 = {1, 2} S2 = 
{2, 3, 4, 5} S3 = {6, 7, 8, 9, 10, 11, 12, 13} S4 = {1, 3, 5, 
7, 9, 11, 13} S5 = {2, 4, 6, 8, 10, 12, 13}. Giả sử cost 
của các subset là giống nhau 
• Kết quả của greedy algorithm là C= {S3, S2, S1}, so 
với nghiệm tối ưu {S4, S5}. 
Giải thuật nâng cao-Lý thuyết số 41 
Phủ tập hợp-giải thuật greedy-ví dụ 
IBM finds computer viruses (wikipedia) 
• Elements: 5000 virus máy tính 
• Sets: 9000 substring, mỗi substring khoảng 20++ 
bytes thể hiện virus. 
• Xác định phủ tập hợp khoảng 180 substrings phủ 
toàn bộ U. 
Chỉ cần search trong 180 substring để xác định có 
virus hay không? 
Giải thuật nâng cao-Lý thuyết số 42 
SC là bài toán NP-complete 
• Định lý: Set Cover (SC) là NP-complete 
• Chứng minh: 
Giải thuật nâng cao-Lý thuyết số 43 
INSTANCE: Given a universe U of n elements, a collection 
of subsets of U, S = {S1, , Sm}, and a positive integer b 
QUESTION: Is there a , |C| ≤ b, 
such that 
(Note: The subcollection {Si | } satisfying the above 
condition is called a set cover of U 
SC là bài toán NP-complete (tt) 
• Cần chứng minh SC thuộc NP. Cho subcollection C, 
dễ dàng kiểm chứng rằng nếu |C| ≤ b và union của 
các tập trong C chứa mọi phần tử của U. 
• Để chứng minh định lý, cần phải chứng minh Vertex 
Cover (VC) ≤p Set Cover (SC) 
Cho instance C của VC (undirected graph G=(V,E) và 
số nguyên dương j), chúng ta cần xây dựng C’ của SC 
trong thời gian đa thức sao cho C là satisfiable iff C’ 
là satisfiable. 
Giải thuật nâng cao-Lý thuyết số 44 
SC là bài toán NP-complete (tt) 
• Construction: Đặt U = E. Định nghĩa n phần tử của U 
và tập S như sau: 
• Đánh nhãn mọi đỉnh trong V từ 1 đến n. Đặt Si là tập các 
cạnh nối với đỉnh i. Sau đó, đặt b = j. Cách xây dựng này là 
poly-time ứng với size của VC instance 
• Chú ý: mỗi cạnh ứng với mỗi phần tử trong U và 
mỗi đỉnh ứng với and một set trong S. 
Giải thuật nâng cao-Lý thuyết số 45 
VERTEX-COVER p SET-COVER 
Giải thuật nâng cao-Lý thuyết số 46 
one set for every vertex, 
containing the edges it covers 
VC 
one element 
for every edge 
SC 
SC là bài toán NP-complete (tt) 
• Cần chứng minh C là satisfiable iff C’ là satisfiable. 
• Nghĩa là, cần chứng minh nếu original instance của 
VC là YES instance iff constructed instance of SC là 
YES instance. 
• (→) 
• Giả sử G có phủ đỉnh C kích thước tối đa là j. Theo 
cách xây dựng trên, C ứng với collection C’ của các 
subsets của U. Vì b = j, |C’| ≤ b. C’ phủ mọi 
elements trong U vì C “phủ ” mọi cạnh trong G. Để 
thấy điều này, xét bất kỳ phần tử nào của U. Sao cho 
một phần tử là cạnh trong G. Vì C là set cover, có ít 
nhất một endpoint của cạnh này thuộc C. 
Giải thuật nâng cao-Lý thuyết số 47 
SC là bài toán NP-complete (tt) 
• (←) 
• Giả sử có set cover C’ kích thước tối đa b trong 
constructed instance. Vì mỗi tập trong in C’ được 
kết hợp với đỉnh trong G, đặt C là tập các đỉnh này. 
Thì |C| = |C’| ≤ b = j. C là vertex cover của G vì C’ là 
set cover. 
• Để thấy điều này, xét cạnh bất kỳ e. Vì e thuộc U, nên 
C’ phải chứa ít nhất một tập set có chứa e. Theo 
cách xây dựng trên, chỉ một tập hợp chứa e ứng với 
các là các endpoint của e. Vậy C phải chứa ít nhất 
một endpoint của e. 
Giải thuật nâng cao-Lý thuyết số 48 
Giải pháp 
Algorithm 1: (trường hợp uniform cost) 
1. C = empty 
2. while U is not empty 
3. pick a set Si such that Si covers the most 
 elements in U 
4. remove the new covered elements from U 
5. C = C union Si 
6. return C 
Giải thuật nâng cao-Lý thuyết số 49 
Solutions 
• Trường hợp non-uniform cost 
• Phương pháp tương tự. Tại mỗi bước lặp, thay vì chọn 
tập Si sao cho Si phủ nhiều nhất các phần tử chưa được 
phủ, thì chọn tập Si có cost-effectiveness α nhỏ nhất, với 
α được định nghĩa : 
𝛼 =
𝑐 𝑆𝑖
𝐴𝑖 ∩ 𝑈
• Câu hỏi: tại sao chọn smallest α? Tạy sao định nghĩa α 
như trên 
Giải thuật nâng cao-Lý thuyết số 50 
Solutions 
Algorithm 2: (trường hợp non-uniform cost) 
1. C = empty 
2. while U is not empty 
3. pick a set Si such that Si has the smallest α 
4. for each new covered elements e in U 
5. set price(e) = α 
6. remove the new covered elements from U 
7. C = C union Si 
8. return C 
 Giải thuật nâng cao-Lý thuyết số 51