Bài giảng Kỹ thuật ra quyết định kỹ sư - Chương 3: Quy hoạch động

1Chương 3. Quy hoạch động9.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động9.2. Giải thuật quy hoạch động giải bài toán tập độc lập lớn nhất.9.3. Giải thuật quy hoạch động giải bài toán cái túi9.4. Giải thuật quy hoạch động giải bài toán dãy con lớn nhất9.5. Giải thuật quy hoạch động giải bài toán dãy con chung dài nhất.9.6. Giải thuật quy hoạch động giải nhân dãy ma trận.     29.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động9.1.1. Ví dụ về bài toán con chung lồng nhau9.1.2. Quy hoạch động là gì?9.1.3. Ba giai đoạn của bài toán quy hoạch động     39.1.1. Các bài toán con chung lồng nhau trong giải thuật chia để trị Khi chia bài toán thành các bài toán con, trong nhiều trường hợp, các bài toán con khác nhau lại chứa các bài toán con hoàn toàn giống nhau. Ta nói rằng chúng chứa các bài toán con chung giống nhauVí dụ:      4Ví dụ về bài toán con lồng nhauTính số Fibonaci thứ nĐịnh nghĩa số Fibonaci F(n):F(0)=0F(1)=1F(n)=F(n-2)+F(n-1) với n>1Ví dụ:F(2)=1, F(3)= 2, F(4) = 3 , F(5)=5, F(6)=8     5Ví dụ: Tính số Fibonaci thứ nTính theo đệ quy {top down}:Function R_Fibonaci(n); If n MaxV[i-1, L])  then MaxV[i, L] := MaxV[i1,Lw[i]]+v[i] ;End; Return MaxV(n, M)      29Ví dụCó 6 đồ vật và tổng trọng lượng tối đa có thể mang là 1030Giảiiwv123456789101612L-w(i)-----01234Yes000001212121212Max000001212121212231L’=L-w(i)--01234567Max(i-1,L’)--0000001212Yes001111111313Max001111212121313338L-w(i)--01234567Max(i-1,L’)000011111313Yes888899992020Max888891212122020319.2.2. Bài toán dãy con chung dài nhấtBài toán; Cho hai dãy X = (x1,x2,,xm) và Y = (y1,y2,,yn). Cần tìm dãy con chung dài nhất của hai dãy X và Y.     32Phân rã . Với mỗi 0≤ ί ≤ m và 0 ≤ j ≤ n xét bài toán con : Tính C[i, j] là độ dài của dãy con chung dài nhất của hai dãy.Xi=x1x2xi và Yj =y1y2yi . Chú y rằng ( Xo và Yo là xâu rỗng) Như vậy ta đã phân bài toán cần giải ra thành (m+1)(n+1) bài toán con. Bản thân bài toán xuất phát là bài toán con có kích thước lớn nhất C(m,n).     33Bài toán con cơ sở và tổng hợpCác bài toán con cơ sởC[0, j] = 0  j = 0.. n và C[i,0] =0,i = 0.. m. (là độ dài dãy con chung lớn nhất của dãy rỗng với một dãy khác).TỔNG HỢP Với i > 0, j > 0 . Tính C[i, j].Có hai tình huống:Nếu xi =yj thì dãy con chung dài nhất của Xi vàYi sẽ thu được bằng việc bổ sung xi vào dãy con chung dài nhất của hai dãy Xi1và Yj1Nếu xi ≠ yi thì dãy con chung dài nhất của Xi và Yj sẽ là dãy con dài hơn trong hai dãy con chung dài nhất của (Xi1 và Yi) và của (Xi và Yj1) .      34Công thức truy hồi để tính C[i,j]. C[i,j] = 0 nếu i =0 hoặc j=0C[i,j] = C[i-1,j-1]+1 nếu xi = yjC[i,j] = Max{ C[i-1,j], C[i,j-1]} nếu xi  yj     35Procedure LCS(X,Y)Begin{Khởi tạo} For i :=1 to m do c[i,0]:=0; For j: =1 to n do c[0,j ]:=0;{Tính từ dưới lên}For i: =1 to m do for j: = 1 to n do If xi = yj then begin c[i,j]:=c[i-1,j-1]+1; b[i,j]:=’’ end else If c [i-1,j]≥ c[i,j-1] then begin c[i,j]:=c[i-1,j]; b[i,j]:=’’; end else begin c[i,j]:=c[i,j-1]; b[i,j]:=’’;end;End;      36Ví dụ: Dãy con chung dài nhất là HDA     37Ví dụ123456DINHVU1N0011112I0 1 11113N01 2 2 2 24H 0 1 2 3 3 35C 0 1 23 3 36U 0 1 2 3 3 4Nếu X[ i ]=Y[ j ] thì lấy giá trị ô đứng hàng trên bên trái + 1Nếu X[ i ]  Y[ j ] thì lấy theo giá trị lớn hơn trong hai giá trị đứng trên hoặc đứng trước     38Bài toán dãy con liên tiếp có tổng lớn nhấtCho dãy A dưới dạng mảng A[1..n ] các sốHãy tìm dãy con các phần tử liên tiếp của dãy A có tổng lớn nhấtVí dụ:     39Phân rãGọi S(i) là tổng của dãy con lớn nhất trong dãy i phần tử Ai = a[1], ., a [i], i = 1,2,, n thì S(n) là giá trị cần tìm.Bài toán con cơ sở Với i =1 ta có S(1)= a[1].     40Phân rã Giả sử i > 1 và S[k] là đã biết với k = 1,.., i1. Ta cần tính S[i] là tổng của dãy con liên tiếp lớn nhất của dãy a[1], a[i-1], a[i].Các dãy con liên tiếp của dãy này có thể là một trong hai trường hợp:Các dãy con liên tiếp có chứa a[i] Các dãy con liên tiếp không chứa a[i] Gọi MaxS(i) là tổng lớn nhất của các dãy con liên tiếp của dãy a[1]...a[i]MaxE(i) là tổng lớn nhất của các dãy con liên tiếp của dãy a[1]..a[i] chứa chính a[i].     41Phân rã .....Tổng lớn nhất của các dãy con liên tiếp của dãy a[1]..a;[i] không chứa a[i] chính là tổng lớn nhất của các dãy con của dãy a[1]..a[i-1]1, nghiã là MaxS(i1). Do đó MaxS(i) = max { MaxS(i1) , MaxE(i)}.     42Tính MaxE(i)Để tính MaxE(i), i = 1, 2, , n, ta cũng có thể sử dụng công thức đệ quy như sau1. Với i=1: MaxE(i) = a[1];2.Với i >1, Gọi S là dãy con kế tiếp lớn nhất của dãy a[1]..a[i] có chứa a[i]. Có hai khả năng:Nếu S chứa a[i1] do đó độ dài lớn nhất có thể là MaxE(i1)+a[i]; Nếu S không chứa a[i1] thì S chỉ gồm a[i]Do đó: MaxE[i] = max {a[i] , MaxE[i1] + a[i] }, i > 1.     43Procedure Maxsub(a); Var MaxS,MaxE, s, e, e1 :Integer ;Begin MaxS:=a[1]; MaxE:= a[1]; s:=1; e:=1; s1:=1;For i: = 2 to n do begin	 if MaxE>0 then MaxE:=MaxE+a[i] else begin MaxE = a[i]; s1:=i;end; if (MaxE > MaxS) then	 begin MaxS:= MaxE; e:=i; s:=s1;end; End;End;      Ý nghĩa các biến: maxS: tổng dãy con lớn nhất maxE: tổng dãy con có chứa phần tử cuối lớn nhấts,e chỉ số đầu và cuối của dãy con có tổng lớn nhấts1 chỉ số đầu của dãy lớn nhất kết thúc tại i44Ví dụ Dãy con có tổng lớn nhất     45Nhân dãy ma trậnBài toán: Khi nhân hai ma trận Amn và Bn,p ta dùng ba vòng For For i: = 1 to m do For j := 1 to p do Begin C[i,j] := 0; For k:=1 to n do C[i,j]:= C[i,j]+a[i,k]*b[k,j]; End;Số các phép nhân phải thực hiện là m*n*p.     46Nhân dãy ma trậnXét phép nhân 3 ma trận A3,4 x B4,5 x C5,6.Có hai cách nhânABC=(AB)C và A(BC).Tính tích AB cần 3*4*5= 60 phép nhân đựợc ma trận D cấp 3x5. Tính DC cần 3x5x6 = 180 phép nhân. Do đó tính (AB)C cần 60+180 = 240 phép nhânTính tích (BC) cần 4*5*6= 120 phép nhân được ma trận E cấp 4x6; tính AE cần 3x4x6=72 phép nhân. Do đó tính A(BC) cần 120+72= 192 phép nhân.     47Bài toán nhân dãy ma trậnXét phép nhân dãy ma trận M1M2..Mn1). Có bao nhiêu cách tổ chức thứ tự thực hiện phép nhân dãy ma trận này?2). Nhân theo thứ tự nào để số phép nhân các số là ít nhất?      48Số cách thực hiện dãy phép nhân n ma trậnKý hiệu T (n) là số cách điền các dấu ngoặc vào biểu thức tích của n ma trận. Giả sử ta định đặt dấu ngoặc phân tách đầu tiên vào giữa ma trận thứ i và ma trận thứ (i + 1) trong biểu thức tích, tức là: M = (M1 M2  Mi)(Mi+1 Mi+2  Mn) Khi đó có T(i) cách đặt dấu ngoặc cho thừa số thứ nhất (M1 M2  Mi) và T(n - i) cách đặt dấu ngoặc cho thừa số thứ hai (Mi+1 Mi+2  Mn) và từ đó T(i)T(n-i) cách tính biểu thức (M1 M2  Mi)(Mi+1 Mi+2  Mn).      49Có bao nhiêu cách tính M1M2...Mn?Công thức truy hồiCông thức hiện     50Có bao nhiêu cách?Một số giá trị của T(n)n123451015T(n)11251448622674440     51Cách tính tối ưu?Cách nào đòi hỏi số phép nhân các số ít nhất     52Phân rã (Xác định cấu trúc con tối ưu).Giả sử cách tính tối ưu tích của n ma trận đòi hỏi dặt dấu ngoặc tách đầu tiên giữa ma trận thứ i và thứ (i+1) của biểu thức tích, thì khi đó cả hai tích con (M1 M2  Mi) và (Mi+1 Mi+2  Mn) cũng phải được tính một cách tối ưu. Do đó đó số phép nhân cần phải thực hiện để nhân dãy ma trận là tổng: số phép nhân cần thực hiện để nhân hai dãy con + số phép nhân cần thực hiện để nhân hai ma trận kết quả     53Phân rã bài toán Gọi mij là số phép nhân ít nhất cần thực hiện để tính tích (i  j) (MiMi+1 Mi+2  Mj), 	1 ≤ i ≤ j ≤ nGiả sử kích thước của các ma trận được cho bởi véc tơ d[0  n], trong đó ma trận Mi có kích thước di1  di, i = 1, 2, 3,  n.      54Trường hợp cơ sởKhi i = j thì mii = 0 Giả sử j = i+s với s  1 và phép nhân cuối cùng tách từ vị trí thứ k (Mi Mi+1 Mk)(Mk+1 . Mi+s1Mi+s).tích thứ nhất là ma trận kích thước (i-1), k, tích thứ hai co kích thước k, i+s số các phép nhân ít nhất để tính tích theo công thức này là mik + mk+1,i+s+ di1dkdi+s      55Công thức đệ quy1 0, có n – s phần tử trên đường chéo cần tính, để tính mỗi phần tử đó ta cần so sánh s giá trị số tương ứng với các giá trị có thể của k. Từ đó suy ra số phép toán cần thực hiện theo thuật toán là cỡ     62Độ phức tạp tính toántương đương với     63Mã giả tựa Pascal tính mijBeginFor i: = 1 to n do m[i,i]:=0;For s:=1 to n do	 For i:= 1 to n–s do begin j:=i+s–1; m[i,j]:= +∞; For k:=i to j–1 do begin q:=m[i,k]+m[k+1,j]+d[i-1]*d[k]*d[j]; If(q<m[i,j]) then begin m[i,j]= q; h[i,j] = k; end; end; end;End;     64Nhân hai ma trận với mảng h[i,j] tính từ thủ tục trênProcedure Mult(i,j);Begin	If(i<j) then	 Begin	k := h[i,j];	X := Mult(i,k);	Y := Mult(k+1,j) 	 Return X*Y; {Nhân ma trận X và Y}	 End	 Else	Return M[i];End;     65Bài tậpTìm cách nhân tối ưu để tính tích của dãy ma trận A1 A2  A3  A4 trong đó vectơ kích thước của chúng là (2,4,5,3,2)     