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:

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)

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) = 2n-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.

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(n2). 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.

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 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ử.

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<xi+1 với mọi giá trị i từ 1 đến k-1.

Có ràng buộc 3 là vì tập hợp không phân biệt thứ tự phần tử nên ta sắp xếp các phần tử theo thứ tự tăng dần.

b) Chỉnh hợp lặp

Chỉnh hợp lặp chập k của n là một dãy k thành phần, mỗi thành phần là một phần tử của tập n phần tử, có xét đến thứ tự và không yêu cầu các thành phần khác nhau.

Một ví dụ dễ thấy nhất của chỉnh hợp lặp là các dãy nhị phân. Một dãy nhị phân độ dài m là một chỉnh hợp lặp chập m của tập 2 phần tử {0,1}. Chẳng hạn 101 là một dãy nhị phân độ dài 3. Ngoài ra ta còn có 7 dãy nhị phân độ dài 3 nữa là 000, 001, 010, 011, 100, 110, 111. Vì có xét thứ tự nên dãy 101 và dãy 011 là 2 dãy khác nhau.

Như vậy, bài toán xác định tất cả các chỉnh hợp lặp chập k của tập n phần tử yêu cầu tìm các nghiệm như sau:

1. Là một vector x =(x1,x2,...xk)

2. xi lấy giá trị trong tập {1,2,...n}

3. Không có ràng buộc nào giữa các thành phần.

Chú ý là cũng như bài toán tìm tổ hợp, ta chỉ xét đối với tập n số nguyên từ 1 đến n. Nếu tập hợp cần tìm chỉnh hợp không phải là tập các số nguyên từ 1 đến n thì ta có thể đánh số các phần tử của tập đó để đưa về tập các số nguyên từ 1 đến n

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:

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.

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:

Hàm mục tiêu là tổng giá trị của các đồ vật được chọn:

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}

3. Ràng buộc:

4. .

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]< với mọi i=1,2,..n, coi xn+1=x1.

4. f(x) =

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 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

if <chọn được a[j]> then begin

x[i] := a[j];

<ghi nhận trạng thái mới>;

if i=n then Update

else Try(i+1);

<trả lại trạng thái cũ>;

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 x2, 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 x1 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:

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.

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

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

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í (x1,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.

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;

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]<. Mặt khác vì phương án là một chu trình nên ta có thể coi thành phố xuất phát là thành phố 1.

Thuật giải bài toán người du lịch bằng vét cạn như sau:

procedure Search;

begin

min := ;

x[1] := 1; dd[1] := 1;

try(2);

end;

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;

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à 2n. 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 xác định được x1=0 không hợp lí thì ta đã tiết kiệm được 2n-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 <chọn được a[j]> then begin

x[i] := a[j];

<ghi nhận trạng thái mới>;

if i=n then Update

else

if Ok(i) then Try(i+1);

<trả lại trạng thái cũ>;

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.

Ta có thể tiếp tục cải tiến cận này bằng việc không chỉ xét chi phí đến thời điểm hiện tại mà còn xét luôn cả chi phí tối thiểu để kết thúc hành trình. Gọi dmin là giá trị nhỏ nhất của bảng d, tương đương với chi phí nhỏ nhất của việc di chuyển từ thành phố này đến thành phố kia. Tại bước thứ i thì ta còn phải thực hiện ni+1 bước di chuyển nữa thì mới kết thúc hành trình (đi qua ni thành phố còn lại và quay về thành phố 1). Do đó chi phí của cả hành trình sẽ tối thiểu là s + (ni+1)*dmin. Nếu chi phí này còn lớn hơn chi phí của phương án tốt nhất thì rõ ràng lựa chọn hiện tại cũng không thể dẫn đến một phương án tốt hơn. Chương trình con vét cạn đệ quy có thể sửa thành:

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 + (n-i+1)*dmin < min then Try(i+1);

dd[j] := 0; s := s - d[x[i-1],j];

end;

end;

Nhìn chung những cận có cải thiện tình hình đôi chút nhưng cũng không thực sự hiệu quả. Người ta cũng đã nghiên cứu nhiều cận chặt hơn, độc giả có thể tìm đọc ở các tài liệu khác.

Ta xét tiếp bài toán từ đẹp nhất. Định nghĩa từ đẹp đã được mô tả ở bài toán từ đẹp. Từ đẹp nhất là từ có ít kí tự C nhất. Rõ ràng bài toán tìm từ đẹp nhất là một bài toán tối ưu tổ hợp.

Chúng ta xây dựng nhánh cận với nhận xét: nếu x[1..n] là từ đẹp thì trong 4 kí tự liên tiếp của x phải có ít nhất một kí tự C. Vậy, nếu ta đã xây dựng i kí tự thì phần còn lại gồm n-i kí tự sẽ có ít nhất (n-i)/4 kí tự C. Do đó số kí tự C tối thiểu của cả xâu sẽ là t + (n-i)/4, trong đó t là số kí tự C của x[1..i]. Ta có thể dùng t+(n-i)/4 làm cận. Chương trình con đệ quy như sau:

procedure Try(i)

var c;

begin

for c := 'A' to 'C' do begin

x := x + c;

if c = 'C' then t := t + 1;

if Ok(i) then

if i=n then Update

else

if t + (n-i) div 4 < minC then Try(i+1);

delete(x,i,1);

if c = 'C' then t := t - 1;

end;

end;

Biến minC ở đây dùng để lưu số kí tự C của phương án tốt nhất đang có.

Nhánh cận là một kĩ thuật mạnh và đòi hỏi tư duy sâu sắc. Chọn được một cận tốt thường không đơn giản, đòi hỏi phải có những phân tích sâu sắc và tỉ mỉ. Một số chú ý khi chọn cận:

1. Cận phải đánh giá chính xác tình trạng cấu hình hiện tại. Nếu quá lỏng thì số cấu hình loại bỏ không đáng kể, nếu quá chặt thì sẽ dẫn đến bỏ sót nghiệm.

2. Cận phải tính toán đơn giản. Vì thao tác tính cận thực hiện tại tất cả các bước nên nếu tính toán cận quá phức tạp thì thời gian rút ngắn nhờ đặt cận tiết kiệm được thì lại mất đáng kể cho việc tính cận.

