Một số phương pháp thiết kế thuật giải

Chia sẻ: Thanhtan09 Thanhtan09 | Ngày: | Loại File: DOC | Số trang:38

0
117
lượt xem
39
download

Một số phương pháp thiết kế thuật giải

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

Nội dung của chương này là một số chiến lược thiết kế thuật giải như chia để trị, vét cạn, tham lam, quy hoạch động...

Chủ đề:
Lưu

Nội dung Text: Một số phương pháp thiết kế thuật giải

  1. Một số phương pháp thiết kế thuật giải Nội dung của chương này là một số chiến lược thiết kế thuật giải như chia đ ể trị, vét cạn, tham lam, quy hoạch động... Mặc dù đó là các chiến lược tổng quát, tuy nhiên mỗi phương pháp chỉ áp dụng cho những lớp bài toán phù hợp. Nội dung của chương, ngoài phần trình bày về các phương pháp còn có những ví dụ cụ thể, cả thuật giải và cài đặt, để người đọc có một cái nhìn chi tiết về việc từ thuật toán đến chương trình. 8.1. Chia để trị (Divide and Conquer) Chia để trị là một tư tưởng rất phổ biến trong cuộc sống và được áp dụng rất hiệu quả trong Tin học. Tư tưởng cơ bản của phương pháp chia đ ể trị là chia một bài toán lớn, khó giải thành các bài toán tương tự, có kích thước nhỏ h ơn và d ễ giải hơn sao cho ta có thể phối hợp kết quả của các bài toán con đó để có k ết qu ả của bài toán lớn. Rất nhiều thuật toán ta gặp ở chương trước đều mang tư tưởng "chia để trị": thuật toán sắp xếp nhanh Quick sort, thuật toán sắp xếp trộn Merge sort, thuật toán tìm kiếm nhị phân,… Chúng ta sẽ nghiên cứu bài toán Tháp Hà n ội, là m ột bài toán điển hình được giải bằng phương pháp chia để trị. 8.1.1. Bài toán Tháp Hà Nội Có N đĩa có đường kính khác nhau được đặt chồng lên nhau theo th ứ t ự gi ảm d ần của đường kính tính từ dưới lên. Có ba vị trí có th ể đặt các đĩa đánh s ố 1, 2, 3. Chồng đĩa ban đầu được đặt ở vị trí 1: 1 2 3 Cần chuyển cả chồng đĩa từ vị trí 1 sang vị trí 2, theo những quy tắc sau: • Khi di chuyển một đĩa, phải đặt nó vào một trong ba vị trí đã cho. • Mỗi lần chỉ có thể chuyển một đĩa và phải là đĩa ở trên cùng. • Tại một vị trí, đĩa nào mới chuyển đến sẽ phải đặt lên trên cùng. Đĩa lớn h ơn không bao giờ được phép đặt lên trên đĩa nhỏ hơn (hay nói cách khác: một đĩa chỉ được đặt trên mặt đất hoặc đặt trên một đĩa lớn hơn)
  2. Bài toán này có nguồn gốc là một truy ền thuy ết c ủa Ấn đ ộ r ằng có m ột nhóm cao tăng Ấn độ giáo được giao trọng trách chuyển dần 64 đĩa vàng gi ữa 3 c ọc kim cương theo các điều kiện đã nói ở phần trên. Khi nào hoàn tất công việc, t ức là khi chuyển xong toàn bộ 64 đĩa từ vị trí ban đầu sang vị trí kết thúc thì cũng là th ời điểm tận thế. Chúng ta giải bài toán bằng cách chia bài toán chuyển N đĩa, t ừ v ị trí 1 sang v ị trí 2 thành ba bài toán đơn giản hơn như sau: 1. Chuyển N-1 đĩa trên cùng từ vị trí 1 sang vị trí 3, dùng vị trí 2 làm trung gian. 2. Chuyển đĩa thứ N từ vị trí 1 sang vị trí 2. 3. Chuyển N-1 đĩa từ vị trí 3 sang vị trí 2, dùng vị trí 1 làm trung gian. Chú ý rằng bài toán 1 và 3 tương tự như bài toán ban đầu, chỉ khác là kích th ước nhỏ hơn. Chúng cũng sẽ được giải bằng phương pháp “chia đ ể trị” gi ống nh ư bài toán ban đầu. Dễ dàng kiểm tra là khi giải như vậy chúng vẫn thoả mãn các đi ều kiện. Bài toán 2 thì được giải rất đơn giản. Thuật toán được viết dưới dạng giả mã như sau: Procedure Hanoi; begin Move(n,1,2,3); end; Procedure Move(n,a,b,c); {chuyển n đĩa, từ vị trí a sang vị trí b, dùng vị trí c làm trung gian } begin if n=0 then exit; Move(n-1,a,c,b); writeln('Chuyển đĩa ',n, ' từ vị trí ',a, 'sang vi tri ',b); Move(n-1,c,b,a); end; Chúng ta hãy dừng lại một chút để phân tích độ phức t ạp tính toán. G ọi T(n) là s ố thao tác chuyển đĩa cần thiết để chuyển xong n đĩa. Theo thuật toán trên ta có: T(n) = T(n-1) + 1 + T(n-1). Bằng các phương pháp giải công thức truy hồi ta có được T(n) = 2 n-1. Áp dụng kết quả này với giả thiết rằng mỗi cao tăng phải mất 1 giây để chuy ển xong một đĩa từ cọc này sang cọc kia, ta thấy thời gian để chuyển toàn bộ 64 đĩa vàng là T(64)=216-1=18446744073709551615 giây. Như vậy ngày tận thế (nếu có) theo truyền thuyết phải 600 tỉ năm nữa mới đến. Chúng ta sẽ phân tích một thuật toán nữa để thấy được sự hiệu quả của ph ương pháp chia để trị. Bài toán được chọn để phân tích tiếp theo là bài toán nhân 2 s ố lớn.
  3. 8.1.2. Bài toán nhân hai số lớn Rất nhiều ứng dụng trong thực tế đòi hỏi phải xử lí các số rất lớn, n ằm ngoài khoảng biểu diễn của các kiểu cơ sở của ngôn ngữ lập trình (ch ẳng h ạn vi ệc tìm các số nguyên tố rất lớn trong mã hoá RSA). Để giải quy ết các yêu c ầu đó, chúng ta phải xây dựng các kiểu số rất lớn và xây dựng các phép toán t ương ứng. Trong phần này ta chỉ xét phép toán nhân đối với hai số rất lớn. Gi ả thi ết c ả hai đ ều có n chữ số và được biểu diễn bằng mảng. Bài toán nhân 2 số lớn phát biểu như sau: Input. A,B là 2 số nguyên có n chữ số: A=A1A2….An và B=B1B2….Bn. Output. C=A.B Thuật toán tự nhiên (brute-force) của bài toán nhân 2 số lớn là giải thuật nhân tay ta vẫn thực hiện: lần lượt nhân từng chữ số của số thứ hai với số thứ nh ất, dịch kết quả theo vị trí và cộng các kết quả trung gian lại. Chẳng hạn để nhân A=1981 và B=1234 ta tiến hành như sau: 1981 × 1234 ------- 7924 + 5943 3962 1981 ------- 2444554 Thuật toán nhân 2 số lớn kiểu nhân tay được mô tả bằng giả mã: function Mul(A,B,n) begin T := 0; for i := 1 to n do begin D := A* Bi; D := D shl (i-1); {dịch D sang trái i-1 chữ số, tức là nhân D với 10i-1} T := T + D; end; return T; end; Dễ dàng tính được độ phức tạp tính toán của thuật toán này là O(n 2). Chúng ta cố gắng giảm bậc của thuật toán với tư tưởng chia để trị. Để đơn giản, ta giả thiết n=2k và tách A,B dưới dạng XY và UV trong đó X,Y,U,V là các số có k ch ữ s ố. Như vậy phép nhân 2 số A,B được tính như sau: A.B = (X.10k + Y).(U.10k+V) = XU.102k + (XV+YU).10k+UV.
  4. Kết quả là bài toán nhân 2 số A.B có 2k chữ số được chia thành 4 bài toán con nhân các số k chữ số và một số phép cộng, trừ. Nh ưng như vậy v ẫn còn nhi ều. Ta ti ếp tục cải tiến bằng nhận xét: XV+YU = (X+U).(Y+V) - (XY + UV). Đặt P = XY; Q = UV; R = (X+U).(Y+V). Từ 2 đẳng thức trên ta có: A.B = P.102k + (R-P-Q).10k+Q. Như vậy bài toán nhân 2 số A.B có n chữ số được chia thành 3 bài toán con nhân các số n/2 chữ số và một số phép cộng, trừ. Thuật toán được viết dạng gi ả mã như sau: function Mul(A,B,n) begin if n=1 then return A1*B1; k = n / 2; X :=A(1..k); Y := A(k+1..n); U :=B(1..k); V := B(k+1..n); P := Mul(X,Y,k); Q := Mul(X,Y,k); R := Mul(X+U,Y+V,k); T := P shl n + (R-P-Q) shl k + Q; return T end; Để xác định độ phức tạp của thuật toán, ta coi là thao tác cơ bản là phép nhân, cộng và dịch trái từng chữ số. Gọi T(n) là số thao tác cơ bản đ ể th ực hi ện nhân 2 số có n chữ số. Ta có: T(n) = 3T(n/2) + C.n Giải ra ta có T(n) = n log23 = n1.59, tức là có một số cải thiện so với thuật toán nhân tay. (Tuy nhiên khác biệt cũng không rõ rệt và ch ỉ th ể hi ện khi n khá l ớn nên thông thường trong các bài toán không lớn lắm người ta thường dùng thuật toán đầu tiên). Qua các phần trên chúng ta đã thấy được phần nào hiệu quả của phương pháp chia để trị. Cuối chương này chúng ta sẽ gặp lại tư tưởng chia đ ể trị trong ph ần nói v ề phương pháp quy hoạch động. Quy hoạch động là tư tưởng chia để trị triệt để và là một phương pháp cực kì hiệu qủa trong việc giải các bài toán tối ưu. 8.2. Vét cạn (Exhausted search) Vét cạn, duyệt, quay lui… là một số tên gọi tuy không đ ồng nghĩa nh ưng cùng ch ỉ một phương pháp rất đơn giản trong tin học: tìm nghiệm của một bài toán bằng cách xem xét tất cả các phương án có thể. Đối với con người phương pháp này thường là không khả thi vì số phương án cần kiểm tra quá l ớn. Tuy nhiên đ ối v ới
  5. máy tính, nhờ tốc độ xử lí nhanh, máy tính có th ể gi ải rất nhi ều bài toán b ằng phương pháp vét cạn. Ưu điểm lớn nhất của phương pháp vét cạn là luôn đảm bảo tìm ra nghiệm chính xác. Ngoài ra phương pháp vét cạn còn có một số ưu điểm so với các phương pháp khác là đòi hỏi rất ít bộ nhớ và cài đặt đ ơn gi ản. H ạn ch ế duy nh ất của phương pháp này là thời gian thực thi rất lớn , độ phức tạp thường ở bậc mũ. Do đó vét cạn thường chỉ áp dụng tốt với các bài toán có kích thước nhỏ. Mặc dù vậy, không nên coi thường phương pháp này. Rất nhiều bài toán ch ỉ có thuật toán duy nhất là vét cạn: từ bài toán đơn giản như tìm s ố l ớn nh ất trong m ột dãy số đến các bài toán NPC. Trong một số tình huống khác, chẳng hạn như thời gian lập trình hạn chế thì vét cạn có thể coi như một giải pháp tình th ế. R ất nhi ều trường hợp ta có thể sử dụng vét cạn theo phương châm: thà mất 1h để viết một chương trình vét cạn chạy trong trong 4 tiếng, còn hơn mất 4 ngày tìm thu ật toán hiệu qủa để chương trình chạy trong 1 phút. Chúng ta không đề cập kĩ về việc áp dụng phương pháp vét cạn đối với các bài toán đơn giản như tìm giá trị nhỏ nhất, lớn nhất hay tìm tất cả các s ố nguyên tố của một tập hợp. Chúng ta sẽ xem xét thuật toán vét cạn đối với các bài toán tìm cấu hình tổ hợp và bài toán tối ưu tổ hợp, là l ớp các bài toán r ất t ổng quát và ph ổ biến trong tin học. 8.2.1. Bài toán tìm cấu hình tổ hợp Có rất nhiều bài toán trong Tin học có yêu cầu dạng: tìm các đối tượng x thoả mãn những điều kiện nhất định trong một tập S các đối tượng cho trước. Bài toán tìm cấu hình tổ hợp là bài toán yêu cầu tìm các đối tượng x có d ạng là m ột vector tho ả mãn các điều kiện sau: 1. Đối tượng x gồm n phần tử: x = (x1,x2,…xn). 2. Mỗi phần tử xi có thể nhận một trong các giá trị rời rạc a1, a2, … am. 3. x thoả mãn các ràng buộc có thể cho bởi hàm logic G(x). Tuỳ từng trường hợp mà bài toán có thể yêu cầu: tìm một nghiệm, tìm tất cả nghiệm hoặc đếm số nghiệm. Trước hết chúng ta nhắc lại một số cấu hình tổ hợp cơ bản. a) Tổ hợp Một tổ hợp chập k của n là một tập con k phần tử của tập n phần tử.
  6. Chẳng hạn tập {1,2,3,4} có các tổ hợp chập 2 là: {1,2}, {1,3, {1,4, {2,3}, {2,4}, {3,4}. Vì trong tập hợp các phần tử không phân biệt thứ tự nên tập {1,2} cũng là tập {2,1} và do đó, ta coi chúng chỉ là một tổ hợp. Bài toán đặt ra cho chúng ta là hãy xác định tất cả các tổ hợp châp k của t ập n phần tử. Để đơn giản ta chỉ xét bài toán tìm các tổ hợp của tập các số nguyên từ 1 đến n. Đối với một tập hữu hạn bất kì, bằng cách đánh số th ứ tự của các ph ần t ử, ta cũng đưa được về bài toán đối với tập các số nguyên từ 1 đến n. Nghiệm cần tìm của bài toán tìm các tổ hợp chập k của n ph ần t ử ph ải tho ả mãn các điều kiện sau: 1. Là một vector x =(x1,x2,…xk) 2. xi lấy giá trị trong tập {1,2,…n} 3. Ràng buộc: xi
  7. c) Chỉnh hợp không lặp Khác với chỉnh hợp lặp là các thành phần được phép lặp lại, tức là có th ể gi ống nhau, chỉnh hợp không lặp chập k của tập n ph ần tử cũng là một dãy k thành ph ần lấy từ tập n phần tử có xét thứ tự nhưng các thành phần không được phép giống nhau. Chẳng hạn có n người, một cách chọn ra k người để xếp thành một hàng là một chỉnh hợp không lặp chập k của n. Một trường hợp đặc biệt của chỉnh hợp không lặp là hoán vị. Hoán vị của một t ập n phần tử là một chỉnh hợp không lặp chập n. Nói một cách trực quan thì hoán vị của tập n phần tử là phép thay đổi vị trí của các phần tử (do đó mới gọi là hoán vị). Nghiệm của bài toán tìm các chỉnh hợp không lặp chập k của tập n số nguyên từ 1 đến n là các vector x thoả mãn các điều kiện: 1. x có k thành phần: x = (x1,x2,…xk) 2. Các giá trị xi lấy trong tập {1,2,..n} 3. Ràng buộc: các giá trị xi đôi một khác nhau, tức là xi≠ xj với mọi i≠ j. Đó là một số bài toán tìm cấu hình tổ h ợp cơ bản. Chúng ta s ẽ xem xét m ột s ố bài toán khác để thấy tính phổ biến của lớp các bài toán dạng này. d) Bài toán xếp hậu Cho bàn cờ vua nxn. Hãy xếp n con hậu lên bàn cờ sao cho không con nào kh ống chế con nào. Hai 2 con hậu khống chế nhau nếu chúng ở trên cùng m ột hàng, m ột cột hoặc một đường chéo. Chẳng hạn ta có một cách đặt sau, các ô đen là các vị trí đặt hậu: Để chuyển bài toán này về dạng chuẩn của bài toán tìm cấu hình t ổ h ợp, ta có có nhận xét: mỗi con hậu phải ở trên một hàng và một cột. Do đó ta coi con h ậu th ứ i ở hàng i và nếu biết x[i] là cột đặt con hậu thứ i thì ta suy ra được l ời gi ải. V ậy nghiệm của bài toán có thể coi là một vector x gồm n thành phần với ý nghĩa:
  8. 1. Con hậu thứ i được đặt ở hàng i và cột x[i]. 2. x[i] lấy giá trị trong tập {1,2…n} 3. Ràng buộc: các giá trị x[i] khác nhau từng đôi một và không có 2 con h ậu ở trên cùng một đường chéo. Trong phần cài đặt, chúng ta sẽ phân tích chi tiết về các ràng buộc trên. e) Bài toán từ đẹp (xâu ABC) Một từ đẹp là một xâu độ dài n chỉ gồm các kí tự A,B,C mà không có 2 xâu con liên tiếp nào giống nhau. Chẳng hạn ABAC là một từ đẹp đ ộ dài 4, BABCA là một từ đẹp độ dài 5. Bài toán tìm tất cả các từ đẹp độ dài n cho trước yêu c ầu tìm nghi ệm là các vector x có n thành phần: 1. xi nhận giá trị trong tập {A,B,C} 2. x không có 2 đoạn con liên tiếp nào bằng nhau. Trước khi trình bày về phương pháp vét cạn giải các bài toán tìm c ấu hình t ổ h ợp, chúng ta xem xét các bài toán tối ưu tổ hợp, vì các bài toán t ối ưu t ổ h ợp th ực ch ất là sự mở rộng của bài toán tìm cấu hình tổ hợp. 8.2.2. Bài toán tối ưu tổ hợp Bài toán tối ưu tổng quát có thể phát biểu như sau: Cho t ập B khác rỗng và m ột hàm f:B→R gọi là hàm mục tiêu. Cần tìm phần tử x thuộc B sao cho f(x) đ ạt giá tr ị nhỏ nhất hoặc lớn nhất. Phần tử x là nghiệm của bài toán còn được gọi là ph ương án tối ưu. Bài toán tối ưu tổ hợp là bài toán tìm phương án tối ưu trên tập các cấu hình tổ hợp. Nghiệm của bài toán cũng là một vector x gồm n thành phần sao cho: 1. x = (x1,x2,…xn) 2. xi lấy giá trị trong tập {a1,a2,…am} 3. x thoả mãn các ràng buộc cho bởi hàm G(x). 4. f(x) → min/max. Chúng ta sẽ phân tích một số bài toán tối ưu tổ h ợp đi ển hình. Ph ần l ớn đ ều là các bài toán NPC.
  9. a) Bài toán xếp balô Có một balô có tải trọng m và n đồ vật, đồ vật i có tr ọng l ượng wi và có giá tr ị vi. Hãy lựa chọn các vật để cho vào balô sao cho tổng trọng lượng của chúng không quá M và tổng giá trị của chúng là lớn nhất. Mỗi cách chọn các đồ vật cho vào balô đều tương ứng với một vector x g ồm n thành phần mà xi=1 nếu chọn đưa vật th ứ i vào balô, và xi=0 n ếu v ật th ứ i không được chọn. Khi đó ràng buộc tổng trọng lượng các đồ vật không quá tải trọng của balô đ ược viết thành: n ∑x w i =1 i i ≤m Hàm mục tiêu là tổng giá trị của các đồ vật được chọn: n f ( x ) = ∑ x i v i → max i =1 Nghiệm của bài toán cũng là một vector x gồm n thành phần sao cho: 1. x = (x1,x2,…xn) 2. xi lấy giá trị trong tập {0,1} n 3. Ràng buộc: ∑x w i =1 i i ≤m n 4. f ( x ) = ∑ x i v i → max . i =1 b) Bài toán người du lịch Có n thành phố, d[i,j] là chi phí để di chuy ển t ừ thành ph ố i đ ến thành ph ố j. (N ếu không có đường đi thì d[i,j] = ∞). Một người muốn đi du lịch qua tất cả các thành phố, mỗi thành phố một lần rồi trở về nơi xuất phát sao cho tổng chi phí là nh ỏ nhất. Hãy xác định một đường đi như vậy. Phương án tối ưu của bài toán cũng là một vector x, trong đó xi là thành phố sẽ đến thăm tại lần di chuyển thứ i. Các điều kiện của x như sau: 1. x = (x1,x2,…xn) 2. xi lấy giá trị trong tập {1,2,…n} 3. Ràng buộc: xi ≠ xj với mọi i≠ j và d[xi,xi+1]
  10. n 4. f(x) = ∑ d[x , x i =1 i i +1 ] → min Trên đây ta đã xét một số bài toán tìm cấu hình tổ hợp và bài toán tối ưu t ổ h ợp. Trong phần tiếp chúng ta sẽ tìm hiểu phương pháp vét cạn giải các bài toán đó. 8.2.3. Phương pháp vét cạn giải các bài toán cấu hình tổ hợp và tối ưu tổ hợp Phương pháp vét cạn là phương pháp rất tổng quát để đơn giản để giải các bài toán cấu hình tổ hợp và tối ưu tổ hợp. ý tưởng cơ bản là: bằng một cách nào đó sinh ra tất cả các cấu hình có thể rồi phân tích các cấu hình b ằng các hàm ràng buộc và hàm mục tiêu để tìm phương án tối ưu (do đó ph ương pháp này còn đ ược gọi là duyệt toàn bộ). Dựa trên ý tưởng cơ bản đó, người ta có 3 cách ti ếp c ận khác nhau đ ể duy ệt toàn bộ các phương án. Phương pháp thứ nhất là phương pháp sinh tuần tự. Phương pháp này cần xác định một quan hệ thứ tự trên các cấu hình (gọi là thứ t ự từ đi ển) và m ột phép bi ến đ ổi để biến một cấu hình thành cấu hình ngay sau nó. Mỗi lần sinh được một cấu hình thì tiến hành định giá, so sánh với cấu hình tốt nhất đang có và cập nhật nếu cấu hình mới tốt hơn. Giả mã của thuật toán tìm cấu hình tối ưu bằng phương pháp sinh như sau: Procedure Generate; begin x := FirstConfig; best := x; Repeat x := GenNext(x); if f(x) "tốt hơn" f(best) then best := x; Until x = LastConfig; end; Thuật toán thực hiện như sau: tìm cấu hình đầu tiên và coi đó là c ấu hình t ốt nh ất. Sau đó lần lượt sinh các cấu hình tiếp theo, m ỗi l ần sinh đ ược m ột c ấu hình ta so sánh nó với cấu hình tốt nhất hiện có (best) và nếu nó tốt hơn thì c ập nh ật best. Quá trình dừng lại khi ta sinh được cấu hình cuối cùng. Kết quả ta được phương án tối ưu là best. Phương pháp sinh tuần tự thường rất khó áp dụng. Khó khăn chủ yếu là do việc xác định thứ tự từ điển, cấu hình đầu tiên, cấu hình cuối cùng và phép biến đổi một cấu hình thành cấu hình tiếp theo thường là không dễ dàng. Phương pháp thứ hai là phương pháp thử sai − quay lui (Backtracking). Tư tưởng cơ bản của phương pháp là xây dựng từng thành ph ần của cấu hình, t ại m ỗi b ước xây dựng đều kiểm tra các ràng buộc và chỉ tiếp tục xây dựng các thành ph ần ti ếp
  11. theo nếu các thành phần hiện tại là thoả mãn. Nếu không còn phương án nào để xây dựng thành phần hiện tại thì quay lại, xây dựng lại các thành phần trước đó. Giả mã của thuật toán quay lui như sau. procedure Backtrack; begin i := 1; x[1] := a0; repeat x[i] := next(x[i]); if ok then Forward else Backward; until i=0; end; procedure Forward; begin if i = n then Update else begin i := i + 1; x[i] := a0; end; end; procedure Backward; begin i := i − 1; end; procedure Update; begin if f(x) "tốt hơn" f(best) then best := x; end; Trong đoạn mã này, hàm Ok để kiểm tra các thành ph ần đ ược sinh ra có tho ả mãn các ràng buộc hay không, còn hàm Next trả lại lựa chọn tiếp theo của mỗi thành phần. Nhìn chung phương pháp quay lui làm giảm đáng kể những khó khăn của ph ương pháp sinh (không cần tìm thứ tự từ điển và nhất là không c ần tìm quy t ắc sinh c ấu hình tiếp theo). Tuy nhiên, trong một số bài toán mà cần đánh dấu trạng thái, phương pháp quay lui không đệ quy được trình bày ở trên phải xử lí ph ức t ạp h ơn nhiều so với phương pháp quay lui đệ quy. Phương pháp quay lui đệ quy là phương pháp đơn giản và tổng quát nhất để sinh các cấu hình tổ hợp. Do cơ chế cục bộ hoá của chương trình con đệ quy và khả năng quay lại điểm gọi đệ quy, thao tác quay lui trở thành m ặc đ ịnh và không c ần xử lý một cách tường minh như phương pháp quay lui không đệ quy. Mô hình cơ bản của phương pháp quay lui đệ quy như sau: Procedure Search; begin Try(1); end; procedure Try(i); var j; Begin for j := 1 to m do
  12. if then begin x[i] := a[j]; ; if i=n then Update else Try(i+1); ; end; end; procedure Update; begin if f(x) "tốt hơn" f(best) then best := x; end; Để duyệt tòan bộ các cấu hình, ban đầu ta gọi đến Try(1). Try(1) s ẽ l ựa ch ọn cho x1 một giá trị thích hợp đầu tiên, ghi nhận trạng thái rồi gọi đ ệ quy đ ến Try(2). Try(2) lại lựa chọn một giá trị cho x 2, ghi nhận trạng thái và gọi đến Try(3). Cứ như vậy ở bước thứ i, thuật toán tìm một giá trị cho xi, ghi nh ận tr ạng thái r ồi g ọi đệ quy để sinh thành phần xi+1. Khi sinh đủ n thành phần của x thì dừng lại để cập nhật phương án tối ưu. Nếu mọi khả năng của xi +1 đều đã xét qua thì vòng for của Try(i+1) thực hiện xong, theo cơ chế đệ quy chương trình sẽ quay về đi ểm gọi đ ệ quy của Try(i). Trạng thái cũ trước khi chọn xi được phục h ồi và vòng for c ủa Try(i) sẽ tiếp tục để chọn giá trị phù hợp tiếp theo của xi, đó chính là thao tác quay lui. Khi quay lui về đến Try(1) và xét hết mọi khả năng của x 1 thì chương trình con đệ quy kết thúc và ta đã duyệt được toàn bộ các cấu hình. Trên đây là các thuật toán vét cạn đối với bài toán tìm cấu hình tối ưu. Trong trường hợp bài toán cần tìm một cấu hình, tìm mọi c ấu hình hay đ ếm s ố c ấu hình thì thuật toán cũng tương tự, chỉ khác ở phần cập nhật (Update) khi sinh đ ược m ột cấu hình mới. Chẳng hạn thủ tục Update đối với bài toán tìm và đếm mọi cấu hình s ẽ tăng s ố cấu hình và in ra cấu hình vừa tìm được: procedure Update; begin count := count + 1; print(x); end; Chúng ta sẽ dùng thuật toán quay lui đệ quy để giải các bài toán cấu hình tổ hợp và tối ưu tổ hợp đã trình bày ở trên. a) Sinh các tổ hợp chập k của n Đây là bài toán sinh tổ hợp đã được chúng ta trình bày ở phần trên. Ta sẽ giải bằng thuật toán tìm cấu hình tổ hợp bằng đệ quy quay lui. Về cấu trúc dữ liệu ta chỉ cần một mảng x để biểu diễn tổ hợp. Ràng buộc đối với giá trị x[i] là: x[i−1]< x[i] ≤ n−k+ i. Thủ tục đệ quy sinh tổ hợp như sau:
  13. procedure Try(i); var j; begin for j := x[i−1]+1 to n−k+i do begin x[i] := j; if i=k then Print(x) else Try(i+1); end; end; Dưới đây là toàn văn chương trình sinh tổ hợp viết bằng ngôn ng ữ Pascal. Đ ể đ ơn giản, các giá trị n,k được nhập từ bàn phím và các tổ h ợp được in ra màn hình. Người đọc có thể cải tiến chương trình để nhập/xuất ra file. program SinhTohop; uses crt; const max = 20; var n,k : integer; x : array[0..max] of integer; {===============================} procedure input; begin clrscr; write('n,k = '); readln(n,k); writeln('Cac to hop chap ',k,' cua ',n); end; procedure print; var i : integer; begin for i := 1 to k do write(' ',x[i]); writeln; end; procedure try(i:integer); var j : integer; begin for j := x[i-1]+1 to n-k+i do begin x[i] := j; if i = k then Print else try(i+1); end; end; procedure solve; begin x[0] := 0; try(1); end; {===============================} BEGIN input; solve; END.
  14. Chú ý trong phần cài đặt là có khai báo thêm phần tử x[0] để làm "lính canh", vì vòng lặp trong thủ tục đệ quy có truy cập đến x[i −1], và khi gọi Try(1) thì sẽ truy cập đến x[0]. b) Sinh các chỉnh hợp lặp chập k của n Xem lại phân tích của bài toán sinh chỉnh hợp lặp chập k của n ta thấy hoàn toàn không có ràng buộc nào đối với cấu hình sinh ra. Do đó, c ấu trúc d ữ li ệu c ủa ta ch ỉ gồm một mảng x để lưu nghiệm. Thuật toán sinh chỉnh hợp lặp như sau: procedure Try(i); var j; begin for j := 1 to n do begin x[i] := j; if i=k then Print(x) else Try(i+1); end; end; Dưới đây là chương trình sinh tất cả các dãy nhị phân độ dài n. Để đơn giản, chương trình nhập n từ bàn phím và in các kết quả ra màn hình. program SinhNhiphan; uses crt; const max = 20; var n : integer; x : array[1..max] of integer; {===============================} procedure input; begin clrscr; write('n = '); readln(n); writeln('Cac day nhi phan do dai ',n); end; procedure print; var i : integer; begin for i := 1 to n do write(' ',x[i]); writeln; end; procedure try(i:integer); var j : integer; begin for j := 0 to 1 do begin x[i] := j; if i = n then Print else try(i+1); end; end; procedure solve; begin
  15. try(1); end; {===============================} BEGIN input; solve; END. c) Sinh các chỉnh hợp không lặp chập k của n Chỉnh hợp không lặp yêu cầu các phần tử phải khác nhau. Để đảm bảo điều đó, ngoài mảng x, ta sẽ dùng thêm một cấu trúc dữ liệu nữa là mảng d để đánh dấu. Khi một giá trị được chọn, ta đánh dấu giá trị đó, và khi chọn, ta chỉ chọn các giá trị chưa đánh dấu. Mảng d sẽ là "trạng thái" của thuật toán. Bạn đọc xem ph ần giả mã dưới đây để thấy rõ hơn ý tưởng đó. procedure Try(i); var j; begin for j := 1 to n do if d[j]=0 then begin x[i] := j; d[j] := 1; if i=k then Print(x) else Try(i+1); d[i] := 0; end; end; Chương trình dưới đây sẽ sinh toàn bộ các hoán vị của tập n số nguyên từ 1 đ ến n. Giá trị n được nhập từ bàn phím và các hoán vị được in ra màn hình. program SinhHoanvi; uses crt; const max = 20; var n : integer; x,d : array[1..max] of integer; {===============================} procedure input; begin clrscr; write('n = '); readln(n); writeln('Cac hoan vi cua day ',n); end; procedure print; var i : integer; begin for i := 1 to n do write(' ',x[i]); writeln; end; procedure try(i:integer); var j : integer; begin for j := 1 to n do
  16. if d[j] = 0 then begin x[i] := j; d[j] := 1; if i = n then Print else try(i+1); d[j] := 0; end; end; procedure solve; begin try(1); end; {===============================} BEGIN input; solve; END. d) Bài toán xếp hậu Khác với những bài toán sinh các cấu hình đơn giản ở ph ần trước, sinh các c ấu hình của bài toán xếp hậu đòi hỏi những phân tích chi tiết hơn về các đi ều ki ện ràng buộc. Ràng buộc thứ nhất là các giá trị x[i] phải khác nhau. Ta có th ể dùng một m ảng đánh dấu như ở thuật toán sinh hoán vị để đảm bảo điều này. Ràng buộc thứ 2 là các con hậu không được nằm trên cùng m ột đ ường chéo chính và phụ. Các bạn có thể dễ dàng nhận ra rằng 2 vị trí (x 1,y1) và (x2,y2) nằm trên cùng đường chéo chính nếu: x1−y1=x2−y2=const. Tương tự, 2 vị trí (x1,y1) và (x2,y2) nằm trên cùng đường chéo phụ nếu: x1+ y1=x2+ y2=const Do đó, con hậu i đặt tại vị trí (i,x[i]) và con hậu j đặt tại v ị trí (j,x[j]) ph ải tho ả mãn ràng buộc: i−x[i] ≠ j−x[j] và i+x[i] ≠ j+x[j] với mọi i≠ j Ta có thể viết riêng một hàm Ok để kiểm tra các ràng buộc đó. Nhưng giải pháp tốt hơn là dùng thêm các mảng đánh dấu để mô t ả rằng m ột đ ường chéo chính và phụ đã có một con hậu khống chế. Tức là khi ta đặc con hậu i ở vị trí (i,j), ta s ẽ đánh dấu đường chéo chính i-j và đường chéo phụ i+j. Như vậy về cấu trúc dữ liệu, ta dùng 4 mảng: 1. Mảng x với ý nghĩa: x[i] là cột ta sẽ đặt con hậu thứ i. 2. Mảng cot với ý nghĩa: cot[j]=1 nếu cột j đã có một con hậu được đặt, ngược lại thì cot[j]=0.
  17. 3. Mảng dcc với ý nghĩa: dcc[k]=1 nếu đường chéo chính thứ k đã có một con hậu được đặt, tức là ta đã đặt một con h ậu tại vị trí (i,j) mà i −j=k; ngược lại thì dcc[k]=0. 4. Tương tự ta dùng mảng dcp với ý nghĩa: dcp[k]=1 nếu đường chéo phụ th ứ k đã có một con hậu được đặt. Giả mã của thuật toán xếp hậu như sau: procedure Try(i); var j; begin for j := 1 to n do if (cot[j]=0) and (dcc[i-j]=0) and (dcp[i+j]=0) then begin x[i] := j; cot[j]:=1; dcc[i-j]:=1; dcp[i+j]:=1; {ghi nhận trạng thái mới} if i=n then Update else Try(i+1); cot[j]:=0; dcc[i-j]:=0; dcp[i+j]:=0; {phục hồi trạng thái cũ} end; end; procedure Update; begin count := count + 1; print(x); end; Phần dưới là toàn bộ chương trình tìm các phương án xếp hậu trên bàn c ờ 8x8. Chương trình tìm được 92 phương án khác nhau. e) Bài toán từ đẹp Tất cả các bài toán ta đã giải ở trên đều có cấu hình có thành ph ần là các số nguyên. Riêng bài toán từ đẹp thì cần tìm cấu hình là m ột xâu. Ta có th ể dùng m ột mảng kí tự để thay thế, tuy nhiên điều đó không cần thi ết vì ngôn ng ữ Pascal cũng có khả năng xử lí xâu kí tự rất tốt. Mô hình quay lui của bài toán từ đẹp có thể viết như sau: procedure Try(i) var c; begin for c := 'A' to 'C' do begin x := x + c; if Ok(i) then if i=n then Update else Try(i+1); delete(x,i,1); end; end; procedure Update; begin count := count + 1; print(x); end;
  18. Các thủ tục Try, Update khá tương tự các bài toán khác. Riêng đ ể vi ết hàm Ok kiểm tra lựa chọn hiện tại cho x[i] có phù hợp không, chúng ta phân tích sâu hơn như sau: Trước hết ta thấy rằng khi lựa chọn đến x[i] thì xâu x[1..i-1] đã thoả mãn tính chất của từ đẹp. Như vậy nếu x[1..i] không thoả mãn tính chất của từ đẹp thì ch ỉ có khả năng là do kí tự thứ i mới được chọn không phù hợp. Vậy hàm Ok(i) ch ỉ cần kiểm tra các xâu con có chứa x[i] có giống một xâu con liền kề trước nó hay không? Nếu có thì giá trị x[i] đó không thoả mãn và ta ph ải ch ọn giá trị khác. Ngược lại nếu giá trị x[i] thoả mãn thì ta cập nhật kết quả hoặc đệ quy ti ếp tuỳ thuộc vào việc ta đã chọn đủ n kí tự chưa. Hàm Ok có thể viết như sau: function Ok(l) begin Ok := false; for k := 1 to l div 2 do if copy(x,l-k+1,k) = copy(x,l-2*k+1,k) then exit; Ok := true; end; Nếu độc giả thấy hàm Ok khó hiểu thì chúng tôi có th ể gi ải thích nh ư sau: ta c ần kiểm tra mọi xâu con có chứa kí tự cuối cùng có bằng xâu con liền kề trước nó hay không? Độ dài xâu đang có là l, do đó các xâu con có chứa kí tự th ứ l có kh ả năng bằng xâu liền kề trước nó chỉ có độ dài từ 1 đến l/2. Bi ểu th ức copy(x,l- k+1,k) cho kết quả là xâu con gồm k kí tự cuối cùng của x và bi ểu th ức copy(x,l- 2*k+1,k) cho xâu con k kí tự ngay trước xâu con có k kí tự cuối cùng. Phần cài đặt chương trình cụ thể xin dành cho độc giả. Phần tiếp theo chúng tôi xin đề cập đến bài toán tối ưu tổ hợp. f) Bài toán người du lịch. Độc giả dễ dàng nhận thấy mỗi phương án của bài toán người du lịch là m ột hoán vị của n thành phố. Do đó ta có thể dùng mô hình vét c ạn c ủa bài toán sinh hoán v ị để tìm các phương án. Và ta sử dụng thêm ràng buộc: d[xi -1,xi]
  19. begin for j := 1 to n do if (dd[j]=0) and (d[x[i-1],j] < ∞) then begin x[i] := j; dd[j] := 1; if i=n then Update else Try(i+1); dd[j] := 0; end; end; procedure Update; var s,i; begin s := d[x[n],1]; for i := 1 to n-1 do s := s + d[x[i],x[i+1]]; if s < min then begin min := s; best := x; end; end; Lớp các bài toán tối ưu tổ hợp rất rộng. Phần lớn các bài toán đó trong tr ường h ợp tổng quát chỉ có thuật toán tối ưu duy nhất là vét cạn. Tuy nhiên, nh ược đi ểm c ủa phương pháp vét cạn là độ phức tạp tính toán rất lớn do hiện tượng bùng nổ t ổ hợp. Các bạn nhớ lại rằng số hoán vị của tập n phần tử là n!. Do đó trong tr ường hợp xấu nhất thuật toán vét cạn đối với bài toán người du lịch là O(n!). Có 2 giải pháp khắc phục vấn đề này. Giải pháp thứ nhất cải tiến phương pháp vét cạn bằng kỹ thuật nhánh cận, tức là loại bỏ ngay các h ướng đi ch ắc ch ắn không dẫn đến phương án tối ưu. Giải pháp thứ 2 là sử dụng các ph ương pháp khác, mà hai phương pháp nổi bật nhất là phương pháp quy hoạch động và phương pháp tham lam. Phần tiếp theo, chúng tôi sẽ trình bày sơ lược về kỹ thuật nhánh cận. 8.2.4. Kỹ thuật nhánh cận Nguyên nhân dẫn đến độ phức tạp của các bài toán tối ưu tổ hợp là hiện t ượng bùng nổ tổ hợp. Đó là hiện tượng số cấu hình tổ hợp tăng theo hàm mũ đ ối v ới s ố thành phần tổ hợp n. Đơn giản nhất là các dãy nhị phân, mỗi thành phần tổ hợp chỉ có 2 khả năng là 0 và 1 thì số các dãy nhị phân độ dài n đã là 2 n. Do đó việc sinh toàn bộ các cấu hình tổ hợp sẽ không khả thi khi n lớn. Quá trình vét cạn kiểu quay lui là một quá trình tìm kiếm phân cấp, tức là các thành phần x1, x2… sẽ được chọn trước. Nếu tại bước i ta chọn một giá trị xi không t ối ưu thì toàn bộ quá trình chọn xi+1, xi+2… sẽ hoàn toàn vô nghĩa. Ngược lại, nếu ta xác định được rằng giá trị xi đó không dẫn đến cấu hình t ối ưu thì ta s ẽ ti ết ki ệm được toàn bộ các bước chọn xi+1, xi+2… Tiết kiệm đó đôi khi là đáng kể. Chẳng hạn nếu đối với bài toán duyệt nhị phân (tối ưu các cấu hình là dãy nh ị phân) ta
  20. xác định được x1=0 không hợp lí thì ta đã tiết kiệm được 2 n-1 bước duyệt phía sau. Đó chính là tư tưởng của phương pháp nhánh cận. Mô hình quay lui có nhánh cận như sau: Procedure Search; begin Try(1); end; procedure Try(i); var j; Begin for j := 1 to m do if then begin x[i] := a[j]; ; if i=n then Update else if Ok(i) then Try(i+1); ; end; end; Cải tiến so với phương pháp vét cạn thuần tuý là ở câu lệnh if Ok(i) then Try(i+1);. Hàm Ok ở đây được dùng để đánh giá tình trạng của cấu hình hiện t ại. Th ứ nh ất là có đảm bảo dẫn đến cấu hình tối ưu hay không. Nếu không thì ít nhất cũng phải đảm bảo cho giá trị hàm mục tiêu tốt hơn phương án tốt nhất ta đang có. Kĩ thuật nhánh cận rất đa dạng, phụ thuộc vào từng bài toán và t ư duy c ủa ng ười lập trình. Chúng ta sẽ xem xét một số bài toán tối ưu giải bằng phương pháp nhánh cận. Đầu tiên là bài toán người du lịch. Ta có nh ận xét: tại l ần di chuy ển th ứ i, n ếu tổng chi phí đang có ≥ chi phí của phương án tốt nhất ta đang có thì rõ ràng việc đi tiếp không mang đến kết quả tốt hơn. Do đó ta có thể đặt một nhánh cận đơn giản như sau: procedure Try(i) var j; begin for j := 1 to n do if (dd[j]=0) and (d[x[i-1],j] < ∞) then begin x[i] := j; dd[j] := 1; s := s + d[x[i-1],j]; if i=n then Update else if s < min then Try(i+1); dd[j] := 0; s := s - d[x[i-1],j]; end; end; Hai biến s, min là các biến toàn cục, trong đó min dùng đ ể l ưu chi phí c ủa ph ương án tốt nhất còn s lưu tổng chi phí hiện tại.

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản