Bài giảng Giải thuật nâng cao - Giải thuật xấp xỉ - Ngô Quốc Việt

GIẢI THUẬT XẤP XỈ 
TS. NGÔ QUỐC VIỆT 
2015 
Nội dung 
1. Nhắc lại NP và các vấn đề liên quan 
2. Giới thiệu giải thuật xấp xỉ 
3. Minh họa giải thuật xấp xỉ với bài toán phủ đỉnh, 
TSP. 
4. Tóm tắt 
Giải thuật nâng cao-Giải thuật xấp xỉ 2 
Bài toán NP 
• Giải thuật hiệu quả: xác định lời giải tối ưu 
trong thời gian đa thức 
• Tuy nhiên, hầu hết các bài toán tối ưu là NP khó. 
Nghĩa là không tồn tại giải thuật hiệu quả để giải. 
• NP là một trong những complexity class cơ 
bản. 
• NP: nondeterministic polynomial time. 
Giải thuật nâng cao-Giải thuật xấp xỉ 3 
Bài toán NP 
• P: thuật giải thời gian đa thức. Lớp bài toán P có 
tính chất bao đóng chính xác (tính cộng, tính nhân). 
• NP: tập các bài toán quyết định (trả lời YES hoặc 
NO) theo đó một số instances cụ thể của bài toán 
đang xét được giải và kiểm chứng (verifier) trong 
thời gian đa thức. 
• NP = Problems with Efficient Algorithms 
for Verifying Proofs/Certificates/Witnesses 
• Định nghĩa: NP là lớp các vấn đề có efficient 
verifiers, i.e. có giải thuật đa thức để kiểm chứng lời 
giải đã cho là đúng 
Giải thuật nâng cao-Giải thuật xấp xỉ 4 
Bài toán NP 
• Phần lớn các bài toán thực tế là NP. Có thể 
efficiently verify nếu given short proof là valid, 
nhưng không tìm được efficient algorithm để giải. 
• 
• Lớp NP là extremely interesting. 
• Hầu hết các vấn đề trong CS, math, biology, physics, 
chemistry, economics, management, sociology, 
business, v.v, đều thuộc lớp NP. 
• Xem thêm compendium of NP optimization 
problems. 
Giải thuật nâng cao-Giải thuật xấp xỉ 5 
Verifier V của bài toán NP-ví dụ 
• Xét bài toán tìm subset có tổng bằng zero (hay hằng 
số bất kỳ). 
• Nhận xét: số lượng các subset của tập hợp là lũy 
thừa (bao nhiêu?) 
• Tuy nhiên: cho subset cụ thể  dễ dàng kiểm chứng 
(verify) tổng các phần tử của nó là zero. Giải thuật 
kiểm chứng tổng zero của một subset được gọi là 
verifier. 
Giải thuật nâng cao-Giải thuật xấp xỉ 6 
Cận dưới của NP problem 
• Xem: https://www.youtube.com/watch?v=K2-
Y4a3BtSE 
• Reductions: giải một yêu cầu dựa trên các hàm hay 
problem khác như Subroutine/Oracle/Black Box. 
Không quan tâm đến độ phức tạp subroutine. 
• Giải thuật reduction A có sử dụng hàm O được ký hiệu: 
𝐴𝑂 
• Vấn đề Q là black-box reducible thành O và viết 𝑄 ≤𝑇 𝑂 
iff tồn tại giải thuật A sao cho mọi input x, thì 𝑄 𝑥 =
𝐴𝑂(𝑥) 
• Nếu A chạy trong thời gian đa thức thì được gọi 
là polynomial-time black-box reduction, ký hiệu 
𝑄 ≤𝑇
𝑃 𝑂. (Subscript T thể hiện ”Turing”) 
Giải thuật nâng cao-Giải thuật xấp xỉ 7 
Cận dưới của NP problem 
• Vấn đề Q là many-one reducible to problem O và viết 
𝑄 ≤𝑚 𝑂 iff có giải thuật A sao cho mọi input x, thì 
𝑄 𝑥 = 𝑂 𝐴 𝑥 
• Nếu reduction algorithm A là polynomial time thì 
được gọi là polynomial-time many-one reduction, 
ký hiệu 𝑄 ≤𝑚
𝑃 𝑂 
• Nếu có polynomial-time many-one reduction từ vấn 
đề A thành NP problem B, thì A thuộc lớp NP. 
Giải thuật nâng cao-Giải thuật xấp xỉ 8 
NP-complete 
• NP-complete là tập các vấn đề vừa NP, vừa NP-khó. 
• A là NP-complete iff 
• A là bài toán NP, và 
• Mọi bài toán B thuộc lớp NP, thì B là polynomial-
time many-one reducible to A 𝐵 ≤𝑚
𝑝 𝐴 
•Nếu problem là NP-complete, thì không tồn tại 
polynomial-time algorithm để tìm nghiệm tối 
ưu 
• Thường sử dụng giải thuật xấp xỉ, tham lam, 
heuristic,  để giải các bài toán NP. 
Giải thuật nâng cao-Giải thuật xấp xỉ 9 
NP & liên quan 
Giải thuật nâng cao-Giải thuật xấp xỉ 10 
NP-complete: ví dụ 
heuristic/text/class/more-np.html 
https://en.wikipedia.org/wiki/List_of_NP-
complete_problems 
Yêu cầu: Anh/Chị đọc và trình bày 2 bài viết trên 
Giải thuật nâng cao-Giải thuật xấp xỉ 11 
Giới thiệu giải thuật xấp xỉ 
• Giải thuật xấp xỉ xác định lời giải xấp xỉ của các bài 
toán tối ưu 
• Thường dùng cho các vấn đề NP-khó 
• Khác với giải thuật heuristic (chỉ cần lời giải đủ tốt, 
và đủ nhanh) 
• Giải thuật xấp xỉ cần xác định rõ chất lượng xấp xỉ, 
độ phức tạp. 
• Ví dụ: giải thuật xấp xỉ cho bài toán phủ đỉnh. 
Giải thuật nâng cao-Giải thuật xấp xỉ 12 
Định nghĩa giải thuật xấp xỉ 
• Giải thuật xấp xỉ  cho bài toán tối ưu là giải thuật 
hiệu quả (thời gian đa thức) cho mọi instance của 
vấn đề sao cho lời giải nằm trong ngưỡng  so với 
lời giải tối ưu thực sự. 
•  : là tỉ lệ xấp xỉ (approximation ratio), hay thừa số 
xấp xỉ (approximation factor). 
• Định nghĩa: approximation ratio 𝝆 𝒏 
• Chi phí của optimal solution là C*, chi phí của 
approximation algorithm là C, thì 
• 𝝆 𝒏 ≥ 𝑚𝑎𝑥(
𝐶
𝐶∗
,
𝐶∗
𝐶
) 
• Gọi là: (n)-approximation algorithm. 
Giải thuật nâng cao-Giải thuật xấp xỉ 13 
Định nghĩa giải thuật xấp xỉ 
• Vấn đề Maximization thì 
 𝐶∗/𝜌(𝑛) ≤ 𝐶 ≤ 𝐶∗ 
