Tài liệu MỘT SỐ ĐỊNH HƯỚNG CHO VIỆC ĐỊNH NGHĨA BÀI TOÁN CON VÀ XÁC ĐỊNH CẤU TRÚC CON TỐI ƯU TRONG QUÁ TRÌNH GIẢI CÁC BÀI TOÁN BẰNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG.DOC

MỘT SỐ ĐỊNH HƯỚNG CHO VIỆC ĐỊNH NGHĨA BÀI TOÁN CON VÀ XÁC ĐỊNH CẤU TRÚC CON TỐI ƯU TRONG QUÁ TRÌNH GIẢI CÁC BÀI TOÁN BẰNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG Nguyễn Văn Minh Trường PTTH Chuyên Lê Quý Đôn - Quảng Trị. Làm sao cho học sinh PTTH có thể tiếp cận được lời giải của bài toán cùng với kỹ thuật lập trình đặc trưng của phương pháp quy hoạch động là trăn trở của rất nhiều giáo viên trong quá trình giảng dạy phương pháp này. Tìm ra các bài toán con phù hợp cho một bài toán khi giải là một công việc phụ thuộc rất nhiều kinh nghiệm và sự sáng tạo của người giải. Tuy nhiên, cũng có một số định nghĩa lặp lại trong các bài toán quy hoạch động. Bài viết đề cập đến bốn định hướng cho việc định nghĩa bài toán con và xác định cấu trúc con tối ưu trên các định nghĩa đó. I. MỞ ĐẦU. Phương pháp quy hoạch động thường dùng để giải các bài toán tối ưu có bản chất đệ quy, tức là việc tìm lời giải tối ưu cho bài toán đó có thể đưa về việc tìm lời giải tối ưu của một số hữu hạn các bài toán con. Thông thường khi giải một bài toán bằng phương pháp quy hoạch động chúng ta cần thực hiện 4 bước sau: 1. Xác định cấu trúc của một lời giải tối ưu.  Tìm cách chia bài toán thành các bài toán con.  Xác định cấu trúc con tối ưu, tức là lời giải tối ưu của các bài toán con sẽ đem lại lời giải tối ưu cho bài toán ban đầu. 2. Định nghĩa đệ quy cho giá trị của một lời giải tối ưu dựa trên giá trị có được từ các bài toán con. 3. Tính giá trị của một lời giải tối ưu từ dưới lên.  Tính giá trị của một lời giải tối ưu, xuất phát từ bài toán con nhỏ nhất và lưu các giá trị đó lại theo một cách nào đó.  Ở bước sau sẽ dùng các giá trị đã lưu từ các bước trước. 4. Xây dựng lời giải tối ưu từ các thông tin đã được lưu lại. Bài viết xin phép trao đổi một số vấn đề liên quan đến bước 1 và 2 nêu trên, đó cũng là các bước quyết định cho việc giải hoàn chỉnh một bài toán quy hoạch động. Có nhiều định hướng khác nhau cho việc định nghĩa các bài toán con, từ đó cho phép chúng ta xác định cấu trúc con tối ưu của bài toán. Bốn định hướng sau cho phép chúng ta tiếp cận 4 lớp bài toán phổ biến có thể giải bằng phương pháp quy hoạch động. II. ĐỊNH NGHĨA CÁC BÀI TOÁN CON VÀ XÁC ĐỊNH CẤU TRÚC CON TỐI ƯU. II. 1. Dạng tiền tố (hậu tố). Định nghĩa bài toán con. Bài toán ở dạng này với đầu vào (input) thường là một dãy gồm n thành phần x1, x2, …, xn. Khi đó việc phân chia bài toán thành các bài toán con ở dạng tiền tố là: x1, x2, …, xi, với i ≤ n. Các bài toán con ở dạng hậu tố là: xi, x2, …, xn, với i ≥ 1. Khi phân chia bài toán ban đầu thành các bài toán con ở dạng tiền tố ta có mô hình như sau: Hình 1: Mô hình dạng tiền tố. Cấu trúc con tối ưu: Trường hợp 1: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc một số bài toán con được xác định (không cần phải tìm kiếm). Cấu trúc đệ quy dạng này hoặc nhị phân, hoặc tam phân, … Bài toán 1: Cho dãy số nguyên dương a1, a2, …an. Hãy chọn một số số hạng của dãy nhưng không được chọn 3 số hạng liền nhau, sao cho tổng giá trị các số hạng được chọn là lớn nhất. Ví dụ: A = (6, 10, 13, 9, 8, 1), có thể chọn (6, 13, 9, 1) cách chọn này có tổng giá trị 29, có thể chọn (6, 10, 9, 8) cách chọn này có tổng giá trị là 33 là cách chọn có tổng giá trị lớn nhất. 1. Bài toán con thứ i gồm các thành phần tứ 1 đến i. Có thể phát biểu lại bài toán như sau: Hãy chọn trong các số hạng từ 1 đến i, nhưng không được chọn 3 số hạng liền nhau, sao cho tổng giá trị các số hạng được chọn là lớn nhất. Bài toán con thứ n là bài toán ban đầu. 2. Với cách chia đó ta có: + Với bài toán con 1, chỉ có 1 món quà nên tổng giá trị thu được là a1, giá trị tối ưu cho bài toán này là a1. + Với bài toán con 2 cũng vậy, chỉ có 2 món quà nên tổng giá trị thu được là a1+a2, giá trị tối ưu cho bài toán này là a1+a2. + Với bài toán con 3 thì sẽ có các cách chọn thỏa mãn yêu cầu của bài toán: (a1, a2), (a1, a3), (a2, a3) với tổng giá trị lần lượt là: a1+a2, a1+a3, a2+a3. Từ đó giá trị tối ưu cho bài toán này là giá trị lớn nhất trong 3 cách chọn: max{a1+a2, a1+a3, a2+a3} + Với bài toán con 4 ta có các cách chọn: (a1, a2), (a1, a3), (a1, a4), (a2, a3), (a2, a4), (a3, a4), (a1, a2, a4), (a1, a3, a4). Từ đó giá trị tối ưu cho bài toán này là: max{a1+a2, a1+a3, a1+a4, a2+a3, a2+a4, a3+a4, a1+a2+a4, a1+a3+a4} = max{max{a1+a2, a1+a3, a2+a3}, max{a1+a4, a2+a4, a1+a2+a4}, max{a1+a3+a4, a3+a4}}. = max{max{a1+a2, a1+a3, a2+a3}, (a1+a2)+a4, (a1)+a3+a4}. BT con 3 BT con 2 BT con 1 (Do a1, a2, a3, a4 nguyên dương nên: max{a1+a4, a2+a4, a1+a2+a4} = a1+a2+a4 và max{a1+a3+a4, a3+a4} = a1+a3+a4) -2- Có thể thấy lời giải tối ưu của bài toán con thứ tư phụ thuộc lời giải tối ưu của các bài toán con 1, 2 và 3. Hay bài toán có cấu trúc con tối ưu: lời giải tối ưu của 3 bài toán con thứ i-1, i-2 và i-3 sẽ cho lời giải tối ưu cho bài toán con thứ i, lời giải tối ưu của 3 bài toán con thứ n-1, n-2 và n-3 sẽ cho lời giải tối ưu cho bài toán con thứ n – bài toán ban đầu. Gọi f(i) là giá trị tối ưu của bài toán con thứ i, là tổng giá trị lớn nhất có thể chọn được trong các món quà từ món quà thứ nhất đến món quà thứ i. Ta có: f(1)=a1. f(2)=a1+a2. f(3)=max{a1+a2, a1+a3, a2+a3} f(4)=max{max{a1+a2, a1+a3, a2+a3}, (a1+a2+a4), (a1)+a3+a4} =max{f(3), f(2)+a4, f(1))+a3+a4}. … f(i)=max{f(i-1), f(i-2)+ai, f(i-3)+ai-1+ai}. Từ đó ta có công thức: Gọi mãng a[1..N] lưu dãy đầu vào (input). Ta có đoạn chương trình đệ quy tính giá trị tối ưu f(n) cho bài toán. function f(i : longint) : longint; begin if i = 1 then f ≔ a[1] else if i = 2 then f ≔ a[1] + a[2] else if i = 3 then f ≔ max(a[1] + a[2], a[1] + a[3], a[2] + a[3]) else f := max(f(i - 1), f(i - 2) + a[i], f(i - 3) + a[i - 1] + a[i]); end; BEGIN … write(f(n)); … END. Trường hợp 2: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc một số bài toán con được chưa được xác định (cần phải tìm kiếm). Cấu trúc đệ quy của bài toán thường ở dạng tuyến tính. Bài toán 2: Dãy con đơn điệu tăng dài nhất. Cho dãy số nguyên A, a1, a2, …, an. Một dãy con của dãy A là dãy thu được bằng cách chọn ra từ A một số phần tử và giữ nguyên thứ tự của chúng. Hãy tìm dãy con đơn điệu tăng của A có độ dài lớn nhất bắt đầu từ a1. Ví dụ: với A = (5, 2, 8, 6, 3, 6, 9, 7) thì (2, 3, 6, 9) là một dãy con đơn điệu tăng dài nhất của A. 1. Bài toán con thứ i gồm các phần tử từ 1 đến i của dãy A. Có thể phát biểu lại bài toán như sau: Hãy tìm dãy con đơn điệu dài nhất của dãy gồm các phần tử từ 1 đến i. Bài toán con thứ n là bài toán ban đầu. 2. Với cách phân chia đó ta có: -3- + Với bài toán con thứ nhất, bởi chỉ có 1 phần tử a1 nên nó là dãy đơn điệu tăng độ dài (lớn nhất) là 1. + Khi xét bài toán con thứ i, ta cần xem phần tử aj của các bài toán con j từ 1 đến i-1 xem chúng có thỏa mãn aj < ai không? Điều này đảm bảo cho ta có thể ghép thêm ai vào cuối các dãy con đơn điệu tăng kết thúc tại j của bài toán con j. Trong trường hợp có nhiều dãy con (của các bài toán con) như vậy chúng ta chọn dãy con nào là dài nhất nhằm bảo đảm tính dài nhất của bài toán. Đó cũng chính là cấu trúc con tối ưu của bài toán: lời giải tối ưu của bài toán con thứ i phụ thuộc vào lời giải tối ưu của các bài toán con trong số các bài toán con từ bài toán con j (1 ≤ j ≤ i - 1) mà aj < ai. Từ phân tích trên, nếu gọi f(i) là giá trị tối ưu của bài toán con thứ i, tức là độ dài của dãy con đơn điệu tăng có được từ dãy gồm các phần tử từ a1 đến ai thì: f(i) = max{f(j)+1| 1 ≤ j < i và aj < ai}. Từ đó ta có công thức sau: Gọi mãng a[1..N] lưu dãy đầu vào, để đơn giản và thấy rõ hơn cấu trúc con tối ưu của bài ta thiết kế chương trình con đệ quy chỉ tính giá trị tối ưu của bài toán con thứ i: f(i). Việc cập nhật giá trị tối ưu cho bài toán ban đầu: max{f(i)|i = 1, 2, …, N} được thực hiện tách rời. function f(i : longint) : longint; var j, tmp : longint; begin if i = 1 then f ≔ 1 else begin tmp ≔ 1 for j := 1 to i – 1 do if a[j] < a[i] then tmp := max(tmp, f(j) + 1); f ≔ tmp; end; end; BEGIN … MaxLenSeq ≔ 0; for i ≔ 1 to N do begin tmp ≔ f(i); if MaxLenSeq < tmp then MaxLenSeq ≔ tmp; end; write(MaxLenSeq); … END. II. 2. Dạng hai hay nhiều tiền tố (hậu tố). Bài toán ở dạng này với đầu vào (input) thường là hai hay nhiều dãy số thành phần của mỗi dãy có thể khác nhau. Ta xét 2 dãy sau X = x1, x2, …, xn và Y = y1, y2, …, ym khi đó mỗi bài toán con của dạng này là 2 tiền tố của X và Y x1, x2, …, xi, với i ≤ n và y1, y2, …, yj, với j ≤ m. Khi phân chia bài toán ban đầu thành các bài toán con ở dạng tiền tố ta có mô hình như sau: -4- Hình 2: Mô hình bài toán con Cấu trúc con tối ưu: tương ứng với quan hệ giữa 2 tiền tố. Thông thường là một số bài toán con xác định. Bài toán 3: Dãy con chung dài nhất (LCS). Cho X = x1, x2, …, xm và Y = y1, y2, …, yn . Hãy tìm dãy con chung Z của X và Y. Ví dụ: 1. Bài toán con (i, j) là các tiền tố x1, x2, …, xi, với i ≤ m và y1, y2, …, yj, với j ≤ n của 2 dãy X và Y. Có thể phát biểu lại bài toán như sau: Hãy tìm dãy con chung dài nhất của 2 dãy x1, x2, …, xi và y1, y2, …, yj. 2. Với cách chia đó ta có. + Với bài toán con (1, 1) nếu x1 = y1 thì độ dài dãy Z là 1, ngược lại là 0. + Với bài toán con (i, j) thì: - nếu x1 = y1 thì độ dài dãy Z sẽ là độ dài dãy con chung dài nhất thu được từ bài toán con (i – 1, j - 1) thêm một phần tử chung nữa. - nếu x1 ≠ y1 thì độ dài dãy Z, hoặc là độ dài dãy con chung dài nhất thu được từ bài toán con (i – 1, j) hoặc là từ bài toán con (i, j - 1), dãy nào dài hơn thì chọn. Gọi f(i, j) là giá trị tối ưu của bài toán con (i, j), ta có công thức sau: -5- Gọi x[1..m], y[1..n] là 2 dãy đầu vào, đoạn chương trình đệ quy sau thực hiện tìm độ dài dãy con chung dài nhất của x và y. function f(i, j : longint) : longint; begin if (i = 0) or (j = 0) then f ≔ 0 else if x[i] = y[j] then f ≔ f(i – 1, j – 1) + 1 else f := max(f(i, j - 1), f(i - 1, j)); end; BEGIN … writeln(f(m, n)); … END. Bài toán 4: Bài toán đổi tiền. Cho tập D gồm n loại tiền có mệnh giá d1, d2, …, dn, tìm cách đổi S đồng gồm các loại tiền trên sao cho số tờ tiền cần đổi là ít nhất. Nghĩa là tìm tập K = (k1, k2, …, kn (ki ≥ 0 với mọi i) sao cho k1d1 + k2d2 + … + kndn = S và tổng k1 + k2 + … + kn nhỏ nhất. Biết số loại tiền không hạn chế. Ví dụ: D = (1, 2, 4), S = 35 khi đó K = (1, 1, 8). Tổng số tờ tiền cần đổi là 10 tờ. 1. Xem X là tập D và Y tập gồm tất cả các số từ 1 đến S. Bài toán con (i, j) là các tiền tố d1, d2, …, di, với i ≤ n và 0, 1, 2, …, j, với j ≤ S. Có thể phát biểu lại bài toán như sau: Tìm cách đổi j đồng gồm các loại tiền d1, d2, …, di sao cho số tờ tiền cần đổi là ít nhất. Bài toán con (n, S) là bài toán ban đầu. 2. Với bài toán con (i, j): + các bài toán con (i, 0) có giá trị tối ưu là 0 với mọi i. + các bài toán con (1, j) mà j < d1 bởi không thể đổi nên giá trị tối ưu của bài toán con này ta quy ước là . + các bài toán con (1, j) mà j > d1 thì ta có thể đổi và giá trị tối ưu của bài toán con này tương ứng sẽ là giá trị tối ưu của bài toán con (1, j – d1) + 1. + các bài toán con (i, j) mà j < di với mọi i = 2, 3, …, n; rõ ràng là không đổi được khi đó giá trị tối ưu của (i, j) sẽ là giá trị tối ưu của bài toán con (i – 1, j). + trường hợp còn lại là ta có thể đổi, tuy nhiên ta có thể chọn việc đổi hay không. - nếu không dùng tờ tiền loại i để đổi thì giá trị tối ưu của (i, j) sẽ bằng giá trị tối ưu của bài toán con (i – 1, j). - còn nếu dùng ít nhất một tờ loại i để đổi thì số tiền còn lại cần đổi là j – di hay giá trị tối ưu của (i, j) sẽ bằng giá trị tối ưu (số tờ tiền ít nhất) của bài toán con (i, j – di) thêm một tờ (di). Gọi f(i, j) là giá trị tối ưu của bài toán con (i, j), ta có công thức: Gọi d[1..n] mãng lưu đầu vào, ta có đoạn chương trình đệ quy sau: -6- const inf = maxlongint; function f(i, j:integer): integer; begin if j = 0 then f :=0 else if (i = 1) and (j < d[1]) then f := inf else if i = 1 then f := 1 + f(1, j - d[1]) else if j < d[i] then f := f(i - 1, j) else f := min(f(i-1, j), 1 + f(i, j-d[i])); end; BEGIN … writeln(f(n, S)); … END. II. 3. Dạng dãy con. Định nghĩa bài toán con. Bài toán ở dạng này với đầu vào là một dãy gồm n thành phần x1, x2, …, xn. Khi đó việc phân chia thành các bài toán con ở dạng dãy con là: xi, x2, …, xj, với 1 ≤ i < j ≤ n. Hình 3: Mô hình dạng dãy con. Cấu trúc con tối ưu: Trường hợp 1: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc một số bài toán con được xác định (không cần phải tìm kiếm). Bài toán 5: PalinDrome. Dãy kí tự s được gọi là đối xứng (palindrome) nếu các phần tử cách đều đầu và cuối giống nhau. Cho dãy s tạo bởi n kí tự gồm các chữ cái hoa và thường phân biệt và các chữ số. Một dãy con của s là dãy thu được sau khi bỏ đi một số bất kỳ các ký tự của s và giữ nguyên thứ tự các ký tự còn lại. Hãy tìm độ dài dãy con đối xứng dài nhất của s. Ví dụ: với dãy s gồm 9 kí tự, s = 'baeadbadb' thì sau khi xoá các kí tự thứ 5, 7, 8 và 9 sẽ thu được dãy con đối xứng chiều dài 5 là baeab: baeadbadb  baeab. Có thể có nhiều cách xoá. Tuy nhiên độ dài dãy con đối xứng dài nhất là 5. 1. Do tính đối xứng ta chọn cách chia theo dạng dãy con. Với cách chia như vậy, bài toán con (i, j) gồm các ký tự si, si+1, …, sj. Gọi f(i, j) là giá trị tối ưu của bài toán con này – độ dài của dãy con đối xứng dài nhất có thể trích ra từ dãy con si, si+1, …, sj. Lời giải của bài toán ban đầu (1, n) là f(1, n). 2. Xét bài toán con (i, j). Ta có: 1. Nếu i > j, chỉ số đầu trái lớn hơn chỉ số đầu phải, ta quy ước đặt f(i, j)=0. 2. Nếu i = j thì f(i, i) = 1, dãy khảo sát chỉ chứa đúng 1 kí tự nên nó là đối xứng. 3. Nếu i < j và si = sj thì f(i, j) = f(i + 1, j – 1) + 2. Vì hai kí tự đầu và cuối dãy si..sj giống nhau nên chỉ cần xác định chiều dài của dãy con đối xứng dài nhất trong -7- đoạn giữa là si+1.. sj–1 (bài toán con (i + 1, j – 1)) rồi cộng thêm 2 đơn vị ứng với hai kí tự đầu và cuối dãy. Hình 4. Hình 4: Trường hợp si = sj. 4. Nếu i < j và si  sj, tức là hai kí tự đầu và cuối của dãy con si..sj là khác nhau thì ta khảo sát hai dãy con là si..sj–1 (bài toán con (i, j – 1)) và si+1..sj (bài toán con (i+1, j)) để lấy chiều dài của dãy con đối xứng dài nhất trong hai dãy này làm kết quả, hình 5: f(i, j) = max{f(i, j-1),f(i+1, j)} Hình 5: Trường hợp si ≠ sj. Vậy lời giải tối ưu của bài toán con (i, j) phụ thuộc vào sự tối ưu của các bài toán con (i+1, j-1), (i, j-1) và (i+1, j). Lời giải tối ưu của bài toán ban đầu (1, n) phụ thuộc vào sự tối ưu của các bài toán con (2, n-1), (1, n-1) và (2, n). Ta có công thức sau: Ta có chương trình con đệ quy sau: function f(i, j : longint) : longint; begin if i > j then f ≔ 0 else if i = j then f ≔ 1 else if s[i] = s[j] then f ≔ f(i + 1, j - 1) + 2 else f := max(f(i, j - 1), f(i + 1, j); end; BEGIN … write(f(1, n)); … END. Trường hợp 2: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc một số bài toán con được chưa được xác định (cần phải tìm kiếm). Bài toán 6: Stones. Có N đống sỏi xếp thành 1 hàng, đống thứ i có ai viên sỏi. Ta có thể ghép hai đống kề nhau thành một đống và mất một chi phí bằng tổng hai đống sỏi đó. Hãy tìm cách ghép N đống sỏi này thành một đống với chi phí nhỏ nhất. -8- Ví dụ có 5 đống sỏi: n = 5, ai = (4, 1, 2, 7, 5). Hình 7: Cách ghép 2. Hình 6: Cách ghép 1. Với cách ghép như hình 6, tổng chi phí 41. Hình 7, tổng chi phí 43. Bài toán là sự đặt dấu ưu tiên phép toán vào giữa các cặp toán hạng và việc thực hiện các phép toán trong dấu ưu tiên có chi phí tương ứng với giá trị của phép toán vừa thực hiện (bài toán nhân ma trận). Như ví dụ hình 6 là cách đặt sau: ((4+(1+2))+(7+5)), hình 7 là (((4+1)+2)+(7+5)). Nếu tìm tất cả các cách đặt móc sẽ có 4n cách đặt móc (số Catalan thứ n). Một cách tiếp cận khác là ta sẽ chia bài toán bởi các điểm chia i dạng: (a1, a2, …, ai)(ai+1, ai+2, …, an) với 1 ≤ i ≤ n. Khi đó để tối ưu bài toán (a1, a2, …, an) ta cần tối ưu các bài toán (a1, a2, …, ai) và (ai+1, ai+2, …, an). Dễ thấy với điểm chia i ta sẽ có các bài toán con tương ứng (cùng kiểu). Nếu bài toán chỉ gồm một đống, chi phí là 0. Nếu bài toán có 2 đống ta cũng có ngay kết quả. Nếu bài toán có 3 đống thì ta có thể dựa trên bài toán 2 đống và 1 đống để tìm kết quả, tiếp tục quá trình như vậy cho đến khi có N đống. Bằng cách dùng điểm chia ta có thể liệt kê tất cả các cách ghép: (a1)( a2, …, an), (a1, a2)(a3, a4, …, an), (a1, a2, a3)(a4, a5, …, an), …, (a1, a2, …, ai-1)(an) và tìm cách tối ưu chúng. 1. Do tính đối xứng của phép đặt móc nên ta chia bài toán theo mô hình trên, bài toán con (i, j) gồm các đống sỏi ai, ai+1, …, aj. Bài toán (1, N) là bài toán ban đầu. 2. Với cách chia bài toán con như vậy ta thấy: lời giải tối ưu cho bài toán (i, j) là tìm cách ghép các đống sỏi từ đống thứ i tới đống thứ j với tổng chi phí nhỏ nhất.  Với mọi cách ghép thì phép ghép cuối cùng luôn có chi phí là ai, ai+1, …, aj.  Với điểm chia k (i ≤ k ≤ j), lời giải tối ưu của bài toán (i, j) phụ thuộc vào lời giải tối ưu của các bài toán con (i, k) và (k+1, j). Hay nói cách khác là sẽ phụ thuộc vào tất cả các bài toán con được tạo ra từ điểm chia k: k=i k = i+1 … k=j (ai)( ai+1, …, aj) (ai, ai+1)(ai+2, ai+3, …, aj) … (ai, ai+1, …, aj-1)(aj) Gọi f(i, j) là giá trị tối ưu của bài toán con (i, j), tương ứng là tổng chi phí nhỏ nhất để ghép các đống sỏi từ đống i đến đống j thành một đống. Từ đó ta có công thức sau: -9- Gọi sum[i] = a1+a2+…+ai. Khi đó ta có ai, ai+1, …, aj = sum[j]-sum[i-1]. Ta có hàm đệ quy tính giá trị tối ưu của bài toán con (i, j) như sau: function f(i, j : longint) : longint; var k, tmp : longint; begin if i = j then f ≔ 0 else begin tmp ≔ maxlongint; for k ≔ i to j – 1 do tmp := min(tmp, f(i, k) + f(k + 1, j) + (sum[j] – sum[i - 1])); f ≔ tmp; end; end; BEGIN … Sum[0] ≔ 0; for i ≔ 1 to N do sum[i] ≔ sum[i - 1] + a[i]; write(f(1, n)); … END. (Một số bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số cũng có cách tiếp cận dạng này) II. 4. Dạng cây con (rooted subtree). Định nghĩa bài toán con. Bài toán ở dạng này với đầu vào là một cây có gốc r. Khi đó mỗi bài toán con tương ứng là một cây con có gốc u nào đó. Hình 8: Mô hình dạng cây. Cấu trúc con tối ưu: Cấu trúc con tối ưu của mỗi bài toán con phụ thuộc vào số bài toán con tương ứng là số node con của cây con đó. Bài toán 7: Tam giác số. Cho một tam giác số như hình sau: 7 3 8 2 4 8 1 7 5 0 4 2 - 10 - 4 6 5 Tìm một đường đi từ đỉnh đến đáy tam giác sao cho tổng tất cả các số trên đường đi là lớn nhất, mỗi bước đi chỉ có thể đi chéo xuống phía trái hoặc chéo xuống phía phải. Ví dụ: đường đi qua các số in đậm là 7 + 3 + 8 + 7 + 5 = 30. Bài toán có thể mô tả qua mô hình như hình 9, nếu tách các node chung ta sẽ có một cây nhị phân đầy đủ. Bởi bài toán dạng đơn giản nên ta mô tả đầu vào như một bảng, mỗi node tương ứng như một ô của bảng (hình 10). 1 2 3 4 5 1 2 3 4 5 7 3 8 2 4 8 1 0 7 4 4 5 2 6 5 Hình 10: Bảng đầu vào. Hình 9: Cây đầu vào. 1. Với cách chia trên, bài toán con (r, c) tương ứng là tìm cách đi tối ưu để đi từ gốc (r, c) đến một node lá. 2. Rõ ràng từ gốc (r, c) chỉ có thể đi xuống một trong hai node (r+1, c) hoặc (r+1, c+1). Hay nói cách khác sự tối ưu của bài toán con gốc (r, c) phụ thuộc sự tối ưu của các bài toán con gốc (r+1, c) và gốc (r+1, c+1). Gọi f(r, c) là giá trị tối ưu của bài toán con (r, c) và bảng t[1..N, 1..N] lưu bảng đầu vào. Ta có công thức sau: Từ đó ta có đoạn chương trình đệ quy tìm giá trị tối ưu của các bài toán con (r, c) và của bài toán ban đầu. function f(r, c : longint) : longint; begin if r = N then f ≔ t[r, c] else f := max(f(r + 1, c), f(r+1, c + 1)) + t[r, c]); end; BEGIN … write(f(1, 1)); … END. (Các bài toán dạng tìm đường đi từ dòng (cột) 1 đến dòng n và “quy hoạch động trên cây” cũng có cách tiếp cận dạng này) - 11 - III. KẾT LUẬN. Những mô hình phân tích vừa trình bày chỉ mang tính chất định hướng cho quá trình giải các bài toán quy hoạch động cơ bản. Định nghĩa bài toán con và xác định cấu trúc con tối ưu chỉ là phần trong quá trình đó. Việc giải hoàn chỉnh một bài toán quy hoạch động còn cần rất nhiều vấn đề khác nữa, chỉ mong giúp một phần cho người giải có một định hướng tiếp cận tốt với lời giải của bài toán. Bài viết là những nhận xét của tôi trong quá trình giảng dạy phương pháp này, rất mong sự trao đổi và chỉ dẫn của các thầy cô giáo, các bạn đồng nghiệp và các em học sinh. Tài liệu tham khảo 1. Tài liệu giáo khoa chuyên Tin – Tập 1, Hồ Sĩ Đàm (chủ biên). 2. Chuyên đề thuật toán – Lê Minh Hoàng. 3. Một số vấn đề chọn lọc trong Tin học – Tập 1, Nguyễn Xuân My (chủ biên). 4. Bài tập Quy hoạch động – Trần Đỗ Hùng (chủ biên). - 12 -