Mặc dù nhánh cận là kĩ thuật mạnh nhưng muốn để áp dụng tốt đòi hỏi những phân tích rất chi tiết. Hơn nữa nhiều trường hợp có đặt cận thì số phương án cần duyệt vẫn quá nhiều. Trong những trường hợp như vậy chúng ta cần phải có những cách tiếp cận khác. Phần tiếp theo trình bày về một phương pháp cực kì hiệu quả, đó là phương pháp quy hoạch động.

8.3. Phương pháp quy hoạch động (Dymnamic plan)

Quy hoạch động là một phương pháp rất hiệu quả để giải các bài toán tối ưu tổ hợp. ý tưởng cơ bản của phương pháp này là: để có lời giải của bài toán tối ưu kích thước n, ta giải các bài toán tương tự có kích thước nhỏ hơn và phối hợp lời giải của chúng để được lời giải của bài toán ban đầu. Đó chính là tư tưởng chia để trị một cách rất nghiêm ngặt.

Không phải bài toán nào cũng có thể giải bằng quy hoạch động. Để giải được bằng quy hoạch động, bài toán thoả mãn nguyên lý tối ưu Bellman: mọi dãy con của một dãy tối ưu cũng phải là dãy tối ưu.

Thông thường hàm mục tiêu của bài toán được xây dựng từ một hàm có dạng: f(n) = max(f(k)+g(n)), trong đó k là một số giá trị phù hợp nhỏ hơn n.

Hàm f(n) được gọi là hàm quy hoạch động. Việc tính giá trị hàm f được hiện từ dưới lên, tức là các giá trị n nhỏ được tính trước. Tất cả các kết quả được lưu vào bảng để phục vụ cho việc tính hàm quy hoạch động với các giá trị n lớn hơn.

Chúng ta sẽ xem xét một số bài toán quy hoạch động tiêu biểu để minh hoạ cho các tư tưởng trên.

8.3.1. Dãy con đơn điệu dài nhất

Cho dãy a1,a2,..an là dãy n số nguyên. Xoá đi một số phần tử của dãy trên và giữ nguyên trình tự của các phần tử còn lại thì ta được một dãy con của dãy ban đầu. Bài toán yêu cầu là xoá đi một số ít nhất các phần tử để dãy con thu được là dãy đơn điệu (chẳng hạn đơn điệu tăng). Yêu cầu này tương đương với yêu cầu chọn ra một số nhiều nhất các phần tử của dãy để dãy thu được (giữ nguyên thứ tự) là một dãy đơn điệu tăng.

Chẳng hạn dãy con tăng dài nhất của dãy 7 số hạng sau:

1 3 5 4 2 6 7

Là dãy con 1 3 5 6 7 có được từ việc xoá 2 phần tử 4 và 2 đi.

Để giải bài toán này bằng phương pháp quy hoạch động, ta trước hết phải xây dựng hàm quy hoạch động.

Gọi L(i) là độ dài dãy con đơn điệu tăng lớn nhất, có các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai.

Ta có công thức quy hoạch động như sau:

1. L(1) = 1

2. L(i) = max(1, L(j)+1 với mọi j<i và ajai).

Chúng ta giải thích công thức như sau:

L(1)=1 là hiển nhiên.

Nếu ta không ghép ai vào dãy nào thì L(i)=1. Nếu ta ghép ai vào một dãy nào đó thì phải có một phần tử j đứng trước i, thoả mãn ajai. Dãy con dài nhất có phần tử cuối cùng là aj có L(j) phần tử, vậy ghép thêm ai sẽ được dãy con có phần tử cuối cùng là ai và có L(j)+1 phần tử.

Trong tất cả các lựa chọn đó, ta chọn lựa chọn tối ưu nhất để tính L(i). Đó là nguyên nhân vì sao ta có hàm max.

Để cài đặt thuật toán ta dùng cấu trúc dữ liệu là một mảng 1 chiều L, L[i] dùng lưu trữ giá trị tương ứng của L(i). Sự khác biệt giữa phương pháp quy hoạch động và chia để trị từ trên xuống là ở điểm này: các bài toán nhỏ được giải trước, và kết quả được lưu trữ lại để giải các bài toán lớn hơn. Cấu trúc dữ liệu dùng để lưu trữ các kết quả đó gọi là bảng phương án.

procedure Optimize;

var i,j;

begin

L[1] := 1;

for i := 2 to n do begin

L[i] := 1;

for j := 1 to i-1 do

if (a[j] <= a[i]) and (L[i] < L[j] + 1) then

L[i] := L[j] + 1;

end;

end;

Sau khi tính xong hàm quy hoạch động, làm thế nào để tìm lại kết quả? Có 2 phương án. Phương pháp thứ nhất là dựa vào bảng phương án. Phương pháp thứ hai là xây dựng bảng truy vết.

Dựa trên bảng phương án ta sẽ tìm được phần tử có L[i] lớn nhất. Đó chính là phần tử cuối cùng của dãy kết quả. Phần tử đứng ngay trước nó sẽ là phần tử j mà aj<ai và L[i]=L[j]+1. Tìm được phần tử j đó, ta lại tìm được phần tử đứng ngay trước nó bằng phương pháp tương tự. Thủ tục lần vết tìm lại kết quả như sau:

procedure Trace;

begin

i := 1;

for j := 2 to n do

if L[i] < L[j] then i := j;

for k := L[i] downto 1 do begin

kq[k] := i;

for j := 1 to i do

if (a[j]<=a[i]) and (L[i]=L[j]+1) then begin

i := j;

break;

end;

end;

end;

Phương pháp thứ hai là dùng một cấu trúc dữ liệu nữa để truy vết. Ta đặt T[i] là phần tử đứng ngay trước i trong dãy. Chương trình con quy hoạch động được viết lại như sau:

procedure Optimize;

var i,j;

begin

L[1] := 1;

for i := 2 to n do begin

L[i] := 1; T[i] := 0;

for j := 1 to i-1 do

if (a[j] <= a[i]) and (L[i] < L[j] + 1) then begin

