Bài giảng Thuật toán nâng cao - Nguyễn Thanh Bình - Phần 2

= 0 có thể ñược chuyển thành 
giải phương trình ax2 + bx + c = 0
452
Rút gọn bài toán

 Ví dụ
 Bài toán P

 Cho tập các giá trị lô-gíc (ñúng/sai), có tồn tại ít nhất 
một giá trị ñúng ?
 Bài toán Q

 Cho tập các số nguyên, tổng của chúng có > 0 ?
 Chuyển P thành Q

 (x1,x2,…,xn) = (y1,y2,…,yn) trong ñó yi = 1 nếu xi = 
ñúng, yi = 0 nếu xi = sai
114
453
Rút gọn bài toán

 ðịnh nghĩa
 Bài toán quyết ñịnh P có thể ñược rút gọn thời gian ña thức
(polynomial-time reducible) thành bài toán quyết ñịnh Q, nếu 
tồn tại hàm f tính ñược bởi thời gian ña thức từ miền dữ liệu 
vào của P vào miền dữ liệu vào của Q sao cho: 
mọi x thuộc miền dữ liệu vào của P, P(x) ñúng nếu và chỉ nếu 
Q(f(x)) ñúng
 P ñược rút gọn thời gian ña thức thành Q ñược ký hiệu P ≤p Q

 Hàm f là một sự rút gọn P thành Q

 Nếu tồn tại thuật toán có ñộ phức tạp hàm ña thức cho Q 
thì cũng sẽ tồn tại thuật toán có ñộ phức tạp hàm ña thức 
cho P
454
NP-khó và NP-ñầy ñủ

 NP-khó (NP-hard)
 Bài toán Q ñược gọi là NP-khó nếu thoả mãn:
1. ∀P ∈ NP, P ≤p Q

 NP-ñầy ñủ (NP-complete)
 Bài toán Q ñược gọi là NP-ñầy ñủ nếu thoả mãn:
1. Q ∈ NP
2. ∀P ∈ NP, P ≤p Q

 Nếu P ≤p Q và P là NP-ñầy ñủ thì Q cũng là NP-
ñầy ñủ
455
Ví dụ

 Các bài toán NP-ñầy ñủ
 Tô màu ñồ thị: có thể tô màu ñồ thị với nhiều nhất 3 màu sao 
cho hai ñỉnh kề nhau bất kỳ có màu khác nhau ?
 Chu trình Hamilton: cho ñồ thị có tồn tại chu trình chứa tất cả
các ñỉnh của ñồ thị ?
 Người du lịch: một người du lịch muốn ñi qua tất cả các thành 
phố với quảng ñường ngắn nhất, với ñiều kiện mỗi thành phố
chỉ ñi qua một lần.
 SAT: cho biểu thức lô-gíc gồm các biến lô-gíc x1, x2, …,xn và
các phép toán (AND, OR, NOT, ⇒, ⇔) và các dẫu ngoặc. Có
tồn tại phép gán các biến x1, x2, …,xn sao cho biểu thức có giá
trị ñúng ?
 …
456
Chứng minh bài toán NP-ñầy ñủ

 Tại sao phải chứng minh một bài toán là 
NP-ñầy ñủ ?
 Không cần tìm kiếm các thuật toán giải quyết 
hiệu quả (thời gian ña thức)
 Cần tìm các thuật toán xấp xỉ (approximative 
algorithms)
115
457
Chứng minh bài toán NP-ñầy ñủ

 Các bước chứng minh P là bài toán NP-ñầy ñủ
1. Chứng minh P ∈ NP
2. Chọn một bài toán Q là NP-ñầy ñủ (ñã biết)
3. Mô tả thuật toán tính hàm f chuyển các bài toán cụ thể
của Q thành bài toán cụ thể của P
4. Chứng minh rằng hàm f thoả mãn: Q(x) ñúng nếu và
chỉ nếu P(f(x)) ñúng
5. Chứng minh thuật toán tính hàm f có ñộ phức tạp hàm 
ña thức

 Cần ít nhất bài toán NP-ñầy ñủ ñã biết
 ðịnh lý Cook

 chứng minh bài toán ñầu tiên là NP-ñầy ñủ
