GR9 1 Quy hoạch động : PHÂN TÍCH ĐỘ PHỨC TẠP CỦA MỘT SỐ GIẢI THUẬT TRÊN CẤU TRÚC DỮ LIỆU PDF

Preview

Summary

TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI TP HỒ CHÍ MINHKHOA CÔNG NGHỆ THÔNG TINTHUYẾT TRÌNH PHÂN TÍCH THIẾT KẾ GIẢI THUẬTCHƯƠNG 3: PHÂN TÍCH ĐỘ PHỨC TẠP CỦA MỘT SỐ GIẢI THUẬTTRÊN CẤU TRÚC DỮ LIỆUNHÓM 7:20H1120138 – HOÀNG ANH KIỆT20H1120174 – TRƯƠNG ĐÌNH THIỆN20H1120114 – ĐẶNG HOÀNG GIA ĐẠTGiảng viên hướng ...

Description

TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI TP HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN

THUYẾT TRÌNH PHÂN TÍCH THIẾT KẾ GIẢI THUẬT CHƯƠNG 3: PHÂN TÍCH ĐỘ PHỨC TẠP CỦA MỘT SỐ GIẢI THUẬT TRÊN CẤU TRÚC DỮ LIỆU

NHÓM 7: 20H1120138 – HOÀNG ANH KIỆT 20H1120174 – TRƯƠNG ĐÌNH THIỆN 20H1120114 – ĐẶNG HOÀNG GIA ĐẠT

Giảng viên hướng dẫn: Trần Tuấn Anh

Thành phố Hồ Chí Minh – 2022

QUY HOẠCH ĐỘNG 1.Giới thiệu: Quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Cấu trúc con tối ưu có nghĩa là các lời giải tối ưu cho các bài toán con có thể được sử dụng để tìm các lời giải tối ưu cho bài toán toàn cục. Ví dụ, đường đi ngắn nhất tới một đỉnh trong một đồ thị có thể được tìm thấy bằng cách: trước hết tính đường đi ngắn nhất tới đích từ tất cả các đỉnh kề nó, rồi dùng kết quả này để chọn đường đi toàn cục tốt nhất, như trong hình sau.

Nói chung, ta có thể giải một bài toán với cấu trúc con tối ưu bằng một quy trình ba bước: 1. Chia bài toán thành các bài toán con nhỏ hơn. 2. Giải các bài toán này một cách tối ưu bằng cách sử dụng đệ quy quy trình ba bước này. 3. Sử dụng các kết quả tối ưu đó để xây dựng một lời giải tối ưu cho bài toán ban đầu. Các bài toán con được giải bằng cách chia chúng thành các bài toán nhỏ hơn, và cứ tiếp tục như thế, cho đến khi ta đến được trường hợp đơn giản dễ tìm lời giải. 2.Quy hoạch động thường được áp dụng như sau: •

Quy động hoạch (dynamic programming) giải các bài toán bằng cách kết hợp các lời giải của các bài toán con của bài toán đang xét

•

Phương pháp này khả dụng khi các bài toán con không độc lập đối với nhau, tức là khi các bài toán con có dung chung những bài toán “cháu” (subsubproblem).

•

Quy hoạch động giải các bài toán cháu dung chung này một lần và lưu lời giải của chúng trong một bảng và sau đó khỏi phải tính lại khi gặp bài toán đó.

•

Quy hoạch động thường được áp dụng cho những bài toán tối ưu hóa (optimization problem).

3.Quá trình xây dựng một giải thuật quy hoạch động: (Gồm 4 bước) 1. Đặc trưng hóa cấu trúc của lời giải tối ưu. 2. Định nghĩa giá trị của lời giải tối ưu một cách đệ quy. 3. Tính trị của lời giải tối ưu theo kiểu từ dưới lên. 4. Cấu tạo lời giải tối ưu từ những thông tin đã được tính toán.