L[i] := L[j] + 1;

T[i] := j;

end;

end;

end;

Quá trình truy vết của chúng ta do đó sẽ đơn giản hơn:

procedure Trace;

var i,j;

begin

i := 1;

for j := 2 to n do

if L[i] < L[j] then i := j;

for k := L[i] downto 1 do begin

kq[k] := i; i := T[i];

end;

end;

Dễ dàng chứng minh được thuật toán này có độ phức tạp tính toán O(n2) và chi phí không gian là O(n).

8.3.2. Xâu con chung dài nhất

Cho 2 xâu X,Y. Hãy tìm một xâu S thoả mãn:

1. S có thể nhận được từ X,Y bằng cách xoá đi một số kí tự (tức là S là xâu con của X và của Y).

2. Độ dài của S là lớn nhất.

Trước hết ta xây dựng hàm quy hoạch động:

Gọi L(i,j) là độ dài xâu con chung dài nhất của xâu X(i) gồm i kí tự phần đầu của X (X(i) = [1..i]) và xâu Y(j) gồm j kí tự phần đầu của Y (Y(j) = [1..j]).

Ta có công thức quy hoạch động như sau:

1. L(0,j)=L(i,0)=0.

2. L(i,j) = L(i1,j1)+1 nếu X[i] = Y[j].

3. L(i,j) = max(L(i1,j), L(i,j1)) nếu X[i]  Y[j].

Công thức 1. là hiển nhiên. Công thức 2 và 3 được hiểu như sau: Nếu X[i]=Y[j] thì ta sẽ chọn ngay cặp phần tử đó, đoạn còn lại của 2 xâu là X[1..i1] và Y[1..j1] có xâu con chung dài nhất L(i1,j1) phần tử, vậy X(i) và Y(j) có xâu con chung dài nhất L(i1,j1)+1.

Ngược lại, nếu X[i]  Y[j] thì ta có 2 giải pháp: hoặc bỏ qua X[i] và so X(i-1) với Y(j). Cách đó cho xâu con dài nhất L(i-1,j) phần tử. Ngược lại, ta có thể bỏ qua Y[j] và so X(i) với Y(j-1) để có xâu con dài nhất L(i,j-1) phần tử. Trong 2 cách chọn ta sẽ chọn cách tối ưu hơn.

Bảng phương án của ta sẽ là một bảng 2 chiều L[0..m,0..n], với n,m lần lượt là độ dài của X và Y. Chương trình con tính bảng phương án như sau:

procedure Optimize;

var i,j;

begin

for i := 0 to m do L[i,0] := 0;

for j := 0 to n do L[0,j] := 0;

for i := 1 to m do

for j := 1 to n do

if X[i]=Y[j] then L[i,j] := L[i-1,j-1]+1

else

L[i,j] := max(L[i-1,j],L[i,j-1]]);

end;

Để lần vết tìm nghiệm, ta dựa trên bảng phương án. Xâu con chung lớn nhất của X,Y có độ dài L[m,n]. Dựa vào tương quan giá trị giữa L[i,j], L[i1,j], L[i,j1] và L[i1,j1] ta sẽ biết trong quá trình quy hoạch động ta đã chọn hướng đi nào:

procedure Trace;

begin

i := m; j := n;

repeat

if X[i]=Y[j] then begin

kq[i] := 1;

i:=i-1; j:=j-1;

end

else

if L[i,j]=L[i-1,j] then i:=i-1

else j:=j-1;

until (i=0) or (j=0);

S := '';

for i:=1 t m do

if kq[i]=1 then S:=S+X[i];

end;

Dễ dàng kiểm tra thuật toán quy hoạch động tìm xâu con chung dài nhất có độ phức tạp tính toán là O(n2) và đòi hỏi không gian bộ nhớ cũng là O(n2).

Qua hai ví dụ trên, chắc bạn đọc đã phần nào nhận thấy sự hiệu quả của phương pháp quy hoạch động. Chúng ta sẽ tìm hiểu tiếp một số bài toán nữa để nhận thấy sức mạnh của quy hoạch động so với các phương pháp khác.

8.3.3. Bài toán xếp balô

Trong phần nói về phương pháp vét cạn, chúng tôi đã đề cập đến bài toán xếp balô nhưng chưa trình bày thuật giải. Dụng ý của chúng tôi là muốn giải bài toán đó bằng phương pháp quy hoạch động. Bạn đọc dễ dàng kiểm chứng được, bài toán xếp balô mà giải bằng vét cạn thì sẽ có độ phức tạp tính toán O(2n). Trong khi đó giải bằng quy hoạch động chỉ có độ phức tạp là O(n.m) mà thôi.

Thật vậy, gọi F(i,j) là giá trị lớn nhất thu được khi ta được chọn i đồ vật từ 1 đến i để xếp vào balô có trọng tải j. Dễ thấy là F(0,j) = F(i,0)=0. Nếu i,j>0 thì ta thấy:

- trường hợp thứ nhất: j<wi. Khi đó ta không thể đưa vật i vào balô, và giá trị lớn nhất thu được sẽ là chọn i-1 vật còn lại và trọng tải balô vẫn là j, tức là F(i,j)=F(i-1,j).

- trường hợp thứ hai: j>=wi. Trong tình huống này ta có thể chọn vật i để đưa vào balô hoặc không. Nếu không chọn thì F(i,j)=F(i-1,j) như trường hợp trên. Nếu chọn thì F(i,j)=F(i-1,j-wi) + vi. Công thức này rất dễ hiểu, vì khi ta chọn vật i thì tải trọng của balô còn lại là j-wi, ta còn i-1 vật nữa để chọn nên giá trị lớn nhất thu được là F(i-1,j-wi) + vi. Trong 2 cách đó ta sẽ chọn cách tốt hơn. Vậy F(i,j)=max(F(i-1,j-wi) + vi, F(i-1,j)).

Công thức quy hoạch động có thể tóm tắt lại như sau:

1. F(0,j) = F(i,0)=0

2. F(i,j) = F(i-1,j) nếu j<wi

3. F(i,j)=max(F(i-1,j-wi) + vi, F(i-1,j)) nếu j>=wi.