458
ðịnh lý Cook

 ðịnh lý Cook (1971)
 SAT là bài toán NP-ñầy ñủ

 Cho biểu thức lô-gíc gồm các biến lô-gíc x1, x2, 
…,xn. Có tồn tại phép gán các biến x1, x2, …,xn
sao cho biểu thức có giá trị ñúng ?

 Chứng minh
 Dựa trên ñịnh nghĩa NP-ñầy ñủ
 Không dựa vào phép rút gọn
459
Chứng minh bài toán NP-ñầy ñủ

 Sử dụng bài toán SAT ñể chứng minh các 
bài toán khác NP-ñầy ñủ
NP
NP
NP
NP
NP
NP
NP
SAT
NP-ñầy ñủ
Bài toán 
NP-ñầy ñủ mới
rút gọn
rút gọn
460
NP-ñầy ñủ

 Chi tiết hơn
 Chapter 34: NP-Completeness, Introduction to 
algorithms, T.H. Cormen, C.E. Leiserson, R.R. 
Rivest, Mit Press 1990.
116
Thuật toán xấp xĩ (11)
Nguyễn Thanh Bình
Khoa Công nghệ Thông tin
Trường ñại học Bách khoa
ðại học ðà Nẵng
462
Thuật toán xấp xĩ
(approximation algorithms)

 Giải quyết các bài toán NP-ñầy ñủ
 Thuật toán hàm mũ

 Thuật toán quay lui

 Không hiệu quả
 Thuật toán xấp xĩ

 Cho kết quả gần ñúng

 ðộ phức tạp hàm ña thức
 Thuật toán cho kết quả gần với kết quả tối ưu ñược gọi 
là thuật toán xấp xĩ
463
Thuật toán xấp xĩ

 Tỷ lệ xấp xĩ (approximation ratio)
 Cần giải quyết bài toán tối ưu

 Bài toán có thể có nhiều giải pháp

 Cần tối ưu hàm một hàm mục tiêu

 Giải pháp tối ưu là giải pháp mà cực ñại (hoặc cự tiểu) 
hoá hàm mục tiêu
 ðặt 

 C là giá trị của hàm mục tiêu của giải pháp xấp xĩ

 C* là giá trị của hàm mục tiêu của giải pháp tối ưu
 Một thuật toán xấp xĩ có tỷ lệ xấp xĩ, ký hiệu ρ(n), với 
