Các chiến lược thiết kế thuật toán

Chia sẻ: Nguyen Xuan Thang | Ngày: | Loại File: DOC | Số trang:35

Thêm vào BST

Báo xấu

408
lượt xem 144
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với một vấn đề đặt ra, làm thế nào chúng ta có thể đưa ra thuật toán giải quyết nó? Trong chương này, chúng ta sẽ trình bày các chiến lược thiết kế thuật toán, còn được gọi là các kỹ thuật thiết kế thuật toán. Mỗi chiến lược này có thể áp dụng để giải quyết một phạm vi khá rộng các bài toán. Mỗi chiến lược có các tính chất riêng và chỉ thích hợp cho một số dạng bài toán nào đó. Chúng ta sẽ lần lượt trình bày các chiến lược sau: chia-để-trị (divide-and-conquer), quy hoạch động (dynamic programming), quay lui (backtracking) và...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các chiến lược thiết kế thuật toán

409
CHƯƠNG 16 CÁC CHI N LƯ C THI T K THU T TOÁN V im tv n t ra, làm th nào chúng ta có th ưa ra thu t toán gi i quy t nó? Trong chương này, chúng ta s trình bày các chi n lư c thi t k thu t toán, còn ư c g i là các k thu t thi t k thu t toán. M i chi n lư c này có th áp d ng gi i quy t m t ph m vi khá r ng các bài toán. M i chi n lư c có các tính ch t riêng và ch thích h p cho m t s d ng bài toán nào ó. Chúng ta s l n lư t trình bày các chi n lư c sau: chia- -tr (divide-and-conquer), quy ho ch ng (dynamic programming), quay lui (backtracking) và tham ăn (greedy method). Trong m i chi n lư c chúng ta s trình bày ý tư ng chung c a phương pháp và sau ó ưa ra m t s ví d minh h a. C n nh n m nh r ng, ta không th áp d ng máy móc m t chi n lư c cho m t v n , mà ta ph i phân tích k v n . C u trúc c a v n , các c i m c a v n s quy t nh chi n lư c có kh năng áp d ng. 16.1 CHIA - - TR 16.1.1 Phương pháp chung Chi n lư c thi t k thu t toán ư c s d ng r ng rãi nh t là chi n lư c chia- -tr . Ý tư ng chung c a k thu t này là như sau: Chia v n c n gi i thành m t s v n con cùng d ng v i v n ã cho, ch khác là c c a chúng nh hơn. M i v n con ư c gi i quy t c l p. Sau ó, ta k t h p nghi m c a các v n con nh n ư c nghi m c a v n ã cho. N uv n con là nh có th d dàng tính ư c nghi m, thì ta gi i quy t nó, n u không v n con ư c gi i quy t b ng cách áp d ng quy th t c trên (t c là l i ti p t c chia nó thành các v n con nh hơn,…). Do ó, các 410
thu t toán ư c thi t k b ng chi n lư c chia- -tr s là các thu t toán quy. Sau ây là lư c c a k thu t chia- -tr : DivideConquer (A,x) // tìm nghi m x c a bài toán A. { if (A nh ) Solve (A); else { Chia bài toán A thành các bài toán con A1, A2,…, Am; for (i = 1; i A[k] ta tìm x trong m ng A[k+1…n-1]. Thu t toán Tháp Hà N i (xem m c 15.5), thu t toán s p x p nhanh (QuickSort) và thu t toán s p x p hoà nh p (MergeSort) s ư c trình bày 411
trong chương sau cũng là các thu t toán ư c thi t k b i k thu t chia- - tr . Sau ây chúng ta ưa ra m t ví d ơn gi n minh ho cho k thu t chia- -tr . 16.1.2 Tìm max và min Cho m ng A c n, chúng ta c n tìm giá tr l n nhât (max) và nh nh t (min) c a m ng này. Bài toán ơn gi n này có th gi i quy t b ng các thu t toán khác nhau. M t thu t toán r t t nhiên và ơn gi n là như nhau. u tiên ta l y max, min là giá tr u tiên A[0] c a m ng. Sau ó so sánh max, min v i t ng giá tr A[i], 1 ≤ i ≤ n-1, và c p nh t max, min m t cách thích ng. Thu t toán này ư c mô t b i hàm sau: SiMaxMin (A, max, min) { max = min = A[0]; for ( i = 1 ; i < n , i ++) if (A[i] > max) max = A[i]; else if (A[i] < min) min = A[i]; } Th i gian th c hi n thu t toán này ư c quy t nh b i s phép so sánh x v i các thành ph n A[i]. S l n l p trong l nh l p for là n-1. Trong trư ng h p x u nh t (m ng A ư c s p theo th t gi m d n), m i l n l p ta c n th c hi n 2 phép so sánh. Như v y, trong trư ng h p x u nh t, ta c n th c hi n 2(n-1) phép so sánh, t c là th i gian ch y c a thu t toán là O(n). Bây gi ta áp d ng k thu t chia- -tr ưa ra m t thu t toán khác. Ta chia m ng A[0..n-1] thành các m ng con A[0..k] và A[k+1..n-1] v i k = [n/2]. N u tìm ư c max, min c a các m ng con A[0..k] và A[k+1..n-1], ta d dàng xác nh ư c max, min trên m ng A[0..n-1]. tìm max, min trên 412
m ng con ta ti p t c chia ôi chúng. Quá trình s d ng l i khi ta nh n ư c m ng con ch có m t ho c hai ph n t . Trong các trư ng h p này ta xác nh ư c d dàng max, min. Do ó, ta có th ưa ra thu t toán sau: MaxMin (i, j, max, min) // Bi n max, min ghi l i giá tr l n nh t, nh nh t trong m ng A[i..j] { if (i = = j) max = min = A[i]; else if (i = = j-1) if (A[i] < A[j]) { max = A[j]; min = A[i]; } else { max = A[i]; min = A[j]; } else { mid = (i+j) / 2; MaxMin (i, mid, max1, min1); MaxMin (mid + 1, j, max2, min2); if (max 1< max2) max = max2; else max = max1; if (min1 < min2) min = min1; else min = min2; } } Bây gi ta ánh giá th i gian ch y c a thu t toán này. G i T(n) là s phép so sánh c n th c hi n. Không khó khăn th y r ng, T(n) ư c xác nh b i quan h quy sau. T(1) = 0 T(2) = 1 413
T(n) = 2T(n/2) + 2 v i n > 2 Áp d ng phương pháp th l p, ta tính ư c T(n) như sau: T(n) = 2 T(n/2) + 2 = 22T(n/22) + 22 + 2 = 23T(n/23) + 23 + 22 + 2 ……… = 2kT(n/2k) + 2k + 2k-1 +… + 2 V i k là s nguyên dương sao cho 2k ≤ n < 2k+1, ta có T(n) = 2kT(1) + 2k+1 – 2 = 2k+1 – 2 ≤ 2(n-1) Như v y, T(n) = O(n). 16.2 THU T TOÁN QUY Khi thi t k thu t toán gi i quy t m t v n b ng k thu t chia- -tr thì thu t toán thu ư c là thu t toán quy. Thu t toán quy ư c bi u di n trong các ngôn ng l p trình b c cao (ch ng h n Pascal, C/C++) b i các hàm quy: ó là các hàm ch a các l i g i hàm n chính nó. Trong m c này chúng ta s nêu lên các c i m c a thu t toán quy và phân tích hi u qu (v không gian và th i gian) c a thu t toán quy. quy là m t k thu t c bi t quan tr ng gi i quy t v n . Có nh ng v n r t ph c t p, nhưng chúng ta có th ưa ra thu t toán quy r t ơn gi n, sáng s a và d hi u. C n ph i hi u rõ các c i m c a thu t toán quy có th ưa ra các thu t toán quy úng n. Gi i thu t quy cho m t v n c n ph i tho mãn các òi h i sau: 1. Ch a l i gi i cho các trư ng h p ơn gi n nh t c a v n . Các trư ng h p này ư c g i là các trư ng h p cơ s hay các trư ng h p d ng. 2. Ch a các l i g i quy gi i quy t các v n con v i c nh hơn. 3. Các l i g i quy sinh ra các l i g i quy khác và v ti m năng các l i g i quy ph i d n t i các trư ng h p cơ s . 414
Tính ch t 3 là c bi t quan tr ng, n u không tho mãn, hàm quy s ch y mãi không d ng. Ta xét hàm quy tính giai th a: int Fact(int n) { if (n = 0) return 1; else return n * Fact(n-1); // g i quy. } Trong hàm quy trên, trư ng h p cơ s là n = 0. tính Fact(n) c n th c hi n l i g i Fact(n-1), l i g i này l i d n n l i g i F(n-2),…, và cu i cùng d n t i l i g i F(0), t c là d n t i trư ng h p cơ s . quy và phép l p. i v i m t v n , có th có hai cách gi i: gi i thu t quy và gi i thu t dùng phép l p. Gi i thu t quy ư c mô t b i hàm quy, còn gi i thu t dùng phép l p ư c mô t b i hàm ch a các l nh l p, phân bi t v i hàm quy ta s g i là hàm l p. Ch ng h n, tính giai th a, ngoài hàm quy ta có th s d ng hàm l p sau: int Fact(int n) { if (n = = 0) return 1; else { int F= 1; for (int i = 1; i
Trong khi ó, n u không s d ng quy mà dùng phép l p thì thu t toán thu ư c thư ng là ph c t p hơn, khó hi u hơn. Ta có th th y i u ó trong ví d tính giai th a, ho c các thu t toán tìm ki m, xem, lo i trên cây tìm ki m nh phân (xem m c 8.4). Tuy nhiên, trong nhi u trư ng h p, các thu t toán l p l i hi u qu hơn thu t toán quy. Bây gi chúng ta phân tích các nhân t có th làm cho thu t toán quy kém hi u qu . Trư c h t, ta c n bi t cơ ch máy tính th c hi n m t l i g i hàm. Khi g p m t l i g i hàm, máy tính t o ra m t b n ghi ho t ng (activation record) ngăn x p th i gian ch y (run-time stack) trong b nh c a máy tính. B n ghi ho t ng ch a vùng nh c p cho các tham bi n và các bi n a phương c a hàm. Ngoài ra, nó còn ch a các thông tin máy tính tr l i ti p t c hi n chương trình úng v trí sau khi nó ã th c hi n xong l i g i hàm. Khi hoàn thành th c hi n l i g i hàm thì b n ghi h at ng s b lo i b kh i ngăn x p th i gian ch y. Khi th c hi n m t hàm quy, m t dãy các l i g i hàm ư c sinh ra. H u qu là m t dãy b n ghi ho t ng ư c t o ra trong ngăn x p th i gian ch y. C n chú ý r ng, m t l i g i hàm ch ư c th c hi n xong khi mà các l i g i hàm mà nó sinh ra ã ư c th c hi n xong và do ó r t nhi u b n ghi ho t ng ng th i t n t i trong ngăn x p th i gian ch y, ch khi m t l i g i hàm ư c th c hi n xong thì b n ghi ho t ng c p cho nó m i ư c lo i ngăn x p th i gian ch y. Ch ng h n, xét hàm quy tính giai th a, n u th c hi n l i g i hàm Fact(5) s d n n ph i th c hi n các l i h i hàm Fact(4), Fact(3), Fact(2), Fact(1), Fact(0). Ch khi Fact(4) ã ư c tính thì Fact(5) m i ư c tính, … Do ó trong ngăn x p th i gian ch y s ch a các b n ghi ho t ng như sau: Bàn ghi ho t ng cho Fact(5) Bàn ghi ho t ng cho Fact(4) Bàn ghi ho t ng cho Fact(3) Bàn ghi ho t ng cho Fact(2) Bàn ghi ho t ng cho Fact(1) 416 Bàn ghi ho t ng cho Fact(0)
Trong ó, b n ghi ho t ng c p cho l i g i hàm Fact(0) nh ngăn x p th i gian ch y. Khi th c hi n xong Fact(0) thì b n ghi ho t ng c p cho nó b lo i, r i b n ghi ho t ng cho Fact(1) b lo i,… Vì v y, vi c th c hi n hàm quy có th òi h i r t nhi u không gian nh trong ngăn x p th i gian ch y, th m chí có th vư t quá kh năng c a ngăn x p th i gian ch y trong b nh c a máy tính. M t nhân t khác làm cho các thu t toán quy kém hi u qu là các l i g i quy có th d n n ph i tính nghi m c a cùng m t bài toán con r t nhi u l n. S Fibonacci th n, ký hi u là F(n), ư c xác nh quy như sau: F(1) = 1 F(2) = 1 F(n) = F(n-1) + F(n-2) v i n>2 Do ó, ta có th tính F(n) b i hàm quy sau. int Fibo(int n) { if ((n = = 1) // (n = = 2)) return 1; else return Fibo (n-1) + Fibo(n-2); } tính F(7), các l i g i trong hàm quy Fibo d n ta n ph i tính các F(k) vói k
T hình v trên ta th y r ng, tính ư c F(7) ta ph i tính F(5) 2 l n, tính F(4) 3 l n, tính F(3) 5 l n, tính F(2) 8 l n và tính F(1) 5 l n. Chính s ki n tính F(n) ta ph i tính các F(k), v i k
và s p x p hoà nh p (MergeSort) mà chúng ta s nghiên c u trong chương 17 cũng là các thu t toán r t hi u qu . Trong m c 6.6 chúng ta ã nghiên c u k thu t s d ng ngăn x p chuy n thu t toán quy thành thu t toán l p. Nói chung, ch nên s d ng thu t toán quy khi mà không có thu t toán l p hi u qu hơn. 16.3 QUY HO CH NG 16.3.1 Phương pháp chung K thu t quy ho ch ng gi ng k thu t chia- -tr ch c hai u gi i quy t v n b ng cách chia v n thành các v n con. Nhưng chia- -tr là k thu t top-down, nó tính nghi m c a các v n con t l n t i nh , nghi m c a các v n con ư c tính c l p b ng quy. i l p, quy ho ch ng là k thu t bottom-up, tính nghi m c a các bài toán t nh n l n và ghi l i các k t qu ã tính ư c. Khi tính nghi m c a bài toán l n thông qua nghi m c a các bài toán con, ta ch vi c s d ng các k t qu ã ư c ghi l i. i u ó giúp ta tránh ư c ph i tính nhi u l n nghi m c a cùng m t bài toán con. Thu t toán ư c thi t k b ng k thu t quy ho ch ng s là thu t toán l p, trong khi thu t toán ư c thi t k b ng k thu t chia- -tr là thu t toán quy. thu n ti n cho vi c s d ng l i nghi m c a các bài toán con, chúng ta lưu l i các nghi m ã tính vào m t b ng (thông thưòng là m ng 1 chi u ho c 2 chi u). Tóm l i, gi i m t bài toán b ng quy ho ch ng, chúng ta c n th c hi n các bư c sau: • ưa ra cách tính nghi m c a các bài toán con ơn gi n nh t. • Tìm ra các công th c (ho c các quy t c) xây d ng nghi m c a bài toán thông qua nghi m c a các bài toán con. • Thi t k b ng lưu nghi m c a các bài toán con. 419
• Tính nghi m c a các bài toán con t nh n l n và lưu vào b ng. • Xây d ng nghi m c a bài toán t b ng. M t ví d ơn gi n c a thu t toán ư c thi t k b ng quy ho ch ng là thu t toán l p tính dãy s Fibonacci mà ta ã ưa ra trong m c 16.2. Trong hàm l p Fibo1, ta ã tính tu n t F(1), F(2),…, n F(n). Và b i vì tính F(k) ch c n bi t F(k-1) và F(k-2), nên ta ch c n lưu l i F(k-1) và F(k-2). K thu t quy ho ch ng thư ng ư c áp d ng gi i quy t các bài toán t i ưu (optimization problems). Các bài toán t i ưu thư ng là có m t s l n nghi m, m i nghi m ư c g n v i m t giá, và m c tiêu c a chúng ta là tìm ra nghi m có giá nh nh t : nghi m t i ưu (optimization solution). Ch ng h n, bài toán tìm ư ng i t thành ph A n thành ph B trong b n giao thông, có nhi u ư ng i t A n B, giá c a m t ư ng i ó là dài c a nó, nghi m t i ưu là ư ng i ng n nh t t A n B. N u nghi m t i ưu c a bài toán ư c t o thành t nghi m t i ưu c a các bài toán con thì ta có th s d ng k thu t quy ho ch ng. Sau ây, chúng ta s ưa ra m t s thu t toán ư c thi t k b ng k thu t quy ho ch ng. 16.3.2 Bài toán s p x p các v t vào ba lô Gi s ta có chi c ba lô có th ch a ư c m t kh i lư ng w, chúng ta có n lo i v t ư c ánh s i,…, n. M i v t lo i i (i = 1,…, n) có kh i lư ng ai và có giá tr ci. Chúng ta mu n s p x p các v t vào ba lô nh n ư c ba lô có gía tr l n nh t có th ư c. Gi s m i lo i v t có nhi u x p vào ba lô. 420
Bài toán ba lô ư c mô t chính xác như sau. Cho trư c các s nguyên dương w, ai, và ci (i = 1,…,n). Chúng ta c n tìm các s nguyên không âm xi (i = 1,…, n) sao cho n ∑ n =1 xi ai ≤ w và n ∑n =1 xi ci t giá tr l n nh t. Xét trư ng h p ơn gi n nh t: ch có m t lo i v t (n = 1). Trong trư ng h p này ta tìm ư c ngay l i gi i: x p v t vào ba lô cho t i khi nào không x p ư c n a thì thôi, t c là ta tìm ư c ngay nghi m xi = w/ai. Bây gi ta i tìm cách tính nghi m c a bài toán “x p n lo i v t vào ba lô kh i lư ng w” thông qua nghi m c a các bài toán con “x p k lo i v t (1 ≤ k ≤ n) vào ba lô kh i lư ng v (1≤ v ≤ w)” Ta g i t t là bài toán con (k,w), g i cost (k,v) là giá tr l n nh t c a ba lô kh i lư ng v (1≤ v ≤ w) và ch ch a các lo i v t 1, 2,….,k. Ta tìm công th c tính cost (k,v).V i k = 1 và 1 ≤ v ≤ w, ta có xi = v / ai và cost (1,v) = xici (1) Gi s ta ã tính ư c cost (s,u) v i 1≤ s < k và 1≤ u ≤ v, ta c n tính cost (k,v) theo các cost (s,u) ã bi t ó. G i yk = v / ak, ta có cost (k,v) = max[cost (k-1,u) + xkck] (2) Trong ó, max ư c l y v i t t c xk = 0, 1,…, yk và u = v - xkak (t c là ư c l y v i t t c các kh năng x p v t th k). Như v y, tính cost (k,v) ư c quy v tính cost (k-1,u) v i u≤v. Giá tr c a xk trong (2) mà cost (k-1,u) + xkck t max chính là s v t lo i k c n x p. Giá tr l n nh t c a ba lô s là cost(n, w). Chúng ta s tính nghi m c a bài toán t c nh n c l n theo các công th c (1) và (2). Nghi m c a các bài toán con s ư c lưu trong m ng 2 421
chi u A[0..n-1][0..w-1], c n lưu ý là nghi m c a bài toán con (k,v) ư c lưu gi trong A[k-1][v-1], vì các ch s c a m ng ư c ánh s t 0. M i thành ph n A[k-1][v-1] s ch a cost(k,v) và s v t lo i k c n x p. T các công th c (1) và (2) ta có th tính ư c các thành ph n c a m ng A l n lư t theo dòng 0, 1,…n-1. T b ng A ã làm y, làm th nào xác nh ư c nghi m c a bài toán, t c là xác nh ư c s v t lo i i (i = 1,2,…,n) c n x p vào ba lô? Ô A[n-1][w-1] ch a giá tr l n nh t c a ba lô cost (n,w) và s v t lo i n c n x p xn. Tính v = w – xnan. Tìm n ô A[n-2][v-1] ta bi t ư c cost(n-1,v) và s v t lo i n-1 c n x p xn-1. Ti p t c quá trình trên, ta tìm ư c xn-2,..,x2 và cu i cùng là x1. 16.3.3 Tìm dãy con chung c a hai dãy s Xét bài toán sau: Cho hai dãy s nguyên a = (a1,…, am) và b = (b1,…bn), ta c n tìm dãy s nguyên c = (c1,…, ck) sao cho c là dãy con c a c a và b, và c là dài nh t có th ư c. Ví d , n u a = (3, 5, 1, 3, 5, 5, 3) và b = (1,5,3,5,3,1) thì dãy con chung dài nh t là c = (5,3,5,3) ho c c = (1,3,5,3) ho c c = (1,5,5,3). Trư ng h p ơn gi n nh t khi m t trong hai dãy a và b r ng (m = 0 ho c n = 0), ta th y ngay dãy con chung dài nh t là dãy r ng. Ta xét các o t u c a hai dãy a và b, ó là các dãy (a1,a2,…,ai) và (b1,b2,…,aj) v i 0 ≤ i ≤ m và 0 ≤ j ≤ n. G i L(i,j) là dài l n nh t c a dãy con chung c a hai dãy (a1,a2,…,ai) và (b1,b2,…,aj). Do ó L(n,m) là dài l n nh t c a dãy con chung c a a và b. Bây gi ta i tìm cách tính L(i,j) thông qua các L(s,t) v i 0 ≤ s ≤ i và 0 ≤ t ≤ j. D dàng th y r ng: L(0,j) = 0 v i m i j L(i,0) = 0 v i m i i (1) N u i > 0 và j > 0 và ai # bj thì L(i,j) = max [L(i,j-1), L(i-1,j)] (2) 422
N u i > 0 và j > 0 và ai = bj thì L(i,j) = 1 + L(i-1,j-1) (3) S d ng các công th c quy (1), (2), (3) tính các L(i,j) l n lư t v i i = 0,1,…,m và j = 0,1,…,n. Chúng ta s lưu các giá tr L(i,j) vào m ng L[0..m][0..n]. Công vi c ti p theo là t m ng L ta xây d ng dãy con chung dài nh t c a a và b. Gi s k = L[m][n] và dãy con chung dài nh t là c = (c1,…ck-1, ck). Ta xác nh các thành ph n c a dãy c l n lư t t ph i sang trái, t c là xác nh ck, r i ck-1,…,c1. Ta xem xét các thành ph n c a m ng L b t t L[m,n]. Gi s ta ang ô L[i][j] và ta ang c n xác nh cr, (1
(các t p con c a m t t p), ho c các hoán v c a n i tư ng, ho c các t h p k i tư ng t n i tư ng. Trong các trư ng h p như th , ta c n ph i sinh ra, ch ng h n, t t c các hoán v , r i ki m tra xem m i hoán v có là nghi m c a bài toán không. Tìm ki m vét c n ương nhiên là kém hi u qu , òi h i r t nhi u th i gian. Nhưng cũng có v n ta không có cách gi i quy t nào khác tìm ki m vét c n. Ví d 1( Bài toán 8 con h u). Chúng ta c n t 8 con h u vào bàn c 8x8 sao cho chúng không t n công nhau, t c là không có hai con h u nào n m cùng hàng, ho c cùng c t, ho c cùng ư ng chéo. Vì các con h u ph i n m trên các hàng khác nhau, ta có th ánh s các con h u t 1 n 8, con h u i là con h u ng hàng th i (i=1,...,8). G i xi là c t mà con h u th i ng. Vì các con h u ph i ng các c t khác nhau, nên (x1, x2, ...,x8) là m t hoán v c a 8 s 1, 2,..., 8. Như v y t t c các ng c viên cho nghi m c a bài toán 8 con h u là t t c các hoán v c a 8 s 1, 2,..., 8. n ây ta có th ưa ra thu t toán như sau: sinh ra t t c các hoán v c a (x1, x2, ...,x8), v i m i hoán v ta ki m tra xem hai ô b t kì (i,xi) và (j,xj) có cùng ư ng chéo hay không. i v i bài toán t ng quát: t n con h u vào bàn c nxn, s các hoán v c n xem xét là n!, và do dó thu t toán t n con h u b ng tìm ki m vét c n òi h i th i gian O(n!). Trong m c sau, chúng ta s ưa ra thu t toán hi u qu hơn ư c thi t k b ng k thu t quay lui. Ví d 2( Bài toán ngư i bán hàng). Bài toán ngư i bán hàng (saleperson problem) ư c phát bi u như sau. M t ngư i bán hàng, hàng ngày ph i i giao hàng t m t thành ph n m t s thành ph khác r i quay l i thành ph xu t phát. Anh ta mu n tìm m t tua qua m i thành ph c n n úng m t l n v i dài c a tua là ng n nh t có th ư c. Chúng ta phát bi u chính xác bài toán như sau. Cho th nh hư ng g m n nh ư c ánh s 0,1,...,n-1. dài c a cung (i,j) ư c kí hi u là dij và là m t s không âm. N u th không có cung (i,j) thì ta 424
xem dij = +∞. Chúng ta c n tìm m t ư ng i xu t phát t m t nh qua t t c các nh khác c a th úng m t l n r i l i tr v nh xu t phát (t c là tìm m t chu trình Hamilton) sao cho dài c a tua là nh nh t có th ư c. M i tua như t là m t dãy các nh (a0, a1,..., an-1, a0), trong ó các a0, a1,..., an-1 là khác nhau. Không m t tính t ng quat, ta có th xem nh xu t phát là nh 0, a0 = 0. Như v y, m i tua tương ng v i m t hoán v (a1,..., an-1) c a các nh 1, 2, ..., n-1. T ó ta có thu t toán sau: sinh ra t t c các hoán v c a n-1 nh 1, 2, ..., n-1; v i m i hoán v ta tính dài c a tua tương ng v i hoán v ó và so sánh các dài ta s tìm ư c tua ng n nh t. Lưu ý r ng, có t t c (n-1)! hoán v và m i tua c n n phép toán tính dài, do ó thu t toán gi i bài toán ngư i bán hàng v i n thành ph b ng tìm ki m vét c n c n th i gian O(n!). Bài toán ngư i bán hàng là bài toán kinh i n và n i ti ng. Ngoài cách gi i b ng tìm ki m vét c n, ngư i ta ã ưa ra nhi u thu t toán khác cho bài toán này. Thu t toán quy ho ch ng cho bài toán ngư i bán hàng òi h i th i gian O(n22n). Cho t i nay ngư i ta v n chưa tìm ra thu t toán có th i gian a th c cho bài toán ngư i bán hàng. 16.4.2 Quay lui Quay lui (backtracking) là k thu t thi t k thu t toán có th s d ng gi i quy t r t nhi u v n khác nhau. Ưu i m c a quay lui so v i tìm ki m vét c n là ch có th cho phép ta h n ch các kh năng c n xem xét. Trong nhi u v n , vi c tìm nghi m c a v n ư c quy v tìm m t dãy các tr ng thái (a1, a2,…, ak,…), trong ó m i ai (i = 1,2,…) là m t tr ng thái ư c ch n ra t m t t p h u h n Ai các tr ng thái, tho mãn các i u ki n nào ó. Tìm ki m vét c n òi h i ta ph i xem xét t t c các dãy tr ng thái ó tìm ra dãy tr ng thái tho mãn các yêu c u c a bài toán. Chúng ta s g i dãy các tr ng thái (a1, a2,…, an) tho mãn các yêu c u c a bài toán là vectơ nghi m. Ý tư ng c a k thu t quay lui là ta xây d ng 425
vectơ nghi m xu t phát t vectơ r ng, m i bư c ta b xung thêm m t thành ph n c a vectơ nghi m, l n lư t a1,a2,… u tiên, t p S1 các ng c viên có th là thành ph n u tiên c a vectơ nghi m chính là A1. Ch n a1 ∈ S1, ta có vectơ (a1). Gi s sau bư c th i-1, ta ã tìm ư c vectơ (a1,a2,…,ai-1). Ta s g i các vectơ như th là nghi m m t ph n (nó tho mãn các òi h i c a bài toán, nh ng chưa “ y ”). Bây gi ta m r ng nghi m m t ph n (a1,a2,…,ai-1) b ng cách b xung thêm thành ph n th i. Mu n v y, ta c n xác nh t p Si các ng c viên cho thành ph n th i c a vectơ nghi m. C n lưu ý r ng, t p Si ư c xác nh theo các yêu c u c a bài toán và các thành ph n a1,a2,…,ai-1 ã ch n trư c, và do ó Si là t p con c a t p Ai các tr ng thái. Có hai kh năng • N u Si không r ng, ta ch n ai ∈ Si và thu ư c nghi m m t ph n (a1,a2,…,ai-1,ai), ng th i lo i ai ã ch n kh i Si. Sau ó ta l i ti p t c m r ng nghi m m t ph n (a1,a2,…,ai) b ng cách áp d ng quy th t c m r ng nghi m. • N u Si r ng, i u này có nghĩa là ta không th m r ng nghi m m t ph n (a1,a2,…,ai-2,ai-1), thì ta quay l i ch n ph n t m i a’i-1 trong Si-1 làm thành ph n th i-1 c a vectơ nghi m. N u thành công (khi Si-1 không r ng) ta nh n ư c vectơ (a1,a2,…,ai-2,a’i-1) r i ti p t c m r ng nghi m m t ph n này. N u không ch n ư c a’i-1 thì ta quay lui ti p ch n a’i-2… Khi quay lui ch n a’1 mà S1 ã tr thành r ng thì thu t toán d ng. Trong quá trình m r ng nghi m m t ph n, ta c n ki m tra xem nó có là nghi m không. N u là nghi m, ta ghi l i ho c in ra nghi m này. K thu t quay lui cho phép ta tìm ra t t c các nghi m c a bài toán. K thu t quay lui mà ta ã trình bày th c ch t là k thu t i qua cây tìm ki m theo sâu ( i qua cây theo th t preorder). Cây tìm ki m ư c xây d ng như sau 426
• Các nh con c a g c là các tr ng thái c a S1 • Gi s ai-1 là m t nh m c th i-1 c a cây. Khi ó các nh con c a ai-1 s là các tr ng thái thu c t p ng c viên Si. Cây tìm ki m ư c th hi n trong hình 16.1. Start S1 a1 ai-1 ai Si Hình 16.1. Cây tìm ki m vectơ nghi m Trong cây tìm ki m, m i ư ng i t g c t i m t nh tương ng v i m t nghi m m t ph n. Khi áp d ng k thu t quay lui gi i quy t m t v n , thu t toán ư c thi t k có th là quy ho c l p. Sau ây ta s ưa ra lư c t ng quát c a thu t toán quay lui. Lư c thu t toán quay lui quy. Gi s vector là nghi m m t ph n (a1,a2,…,ai-1). Hàm quy ch n thành ph n th i c a vector nghi m là như sau: Backtrack(vector , i) 427
// Ch n thành ph n th i c a vector. { if (vector là nghi m) vi t ra nghi m; Tính Si; for (m i ai∈Si) Backtrack(vector + (ai) , i+1); } Trong hàm trên, n u vector là nghi m m t ph n (a1,…,ai-1) thì vector + (ai) là nghi m m t ph n (a1,a2,…,ai-1,ai). tìm ra t t c các nghi m, ta ch c n g i Backtrack(vector,1), v i vector là vector r ng. Lư c thu t toán quay lui không quy Backtrack { k = 1; Tính S1; while (k>0) { if (Sk không r ng) { ch n ak ∈ Sk; Lo i ak kh i Sk; if ((a1,…,ak) là nghi m) vi t ra nghi m; k++; Tính Sk; } else k-- ; //Quay lui } } Chú ý r ng, khi cài t thu t toán theo lư c không quy, chúng ta c n bi t cách lưu l i v t c a các t p ng viên S1, S2,…,Sk khi quay lui ta có th ch n ư c thành ph n m i cho vectơ nghi m. 428