PHẦN I: NHÂN MA TRẬN 1. Giới thiệu về bài toán nhân ma trận: Cho 2 ma trận A(p,q) và B(q,r). Khi nhân 2 ma trận thì độ phức tạp bằng số phép nhân 2 số (p*q*r). Phép nhân không có tính giao hoán nhưng có tính kết hợp. VD: A1*A2*A3 = A1*(A2*A3) = (A1*A2)*A3 Nên với phép nhân từ 3 ma trận trở lên thì với các cách kếp hợp khác nhau sẽ có độ phức tạp khác nhau. VD: A1(10x100), A2(100x5), A3(5x50) A1*(A2*A3) có 100x5x50 + 10x100x50 = 25000 + 50000 = 75000 phép nhân 2 số. (A1*A2)*A3 có 10x100x5 + 10x5x50 = 5000 + 2500 = 7500 phép nhân 2 số (giảm 10 lần). Mục tiêu của quy hoạch động trong bài toán nhân n ma trận là tìm ra cách kết hợp các phép nhân sao cho tổng số các phép nhân 2 số là nhỏ nhất (phép nhân vô hướng). 2. Độ phức tạp: Nhân ma trận: Với ma trận AA kích thước (m×n)(m×n) và ma trận BB kích thước (n×p)(n×p). Độ phức tạp của thuật toán để tính A×BA×B là O(m×n×p)O(m×n×p).  Ghi chú: Đối với phép nhân các ma trận vuông kích thước (n×n), có thuật toán nhân ma trận Strassen với độ phức tạp O(nlog27)≈O(n2.807) theo tư tưởng chia nhỏ ma trận (tương tự cách nhân nhanh 2 số lớn). Tuy nhiên cài đặt rất phức tạp và trên thực tế với giá trị n thường gặp, cách này không chạy nhanh hơn nhân ma trận thông thường O(n3). Lũy thừa ma trận: Với ma trận vuông A cấp n, thuật toán tính Ak có độ phức tạp O(n3×log k). 3. Cách giải quyết bài toán theo phương pháp quy hoạch động: Cho 1 dãy các ma trận A1, A 2,…,An, mỗi ma trận Ai có kích thước Pi-1 x Pi. Đầu vào: dãy các kích thước P0, P1,…, Pn. Đầu ra: dãy tích các ma trận A1, A2,…,An kết hợp với nhau bởi dấu ngoặc sao cho tích các ma trận có tổng số các phép tính vô hướng nhỏ nhất.  Gọi A i…j (i < j) là tích A i*Ai+1*…*Aj.  Ta có thể chia tích Ai*Ai+1*…*Aj = (Ai*Ai+1*…*Ak)*(Ak+1*Ak+2*…*Aj) Tức là Ai…j = Ai…k * Ak+1…j Có (j - i) cách chia như vậy (ứng với k = i,…, j -1). Để tối ưu hoá tích Ai…j thì cả A i…k và Ak+1…j cũng phải được tối ưu.  Đặt m[i, j] là số nhỏ nhất các phép nhân 2 số để tính tích A i…j.

Như vậy m[1, n] là số nhỏ nhất các phép nhân 2 số để tính tích A 1…n. Muốn cho m[1, n] nhỏ nhất thì các m[i, j] cũng phải nhỏ nhất.  Vì Ai…j có thể tính bằng Ai…k * A k+1…j, ta có công thức:  m[i, j] = 0, nếu i = j.  m[i, j] = min {m[i, k] + m[k+1, j] + Pi-1*Pk*Pj}, với i s[1, 2] = 1 tương tự cho m[2, 3], m[3, 4] và m[4, 5].  m[2, 4] = min{m[2, 2] + m[3, 4] + P1*P2*P4; m[2, 3] + m[4, 4] + P1*P3*P4} = min{0 + 54 + 4*3*3; 72 + 0 + 4*6*3} = min{90; 144} = 90 k = 2 => s[2, 4] = 2  Nhân 5 ma trận A1, A 2, A3, A 4, A5:  A1…A5: s[1, 5] = 4 => ((A1*A2*A3*A4)*A5)  A1…A4: s[1, 4] = 2 => (((A1*A2)*(A3*A4))*A5)  A1…A2: s[1, 2] = 1 => (A1*A2)  A3…A4: s[3, 4] = 3 => (A3*A4)

4. Code:  Tạo bảng:

 Tra bảng:

 Full code:

Và đây là kết quả:

PHẦN II: TÌM XÂU CON CHUNG DÀI NHẤT 1. Giới thiệu bài toán xâu con chung dài nhất (LCS – Longest common subsequence): Bài toán xâu con chung dài nhất (lớn nhất) là một bài toán kinh điển cho việc ứng dụng thuật toán quy hoạch động để giải quyết. Chương này chúng ta đang tìm hiểu về Dynamic Programming. Có thể nói, đây là một bài toán rất hay giúp chúng ta hiểu cả về QHD, cả về cấu trúc ma trận mảng hai chiều. Bài toán được phát biểu như sau: Viết chương trình nhập vào hai xâu kí tự, in ra độ dài xâu con chung lớn nhất và xâu chung đó của hai xâu vừa nhập. Ví dụ: hai xâu “BACDB” và “BDCB”, xâu con chung lớn nhất có độ dài là 3 và là “BCB”. Như vậy có hai điểm cần chú ý trong bài toán này đó là:  Tìm độ dài của xâu con chung dài nhất  In xâu con tìm được ra màn hình 2. Ý tưởng giải quyết bài toán: 2.1 Tìm độ dài xâu con lớn nhất: Bài toán nhỏ nhất ở đây chính là việc so sánh các phần từ nằm trong xâu, nếu chúng bằng nhau thì ta ghi nhận kết quả: Công thứu quy hoạch động của bài toán xâu con chung lớn nhất:  Nếu A[i] == B[j] thì L[i][j] = L[i-1][j-1] + 1  Ngược lại thì L[i][j] = max (L[i-1][j], L[i][j-1]) Trong đó:

 A, B là hai xâu cần xét  i, j tương ứng là chỉ số hàng và cột của mảng kết quả L  Hàm max là hàm để tìm ra số lớn hơn trong hai số, trường hợp hai số bằng nhau thì lấy số đầu tiên – L[i-1][j-1] Để dễ hiểu hơn chúng ta hãy xem minh họa dưới đây:

Công thức: Nếu A [i] == B [j] : L [i] [j] == L [i-1] [j-1] + 1 Ngược lại : L [i] == max (L [i-1] [j], L [i] [j-1]) Xét hai xâu: BACDB và BDCB L[][] “” B A C D B

“” 0 0 0 0 0 0

B 0 1 1 1 1 1

D 0 1 1 1 2 2

C 0 1 1 2 2 2

B 0 1 1 2 2 3

Kết quả: BCB Chú ý: độ dài hàng i trước, số cột j sau. Mảng lưu kết quả là một mảng hai chiều có kích thước L[n+1][m+1] trong đó n, m chính là độ dài của hai xâu a và b. Sở dĩ phải tăng thêm một đơn vị (n+1, m+1) để lưu thêm một hàng, cột có giá trị = 0. Tức là khi chưa có phần tử nào thì số con chung sẽ là 0. Giá trị L[n][m] chính là độ dài của xâu con chung lớn nhất ta cần tìm. 2.2 Truy vết xâu con chung: Truy vết để tìm và in ra xâu con ra màn hình sẽ dựa vào bảng kết quả mà ta tìm được ở phần trên. Bắt đầu từ vị trí L[n][m] và dừng lại khi L[i][j] == 0.  Bắt đầu duyệt từ i = n, j = m. Phần tử thứ i của xâu a sẽ là a[i-1], thứ j của xâu b sẽ là b[j-1]  Nếu a[i-1] == b[j-1] ta sẽ lưu lại con chung a[i-1] và giảm i và j đi 1 đơn vị  Nếu a[i-1] != b[j-1] có 2 trường hợp: - Nếu L[i-1][j] >= L[i][j-1] thì giảm i 1 đơn vị - Ngược lại giảm j đi 1 đơn vị Nếu thấy khó hiểu, bạn xem hình phía trên. Màu green là trường hợp a[i-1] == b[j-1], màu blue là trường hợp a[i-1] != b[j-1].

3. Phân tích độ phức tạp: Khảo sát độ phức tạp trên số phép gán:

Gọi F(i,j) là LCS của hai tiền tố A1..i và B1..j. Khi đó ta có thể maximize F(i,j) theo F(i−1,j) và F(i,j−1). Nếu Ai=Bj thì ta có thể cập nhật F(i,j) theo F(i−1,j−1)+1. Kết quả bài toán là F(m,n). Vậy ta có độ phức tạp của bài tóan này theo phương pháp quy hoạch động là O(nm).

4. Code xâu con chung dài nhất C/C++:

Và đây là kết quả chương trình trên:

PHẦN III: BÀI TOÁN XẾP BALO 1.Giới thiệu về bài toán xếp balo: Bài toán xếp ba lô (còn được biết đến với tên gọi bài toán cái túi) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học và toán ứng dụng. 2.Cách giải quyết bài toán bằng phương pháp quy hoạch động: -Cho một cái balo có thể đựng một trọng lượng W và n loại đồ vật, mỗi đồ vật i có một trọng lượng gi và một giá trị vi . Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào balo, chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất. 3.Xây dựng công thức truy hội để giải quyết bài toán: •