bất kỳ dữ liệu vào kích thước n là:
)(,max
*
*
n
C
C
C
C ρ≤





464
Thuật toán xấp xĩ

 Tỷ lệ xấp xĩ (2)
 ðịnh nghĩa tỷ lệ xấp xĩ ñúng cho cả bài toán cực tiểu hoá và
bài toán cực ñại hoá

 Bài toán cực tiểu hoá: C ≥ C* > 0, khi ñó ρ(n) = C/C*

 Bài toán cực ñại hoá: C* ≥ C > 0, khi ñó ρ(n) = C*/C
 Một thuật toán với tỷ lệ xấp xĩ ρ(n) ñược gọi là thuật toán xấp 
xĩ-ρ(n)
 Luôn có: ρ(n) ≥ 1

 Nếu ρ(n) càng nhỏ thì giải pháp xấp xĩ càng gần với giải pháp tối 
ưu
 Thuật toán xấp xĩ-1 cho giải pháp tối ưu (nghĩa là ρ(n) = 1)
117
465
Một số thuật toán xấp xĩ

 Bài toán phủ các ñỉnh (vertex cover 
problem)

 Bài toán người du lịch (traveling salesman 
problem)
466
Bài toán phủ các ñỉnh

 Bài toán
 Cho ñồ thị vô hướng G = (V,E). Phủ các ñỉnh của G là
một tập con V’ ⊂ V sao cho nếu (u,v) là một cạnh của G 
thì hoặc u ∈ V’ hoặc v ∈ V’
 Cần xác ñịnh phủ các ñỉnh có kích thước nhỏ nhất

 Bài toán quyết ñịnh phủ các ñỉnh tương ứng là 
NP-ñầy ñủ
 Với k cho trước, có tồn tại phủ các ñỉnh V’ của ñồ thị G 
sao cho |V’| ≤ k

 Rất phức tạp ñể tìm giải pháp tối ưu V’

 Tuy nhiên, thuật toán xấp xĩ rất ñơn giản
467
Bài toán phủ các ñỉnh

 Thuật toán xấp xĩ
 Thuật toán có ñộ phức tạp là hàm tuyến tính
phucacdinh-xapxi (G=(V,E))
begin
C = ∅
U = E
while (U ≠ ∅) do
(u,v) là cạnh bất kỳ thuộc U
C = C ∪ (u,v)
xoá trong U tất cả các cạnh nối ñến u hoặc v
endwhile
return (C)
end
468
b c
e f
d
ga
Bài toán phủ các ñỉnh

 Minh hoạ (1)
b c
e f
d
ga
118
469
Bài toán phủ các ñỉnh

 Minh hoạ (2)
b c
e f
d
ga
b c
e f
d
ga
470
Bài toán phủ các ñỉnh

 Minh hoạ (3)
b c
e f
d
ga
b c
e f
d
ga
Giải pháp xấp xĩ: b, c, d, e, f, g
Giải pháp tối ưu: b, d, e
471
Bài toán phủ các ñỉnh

 ðịnh lý: phucacdinh-xapxi là thuật toán xấp xĩ-2 (ρ(n) ≤ 2)

 Chứng minh
 Gọi A là tập các cạnh (u,v) ñược chọn bởi thuật toán. Bởi cách 
xây dựng A, thì không thể có hai cạnh bất kỳ của A có chung 
ñỉnh (do bước xoá các cạnh nối ñến u và v).
 Vậy, mỗi bước lặp sẽ thêm vào C hai ñỉnh u và v mới và |C| = 
2 x |A| (*).
 Gọi C* là phủ các ñỉnh với kích thước nhỏ nhất.
 Vì hai cạnh của A không có ñỉnh chung, nên một ñỉnh của C*
chỉ nối ñến nhiều nhất một cạnh của A.
 Theo ñịnh nghĩa phủ các ñỉnh, thì C* phải chứa ít nhất một 
ñỉnh của mỗi cạnh thuộc A. Vậy |C*| ≥ |A| (**).
 Kết hợp (*) và (**), ta có |C| ≤ 2|C*|
472
Bài toán người du lịch

 Bài toán
 Cho ñồ thị vô hướng liên thông hoàn toàn G=(V,E), nghĩa là giữa hai 
ñỉnh bất kỳ luôn tồn tại cạnh nối chúng. Mỗi cạnh (u,v) có một trọng 
số c(u,v) ≥ 0. Tìm chu trình Hamilton có tổng trọng số nhỏ nhất.

 Trong thực tế, ñi từ ñỉnh u ñến trực tiếp một ñỉnh v sẽ nhanh hơn 
ñi từ u ñến v qua một ñỉnh trung gian w

 Tình huống này ñược mô tả bởi bất ñằng thức tam giác ñối với 
hàm trọng số c
 c(u,v) ≤ c(u,w) + c(w,v), với u, v, w là các ñỉnh bất kỳ thuộc V

 Giả sử hàm trọng số c của bài toán thoả mãn bất ñằng thức tam 
giác

 Hầu hết các bài toán thực tế cũng thoả mãn bất ñằng thức tam 
giác

 Bài toán người du lịch thuộc lớp NP-ñầy ñủ
119
473
Bài toán người du lịch

 Thuật toán xấp xĩ
 Cây khung nhỏ nhất: chứa tất cả các ñỉnh của ñồ thị có tổng 
trọng số các cạnh nhỏ nhất
 Duyệt thứ tự trước: một nút ñược thăm trước khi thăm các nút 
con của nó
 ðộ phức tạp thuật toán: O(|V|2)

 ðộ phức tạp thuật toán Prim
nguoidulich-xapxi (G)
begin
Chọn một ñỉnh r bất kỳ của G là ñỉnh « gốc »
Xác ñịnh cây khung nhỏ nhất T của G bởi thuật toán Prim
Gọi L là danh sách các ñỉnh khi duyệt T theo thứ tứ trước
return (trả về chu trình Hamilton H khi 
 thăm các ñỉnh của L theo thứ tự)
end
474
Bài toán người du lịch

 Minh hoạ (1)
b
a
c
f
d
e
h
g
ðồ thị G với khoảng cách giữa các 
ñỉnh là trọng số của cạnh tương ứng
b
a
c
f
d
e
h
g
Cây khung nhỏ nhất, gốc là a
475
Bài toán người du lịch

 Minh hoạ (2)
Duyệt cây T theo thứ tự trước: 
a, b, c, b, h, b, a, d, e, f, e, g, e, d, a
b
a
c
f
d
e
h
g
Chu trình Hamilton, các ñỉnh 
của L: a, b, c, h, d, e, f, g, a
b
a
c
f
d
e
h
g
476
Bài toán người du lịch

 Minh hoạ (3)
Giải pháp xấp xĩ Giải pháp tối ưu
b
a
c
f
d
e
h
g
Tổng trọng số của giải pháp xấp xĩ
≈ 123% của tổng trọng số của giải pháp tối ưu
b
a
c
f
d
e
h
g
120
477
Bài toán người du lịch

 ðịnh lý: nguoidulich-xapxi là thuật toán xấp xĩ-2 (ρ(n) ≤ 2)

 Chứng minh
 H là chu trình Hamilton xác ñịnh bởi thuật toán xấp xĩ. H* là
chu trình Hamilton có kích thước nhỏ nhất. Cần chứng minh 
c(H) ≤ 2c(H*).
 Bằng cách xoá một cạnh bất kỳ trong chu trình Hamilton H* ta 
có một cây khung T’. Vậy c(T’) ≤ c(H*).
 Theo thuật toán T là cây khung nhỏ nhất. Nên c(T) ≤ c(T’) ≤
c(H*).
 Một phép duyệt ñầy ñủ cây T liệt kê tất cả các ñỉnh khi gặp lần 
ñầu và cả khi gặp lại sau khi ñã duyệt cây con của chúng. Gọi 
W là phép duyệt ñầy ñủ T.
 Chẳng hạn, trong ví dụ trước, phép duyệt ñầy ñủ liệt kê các 
ñỉnh theo thứ tự trước:
a, b, c, b, h, b, a, d, e, f, e, g, e, d, a
478
Bài toán người du lịch

 Chứng minh (tiếp)
 Như thế, phép duyệt ñầy ñủ W của cây T sẽ thăm mỗi cạnh 
ñúng hai lần. Vậy c(W) = 2c(T) ≤ 2c(H*).
 Ngoài ra, nhờ vào tính chất bất ñẳng thức tam giác, chúng ta 
có thể xoá lần thăm một ñỉnh của W mà không làm tăng trọng 
số của W:

 nếu một ñỉnh w ñược xoá giữa lần thăm ñỉnh u và ñỉnh v, thì danh 
sách mới các ñỉnh sẽ ñi trực tiếp từ u ñến v (với trọng số c(u,v) ≤
c(u,w) + c(w,v)).
 Áp dụng xoá tất cả các lần thăm mỗi ñỉnh của W, trừ lần thăm 
ñầu tiên (nghĩa là xoá tất cả các lần thăm sau lần ñầu tiên) và
trừ lần thăm cuối cùng của ñỉnh « gốc ».
 Chẳng hạn, trong ví dụ trên, chúng la có danh sách:
a, b, c, h, d, e, f, g, a
 Danh sách này chính là chu trình Hamilton H cho bởi thuật 
toán xấp xĩ. Vậy chu trình Hamilton H có ñược bởi việc xoá các 
ñỉnh của W (áp dụng tính chất bất ñẳng thức tam giác).
 Như thế: c(H) ≤ c(W) ≤ 2c(H*)