Chương trình con tính bảng phương án sẽ thực hiện tính các giá trị i,j từ nhỏ đến lớn. Cụ thể như sau:

procedure Optimize;

begin

for i := 0 to n do F[i,0]:=0;

for j := 0 to m do F[0,m]:=0;

for i := 1 to n do begin

for j := 1 to m do

if j<w[i] then F[i,j] := F[i-1,j]

else

F[i,j] := max(F[i-1,j], F[i-1,j-w[i]]+v[i]);

end;

end;

Sau quá trình tính toán, giá trị lớn nhất thu được khi được chọn n đồ vật với balô trọng tải m sẽ là F[n,m]. Quá trình lần vết dựa vào tương quan giữa F[i,j], F[i-1,j] và F[i-1,j-w[i]]+v[i] sẽ xác định được các vật được chọn. Độc giả có thể dễ dàng xây dựng chương trình con truy vết và chứng minh được thuật giải quy hoạch động này có độ phức tạp tính toán là O(n.m). Chi phí bộ nhớ cũng là O(n.m).

Trong phần sau trình bày về những cải tiến đối với quy hoạch động, chúng tôi sẽ trình bày những cách cài đặt các thuật toán trên với chi phí bộ nhớ thấp hơn. Trước khi kết thúc, chúng tôi sẽ trình bày một bài toán quy hoạch động kinh điển nữa, đó là bài toán nhân ma trận.

8.3.4. Bài toán nhân ma trận

Từ cách tính nhân ma trận cho thấy: nhân một ma trận kích thước mn với một ma trận np, số phép nhân phải thực hiện là m.n.p. Mặt khác phép nhân các ma trận có tính kết hợp, tức là:

(A.B).C = A.(B.C)

Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau. Việc lựa chọn trình tự tính sẽ quyết định số phép nhân cần thực hiện.

Ví dụ ta có 4 ma trận: A(13,5), B(5,89), C(89,3), D(3,34) thì ta có một số cách tính A.B.C.D theo các trình tự khác nhau như sau:

1. Tính theo trình tự (((A.B).C).D) thì số phép nhân là 10592.

2. Tính theo trình tự ((A.B).(C.D)) thì số phép nhân là 54201.