Giả sử X[k,V] là số lượng đồ vật k được chọn,F[k,V] là tổng giá trị của k đồ vật đã được chọn và V là trọng lượng còn lại của balo, k=1..n, V=0..W.

•

F[n,W]=F(X)=x1*v1+x2*v2+….+xn*vn->Max

•

Trong trường hợp đơn giản nhất, khi chỉ có một đồ vật, ta tính được X[1,V] và F[1,V] với mọi V từ 0 đến W như sau:

•

X[1,V] = V/g1 và F[1,V] = X[1,V] * v1.

•

Giả sử ta đã tính được F[k-1,U], khi có thêm đồ vật thứ k, ta sẽ tính được F[k,V], với mọi V từ 0 đến W. Cách tính như sau: Nếu ta chọn xk đồ vật loại k, thì trọng lượng còn lại của balo dành cho k-1 đồ vật từ 1 đến k-1 là U = V-xk*vk, với xk thay đổi từ 0 đến yk = V/gk và ta sẽ chọn xk sao cho F[k,V] lớn nhất.

Ta có công thức truy hồi như sau: •

X[1,V] = V/g1 và F[1,V] = X[1,V] * v1.

•

F[k,V] = Max(F[k-1,V-xk*gk]+xk*vk) với xk chạy từ 0 đến V/gk.

•

Sau khi xác định được F[k,V] thì X[k,V] là xk ứng với giá trị F[k,V] được chọn trong công thức trên.

•

Để lưu các giá trị trung gian trong quá trình tính F[k,V] và X[k,V] theo công thức truy hồi trên, ta sử dụng một bảng gồm n dòng từ 1 đến n, dòng thứ k ứng với đồ vật loại k và W+1 cột từ 0 đến W, cột thứ V ứng với trọng lượng V.

•

Mỗi cột V bao gồm hai cột nhỏ, cột bên trái lưu F[k,V], cột bên phải lưu X[k,V]. Trong lập trình ta sẽ tổ chức hai bảng tách rời là F và X.

Ví dụ: Cho bài toán balo với trọng lượng W=9, và 5 loại đồ vật được cho trong bảng sau:

Đồ vật

Trọng lượng (gi)

Giá trị (vi)

1 2 3 4 5

3 4 5 2 1

4 5 6 3 1

Tóm tắt bảng trên như sau: ĐV 1 2 3 4 5

gi 3 4 5 2 1

vi 4 5 6 3 1

X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1. F[k,V] = Max(F[k-1, V-xk*gk] + xk*vk) với xk chạy từ 0 đến V DIV gk V 0

1

2

3

4

5

6

7

8

9

K 1

0

0

0

0

0

0

4

1

4

1

4

1

8

2

8

2

8

2

2

0

0

0

0

0

0

4

0

5

1

5

1

8

0

9

1

2

3

0

0

0

0

0

0

4

0

5

0

6

1

8

0

9

0

4

0

0

0

0

3

1

4

0

6

2

7

1

9

3

2

5

0

0

1

1

3

0

4

0

6

0

7

0

9

0

1 0 1 0

1 0 1 0 1 2 1 2

0

0 4 0

1 2 1 2 1 2 1 3 1 3

3 0 0 3 0

Chúng ta sẽ tra bảng đã được tính ở trên để xác định phương án:  Khởi đầu, trọng lượng còn lại của balo V=W.  Xét các đồ vật từ n đến 1, với mỗi đồ vật k, ứng với trọng lượng còn lại V của balo, nếu X[k,V]>0 thì chọn X[k,v] đồ vật loại k. tính lại V= V – X[k,V]*gk  Ví dụ, trong bảng trên, ta xét các đồ vật từ 5 đến 1. Khởi đầu V =W = 9.  Với k = 5, vì X[5,9] = 0 nên ta không chọn đồ vật loại 5.  Với k = 4, vì X[4,9] = 3 nên ta chọn 3 đồ vật loại 4. Tính lại V= 9 - 3*2=3.  Với k = 3, vì X[3,3] = 0 nên ta không chọn đồ vật loại 3.  Với k = 2, vì X[2,3] = 0 nên ta không chọn đồ vật loại 2.  Với k = 1, vì X[1,3] = 1 nên ta chọn 1 đồ vật loại 1. Tính lại V = 3 – 1*3=0.

 Vậy tổng trọng lượng các vật được chọn là 3 * 2 + 1*3 = 9.  Tổng giá trị các vật được chọn là 3 * 3 + 1 * 4 = 13. Độ phức tạp của bài toán cái balo: Gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Khi đó, với mỗi i ≤ C, đặt A(i) là giá trị lớn nhất có thể đạt được với tổng chi phí không vượt quá i. Rõ ràng, A(C) là đáp số của bài toán. Định nghĩa A(i) một cách đệ quy như sau:  