• Vấn đề Minimization thì 
 𝐶∗ ≤ 𝐶 ≤ 𝜌(𝑛). 𝐶∗ 
• ρ(n) không nhỏ hơn 1. 
• 1-approximation algorithm là optimal solution 
• Mục tiêu là tìm polynomial-time approximation 
algorithm với small constant approximation ratios 
Giải thuật nâng cao-Giải thuật xấp xỉ 14 
Approximation scheme 
• Approximation scheme là approximation algorithm 
thêm tham số Є>0, sao cho với Є>0 xác định thì 
scheme là (1+Є)-approximation algorithm. 
• Polynomial-time approximation scheme: runs in 
time polynomial in the size of input. 
• Khi Є giảm, thì thời gian thực hiện có thể tăng 
nhanh, ví dụ 𝑂 𝑛
2
𝜖 
Giải thuật nâng cao-Giải thuật xấp xỉ 15 
Phủ đỉnh 
• 𝐺 = (𝑉, 𝐸) là đồ thị, V={tập đỉnh}, E={tập cạnh} 
• 𝑆 ⊆ 𝑉 là một phủ, nếu ∀ (𝑢, 𝑣) ∈ 𝐸, thì 𝑢 ∈ 𝑆, hoặc 
𝑣 ∈ 𝑆 hoặc 𝑢, 𝑣 ∈ 𝑆. 
• Ví dụ: 
Giải thuật nâng cao-Giải thuật xấp xỉ 16 
Phủ đỉnh S 
Một số ứng dụng của phủ đỉnh 
• Bioinformatics 
• Cơ sở cho novo genome assembly sử dụng phương pháp 
overlap-consensus (liên ứng). CABOG, Celera, xây dựng 
overlap graph của nhiều whole-genome shotgun reads, với 
each vertex ứng với read và cạnh biểu diễn mutual overlap 
giữa hai reads 
• SNP Assembly Problem 
• Computer network securities 
• Mô phỏng sự lan truyền của worm máy tính nhằm tìm giải 
pháp bảo vệ mạng máy tính lớn. 
Giải thuật nâng cao-Giải thuật xấp xỉ 17 
Phủ đỉnh 
• OPTIMIZATION VERSION: 
• INPUT: graph G 
• OUTPUT: vertex cover S of minimum-size (số đỉnh ít 
nhất) 
• DECISION VERSION: 
• INSTANCE: graph G, integer k 
• QUESTION: does G have vertex cover of size  k 
Giải thuật nâng cao-Giải thuật xấp xỉ 18 
Phủ đỉnh 
• Dạng bài toán NP-Complete 
• Sử dụng dạng giải thuật tham lam, hoặc xấp xỉ để 
giải quyết 
• Yêu cầu: Sử dụng chiến lược tham lam để giải bài 
phủ đỉnh. Trình bày thuật giải, cho biết độ phức tạp, 
và cài đặt chương trình minh họa. 
Giải thuật nâng cao-Giải thuật xấp xỉ 19 
Phủ đỉnh-xấp xỉ 
Giải thuật 1 
1. Chọn cạnh A bất kỳ, bỏ tất cả các cạnh có nối đến hai đỉnh 
của A ( kể cả cạnh A) 
2. Chọn cạnh khác & lặp lại bước 1 đến khi mọi cạnh bị loại 
bỏ. 
vertex-cover tìm được theo giải thuật 1, thường gấp đôi phủ 
đỉnh tối ưu 
Giải thuật nâng cao-Giải thuật xấp xỉ 20 
Phủ đỉnh-xấp xỉ-giải thuật 1 
Giải thuật nâng cao-Giải thuật xấp xỉ 21 
Optimal 
Size=3 
Near Optimal 
size=6 
Phủ đỉnh-xấp xỉ-giải thuật 1 
Giải thuật nâng cao-Giải thuật xấp xỉ 22 
4 
1 2 3 
6 5 7 
4 
1 2 3 
6 5 7 
Not cover 
Phủ đỉnh-xấp xỉ-giải thuật 1 
Giải thuật nâng cao-Giải thuật xấp xỉ 23 
4 
1 2 3 
6 5 7 
4 
1 2 3 
6 5 7 
Cover 
Size=4 
Cover 
Size=7 
Phủ đỉnh-xấp xỉ-giải thuật 1 
Giải thuật nâng cao-Giải thuật xấp xỉ 24 
4 
1 2 3 
6 5 7 
4 
1 2 3 
6 5 7 
Cover 
Size=5 
Cover 
Size=3 
Phủ đỉnh-xấp xỉ-giải thuật 1 
APPROX-VERTEX-COVER là 2-approximate algorithm 
• Gọi c là phủ đỉnh xấp xỉ, và c* là phủ đỉnh tối ưu, A là 
tập cạnh của lệnh 4. Cần chứng minh 
𝑐
𝑐∗
≤ 2. 
• Lệnh 5 thêm cả hai đỉnh, trong khi chỉ cần thêm một 
hoặc hai đỉnh trên 
• Không có hai cạnh trong A, phủ cùng một đỉnh trong 
c* (vì đã bị xóa-lệnh 6)  𝑐∗ ≥ 𝐴 
• Vì vậy: 
𝑐
𝑐∗
≤ 2. 
Giải thuật nâng cao-Giải thuật xấp xỉ 25 
Phủ đỉnh-xấp xỉ-giải thuật 1 
Giải thuật nâng cao-Giải thuật xấp xỉ 26 
4 
1 2 3 
6 5 7 
𝛼 = 𝑀𝑎𝑥(6/3, 3/6) = 2 
4 
1 2 3 
6 5 7 
𝛼 = 𝑀𝑎𝑥(4/3, 3/4) = 1.33 
Phủ đỉnh-xấp xỉ 
Giải thuật 2 
1. Chọn đỉnh v có bậc lớn nhất, cho v vào S. 
2. Xóa mọi cạnh có nối với v. 
3. Tiếp tục bước 1, 2 đến khi không còn cạnh nào 
Giải thuật 3 
1. Tìm matching M tối đại trong G. 
2. Với mỗi cạnh 𝑢, 𝑣 ∈ 𝑀, thêm hai đỉnh u, v vào S. 
Giải thuật nâng cao-Giải thuật xấp xỉ 27 
(ln n)-approximation 
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ố 28 
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ố 29 
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ố 30 
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 S 
Giải thuật nâng cao-Lý thuyết số 31 
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ố 32 
INSTANCE: Cho universe U n phần tử, tập các subset 
của U, S = {S1, , Sm}, và số nguyên dương b 
QUESTION: Tồn tại tập 𝐶 ⊆ 1,2, ,𝑚 , |C| ≤ b, sao 
cho 
 𝑆𝑖