3. Tính theo trình tự ((A.(B.C)).D thì số phép nhân là 2856.

4. Tính theo trình tự A.((B.C).D) thì số phép nhân là 4055.

5. Tính theo trình tự A.(B.(C.D)) thì số phép nhân là 26418.

Phép nhân (nhất là các phép nhân số thực) thường có thời gian thực hiện lâu hơn phép cộng, trừ. Do đó người ta đặt ra bài toán:

Cho n ma trận A1,A2...An, ma trận Ai có kích thước là di-1di. Hãy xác định trình tự nhân ma trận A1.A2...An sao cho số phép nhân cần thực hiện là ít nhất.

Nếu dùng phương pháp vét cạn để giải bài toán này thì chúng ta sẽ xét mọi cách đặt các dấu ngoặc khác nhau để tìm số phép nhân của từng cách đặt, từ đó tìm được cách đặt tối ưu. Gọi T(n) là số cách đặt dấu ngoặc với n ma trận thì ta dễ dàng chứng minh được công thức tính T(n) như sau:

Dãy T(n) được gọi là dãy Catalan, bảng sau cho một số phần tử của dãy:

n 1 2 3 4 5 10 15

T(n) 1 1 2 5 14 4862 2674440

Dễ thấy là T(n) tăng rất nhanh theo n. Người ta đã chứng minh được T(n) cỡ 4n/n. Kết luận là giải bằng phương pháp vét cạn thì chỉ giải được với những giá trị n rất bé.

Đáng ngạc nhiên là ta có thể giải bài toán nhân ma trận bằng phương pháp quy hoạch động với độ phức tạp tính toán chỉ là O(n3).

Gọi F(i,j) là số phép nhân để tính tích Ai.Ai+1....Aj thì ta thấy:

Nếu i=j thì chỉ có một ma trận do đó F(i,i)=0.

Nếu j=i+1 thì ta chỉ phải nhân Ai và Ai+1. Ai có kích thước di-1di, Ai+1 có kích thước didi+1, do đó F(i,i+1)=di-1.di.di+1.

Nếu j>i+1 thì ta thấy có thể tính Ai.Ai+1....Aj cách chọn một vị trí k nào đó để đặt ngoặc theo trình tự:

Ai.Ai+1....Aj = (Ai..Ak).(Ak+1..Aj¬¬)

Ma trận kết quả của phép nhân (Ai..Ak) có kích thước di-1dk, ma trận kết quả của phép nhân (Ak+1..Aj¬¬) có kích thước dkdj. Với cách đặt đó ta sẽ mất F(i,k) phép nhân để có kết quả trong dấu ngoặc thứ nhất, mất thêm F(k+1,j) phép nhân để có kết quả trong dấu ngoặc thứ hai, và cuối cùng mất di-1.dk.dj để nhân 2 ma trận kết quả đó. Từ đó tổng số phép nhân của cách đặt đó là:

F(i,k)+F(k+1,j)+di-1.dk.dj

Có nhiều cách chọn k : k=i+1,i+2,...j-1. Ta chọn cách cho phép số phép nhân ít nhất:

F(i,j) = min(F(i,k)+F(k+1,j)+di-1.dk.dj) với mọi k=i+1,i+2,...j-1.

Tóm lại ta có công thức quy hoạch động như sau:

1. F(i,i)=0

2. F(i,i+1)=di-1.di.di+1

3. F(i,j) = min(F(i,k)+F(k+1,j)+di-1.dk.dj, k=i+1,i+2,...j-1)

Đã có công thức quy hoạch động, ta sẽ chọn cấu trúc dữ liệu là một bảng 2 chiều F để lưu F(i,j). Tuy nhiên có một chú ý khi cài đặt là để tính được F(i,j), ta phải tính F(i,k) và F(k+1,j) trước. Như vậy trình tự tính không phải là tính các giá trị F(i,j) với i,j từ nhỏ đến lớn. Ta có nhận xét là trong công thức trên j-i lớn hơn k-i và j-k. Do đó nếu ta tính các phần tử F(x,y) với y-x từ nhỏ đến lớn thì khi tính F(i,j), ta đã có F(i,k) và F(k+1,j).

procedure Optimize;

begin

for i := 1 to n do F[i,i] := 0;

for i := 1 to n-1 do F[i,i+1] := d[i-1]*d[i]*d[i+1];

for m := 2 to n-1 do begin

for i := 1 to n-m do begin

j := i + m; F[i,j] := ;

for k := i+1 to j-1 do

F[i,j] := min(F[i,j], F[i,k]+F[k+1,j]+d[i-1]*d[k]*d[j]);

end;

end;

end;

Kết quả của bài toán là F[1,n]. Để lần vết ta có thể dựa trên bảng phương án hoặc đặt riêng một bảng truy vết: T[i,j] sẽ là chỉ số k mà F[i,j] đạt min. Khi đó ta biết rằng đã đặt cặp dấu ngoặc (Ai...Ak) và (Ak+1...Aj). Ta lại dựa vào T[i,k] và T[k+1,j] để cách đặt dấu ngoặc ở các ma trận bên trong.

8.3.4. Cải tiến phương pháp quy hoạch động

Chúng ta đã nhận thấy sức mạnh và tính hiệu quả của phương pháp quy hoạch động. Tuy nhiên không có phương pháp nào là hoàn hảo. Phương pháp quy hoạch động có một số nhược điểm lớn như sau:

1. Không phải bài toán nào cũng giải được bằng quy hoạch động. Hiện nay người ta vẫn chưa tìm được điều kiện cần và đủ để một bài toán có thể giải được bằng phương pháp quy hoạch động. Do đó để xác định được một bài toán có thể giải được bằng quy hoạch động và tìm được công thức quy hoạch động của nó thường là việc rất khó khăn.

2. Nếu bài toán có thể giải được bằng quy hoạch động thì yêu cầu về không gian nhớ cũng khá lớn. Đa số các bài toán đều có đòi hỏi không gian bộ nhớ cỡ O(n2). Nếu môi trường lập trình hạn chế bộ nhớ thì sẽ không thể làm việc được với các dữ liệu lớn, mặc dù phương pháp quy hoạch động có độ phức tạp tính toán không cao.

Nhược điểm 1 nhìn chung là khó giải quyết. Chỉ có cách cố gắng đưa bài toán đang xét về một mô hình nào đó đã được chứng minh là làm được bằng quy hoạch động và đã tìm được công thức quy hoạch động. Chẳng hạn: mô hình dãy con đơn điệu tăng dài nhất, xâu con chung, xếp balô, nhân ma trận...

Nhược điểm 2 thì có thể giải quyết dễ dàng hơn. Chú ý vào công thức quy hoạch động, ta thường thấy F[n] thường chỉ phải tính qua F[n-1]. Do đó ta không cần phải lưu trữ cả bảng phương án mà chỉ cần lưu một số vị trí cần thiết. Nếu bài toán có yêu cầu truy vết tìm nghiệm thì ta có thể dùng bảng truy vết có kích thước thường là nhỏ hơn bảng phương án.

Chẳng hạn ta có kỹ thuật sau giải bài toán xâu con chung dài nhất cho 2 xâu có độ dài cỡ 1000. (Chú ý, xâu trong TP chỉ có độ dài tối đa 255 nên trong trường hợp này ta phải dùng mảng kí tự để lưu trữ 2 xâu).

Nhắc lại công thức quy hoạch động của bài toán:

1. L(0,j)=L(i,0)=0.

2. L(i,j) = L(i1,j1)+1 nếu X[i] = Y[j].

3. L(i,j) = max(L(i1,j), L(i,j1)) nếu X[i]  Y[j].

Như vậy để tính L(i) ta chỉ cần L(i-1). Do đó để tính cả bảng phương án, ta chỉ cần lưu trữ hai dòng của nó: L để lưu L(i) và L1 để lưu L(i-1). Chương trình con quy hoạch động được viết lại như sau:

procedure Optimize;

var i,j;

begin

for j := 0 to n do L1[j] := 0; {L(0,j):=0}

for i := 1 to m do begin

L[0]:=0;

for j := 1 to n do

if X[i]=Y[j] then L[j] := L1[j-1]+1 {L(i,j)=L(i-1,j-1)+1}

else

L[j]:=max(L1[j],L[j-1]]); {L(i,j)=max(L(i1,j), L(i,j1))}

L1 := L;

end;

end;

Nếu chỉ yêu cầu tìm độ dài xâu con chung dài nhất (L[m,n]) thì với cách này ta có thể giải với kích thước m,n=10000 cũng được. Nếu bài toán yêu cầu tìm lại kết quả thì ta phải dùng thêm một bảng truy vết 2 chiều. Khi đó mỗi phần tử của bảng truy vết chỉ cần lưu 1 trong 3 giá trị: T[i,j]=1 nếu L(i,j)=L(i-1,j-1)+1, T[i,j]=2 nếu L(i,j)=L(i-1,j) và T[i,j]=3 nếu L(i,j)=L(i,j-1). Do đó kích thước bảng truy vết nhỏ hơn nhiều so với bảng phương án. (Ta chỉ cần 2 bit cho một phần tử của bảng truy vết nên kích thước bảng truy vết là 1000x1000x2bit=2.000.000 bit, tức là khoảng 250KB. Trong khi đó bảng phương án 2 chiều có kích thước là 1000x1000x2byte=2.000.000 byte, tức là lớn hơn 8 lần).

Chi tiết cài đặt cụ thể, độc giả có thể xem ở phần phụ lục.

Kĩ thuật này có thể áp dụng được bài toán xếp balô.

8.3.5. Phương pháp quy hoạch động với bài toán đếm cấu hình tổ hợp

Bài toán đếm cấu hình tổ hợp đã được đề cập trong phần trình bày về phương pháp vét cạn. Tương tự các bài toán tối ưu tổ hợp, khá nhiều bài toán đếm cấu hình tổ hợp cũng có thể giải một cách tương đối hiệu quả bằng phương pháp quy hoạch động. Chúng ta sẽ xem xét một số bài toán.

