Giải thuật quy hoạch động

CongHiep_87@yahoọcom

Đối với các bạn yêu thích môn lập trình thì có lẽ giải thuật qui hoạch động tương đối quen thuộc trong việc giải quyết các vấn đề tin học. Tuy nhiên, sẽ thật là khó để có thể tìm được cơ cở và công thức cho việc sử dụng qui hoạch động. Chính vì vấn đề này, qui hoach động lại trở thành không phổ biến. Đối với những bài toán như vậy, chúng ta lại cố gắng đi tìm cách giải khác ví dụ như vét cạn hay tham lam....điều đó thật là dở! Chính vì vậy, tôi muốn đưa ra một số bài toán áp dụng qui hoạch động để mong rằng sau bài báo này, các bạn sẽ yêu thích giải thuật này hơn.
Trước hết các bạn phải luôn nhớ rằng, giải thuật qui hoạch động được xuất phát từ nguyên lí Bellman: nếu 1 cấu hình là tối ưu thì mọi cấu hình con của nó cũng là tối ưu. Chính vì vậy để xây dựng 1 cấu hình tối ưu, ta hãy xây dựng dần các cấu hình con sao cho các cấu hình con này cũng phải tối ưu Đây chính là đường lối chủ đạo cho mọi bài toán qui hoạch động. Sau đây là một số bài toán được giải quyết bằng qui hoạch động.
I. Các bài toán
Bài 1: Trước tiên chúng ta hãy xét 1 bài toán thật đơn giản và quen thuộc đó là tìm giá trị lớn nhất trong n số là a₁, a₂, ..., a_n. Giải quyết bài toán này, ta sẽ xây dựng các cấu hình con tối ưu bằng cách lần lượt tìm số lớn nhất trong k số đầu tiên với k chạy từ 1 đến n:
K=1: max1:=a1;
K=2: max2:=max(max1,a2);
K=3: max3:=max(max2,a3);
..............................................
K=n: maxn:=max(maxn-1,an);
Như vậy khi k đạt tới n thì max_n chính là giá trị lớn nhất trong n số đã chọ Việc cài đặt chương trình hết sức đơn giản như sau:
Uses crt;
Var a: array[1..100] of integer;
n,k,max: integer;
Begin
Write('Cho so luong phan tu: ');readln(n);
For i:=1 to n do begin write('a[',i,']= ');readln(a[i]);end;
Max:=a[1];
For k:=2 to n do
If a[k]>max then max:=a[k];
Write('Gia tri lon nhat cua day cac so da cho la: ',max);
Readln
End.
Bây giờ chúng ta xét đến bài toán 2 có phần hấp dẫn hơn. Đây chính là một trong những bài toán điển hình cho giải thuật qui hoạch động:
Bài 2: Bài toán cái túi: Cho n loại đồ vật (1≤n≤100) với một đồ vật loại thứ i (1≤i≤n) có trọng lượng là a[i] và giá trị sử dụng là c[i]. Một nhà thám hiểm cần mang theo một số đồ vật vào túi của mình sao cho tổng trọng lượng các đồ vật đem theo không vượt quá sức chịu đựng của túi là w (1≤w≤250) và tổng giá trị sử dụng từ các đồ vật đem theo là lớn nhất. Hãy tìm một phương án mang cho nhà thám hiểm với giả sử rằng số lượng đồ vật của mỗi loại là luôn đủ dùng.
* Thuật giải bằng qui hoạch động được mô tả như sau:
Ta xây dựng một mảng 2 chiều f với f[i,j] là giá trị sử dụng lớn nhất có được bởi j vật từ 1 đến j mà tổng trọng lượng không vượt quá j.
Khởi tạo : f[i,1]:=0 với i < a[1]
F[i,1]:=c[1]*(i div a[1]) với i > =a[1]; (i = 1..w);
Ta lần lượt cho i đạt tới w và j đạt tới n bằng cách sau:
For j:=2 to n do
For i:=1 to w do
If i >= a[i] then f[i,j]:=Max(f[i-a[j],j]+ c[j],f[i-1,j])
Else f[i,j]:=f[i-1,j].
Như vậy cho đến f[w,n] ta sẽ thu được giá trị lớn nhất có thể đạt được từ n loại đồ vật đã cho sao cho trọng lượng không vượt quá w. Hệ thức toán trên được gọi là hệ thức Dantzig. Có thể rất dễ hiểu được thuật toán như sau:
Phần khởi tạo: f[i,1] có nghĩa là giá trị lớn nhất nếu chỉ có 1 loại vật (ở đây là vật 1) mà trọng lượng không quá ị Như vậy nếu i < a[1] thì rõ ràng không thể mang theo vật nào và giá trị f=0. Ngược lại nếu i ≥ a[1] thì số vật được phép mang theo đi sẽ là i div a[1] và giá trị đạt được là f= c[1]*(i div a[1]).
Phần xây dựng: chúng ta xét đến f[i,j] có nghĩa là xét đến giá trị lớn nhất có thể đạt được từ j loại đồ vật (1,,j) mà trọng lượng không qúa i. Vậy thì rõ ràng là nếu i < a[j] thì có nghĩa là đồ vật j không thể mang đi hay với trọng lượng là i thì ta vẫn không thể cải thiện được giá trị f và f vẫn nhận giá trị f[i,j-1]. Ngược lại nếu i ≥a[j] thì chúng ta xét việc nếu mang thêm vật j thì sẽ có lợi hơn việc không mang hay không, điều đó có nghĩa là xét Max(f[i-a[j],j]+ c[j],f[i-1,j]).
Chương trình cài đặt giải quyết bài toán cái túi rất đơn giản như sau:
Uses crt;
Var value,weight:array[1..30]of 0..500;{value: gia tri;weight: trong luong}
f:array[0..500,0..30] of 0..10000;
w,w1,sl:integer;
fi:text;
Procedure Init;
Var i:byte;
Begin
clrscr;
assign(fi,'tuịtxt');reset(fi);
readln(fi,w,sl);w1:=w;
for i:=1 to sl do readln(fi,weight[i],value[i]);
End;
{***********************************************}
Procedure Solve;
Var i,j:word;
Begin
for j:=1 to sl do f[0,j]:=0;
for i:=1 to w do f[i,1]:=(i div weight[1])*value[1];
for j:= 2 to sl do
for i:=1 to w do
begin
if i else begin
f[i,j]:=f[i,j-1];
if (value[j]+f[i-weight[j],j])>f[i,j] then
f[i,j]:=(value[j]+f[i-weight[j],j]);
end;
end;
(************************************************}
Procedure Print_rerult;
Var i:byte;
Begin
write('* Gia tri cao nhat dat duoc la: ',f[w,sl]);writeln;
End;
(*************************************************)
Begin
Init;
Solve;
Print_result;
Readln;
End.
Chú ý: chương trình trên được đọc dữ liệu từ file.
II. Vấn đề công thức truy hồi
Đối với một bài toán qui hoạch động thì công thức truy hồi cũng là một phần rất quan trọng. Nếu chúng ta chỉ xây dựng được giá trị tối ưu thì đôi khi vẫn là chưa đủ. Vấn đề được đặt ra là làm thế nào để xác định được cấu hình tối ưụ Để giải quyết vấn đề này ta lại phải xác định được công thức truy hồị Thực tế là để xác định được công thức truy hồi này thì cũng không phải quá khó bởi từ công thức qui hoạch động chúng ta cũng có thể suy ngay ra được công thức truy hồị
Tôi xin trở lại với bài toán cái túi đã nêu ở trên để xây dựng cấu hình tối ưu cho bài toán cái túi có nghĩa là phải mang những loại vật nào và mỗi loại vật là bao nhiêu để có được giá trị sử dụng max: Xây dựng hàm phụ choose[i,k] với ý nghĩa để đạt được giá trị tốt nhất tại f[i,k] thì cần phải sử dụng đến loại đồ vật nào (i=1..w,k=1..n) bằng cac công thức sau:
Choose[i,1]:=0 nếu i
Ta lần lượt cho k chạy tới n và i chạy tới w để xây dựng mảng choose như sau:
Nếu f[i,k]=f[i,k-1] thì choose[i,k]:=choose[i,k-1] (do không mang vật k)
Nếu không thì n choose[i,k]:=k (có nghĩa mang theo vật k)
Khi xây dựng đến choose[w,n] thì ta chỉ cần chú ý đến cột cuối cùng của mảng choose và bắt đầu truy hồi. Giả sử mảng number[i] (i=1..n) sẽ cho ta số lượng loại vật i được mang theo. Ta sẽ cải thiện chương trình giải bài toán cái túi ở trên như sau:
Program Bai_toan_cai_tui;
Uses crt;
Var value,weight,number:array[1..20]of 0..1000;{value:gia tri}
f,choose:array[0..1200,0..12]of 0..10000;
w,w1,sl:0..2000;
fi:text;
Procedure Init;
Var i:byte;
Begin
clrscr;
assign(fi,'tui.txt');reset(fi);
readln(fi,w,sl);w1:=w;
for i:=1 to sl do readln(fi,weight[i],value[i]);
End;
{***********************************************}
Procedure Solve;
Var i,j:word;
Begin
for j:=1 to sl do begin f[0,j]:=0;choose[0,j]:=0;end;
for i:=1 to w do
begin
f[i,1]:=(i div weight[1])*value[1];
if i>=weight[1] then choose[i,1]:=1
else choose[i,1]:=0;
end;
for j:= 2 to sl do
for i:=1 to w do
begin
choose[i,j]:=choose[i,j-1];
if i else begin
f[i,j]:=f[i,j-1];
if (value[j]+f[i-weight[j],j])>f[i,j] then
begin
f[i,j]:=(value[j]+f[i-weight[j],j]);
choose[i,j]:=j;
end;
end;
end;
for i:=1 to sl do number[i]:=0;
while choose[w1,sl]<>0 do
begin
number[choose[w1,sl]]:=number[choose[w1,sl]]+1;
w1:=w1-weight[choose[w1,sl]];
end;
End;
{**************************************************}
Procedure Print;
Var i:byte;
Begin
write('* Gia tri cao nhat dat duoc la: ',f[w,sl]);writeln;
write('* Khoi luong da dung la: ',w-w1);writeln;writeln;
writeln('* Nha tham hiem can dem nhu sau: ');
for i:=1 to sl do
if number[i]<>0 then
begin write(' - ',number[i],' vat ',i, ' voi trong luong ',number[i]*weight[i],' va gia tri: ',number[i]*value[i]);
writeln;
end;
End;
{************* Main **********************}
Begin
Init;
Solve;
Print;
Readln;
End.
III. Bàn luận
Về bài toán cái túi còn rất nhiều lời giảị Ta cũng có thể giải quyết bài toán cái túi bằng thuật toán nhánh cận. Ưu điểm lớn nhất của thuật toán nhánh cận là có thể chỉ ra được mọi cấu hình tối ưu của bài tóan, tuy nhiên trong trường hợp xấu nhất, nhánh cận lại chính là vét cạn. Chính vì vậy, thời gian để thực hiện chương trình bằng nhánh cận sẽ rất lâụ
Rất tiếc rằng, giải thuật qui hoạch động luôn luôn chỉ nêu ra được một cấu hình tối ưu. Nếu chúng ta giải bằng qui hoạch động như trên, thời gian chạy chương trình rất nhanh chóng. Chương trình trên hoàn toàn có thể cải thiện được bằng cách thay vì dùng mảng 2 chiều f và choose ta có thể chỉ dùng 4 mảng 1 chiều đó là f1, f2, choose1, choose2 bởi thực chất tại cột j của f thì ta chỉ có thể liên quan đến cột j-1 của f. Chính vì vậy, 2 mảng f1,f2 có thể dùng thế lần lượt cho nhau tương đương dùng mảng 2 chiều f. Khi đó chương trình sẽ có thể chạy với bộ dữ liệu cỡ vài nghìn!
Thuật toán qui hoạch động còn được ứng dụng trong rất nhiều bài toán, tôi xin được nêu ra thêm một số bài toán khác nữa :
Bài 3: Một tam giác được tạo bởi các số x và sắp xếp như hình bên
Hãy tìm đường đi từ đỉnh xuống đáy sao cho: tổng các số đi qua là
lớn nhất. Cho biết:
- x là các số nguyên bất kì từ 0 đến 99.
- tam giác có số hàng <=20.
- mỗi bước đi: xuống 1 hàng tới số gần nhất bên trái hay phải.
* Dữ liệu: đọc từ file 'vaọinp' có dạng:
- Dòng đầu: số lượng dòng của tam giác.
- Từ dòng 2: các số cụ thể.
* Output: in ra màn hình
- Hình tam giác cân được tạo từ các số.
- Giá trị tổng các số đã gặp trên đường đi.
- Các số đã gặp trên đường đi
( Câu 2 trong đề thi chọn đội tuyển Tin học Hà Nội 2001-2002)
Bài 4: Chúng ta hãy giải quyết bài toán cái túi nhưng được thay đổi đi một số chi tiết như sau: Một nhà thám hiểm cần đem theo một số đồ vật vào cái túi có trọng tải không quá w của ông. Có tất cả n đồ vật, mỗi đồ vật i có trọng lượng là a[i] và giá trị sử dụng là c[i]. Hãy giúp nhà thám hiểm cách mang các đồ vật sao cho tổng giá trị sử dụng là lớn nhất có thể được (mỗi đồ vật chỉ có thể mang 1 lần hoặc không mang).
Một bài báo không thể nói hết được tất cả những ưu việt của cả một thuật toán. Tuy nhiên, sau bài báo này, tôi hy vọng các bạn sẽ hay sử dụng qui hoạch động hơn trong việc giải toán. Nếu bạn nào muốn lời giải cụ thể của tất cả các bài toán trên, hãy liên hệ với tôi theo địa chỉ:
Theo THNT