Tài liệu CHUYÊN ĐỀ PHƯƠNG PHÁP QUY HOẠCH ĐỘNG.DOC

CHUYÊN ĐỀ PHƯƠNG PHÁP QUY HOẠCH ĐỘNG Quy hoạch động – giống như phương pháp chia để trị - giải quyết các bài toán bằng cách kết hợp các giải pháp của các bài toán con. Điểm khác biệt là một thuật toán quy hoạch động giải quyết các bài toán con đúng một lần và sau đó ghi kết quả của chúng trong một bảng, như vậy tránh được việc phải tính lại các kết quả khi bài toán con được lặp lại. 1. Nguyên lý tối ưu Bellman Quy hoạch động là quá trình điều khiển tối ưu với trạng thái bắt đầu. Mọi trạng thái A bất kỳ thuộc quá trình này cũng tối ưu. Tư tưởng chính: Thực hiện các bài toán con trước, sử dụng các kết quả này để giải bài toán lớn. Hướng tiếp cận: - Giải bài toán theo công thức truy hồi. - Giải các bài toán con trước. - Dựa vào bài toán con để giải bài toán lớn hơn cho đến khi gặp bài toán cần giải. Tổng quát: Giải bài toán qua N bước. Giải bài toán sao cho tổng chi phí 1N-1 và N-1 N là tối ưu. 2. Thuật toán quy hoạch động Bước 1: Xây dựng công thức truy hồi Giả sử: Chia bài toán thành N giai đoạn 1->N Xác định F(1) - cơ sở quy nạp - Gọi (i) là hàm số xác định giá trị tối ưu, tính đến giá trị thứ i  F(n) là nghiệm của bài toán - Đối với bài toán + Tìm Min: F(N) = Min{F(i), F(j)} i = 1, N-1 j = N-1, N 1 + Tìm Max: F(N) = Max{F(i), F(j)} i = 1, N-1 j = N-1, N Bước 2: Tìm cơ sở quy hoạch động Để chia bài toán lớn thành các bài toán con có cùng một cách giải thì yêu cầu phải biến đổi một số bài toán con ở trường hợp cơ sở quy nạp bằng cách thêm biến phụ, chính là cơ sở quy hoạch động Bước 3: Lấp đầy bảng phương án, dựa vào cơ sở quy hoạch động, công thức quy hoạch động Giải bài toán Bước 4: Truy vết Tìm nghiệm của bài toán 3. Một số ví dụ minh họa Bài 1. Dãy con không giảm dài nhất Cho N số nguyên dương (0ld then begin ld:= d[j]; lj:= j; end; vitri_truoc:= lj; end; 3 procedure tao_td; var i: longint; begin khoitri; for i:=2 to n do begin t[i]:= vitri_truoc(i); if t[i]=0 thend[i]:= 1 else d[i]:= d[t[i]]+1; end; end; function maxd: longint; var i,p,li: longint; begin p := -maxint; li := 0; for i:=1 to n do if d[i]>p then begin p := d[i]; li := i; end; maxd:= li; end; procedure timketqua; var i: longint; begin i := maxd; d[i] := -d[i]; dem := 1; repeat i:= t[i]; if i<>0 then begin d[i]:= -d[i]; inc(dem) end; until i=0; end; procedure ghi; var f : text; i : longint; begin assign(f,fo); rewrite(f); writeln(f,dem); dem:= 0; for i:= 1 to n do 4 if d[i]<0 then begin write(f,a[i]:7); inc(dem); if dem mod 10 = 0 then writeln(f); end; close(f); end; BEGIN clrscr; nhap; tao_td; timketqua; ghi; END. Bài 2. Cho hai dãy số nguyên (a1,a2,...,am), (b1,b2,...,bn). Tìm dãy con chung có độ dài lớn nhất của hai dãy trên (coi dãy không có số nguyên nào là dãy con của mọi dãy và có độ dài bằng 0). Lời giải Chúng ta có thể thấy ngay rằng độ phức tạp của bài toán trên phụ thuộc vào hai số m, n. Xét hai trường hợp: +Trường hợp1: m=0 hoặc n=0. Đây là trường hợp đặc biệt, có duy nhất một dãy con chung của hai dãy có độ dài bằng 0. Vì vậy dãy con chung có độ dài lớn nhất của chúng có độ dài bằng 0. +Trường hợp 2: m# 0 và n # 0. Trong trường hợp này, ta xét các bài toán nhỏ hơn là tìm dãy con chung có độ dài lớn nhất của hai dãy (a1,a2,...,ai), (b1,b2,...,bj) với 0 <= i <= m, 0 <= j <= n. Gọi l[i,j] là độ dài của dãy con chung lớn nhất của hai dãy (a1,...,ai), (b1,...,bj). ; Như vậy ta phải tính tất cả các l[i,j] trong đó 0<=i<=m, 0<=j<=n. Chúng ta có thể thấy ngay rằng l[0,0]=0. - Nếu ai # bj thì l[i, j]=max{l[i-1, j], l[i, j-1]}. 5 - Nếu ai=bj thì l[i, j]= 1+l[i-1, j-1]. Với những nhận xét trên, ta hoàn toàn tính được l[m,n] chính là độ dài dãy con chung dài nhất của (a1,..am), (b1,..bn). Để tìm phần tử của dãy con, ta xuất phát từ ô l[m,n] tới ô l[0,0]. Giả sử ta đang ở ô l[i,j]. Nếu ai=bj thì ta thêm a i vào dãy con rồi nhảy tới ô l[i1,j-1]. Nếu ai # bj thì l[i, j]=l[i-1,j] hoặc l[i,j]=l[i, j-1]. Nếu l[i,j]=l[i-1,j] thì nhảy tới ô l[i-1,j], ngược lại thì nhảy tới ô l[i,j-1]. Sau đây là lời giải của bài toán. Chương trình được viết bằng ngôn ngữ Pascal: uses crt; const fi='b2.inp'; var a: array[1..10] of integer; b: array[1..10] of integer; kq: array[0..10,0..10] of integer; i, j, maxa, maxb: integer; f: text; procedure init; begin assign(f,fi); reset(f); i:=0; while not(eoln(f)) do begin inc(i); read(f,a[i]); end; maxa:=i; readln(f); i:=0; while not(eoln(f)) do begin inc(i); read(f,b[i]); 6 end; maxb:=i; close(f); end; function max(a,b:integer):integer; begin if a>b then max:=a else max:=b; end; begin init; kq[0,0]:=0; for i:=1 to maxa do for j:=1 to maxb do if a[i]<>b[j] then kq[i,j]:=max(kq[i-1,j],kq[i,j-1]) else kq[i,j]:=kq[i-1,j-1]+1; writeln('Do dai day con chung lon nhat:', kq[maxa,maxb]); i:=maxa; j:=maxb; while (i>0)or(j>0) do if a[i]=b[j] then begin write(a[i]); dec(i); dec(j); end else if kq[i-1,j]=kq[i,j] then dec(i) else dec(j); end. Bài 3. Bài toán chia kẹo Có N gói kẹo, gói thứ i có Ai cái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất. Dữ liệu vào trong file "chiakeo.inp" có dạng : 7 - Dòng đầu tiên là số N(N<=100); - Dòng thứ hai là N số Ai(i=1, 2,.., N; Ai <=100). Kết quả ra file "chiakeo.out" có dạng: - Dòng đầu là độ chênh lệch nhỏ nhất giữa hai phần có thể được. - Dòng hai là một dãy N số, nếu s i =1 thì gói thứ i thuộc phần 1, nếu si=2 thì gói thứ i thuộc phần 2 Thuật toán: Với một số M bất kì, nếu ta biết được có tồn tại một cách chọn các gói kẹo để tổng số kẹo của các gói được chọn bằng đúng M không, thì bài toán sẽ được giải quyết. Vì đơn giản là ta chỉ cần chọn số M sao cho M gần với Ai/2 nhất (với i =1,2,..,N). Sau đó xếp các gói kẹo để tổng bằng M vào phần một, phần thứ hai sẽ gồm các gói kẹo còn lại. Để kiểm tra được điều trên ta sẽ xây dựng tất cả các tổng có thể có của N gói kẹo bằng cách: ban đầu chưa có tổng nào được sinh ra. Làm lần lượt với các gói kẹo từ 1 đến N, với gói kẹo thứ i, ta kiểm tra xem hiện tại có các tổng nào đã được sinh ra, giả sử các tổng đó là x1, x2,.., xt vậy thì đến bước này sẽ có thể sinh ra các tổng x 1, x2,.., xt và Ai và x1+Ai, x2+Ai,.., xt+Ai.Với N gói kẹo, mà mỗi gói có không quá 100 cái kẹo vậy tổng số kẹo không vượt quá N*100 <= 10000 cái kẹo. Dùng mảng đánh dấu D, nếu có thể sinh được ra tổng bằng k thì D[k] = 1 ngược lại D[k] = 0. * Chương trình {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} Program chia_keo; uses crt; const max = 100; fi ='chiakeo.inp'; fo ='chiakeo.out'; var a,s : array[1..max]of integer; d1,d2,tr : array[0..max*max]of integer; n,m,sum : integer; Procedure docf; var f: text; k : integer; begin assign(f,fi); reset(f); readln(f,n); 8 sum:=0; for k:=1 to n do begin read(f,a[k]); sum:=sum+a[k]; end; close(f); end; Procedure lam; var i,j : integer; Begin fillchar(d1,sizeof(d1),0); fillchar(tr,sizeof(tr),0); d1[0]:=1;d2:=d1; for i:=1 to n do begin for j:=0 to sum-a[i] do if (d1[j]=1)and(d2[j+a[i]]=0) then begin d2[j+a[i]]:=1; tr[j+a[i]]:=i; end; d1:=d2; end; end; Procedure ghif; var m,k : integer; f :text; Begin fillchar(s,sizeof(s),0); m:=sum div 2; while d2[m]=0 do dec(m); assign(f,fo); rewrite(f); writeln(f,sum-2*m); while tr[m]>0 do begin s[tr[m]]:=1; m:=m-a[tr[m]]; end; 9 for k:=1 to n do if s[k]=1 then write(f,s[k],#32) else write(f, 2,#32); close(f); end; BEGIN {main} docf; lam; ghif; END. 4. Bài tập ứng dụng Bài 1. Dãy con có tổng bằng S: Cho dãy a1,a2,..an. Tìm một dãy con của dãy đó có tổng bằng S. Hướng dẫn Đặt L[i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1, a2,.., ai. Ngược lại thì L[i,t)=0. Nếu L[n,S)=1 thì đáp án của bài toán trên là “có”. Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i– 1,t–a[i]]=1. Cài đặt Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và được tính như sau: L[t]:=0; L[0]:=1; for i := 1 to n do for t := S downto a[i] do if (L[t]=0) and (L[t–a[i]]=1) then L[t]:=1; Bài 2. Bắc cầu Hai nước Anpha và Beta nằm ở hai bên bờ sông Omega, Anpha nằm ở bờ bắc và có M thành phố được đánh số từ 1 đến m, Beta nằm ở bờ nam và có N thành phố được đánh số từ 1 đến n (theo vị trí từ đông sang tây). Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu, hãy chỉ ra cách bắc cầu được nhiều cầu nhất. 10 Hướng dẫn: Gọi các thành phố của Anpha lần lượt là a 1, a2,…, am; các thành phố của Beta là b1, b2,..., bn. Nếu thành phố ai và bj kết nghĩa với nhau thì coi ai “bằng” bj. Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố (a i, bj) để xây cầu thì cặp tiếp theo phải là cặp (a u,bv) sao cho u>i và v>j. Như vậy các cặp thành phố được chọn xây cầu có thể coi là một dãy con chung của hai dãy a và b. Bài toán của chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở đây hai phần tử “bằng” nhau nếu chúng có quan hệ kết nghĩa. Bài 3. Tại thời điểm 0, ông chủ một máy tính hiệu năng cao nhận được đơn đặt hàng thuê sử dụng máy của n khách hàng. Các khách hàng được đánh số từ 1 đến n. Khách hàng i cần sử dụng máy từ thời điểm d i đến thời điểm ci (di, ci là các số nguyên và 0 < di < ci < 1000000000) và sẽ trả tiền sử dụng máy là pi (pi nguyên, 0 < p i ≤ 10000000). Bạn cần xác định xem ông chủ cần nhận phục vụ những khách hàng nào sao cho khoảng thời gian sử dụng máy của hai khách được nhận phục vụ bất kỳ không được giao nhau đồng thời tổng tiền thu được từ việc phục vụ họ là lớn nhất. Dữ liệu vào: Từ file văn bản THUE.INP - Dòng đầu tiên ghi số n (0 < n =< 1000); - Dòng thứ i+1 trong số n dòng tiếp theo ghi 3 số d i, ci, pi cách nhau bởi dấu trắng (i = 1, 2,... n). Kết quả: Ghi ra file văn bản THUE.OUT -Dòng đầu tiên ghi hai số nguyên dương theo thứ tự là số lượng khách hàng nhận phục vụ và tổng tiền thu được từ việc phục vụ họ. -Dòng tiếp theo ghi chỉ số của các khách hàng được nhận phục vụ. Ví dụ: THUE.INP THUE.OUT THUE.INP THUE.OUT 3 2 180 4 2 1100 150 500 150 2 3 400 821 800 2 4 1 200 100 200 513 500 400 800 80 100 325 200 600 900 600 Bài toán này chúng ta phải chú ý ở chỗ: Để dùng thuật toán Quy hoạch động tối ưu từng bước thì trước hết chúng ta phải sắp xếp các c i theo thứ tự tăng dần: Giả sử c1 ≤ c2 ≤... ≤ cN. Gọi F[k] là số tiền lớn nhất khi phục vụ một số khách hàng từ 1 đến k. 11 Với mỗi F[k] ta có: - Nếu chấp nhận phục vụ khách k thì F[k]:=F[t]+p k ((với t là chỉ số max thoả mãn khoảng thời gian [dt, ct [dk,ck]=  ). - Nếu không chấp nhận phục vụ k thì F[k]:=F[k-1]. Như vậy hàm quy hoạch động của F[k] sẽ là: F[k]:=Max{F[t]+pk ,F[k-1]} với k = 2, 3,... N và t có ý nghĩa như trên. Để lấy lại chỉ số các khách hàng được phục vụ chúng ta lại dùng mảng Truoc[i] là chỉ số của khách hàng được chọn trước khách hàng i sao cho tổng tiền thu được là lớn nhất và thỏa mãn các yêu cầu bài toán. 12