a) Bài toán phân tích số

Cho số tự nhiên n. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng các số nguyên dương. Các cách phân tích không xét thứ tự, chẳng hạn 6=1+5=5+1 được coi là một cách. n=0 cũng được coi là 1 cách phân tích.

Để giải bài toán bằng phương pháp quy hoạch động, trước hết ta phải lập được công thức quy hoạch động.

Gọi F(i,j) là số cách phân tích số j thành tổng các số nguyên dương nhỏ hơn hoặc bằng i.

Các cách phân tích chỉ thuộc một trong 2 nhóm:

1. Nhóm thứ nhất không chứa giá trị i. Như vậy, j chỉ được phân tích thành tổng các số nguyên dương nhỏ hơn i và có F(i-1,j) cách như vậy.

2. Nhóm thứ hai có chứa ít nhất 1 giá trị i. Loại bỏ giá trị i này, ta sẽ thấy số cách phân tích j theo kiểu này bằng số cách phân tích j-i thành tổng các số nguyên nhỏ hơn hoặc bằng i, tức là có F(i,j-i) cách. Chú ý rằng điều này chỉ đúng khi ta không xét thứ tự các số hạng trong phân tích. Và j phải lớn hơn hoặc bằng i thì mới phân tích như vậy được.

Tóm lại, ta có công thức quy hoạch động như sau:

1. F(i,0)=1 với mọi i>0.

2. F(i,j)=F(i-1,j) nếu j<i.

3. F(i,j)=F(i-1,j)+F(i,j-i) với j>=i.

Sau khi đã xác định được công thức quy hoạch động, ta dễ dàng xây dựng được thuật toán tính bảng phương án. Về cấu trúc dữ liệu, ta có thể sử dụng một bảng phương án 2 chiều (hoặc áp dụng kĩ thuật cải tiến dựa trên nhận xét: để tính F(i) thì chỉ cần F(i-1)).

Thuật toán tính bảng phương án:

procedure Calculate;

begin

F[0,0]:= 1;

for j := 1 to n do F[i,0] := 0;

for i := 1 to n do begin

for j := 0 to n do

if j<i then F[i,j]:=F[i-1,j]

else F[i,j] := F[i-1,j]+ F[i,j-i];

end;

end;

Đáp số của bài toán là F(n,n).

b) Bài toán dãy số Catalan

Dãy số Catalan bậc n là một dãy số được định nghĩa như sau:

1. Có 2n+1 phần tử nguyên dương. Phần tử đầu tiên và cuối cùng bằng 0.

2. Phần tử sau hơn kém phần tử trước 1.

Chẳng hạn, các dãy số Catalan bậc 3 là:

0 1 0 1 0 1 0

0 1 0 1 2 1 0

0 1 2 1 0 1 0

0 1 2 1 2 1 0

0 1 2 3 2 1 0

Bài toán của chúng ta là tính T(n) số dãy Catalan bậc n. Chẳng hạn T(0)=0, T(1)=1, T(2)=2, T(3)=5...

Bước đầu tiên là thiết lập công thức quy hoạch động:

Gọi F(i,j) là số dãy số kiểu Catalan có i phần tử, phần tử cuối cùng là j. Số dãy Catalan của ta sẽ là F(2n+1,0). Dễ dàng chứng minh được công thức truy hồi sau:

1. F(1,0)=1.

2. F(i,0) = F(i-1,1).

3. F(i,j) = F(i-1,j+1) + F(i-1,j-1) nếu j>=1.

4. Công thức áp dụng với i<=1<=2n+1, 0<=j<=n. Với các giá trị i,j khác F(i,j)=0.

Sau khi đã có công thức thì việc xây dựng thuật toán trở nên dễ dàng hơn:

procedure Calculate;

begin

F[i,j]:=0 với mọi i,j;

F[1,0]:= 1;

for i:=2 to 2*n+1 do begin

F[i,0]:=F[i-1,1];

for j:=1 to n do F[i,j]:=F[i-1,j-1]+F[i-1,j+1];

end;

end;

Qua các bài toán trên, chúng ta có thể nhận xét một cách có cơ sở rằng quy hoạch động là một phương pháp rất hiệu quả để giải các bài toán đếm cấu hình tổ hợp và tối ưu tổ hợp. Tuy nhiên giải một bài toán bằng quy hoạch động thường gặp 2 khó khăn: thứ nhất là tìm công thức quy hoạch động, thứ 2 là lưu trữ bảng phương án.

Cũng qua hai phương pháp vét cạn và quy hoạch động, ta thấy rằng việc giải nhiều bài toán tối ưu thường đòi hỏi chi phí khá lớn về thời gian tính toán và không gian bộ nhớ. Nhưng trong thực tế, nhiều bài toán không nhất thiết phải tìm nghiệm tối ưu. Trong điều kiện thời gian và không gian hạn chế, chúng ta chỉ cần những nghiệm đủ "tốt" là được. Đó chính là tư tưởng của phương pháp tham lam và các thuật toán xấp xỉ.

8.4. Phương pháp tham lam (Gready)

Tìm nghiệm của bài toán tối ưu thường đòi hỏi chi phí lớn về thời gian tính toán và không gian bộ nhớ. Tuy nhiên trong nhiều trường hợp ta chỉ tìm được một nghiệm đủ tốt, khá gần với nghiệm tối ưu là đạt yêu cầu, nhất là khi có hạn chế về mặt thời gian và bộ nhớ.

Phương pháp tham lam xây dựng các thuật toán giải các bài toán tối ưu dựa trên tư tưởng tối ưu cục bộ theo một chiến lược tư duy kiểu con người, nhằm nhanh chóng đạt đến một lời giải "tốt".

Có một số thuật toán dựa trên tư tưởng của phương pháp tham lam thực sự tìm được phương án tối ưu (chẳng hạn thuật toán Kruscal tìm cây khung cực tiểu), còn lại đa số các thuật toán dựa trên phương pháp tham lam thường là thuật toán gần đúng, chỉ cho một lời giải xấp xỉ lời giải tối ưu.

8.4.1. Một số chiến lược tham lam