𝑖∈𝐶
= 𝑈 
Subcollection 𝑆𝑖 | 𝑖 ∈ 𝐶 thỏa điều kiện trên là set 
cover của U 
SC là bài toán NP-complete (tt) 
1. Cần chứng minh SC thuộc NP. Dễ dàng kiểm 
chứng điều kiện YES của instance trên. Nghĩa là, 
cho subcollection C, nếu |𝐶| ≤ 𝑏 và hội của các 
tập trong C chứa mọi phần tử của U theo thời gian 
đa thức. 
2. Để 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ố 33 
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à 
thời gian đa thức ứng với kích thước 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 một set trong S. 
Giải thuật nâng cao-Lý thuyết số 34 
Phủ đỉnh có trọng số 
• Tìm tập các đỉnh của graph sao cho mỗi cạnh chứa 
ít nhất một đỉnh trong tập. 
• Mỗi đỉnh có trọng số, cần tìm phủ đỉnh total weight 
nhỏ nhất. 
• Các phủ đỉnh: *1,3,4+; *1,7,5+ 
Giải thuật nâng cao-Giải thuật xấp xỉ 35 
1 
2 
7 
4 
5 
3 
6 
VERTEX-COVER p SET-COVER 
• Vertex Cover là trường hợp đặc biệt của Set 
Cover 
• Chuyển vertex cover sang set cover: 
1. T = the set of edges E 
2. Các subsets ứng với từng vertex, mỗi subset 
chứa tập các cạnh nối với corresponding vertex 
Giải thuật nâng cao-Giải thuật xấp xỉ 36 
VERTEX-COVER p SET-COVER 
• T = { (1, 3), (3,7), (1, 7), (4, 5), (4, 6) } 
• Subsets: 
1. S1 = { (1, 3), (1, 7) } w = 1 
2. S3 = { (1, 3), (3, 7) } w = 3 
3. S7 = { (1, 7), (3, 7) } w = 7 
4. S4 = { (4, 5), (4, 6) } w = 4 
5. S6 = { (4, 6) } w = 6 
6. S5 = { (4, 5) } w = 5 
Giải thuật nâng cao-Giải thuật xấp xỉ 37 
1 
2 
7 
4 
5 
3 
6 
VERTEX-COVER p SET-COVER 
Giải thuật nâng cao-Lý thuyết số 38 
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ố 39 
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ố 40 
Giải thuật Set Cover 
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ố 41 
Giải thuật Set Cover 
• Trường hợp non-uniform cost 
• Phươn pháp ương tự. Tại mỗi bước lặp, tah 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ố 42 
Giải thuật Set Cover 
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ố 43 
Giải thuật xấp xỉ cho Max-Cut 
• Cho đồ thị 𝐺 = 𝑉, 𝐸 . Yêu cầu tách thành hai tập 
đỉnh S, T sao cho số cạnh bị cắt (cut edge: một đỉnh 
trong S, đỉnh kia trong T) là nhiều nhất 
Giải thuật 2-approximation 
1. S ← Ø , T ← V 
2. Nếu chuyển một từ S sang T, hoặc ngược lại mà 
làm tăng số cut edges, thì thực hiện chuyển nút. 
Repeat 2. 
3. Output số cut edges. 
Giải thuật nâng cao-Giải thuật xấp xỉ 44 
Bài toán TSP 
• Cho đồ thị 𝐺 = 𝑉, 𝐸 có trọng số, vô hướng. Từ 
đỉnh bất kỳ đi đến mọi đỉnh khác và quay trở lại 
đỉnh xuất phát với chi phí thấp nhất 
• TSP thuộc lớp NP-complete 
• Không tồn tại polynomial-time approximation 
algorithm với constant approximation ratio. 
Giải thuật nâng cao-Giải thuật xấp xỉ 45 
3 
1 2 
4 
2 1 
3 
30 
20 
1 
Bài toán TSP 
• Có thể giải TSP theo 2 bước 
• Tìm MST cho đồ thị đang xét 
• Bắt đầu từ bất kỳ node và di chuyển trên các cung của 
MST, và thêm cung tắt để đi khi cần. 
Giải thuật nâng cao-Giải thuật xấp xỉ 46 
start node 
red bold arcs 
form a tour 
Bài toán TSP 
• Thông thường, có thể giả thiết triangle inequality 
đúng cho cost function c: E  R xác định trên các 
cung của đồ thị G=(V,E) : 
 cuw  cuv + cvw for any u, v, w V 
• Định lý: 
 If the cost function satisfies the triangle inequality, 
 then the algorithm for TSP 
 is a 2-approximation algorithm. 
Giải thuật nâng cao-Giải thuật xấp xỉ 47 
w 
v 
u 
Bài toán TSP 
 Với e là cung trên tour, thì (triangle inequality), 
 c(e)  c(f1)++c(fk) 
 Vd: c15  c13 + c35 
 c23  c23 
 Mỗi cung của tree (**) là shortcut 
 nhiều nhất hai lần. 
 Vd: cung tree 3-5 là shortcut bởi cung tour 1-5 và 5-6 . 
 Nhận xét 
𝑐𝑜𝑠𝑡 𝑡𝑠𝑝 𝑡𝑜𝑢𝑟 = 𝑐(𝑒)
𝑒∈𝑇𝑜𝑢𝑟
≤ 2. 𝑐 𝑒
𝑒∈𝑀𝑆𝑇
= 2. 𝑐𝑜𝑠𝑡(𝑀𝑆𝑇) 
Giải thuật nâng cao-Giải thuật xấp xỉ 48 
start node 
red bold arcs 
of tour 
1 
2 
3 
4 
5 
6 
Bài toán TSP 
• Trọng số cạnh là khoảng cách giữa hai đỉnh 
Giải thuật nâng cao-Giải thuật xấp xỉ 49 
Use Prim’s algorithm to get a 
MST 
a 
b 
c 
d 
e 
f g 
h 
Bài toán TSP 
• Trọng số cạnh là khoảng cách giữa hai đỉnh 
• Bất phương trình tam giác thỏa 
Giải thuật nâng cao-Giải thuật xấp xỉ 50 
Use Prim’s algorithm to get a 
MST 
a 
b 
c 
d 
e 
f g 
h 
Chọn “a”là root 
Preorder tree walk 
a b c h d e f g 
Bài toán TSP 
• Tổng trọng số gấp đôi lời giải tối ưu 
 Giải thuật nâng cao-Giải thuật xấp xỉ 51 
