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

Với một vấn đề đặt ra, làm thế nào chúng ta có thể đưa ra thuậttoán giải quyết nó? Trong chương này, chúng ta sẽ trình bày các chiếnlượ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ộngcá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 chomộ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ếnlược sau: chia-để-trị (divide-and-conquer), quy hoạch động (dynamicprogramming), quay lui (backtracking) và...
Nội dung trích xuất từ tài liệu:
Các chiến lược thiết kế thuật toán409 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ángi i quy t nó? Trong chương này, chúng ta s trình bày các chi n lư c thi tk 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 nlư 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àitoá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 tas trình bày ý tư ng chung c a phương pháp và sau ó ưa ra m t s ví dminh 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ư ccho 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 - - TR16.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 nlư c chia- -tr . Ý tư ng chung c a k thu t này là như sau: Chia v n c ngi i thành m t s v n con cùng d ng v i v n ã cho, ch khác là cc a chúng nh hơn. M i v n con ư c gi i quy t c l p. Sau ó, ta k th 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 tnó, n u không v n con ư c gi i quy t b ng cách áp d ng quy th t ctrê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 410thu t toán ư c thi t k b ng chi n lư c chia- -tr s là các thu t toánquy. 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 411trong 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 ttoá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 ymax, min là giá tr u tiên A[0] c a m ng. Sau ó so sánh max, min v it 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 sosá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. Trongtrư 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 tac 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 nth 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], tad dàng xác nh ư c max, min trên m ng A[0..n-1]. tìm max, min trên 412m ng con ta ti p t c chia ôi chúng. Quá trình s d ng l i khi ta nh n ư cm 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 ...