A(0) = 0 A(i) = max { vj + A(i − cj),A(i) | cj ≤ i }

Ở đây, giá trị lớn nhất của tập rỗng được lấy bằng 0. Tính dần các kết quả từ A(0) tới A(C), ta sẽ được lời giải. Do việc tính mỗi A(i) đòi hỏi xem xét n đồ vật (tất cả các giá trị này đã được tính từ trước), và có C giá trị của các A(i) cần tính, nên thời gian chạy của lời giải quy hoạch động là O(nC). Điều này không mâu thuẫn với thực tế rằng bài toán xếp ba lô là NP-đầy đủ, do C, không như n, không thuộc mức đa thức theo độ dài của đầu vào cho bài toán. Độ dài đầu vào bài toán tỉ lệ thuận với số bit trong C, chứ không tỉ lệ với chính C. Một giải pháp quy hoạch động tương tự cho bài toán xếp ba lô 0-1 cũng chạy trong thời gian giả-đa thức. Cũng như trên, gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Định nghĩa một hàm đệ quy A(i, j) là giá trị lớn nhất có thể đạt được với chi phí không vượt quá j và sử dụng các đồ vật trong khoảng từ x1 tới xi. A(i,j) được định nghĩa đệ quy như sau:     

   

f[i][j]:= giá trị lớn nhất có thể lấy được; v[i]:= là giá trị của đồ vật thứ i; w[i]:=trọng lượng của đồ vật thứ i NOTES: Đây là bài toán không giới hạn đồ vật f[i][j]=max(f[i-1][j],v[i]+f[i][j-w[i]]) // khi đã lấy vật thứ i thì có thể lấy thêm nữa nên ta có f[i][j-w[i]]:= đã trừ đi trọng lượng của đồ vật thứ i và vẫn có thể lấy thêm được nữa // i là đồ vật không giới hạn A(0, j) = 0 A(i, 0) = 0 A(i, j) = A(i - 1, j) if ci > j A(i, j) = max(A(i - 1, j), vi + A(i - 1, j - ci)) if ci ≤ j

Để có lời giải, ta tính A(n, C). Để làm điều này, ta có thể dùng 1 bảng để lưu các tính toán trước đó. Cách giải này do đó sẽ chạy trong thời gian O(nC) và không gian O(nC), tuy ta có thể giảm độ phức tạp không gian xuống O(C) bằng một số sửa đổi nhỏ.

Code bài toán xếp balo:

Kết quả chạy bài toán xếp balo cho ví dụ trên:

PHẦN IV: Đánh giá tổng quan về thuật toán quy hoạch động: Quy hoạch động (Dynamic programming) là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu trữ toàn bộ hay một phần kết quả tính toán tại mỗi bước với mục đích sử dụng lại. Đối với dạng bài toán, độ phức tạp thường sẽ là O(n). Tuy nhiên, chúng ta có thể sử dụng một số biện pháp để giảm độ phức tạp, cũng như giảm thời gian chạy. Đầu tiên là phải kể đến việc tối ưu hoá cấu trúc. Biện pháp này có thể được áp dụng rộng rãi trong rất nhiều lĩnh vực. Đương nhiên, đây cũng không phải là một việc dễ dàng mà nó đòi hỏi một mức độ hiểu biết cũng như kinh nghiệm nhất định. Cách thứ hai đó là lưu trữ lại đáp án của các bài toán con (memoization), nhằm hạn chế việc tính toán. Chúng ta sẽ có hai hướng tiếp cận chính, đó là từ trên xuống và từ dưới lên. Từ trên xuống (topdown) là hướng tiếp cận mà chúng ta sẽ bắt đầu từ bài toán phức tạp. Từ dưới lên (bottom-up) là hướng tiếp cận mà chúng ta sẽ giải các bài toán con cần thiết trước khi tiếp xúc với bài toán phức tạp....