Phương pháp tham lam tìm nghiệm tối ưu dựa trên các chiến lược tối ưu cục bộ của con người. Trước khi trình bày những thuật giải tham lam cho những bài toán cụ thể, chúng tôi đề cập đến hai chiến lược tối ưu cục bộ cơ bản:

- Chọn cái tốt nhất trước (còn gọi là "chọn miếng ngon trước". Đây là lí do vì sao phương pháp này được gọi là "tham lam" hay "tham ăn").

- Cải tiến cái đang có thành cái tốt hơn.

Chiến lược thứ nhất thường được áp dụng khi xây dựng dần từng thành phần của nghiệm tối ưu. Thuật giải sẽ đánh giá các lựa chọn theo một tiêu chuẩn nào đó và sắp xếp từ nhỏ đến lớn rồi tiến hành chọn theo trình tự đó.

Chiến lược thứ hai thường bắt đầu bằng một hay một vài phương án. Sau đó, bằng một số cách thức nào đó, các phương án được điều chỉnh để có giá trị tốt hơn. Quá trình điều chỉnh sẽ dừng lại khi không điều chỉnh được thêm hoặc sự cải thiện rất nhỏ hoặc hết thời gian cho phép... Phần lớn các thuật toán hiện nay áp dụng cho bộ dữ liệu lớn được thiết kế theo chiến lược này: chẳng hạn tìm kiếm leo đồi, giải thuật di truyền... Độc giả có thể tham khảo trong những tài liệu khác.

Chúng ta sẽ đi vào một số bài toán cụ thể và vận dụng những chiến lược trên để thiết kế các thuật giải tham lam.

8.4.2. Bài toán xếp balô

Giải thuật tham lam giải bài toán xếp balô dựa trên chiến lược "chọn cái tốt nhất trước". Việc chọn các vật đưa vào balô có thể theo 3 chiến lược như sau:

- Ưu tiên vật nhẹ trước (với hi vọng chọn được nhiều đồ vật).

- Ưu tiên vật có giá trị cao trước.

- Ưu tiên chọn những vật có tỉ số giá trị/trọng lượng lớn trước.

Ta thấy chiến lược thứ 3 tổng quát hơn nhất. Do vậy việc tìm nghiệm của chúng ta sẽ tiến hành theo 2 bước:

1. Sắp xếp các đồ vật giảm dần theo tỉ lệ: giá trị/trọng lượng.

2. Lần lượt đưa vào balô những đồ vật nào có thể đưa được theo trình tự đã sắp xếp đó.

Thuật giải chi tiết như sau:

procedure Gready;

begin

for i := 1 to n do begin a[i]:=v[i]/w[i];id[i] := i; end;

sắp xếp w,v,a,id theo a;

for i:=1 to n do begin

if m >= w[i] then begin

m := m - w[i];

t := t + v[i];

s := s + [id[i]];

end;

end;

end;

Kết quả: S là tập các đồ vật được chọn, T là tổng giá trị của chúng. Thuật giải này có độ phức tạp O(nlogn) do thao tác chủ yếu ở phần sắp xếp.

8.4.3. Bài toán người du lịch

Có nhiều giải thuật tham lam khác nhau giải bài toán này. Chúng tôi xin trình bày một giải thuật theo chiến lược chọn cái tốt trước và một giải thuật theo chiến lược cải tiến cái hiện có.

Giải thuật theo chiến lược chọn cái tốt nhất trước có ý tưởng rất đơn giản: tại mỗi bước ta sẽ chọn thành phố tiếp theo là thành phố chưa đến thăm mà chi phí từ thành phố hiện tại đến thành phố đó là thấp nhất.

Giải thuật theo chiến lược cải tiến cái hiện có cũng có ý tưởng rất đơn giản: xuất phát từ một lộ trình nào đó (1,2,..n chẳng hạn), ta cải tiến lộ trình hiện có bằng cách tìm 2 thành phố mà đổi chỗ chúng cho nhau thì tổng chi phí giảm đi. Quá trình đó dừng lại khi không còn cải tiến được hơn nữa.

Dựa trên 2 ý tưởng đó, bạn đọc có thể dễ dàng xây dựng được các thuật giải. Thuật giải thứ nhất có độ phức tạp tính toán là O(n2), thuật giải thứ hai có độ phức tạp tính toán là O(n3).

Ngoài 2 giải thuật trên, người ta còn xây dựng được giải thuật di truyền cho bài toán này. ý tưởng cơ bản là thay vì xuất phát từ một phương án, chúng ta xử lí nhiều phương án đồng thời, cải tiến chúng bằng việc mô phỏng quá trình di truyền, thích nghi và tiến hoá của sinh vật để có được những phương án ngày một tốt hơn. Tuy nhiên vấn đề đó nằm ngoài khuôn khổ của cuốn giáo trình này.

Đối với đồ thị metric (tức là có bất đẳng thức tam giác d[i,j]<=d[i,k]+d[k,j] với mọi i,j,k) người ta còn tìm được thuật giải tham lam cho nghiệm có tổng chi phí <=2 tổng chi phí của nghiệm tối ưu. Thuật giải tiến hành cũng theo 2 bước:

1. Tìm cây khung cực tiểu của đồ thị.

2. Duyệt cây khung theo chiều sâu.

3. Xây dựng lộ trình là thứ tự duyệt của các đỉnh, loại bỏ các đỉnh trùng nhau.

8.4.4. Bài toán đóng thùng (Bin-Packing)

Cho N đồ vật, mỗi đồ vật có trọng lượng là ai. Có rất nhiều thùng giống nhau và mỗi thùng chỉ có khả năng chứa được các đồ vật có tổng khối lượng không quá M (tất nhiên ai<=M) . Hãy xếp các đồ vật vào các thùng sao cho số thùng sử dụng là ít nhất.

Bài toán đóng thùng cũng là một bài toán NPC, tức là chưa có thuật giải đa thức. Thuật giải tham lam của bài toán này dựa trên ý tưởng:

1. Sắp xếp các đồ vật theo thứ tự trọng lượng giảm dần.

