CH NG 19ƯƠ
CÁC BÀI TOÁN NP – KHÓ VÀ NP - Đ Y ĐẦ Ủ
Chúng ta đã bi t nhi u bài toán, đi n hình là bài toán ng i bánế ề ể ườ
hàng, bài toán balô, bài toán chu trình Hamilton, … Các thu t toán t t nh tậ ố ấ
đ gi i quy t các bài toán này đ u có th i gian ch y không ph i là th iể ả ế ề ờ ạ ả ờ
gian đa th c, ch ng h n thu t toán quy ho ch đ ng cho bài toán ng iứ ẳ ạ ậ ạ ộ ườ
bán hàng có th i gian ch y O(nờ ạ 22n), … Cho t i nay ch a có ai tìm ra đ cớ ư ượ
thu t toán th i gian đa th c cho b t kỳ bài toán nào trong l p các bài toánậ ờ ứ ấ ớ
trên. V n đ đ t ra là có t n t i hay không thu t toán th i gian ch y đaấ ề ặ ồ ạ ậ ờ ạ
th c cho các bài toán trên?ứ
Các v n đ lý thuy t đ c trình bày trong ch ng này không kh ngấ ề ế ượ ươ ẳ
đ nh r ng, không t n t i thu t toán th i gian đa th c cho các bài toán trên.ị ằ ồ ạ ậ ờ ứ
Đi u mà các nhà nghiên c u đã làm đ c là ch ra r ng, nhi u bài toánề ứ ượ ỉ ằ ề
ch a có thu t toán gi i trong th i gian đa th c là có liên quan v i nhau vư ậ ả ờ ứ ớ ề
m t tính toán. C th là, chúng ta s thi t l p hai l p: l p các bài toán NPặ ụ ể ẽ ế ậ ớ ớ
– khó (NP-hard) và l p các bài toán NP- đ y đ (NP – complete). M t bàiớ ầ ủ ộ
toán là NP-đ y đ có tính ch t r ng, nó có th gi i đ c trong th i gianầ ủ ấ ằ ể ả ượ ờ
đa th c n u và ch n u t t c các bài toán NP-đ y đ khác gi i đ cứ ế ỉ ế ấ ả ầ ủ ả ượ
trong th i gian đa th c. N u m t bài toán NP- khó gi i đ c trong th iờ ứ ế ộ ả ượ ờ
gian đa th c thì t t c các bài toàn NP-đ y đ gi i đ c trong th i gian đaứ ấ ả ầ ủ ả ượ ờ
th c. Ng i ta đã ch ra r ng, l p NP-đ y đ là l p con c a l p NP – khó,ứ ườ ỉ ằ ớ ầ ủ ớ ủ ớ
nh ng có bài toán là NP – khó nh ng không ph i là NP-đ y đ .ư ư ả ầ ủ
Các l p bài toán NP–khó và NP - đ y đ là r t giàu có. T t c cácớ ầ ủ ấ ấ ả
bài toán n i ti ng mà ta đã quen bi t (bài toán ng i bán hàng, bài toánổ ế ế ườ
chi c balô, và r t nhi u bài toán t h p, các bài toán c a lý thuy t đ thế ấ ề ổ ợ ủ ế ồ ị
…) đ u là NP – khó.ề
245
Các l p NP – khó và NP - đ y đ liên quan t i s tính toán khôngớ ầ ủ ớ ự
đ n đ nh (nondeterministic computations). Không th th c hi n đ c sơ ị ể ự ệ ượ ự
tính toán không n đ nh trong th c t , b i v y v m t tr c quan, chúng taổ ị ự ế ở ậ ề ặ ự
có th ph ng đoán (ch a ch ng minh đ c) r ng, các bài toán NP - đ yể ỏ ư ứ ượ ằ ầ
đ ho c NP – khó không gi i đ c trong th i gian đa th c.ủ ặ ả ượ ờ ứ
Chúng ta s c g ng trình bày các v n đ đã nêu trên m t cách đ nẽ ố ắ ấ ề ộ ơ
gi n, không hình th c, không đi sâu vào các ch ng minh ph c t p.ả ứ ứ ứ ạ
19.1 THU T TOÁN KHÔNG Đ N Đ NHẬ Ơ Ị
Khái ni m thu t toán mà chúng ta s d ng cho đ n nay có tính ch tệ ậ ử ụ ế ấ
r ng, k t qu th c hi n m i phép toán là đ c xác đ nh duy nh t. Thu tằ ế ả ự ệ ỗ ượ ị ấ ậ
toán v i tính ch t này đ c g i là ớ ấ ượ ọ thu t toán đ n đ nhậ ơ ị (deterministic
algorithm).
Đ nh nghĩa 1ị. L p ớP bao g m t t c các bài toán gi i đ c b iồ ấ ả ả ượ ở
thu t toán đ n đ nh trong th i gian đa th c (t c là t n t i thu t toán gi iậ ơ ị ờ ứ ứ ồ ạ ậ ả
quy t nó v i th i gian ch y đa th c).ế ớ ờ ạ ứ
Đ xác đ nh l p NP các bài toán, chúng ta c n ph i đ a vào kháiể ị ớ ầ ả ư
ni m ệthu t toán không đ n đ nhậ ơ ị (nondeterministic algorithm). S mự ở
r ng khái ni m thu t toán đ n đ nh thành khái ni m thu t toán không đ nộ ệ ậ ơ ị ệ ậ ơ
đ nh cũng hoàn toàn t ng t nh khi ta m r ng khái niêm otomat h uị ươ ự ư ở ộ ữ
h n đ n đ nh thành otomat h u h n không đ n đ nh. Trong các thu t toánạ ơ ị ữ ạ ơ ị ậ
không đ n đ nh chúng ta đ c phép đ a vào các phép toán mà k t qu c aơ ị ượ ư ế ả ủ
nó không ph i là m t giá tr đ c xác đ nh duy nh t mà là m t t p h uả ộ ị ượ ị ấ ộ ậ ữ
h n các giá tr . Các phép toán đó đ c bi u di n b i hàm l a ch n:ạ ị ượ ể ễ ở ự ọ
choice(S)
Đây là hàm đa tr , giá tr c a nó là các ph n t c a t p h u h n S. Ngoàiị ị ủ ầ ử ủ ậ ữ ạ
hàm choice, đ mô t các thu t toán không đ n đ nh chúng ta đ a vào haiể ả ậ ơ ị ư
l nh: ệ
246
success
failure
Các l nh này là các l nh d ng, hi u qu c a chúng s đ c mô t d iệ ệ ừ ệ ả ủ ẽ ượ ả ướ
đây.
Các thu t toán không đ n đ nh đ c th c hi n nh th nào? Đậ ơ ị ượ ự ệ ư ế ể
th c hi n thu t toán không đ n đ nh, chúng ta c n th c hi n các tính toánự ệ ậ ơ ị ầ ự ệ
theo dòng đi u khi n đ c quy đ nh b i các câu l nh nh khi ta th c hi nề ể ượ ị ở ệ ư ự ệ
thu t toán đ n đ nh, ch có m t đi u khác bi t so v i thu t toán đ n đ nhậ ơ ị ỉ ộ ề ệ ớ ậ ơ ị
là, khi g p hàm l a ch n choice(S) thì s tính toán đ c phân thành nhi uặ ự ọ ự ượ ề
nhánh, m i nhánh t ng ng v i m t giá tr đ c ch n ra t t p S, t t cỗ ươ ứ ớ ộ ị ượ ọ ừ ậ ấ ả
các nhánh này s làm vi c đ ng th i và đ c l p v i nhau. M i nhánh tínhẽ ệ ồ ờ ộ ậ ớ ỗ
toán đó khi g p m t hàm l a ch n khác choice(S’) l i đ c phân thànhặ ộ ự ọ ạ ượ
nhi u nhánh tính toán khác. Và nh v y, khi th c hi n thu t toán khôngề ư ậ ự ệ ậ
đ n đ nh, chúng ta c n ph i th c hi n đ ng th i và đ c l p nhi u đ ngơ ị ầ ả ự ệ ồ ờ ộ ậ ề ườ
tính toán (đ c t o thành t các nhánh t ng ng v i các l a ch n). Doượ ạ ừ ươ ứ ớ ự ọ
đó, ta có th quan ni m r ng, thu t toán không đ n đ nh mô t s tínhể ệ ằ ậ ơ ị ả ự
toán song song không h n ch . Khi mà m t đ ng tính toán g p l nhạ ế ộ ườ ặ ệ
success, thì có nghĩa là đ ng tính toán đó đã đ c t o thành t các l aườ ượ ạ ừ ự
ch n đúng đ n và đã thành công cho ra nghi m c a bài toán, khi đó t t cọ ắ ệ ủ ấ ả
các đ ng tính toán đ u d ng làm vi c. Còn n u m t đ ng tính toán g pườ ề ừ ệ ế ộ ườ ặ
l nh failure, thì có nghĩa là đ ng tính toán này đã th t b i, không cho raệ ườ ấ ạ
nghi m c a bài toán, và ch riêng đ ng này d ng làm vi c. Máy có khệ ủ ỉ ườ ừ ệ ả
năng th c hi n thu t toán không đ n đ nh s đ c g i là ự ệ ậ ơ ị ẽ ượ ọ máy không đ nơ
đ nhị (nondeterministic machine). Không t n t i các máy không đ n đ nhồ ạ ơ ị
trong th c t . Sau đây chúng ta s đ a ra m t vài ví d v thu t toánự ế ẽ ư ộ ụ ề ậ
không đ n đ nh.ơ ị
Ví d 1ụ. Xét bài toán tìm xem ph n t x có trong m ng A[0 … n -ầ ử ả
1], n ≥ 1, hay không ? N u có ta c n in ra ch s i mà A[i] = x, n u khôngế ầ ỉ ố ế
thì in ra n. Thu t toán không đ n đ nh là nh sau:ậ ơ ị ư
247
Search (x, A, n)
// Tìm x trong m ng A[0… n - 1].ả
{
i = choice( 0: n – 1);
if (A[i] = = x)
{
print(i);
success;
}
else {
print(n);
failure ;
}
}
Chú ý r ng, l nh gán i = choice( 0 : n – 1) cho k t qu là bi n iằ ệ ế ả ế
đ c gán m t trong các giá tr trong đo n [0 … n - 1].ượ ộ ị ạ
Ví d 2ụ. Chúng ta đ a ra thu t toán không đ n đ nh đ s p x pư ậ ơ ị ể ắ ế
m ng A[0 … n – 1] theo th t không gi m. Trong thu t toán ta s d ngả ứ ự ả ậ ử ụ
m ng ph B[0 … n - 1].ả ụ
Sort (A, n)
// S p x p m ng A[0 … n - 1], n ắ ế ả ≥ 1.
{
(1) for ( i = 0 ; i < n ; i + + )
B[i] = ∞ ;
(2) for ( i = 0 ; i < n ; i + +)
{
(3) k = choice( 0 : n – 1);
(4) if (B[k] ≠ ∞ )
248
failure ;
else
B[k] = A[i] ;
}
(5) for ( i = 0 ; i < n-1 ; i + +)
if (B[i] > B[i + 1])
failure;
(6) print (B);
// in ra m ng B đã đ c s p theo th t không gi m.ả ượ ắ ứ ự ả
(7) success;
}
L nh l p (1) kh i t o m ng B ch a m t giá tr khác v i t t c cácệ ặ ở ạ ả ứ ộ ị ớ ấ ả
giá tr trong m ng A. L nh l p (2) th c hi n đ t m i giá tr A[i] trongị ả ệ ặ ự ệ ặ ỗ ị
m ng A vào m ng B t i ch s k, v i k đ c l a ch n không đ n đ nh b iả ả ạ ỉ ố ớ ượ ự ọ ơ ị ở
l nh (3). L nh (4) ki m tra xem B[k] đã ch a m t giá tr trong m ng Aệ ệ ể ứ ộ ị ả
hay ch a. Sau khi th c hi n l nh l p (2), nhánh tính toán không g p l như ự ệ ệ ặ ặ ệ
failure s cho k t qu m ng B ch a các giá tr là hoán v c a các giá trẽ ế ả ả ứ ị ị ủ ị
trong m ng A. L nh (5) ki m tra các giá tr trong m ng B có tho mãn thả ệ ể ị ả ả ứ
t không gi m hay không.ự ả
Bây gi chúng ta xác đ nh th i gian th c hi n thu t toán không đ nờ ị ờ ự ệ ậ ơ
đ nh. Th i gian này đ c xác đ nh là th i gian th c hi n đ ng tính toánị ờ ượ ị ờ ự ệ ườ
ng n nh t d n t i s k t thúc thành công (l nh success). Khi đánh giá th iắ ấ ẫ ớ ự ế ệ ờ
gian ch y c a thu t toán không đ n đ nh, chúng ta có th s d ng các kạ ủ ậ ơ ị ể ử ụ ỹ
thu t đánh giá th i gian ch y c a thu t toán đ n đ nh đã trình bày trongậ ờ ạ ủ ậ ơ ị
ch ng 15, ch c n l u ý r ng, th i gian th c hi n hàm choice(S) và cácươ ỉ ầ ư ằ ờ ự ệ
l nh success và failure là O(1). Ch ng h n, d dàng th y r ng, thu t toánệ ẳ ạ ễ ấ ằ ậ
không đ n đ nh tìm ph n t x trong m ng A[0 … n - 1] (ví d 1) có th iơ ị ầ ử ả ụ ờ
gian ch y là O(1), trong khi đó thu t toán đ n đ nh (tìm ki m tu n t ) c nạ ậ ơ ị ế ầ ự ầ
th i gian O(n).ờ
249