a 
b 
c 
d 
e 
f g 
h 
a b c h d e f g 
The route là 
Use Prim’s algorithm to get a 
MST 
Chọn “a”là root 
Preorder tree walk 
Bài toán TSP 
Giải thuật nâng cao-Giải thuật xấp xỉ 52 
• Giải thuật APPROX-TSP-1 là polynomial-time 2-
approximation algorithm. 
• APPROX-TSP-TOUR là O(V2) 
• C(MST) ≤ C(H*) H*: optimal soln 
 C(W)=2C(MST) W: Preorder walk 
 C(W)≤2C(H*) 
 C(H)≤C(W) H: approx soln & 
 C(H)≤2C(H*) triangle inequality 
Optimal 
Pre-order 
Solution 
Bài toán TSP 
APPROX-TSP-2(G, c) 
1. Select a vertex r Є V[G] to be root. 
2. Compute a MST T for G from root 
r using Prim Alg. 
3. Find a minimal-weight matching M 
for vertices of odd degree in T. 
4. Find an Euler cycle C in G’ = (V, T U 
M). 
5. L=list of vertices in preorder walk 
of C. 
6. return the Hamiltonian cycle H in 
the order L. 
Giải thuật nâng cao-Giải thuật xấp xỉ 53 
O(1) 
O(n lg n) 
O(n3) 
O(n2) 
O(n) 
Chu trình Hamilton 
• Cho đồ thị 𝐺 = 𝑉, 𝐸 , tìm chu trình sao cho đi qua 
mỗi đỉnh đúng một lần 
• HAM-CYCLE trở thành Spanning Tree khi bỏ một 
cạnh bất kỳ 
• cost(MST) ≤ cost(min-HAM-CYCLE) 
Giải thuật nâng cao-Giải thuật xấp xỉ 54 
Tóm tắt 
• Các khái niệm P, NP, NP-complete 
• Giải thuật xấp xỉ với hệ số xấp xỉ 
• Minh họa với các bài toán phủ đỉnh, TSP, chu trình 
Hamilton 
Giải thuật nâng cao-Giải thuật xấp xỉ 55