2. Lần lượt đưa các đồ vật vào các thùng bằng cách tìm thùng đầu tiên vẫn còn đủ để chứa vật ấy. Nếu không có thì thêm một thùng mới để chứa vật ấy.

procedure Gready;

begin

for i:=1 to n do id[i] := i;;

sxep a,id on a;

k:=0;

for i:=1 to n do begin

for j := 1 to k+1 do

if t[j]+a[i]<=M then break; {tìm thùng j đầu tiên}

if j=k+1 then k:=k+1; {k thùng đầu tiên không thể chứa được => dùng thùng mới}

t[j] := t[j] + a[i];

s[j] := s[j] + [id[i]];

end;

end;

ý nghĩa của các cấu trúc dữ liệu như sau: id[i] là chỉ số ban đầu đồ vật i sau khi sắp xếp, k là số thùng cần dùng, t[j] là tổng trọng lượng các vật đang có trong thùng j, s[j] là tập hợp các vật được đưa vào thùng j.

Độ phức tạp tính toán của thuật toán là O(n2).

Johnson đã chứng minh được thuật giải này cho nghiệm x thoả mãn:

f(x) xấp xỉ 11*f(x0)/9+4 với x0 là nghiệm tối ưu.

Trước khi kết thúc trình bày về phương pháp tham lam, chúng tôi đề cập đến thuật toán Kruscal, một thuật toán tham lam thực sự tối ưu.

8.4.5. Thuật toán Kruscal

Thuật toán Kruscal giải bài toán tìm cây khung cực tiểu của đồ thị vô hướng có trọng số. Bài toán cây khung cực tiểu đã được trình bày ở chương Đồ thị. Nói một cách đơn giản, cây khung cực tiểu của một đồ thị N đỉnh là một đồ thị con N đỉnh, N-1 cạnh, liên thông và có tổng trọng số các cạnh là nhỏ nhất.

Lý thuyết đồ thị đã chứng minh một đồ thị liên thông không có chu trình sẽ là một cây.

Tư tưởng tham lam trong thuật toán Kruscal là "chọn cái tốt nhất trước". Chúng ta sẽ tiến hành chọn N-1 cạnh ưu tiên các cạnh có trọng số nhỏ trước sao cho khi chọn cạnh được chọn phải không tạo thành chu trình với các cạnh đã chọn.

Như vậy thuật toán sẽ tiến hành qua 2 bước: sắp xếp và chọn. Để kiểm tra một cạnh khi được chọn có tạo thành chu trình hay không, ta sẽ lưu trữ các đỉnh vào các cây con. Nếu hai đỉnh đầu mút của một cạnh mà cùng thuộc một cây thì thêm cạnh đó sẽ tạo thành chu trình. Đồng thời, khi thêm một cạnh ta cũng hợp nhất 2 cây của 2 đỉnh tương ứng.

Về cấu trúc dữ liệu: ta biểu diễn đồ thị bằng danh sách cạnh, gồm các bộ ba (u,v,d) với ý nghĩa trọng số cạnh (u,v) là d. Để biểu diễn các cây con ta dùng mảng T, trong đó T[u] là đỉnh cha của đỉnh u trong cây. Nếu T[u] bằng 0 thì u là đỉnh gốc. Hai đỉnh cùng thuộc một cây nếu chúng cùng đỉnh gốc.

Thuật toán chi tiết như sau:

procedure Kruscal;

begin

sắp xếp u,v,d tăng dần theo d; {sắp xếp danh sách cạnh tăng dần}

for i := 1 to m do begin

x := Root(u[i]); y := Root(v[i]); {tìm gốc của mỗi đỉnh }

if x <> y then begin {thuộc 2 cây khác nhau }

k := k + 1;

s := s + [i]; {chọn cạnh i}

T[y] := x; {hợp nhất 2 cây}

if k=n-1 then exit; {chọn đủ n-1 cạnh thì xong}

end;

end;

end;

function Root(u); {tìm gốc của đỉnh u, là đỉnh có T = 0}

begin

while T[u] <> 0 do u := T[u];

Root := u;

end;

Kết quả ta được s là danh sách các cạnh được chọn. Dễ dàng chứng minh được độ phức tạp của thuật toán là O(mlogm), chủ yếu là ở thời gian sắp xếp các cạnh.

Qua các thuật giải tham lam đã trình bài, chúng ta có thể kết luận:

1. Phương pháp tham lam có độ phức tạp tính toán thấp, thường nhanh chóng tìm được lời giải .

2. Lời giải của phương pháp tham lam thường chỉ là một lời giải tốt chứ không phải lời giải tối ưu.

8.5. kết luận

Trong chương này chúng ta đã tìm hiểu về bốn phương pháp thiết kế thuật toán phổ biến: chia để trị, vét cạn, quy hoạch động và tham lam. Chúng ta cũng vận dụng chúng, đặc biệt là 3 phương pháp sau để giải các bài toán tối ưu.

Mỗi phương pháp có những ưu điểm và nhược điểm riêng. Phương pháp vét cạn có ưu điểm là đơn giản và chắc chắn tìm được lời giải tối ưu. Bù lại nhược điểm của nó là độ phức tạp quá lớn. Phương pháp quy hoạch động có độ phức tập không lớn, cũng chắc chắn tìm được lời giải tối ưu nhưng lại đòi hỏi lượng bộ nhớ rất lớn, nhiều khi vượt quá mức đáp ứng của hệ thống. Phương pháp tham lam thì nhanh chóng, đơn giản và không đòi hỏi nhiều bộ nhớ, nhưng lại không chắc chắn tìm được lời giải tối ưu.

Do mỗi phương pháp đều có ưu, nhược điểm riêng nên tuỳ vào yêu cầu của bài toán và khả năng cho phép mà ta có thể lựa chọn hay phối hợp các phương pháp khác nhau để tìm kiếm lời giải tốt nhất. Chẳng hạn nếu bộ nhớ hạn hẹp thì ta có thể dùng vét cạn với bộ dữ liệu nhỏ và tham lam với bộ dữ liệu lớn, hoặc dùng phương pháp tham lam để xác định một số cận cho vét cạn. Còn nếu bộ nhớ rộng rãi hơn thì có thể phối hợp quy hoạch động và tham lam.