Thuật toán qui hoạch động

Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán-Tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như chia để trị, tham ăn, quay lui,... Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong bài viết này, tôi muốn đề cập với các bạn một thuật toán khác, đó...
Nội dung trích xuất từ tài liệu:
Thuật toán qui hoạch động TÀI LIỆU THUẬT TOÁNQUI HOẠCH ĐỘNG MỤC LỤCThuật toán qui hoạch động.................................................................33Thuật toán quy hoạch động trên mảng một chiều............................39Giải thuật quy hoạch động................................................................. 45Đố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 choviệc sử dụng qui hoạch động. Chính vì vấn đề này, qui hoach độnglại trở thành không phổ biến. Đối với những bài toán như vậy, chúngta lại cố gắng đi tìm cách giải khác ví dụ như vét cạn hay thamlam....điều đó thật là dở! Chính vì vậy, tôi muốn đưa ra một số bàitoán áp dụng qui hoạch động để mong rằng sau bài báo này, cácbạ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ọicấu hình con của nó cũng là tối ưu. Chính vì vậy để xây dựng 1 cấuhì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ấuhình con này cũng phải tối ưu Đây chính là đường lối chủ đạo chomọi bài toán qui hoạch động. Sau đây là một số bài toán được giảiquyết bằng qui hoạch động.I. Các bài toánBài 1: Trước tiên chúng ta hãy xét 1 bài toán thật đơn giản và quenthuộc đó là tìm giá trị lớn nhất trong n số là a1, a2, ..., an. Gi ải quy ếtbà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ầnlượ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ì maxn 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;BeginWrite(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 doIf a[k]>max then max:=a[k];Write(Gia tri lon nhat cua day cac so da cho la: ,max);ReadlnEnd.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ínhlà 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ậtloại thứ i (1≤i≤n) có trọng lượng là a[i] và giá trị sử dụng là c[i]. Mộtnhà thám hiểm cần mang theo một số đồ vật vào túi của mình saocho 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ámhiể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ấtcó đượ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 doFor i:=1 to w doIf 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 ớnnhất có thể đạt được từ j loại đồ vật (1,,j) mà trọng lượng không qúai. 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 đượcgiá 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 taxét việc nếu mang thêm vật j thì sẽ có lợi hơn việc không mang haykhô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: trongluong}f:array[0..500,0..30] of 0..10000;w,w1,sl:integer;fi:text;Procedure Init;Var i:byte;Beginclrscr;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;Beginfor 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 dofor i:=1 to w dobeginif i else beginf[i,j]:=f[i,j-1];if (value[j]+f[i-w ...