Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Quy hoạch động

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Quy hoạch động

1. 9.1. Các bài toán con chung lồng nhau và giải thuật quy hoạch động 9.1.1. Ví dụ về bài toán con chung lồng nhau 9.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    2
2. Ví dụ về bài toán con lồng nhau Tính số Fibonaci thứ n Định nghĩa số Fibonaci F(n): ▪ F(0)=0 ▪ F(1)=1 ▪ F(n)=F(n-2)+F(n-1) với n>1 Ví dụ: F(2)=1, F(3)= 2, F(4) = 3 , F(5)=5, F(6)=8    4
3. So sánh hai giải thuật ➢ Khi tính F(5): ➢ Giải thuật đệ quy tính ➢ F(5) = F(3)+F(4) ➢ Tính F(3) F(3)= F(2)+F(1) Để tính F(5): ➢ F(2)=F(1)+F(0) = 1 ➢ 2 lần tính F(3) ➢ F(3)= 1+1= 2 ➢ 3 lần tính F(2) ➢ Tính F(4) F(4)= F(2)+F(3) ➢ F(2)= F(0)+F(1) = 1 ➢ F(3)=F(1)+F(2) = 1+F(2) ➢ F(2)= F(0)+F(1) = 2 ➢ F(3)= 1+2 =3 ➢ F(4) = 2+3 = 5 ➢ Tổng hợp F(5) = 3+5 =8 ➢    6
4. Dùng Quy hoạch động để tính số Fibonacy thứ n Function Fibonaci(n); ▪ If n < 2 then f:= n ▪ else ▪ begin f_0:=0 ; f_1:= 1; ▪ For k:=2 to n do ▪ begin ▪ f:=f_0+f_1 ; f_0:= f_1; f_1:= f; ▪ end; ▪ end; ▪ Return f;    8
5. 9.1.3. Ba giai đoạn của quy hoạch động ➢ Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất có thể giải một cách trực tiếp. Bài toán xuất phát có thể coi là bài toán con có kích thước lớn nhất ➢ Giải các bài toán con và ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một bảng để sử dụng lại nhiều lần do đó không phải giải lặp lại cùng một bài toán. ➢ Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán con kích thước nhỏ hơn xây dựng lời giải của bài toán kích thước lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất).    10
6. Các yếu tố của một giải thuật quy hoạch động giải bài toán tối ưu ➢ Cơ sở của quy hoạch động: Những trường hợp đơn giản có thể tính trực tiếp ➢ Cấu trúc con tối ưu: Phương pháp chia nhỏ các bài toán cho đến khi gặp được bài toán cơ sở. ➢ Tổng hợp: hệ thức truy hồi tính giá trị tối ưu của hàm mục tiêu của bài toán lớn qua giá trị tối ưu của các bài toán con thành phần.    12
7. Các ví dụ áp dụng quy hoạch động ➢ 9.3. Tập độc lập lớn nhất trên cây ➢ 9.4. Bài toán Cái túi dạng 0-1 ➢ 9.5. Bài toán dãy con chung dài nhất ➢ 9.5 Bài toán nhân dãy ma trận ➢ và nhiều bài toán khác    14
8. 1. Tập độc lập trong đồ thị Định nghĩa: B F Cho G = (V,E) là đơn đồ thị vô A hướng. Một tập con U các đỉnh của đồ thị được gọi là tập độc lập, nếu như hai đỉnh C bất kỳ trong U là không kề nhau trong G. E H Trong đồ thị bên : ▪ tập các đỉnh {A, H, D} là độc I lập. ▪ tập các đỉnh {F, E, I, , D, G} là không độc lập. D G    16
9. Bài toán tập độc lập lớn nhất trong cây INPUT: ▪ Cây T = (V,E) ▪ Hàm trọng số trên tập các đỉnh w: V → R OUTPUT ▪ Tập con độc lập U  V có w(u) , u U lớn nhất    18
10. Trường hợp cơ sở và công thức truy hồi ➢ Trường hợp cơ sở: Nếu v là lá thì BigNotR(v) = 0; BigR(v) = w(v) ➢ Công thức truy hồi: Giả sử v có các cây con gốc u1, u2 , uk Gọi U là tập độc lập của cây con gốc v. ▪ Bài toán con 1: Nếu U chứa v thì không chứa u1, u2 , uk. BigR(v)= W(v) +  BigNotR(ui) (tổng chạy qua tất cả các con của v) ▪ Bài toán con 2: Nếu tập độc lập U không chứa v thì nó là hợp của các tập độc lập của các cây con. Do đó BigNotR(v) =  Big(ui) ▪ Tổng hợp: Big(v) = max{BigR(v) , BigNotR(v)}    20
11. Tính Big(v) tại đỉnh v ➢ Procedure CalculateBig(v); ➢ Begin ➢ BigR(v) := W(v); BigNotR(v):= 0 ➢ For each u in v.Children do {với mỗi con của đỉnh v} ➢ begin ➢ BigR(v):= BigR(v)+BigNotR(u); ➢ BigNotR(v):= BigNotR(v)+Big(u); ➢ end; ➢ Big(v):=max(BigNotR(v), BigR(v)); ➢ End;    22
12. Ví dụ: tập độc lập lớn nhất trong cây    24
13. Phân rã Giảm kích thước: Với các giá trị i và L: i = 1,2, , n và L =0, 1, 2, , M. Gọi MaxV(i,L) là tổng giá trị lớn nhất có thể chọn trong i đồ vật (1, , i) với trọng lượng tối đa L. Bài toán con: Trong dãy i đồ vật 1, , i có thể ▪ Bài toán con 1: Nếu có chọn vật thứ i (nếu w[i] ≤ L), khi đó giá trị lớn nhất có thể là: MaxV(i−1, L− w[i]) + v[i] ; ▪ Bài toán con 2: Nếu không chọn vật thứ i, khi đó giá trị lớn nhất là : MaxV(i−1, L) Tổng hợp MaxV(i, L) = max{MaxV(i −1,L− w[i]) +v[i] , MaxV(i −1,L)}    26
14. Mã: Giải thuật Bag_Best Procedure Bag_best ▪ {Khởi tạo}: For L: = 0 to M do MaxV[0,L] :=0 ; ▪ For i = 1 to n do ▪ For L = 1 to M do ▪ Begin ▪ MaxV[i,L] := MaxV[ i−1,L]; ▪ If (w[i] ≤ L) and (MaxV[i−1,L−w[i]] + v[i] > MaxV[i-1, L]) then MaxV[i, L] := MaxV[i−1,L−w[i]]+v[i] ; ▪ End; ▪ Return MaxV(n, M)    28
15. Giải i w v 1 2 3 4 5 6 7 8 9 10 L-w(i) - - - - - 0 1 2 3 4 1 6 12 Yes 0 0 0 0 0 12 12 12 12 12 Max 0 0 0 0 0 12 12 12 12 12 L’=L-w(i) - - 0 1 2 3 4 5 6 7 Max(i-1,L’) - - 0 0 0 0 0 0 12 12 2 3 1 Yes 0 0 1 1 1 1 1 1 13 13 Max 0 0 1 1 1 12 12 12 13 13 L-w(i) - - 0 1 2 3 4 5 6 7 Max(i-1,L’) 0 0 0 0 1 1 1 1 13 13 3 3 8 Yes 8 8 8 8 9 9 9 9 20 20 Max 8 8 8 8 9 12 12 12 20 30 20
16. Phâ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=x1x2 xi và Yj =y1y2 yi . 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).    32
17. Công thức truy hồi để tính C[i,j]. ➢ C[i,j] = 0 nếu i =0 hoặc j=0 ➢ C[i,j] = C[i-1,j-1]+1 nếu xi = yj ➢ C[i,j] = Max{ C[i-1,j], C[i,j-1]} nếu xi yj    34
18. Ví dụ: Dãy con chung dài nhất là HDA    36
19. Bài toán dãy con liên tiếp có tổng lớn nhất ➢ Cho 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ất ➢ Ví dụ:    38
20. Phâ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].    40
21. Tí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ư sau ➢ 1. 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.    42
22. Ví dụ Dãy con có tổng lớn nhất    44
23. Nhân dãy ma trận ➢ Xét phép nhân 3 ma trận A3,4 x B4,5 x C5,6. Có hai cách nhân ABC=(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ân ➢ Tí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.    46
24. Số cách thực hiện dãy phép nhân n ma trận Ký 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).    48
25. Có bao nhiêu cách? ➢ Một số giá trị của T(n) n 1 2 3 4 5 10 15 T(n) 1 1 2 5 14 4862 2674440    50
26. Phâ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ả    52
27. Trườ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    54
28. Ví dụ ➢ Tìm cách tính tối ưu cho tích của bốn ma trận M1M2M3M4 với các kích thước d = (2, 5, 4, 3, 7). Ta có với s=1 m12 M1M2 2 5 4 = 40 m23 M2M3 5 4 3 = 60 m34 M3M4 4 3 7 =84    56
29. Ví dụ với d = (2, 5, 4, 3, 7). m12 = 40 m23 = 60 ➢ Tính m24 m34 =84 m24 M2M3M4 (M2M3) (M4) 165 m + m + d *d * d = k=1 (M )(M M ) 22 34 1 2 4 224 2 3 4 0+ 84+5*4*7 m + m + d d d k=2 (M M ) (M ) 23 44 1 3 4 165 2 3 4 =60+0+5 3 7    58
30. Ví dụ với d = (2, 5, 4, 3, 7). ➢ Tổng hợp kết quả ➢ Tính tối ưu M1M2M3 M4 là tính (M1M2M3) M4 với 126 phép nhân các số ➢ Tính tối ưu (M1M2 M3) là tính (M1)(M2 M3) Trả lời: Với dãy các kích thước đã cho cách tính tối ưu là (M1(M2 M3))M4.    60
31. Độ phức tạp tính toán tương đương với    62
32. Nhân hai ma trận với mảng h[i,j] tính từ thủ tục trên ➢ Procedure 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;    64