Bài giảng Giải thuật - Chương 1: Dynamic Programming
° Dynamic programming
— giải 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.
— (ở đây “programming” không có nghĩa là lập trình).
° So sánh dynamic programming và “chia-và-trị” (divide-and-conquer)
— Giải thuật chia-và-trị
° chia bài toán thành các bài toán con độc lập ,
° giải chúng bằng đệ quy,
° kết hợp chúng để có lời giải cho bài toán ban đầu.
— Giải thuật dynamic programming
° các bài toán con không độc lập với nhau: chúng có chung các bài toán con nhỏ hơn.
° giải mỗi bài toán con chỉ một lần, và ghi nhớ lời giải đó trong một bảng để truy cập khi cần đến.
mming Một lời giải không tối ưu Giải thuật không ghi nhớ lời giải của các bài toán con. R ECURSIVE -M ATRIX -C HAIN ( p , i , j ) 1 if i = j 2 then return 0 3 m [ i , j ] 4 for k i to j 1 5 do q R ECURSIVE -M ATRIX -C HAIN ( p , i , k ) + R ECURSIVE -M ATRIX -C HAIN ( p , k + 1, j ) + p i 1 p k p j 6 if q < m [ i , j ] 7 then m [ i , j ] q 8 return m [ i , j ] 13.9.2004 21 Ch. 1: Dynamic Programming Phân tích R ECURSIVE -M ATRIX -C HAIN Gọi T ( n ) là thời gian chạy của R ECURSIVE -M ATRIX -C HAIN ( p , 1, n ), thì T ( n ) phải thỏa (xem code) Từ đó chứng minh được: T ( n ) = (2 n ). Tại sao R ECURSIVE -M ATRIX -C HAIN chạy trong thời gian (2 n ) còn M ATRIX -C HAIN -O RDER chỉ cần thời gian đa thức? Đó là vì R ECURSIVE -M ATRIX -C HAIN là giải thuật đệ quy từ trên xuống (top-down) và không tận dụng được tính chất “các bài toán con trùng nhau” (overlapping subproblems). M ATRIX -C HAIN -O RDER là giải thuật dynamic-programming từ dưới lên (bottom-up), tận dụng được tính chất “các bài toán con trùng nhau”. 13.9.2004 22 Ch. 1: Dynamic Programming Cây đệ quy Cây đệ quy cho R ECURSIVE -M ATRIX -C HAIN ( p , 1, 4) 1..4 2..2 1..1 3..4 2..3 4..4 2..2 3..3 1..2 4..4 1..1 2..3 3..3 1..1 2..4 1..2 3..4 1..3 4..4 4..4 3..3 2..2 3..3 1..1 2..2 3..3 2..2 13.9.2004 23 Ch. 1: Dynamic Programming Một biến dạng của dynamic programming: memoization Memoization là phương pháp tận dụng tính chất “các bài toán con trùng nhau” để cải tiến giải thuật đệ quy từ trên xuống bằng cách sử dụng một bảng chung mà mỗi triệu gọi của giải thuật đệ quy có thể truy cập để ghi kết quả sau khi giải một bài toán con mới đọc kết quả của một bài toán con đã được giải rồi. 13.9.2004 24 Ch. 1: Dynamic Programming Memoize giải thuật R ECURSIVE -M ATRIX -C HAIN Memoize giải thuật R ECURSIVE -M ATRIX -C HAIN bằng cách sử dụng bảng m [1.. n , 1.. n ]. M EMOIZED -M ATRIX -C HAIN có input là một chuỗi p = M EMOIZED -M ATRIX -C HAIN ( p ) 1 n length [ p ] 1 2 for i 1 to n 3 do for j i to n 4 do m [ i , j ] 5 return L OOKUP -C HAIN ( p , 1, n ) 13.9.2004 25 Ch. 1: Dynamic Programming Memoization L OOKUP -C HAIN bao giờ cũng trả về m [ i , j ]. Nhưng nó chỉ tính m [ i , j ] khi nào đó là lần gọi đầu tiên với các tham số i và j . L OOKUP -C HAIN ( p , i , j ) 1 if m [ i , j ] < 2 then return m [ i , j ] 3 if i = j 4 then m [ i , j ] 0 5 else for k i to j 1 6 do q L OOKUP -C HAIN ( p , i , k ) + L OOKUP -C HAIN ( p , k + 1, j ) + p i 1 p k p j 7 if q < m [ i , j ] 8 then m [ i , j ] q 9 return m [ i , j ] 13.9.2004 26 Ch. 1: Dynamic Programming Phân tích M EMOIZED -M ATRIX -C HAIN M EMOIZED -M ATRIX -C HAIN chạy trong thời gian O ( n 3 ). Nhận xét : M EMOIZED -M ATRIX -C HAIN tận dụng được tính chất “các bài toán con trùng nhau”, còn R ECURSIVE -M ATRIX -C HAIN chạy trong thời gian (2 n ) vì nó luôn luôn giải các bài toán con mà không để ý xem bài toán con đã được giải rồi hay chưa. 13.9.2004 27 Ch. 1: Dynamic Programming Phân tam giác Đa giác Đa giác đơn (“simple”) Đa giác lồi Phân tam giác (triangulation) 13.9.2004 28 Ch. 1: Dynamic Programming Các khái niệm cơ bản Cạnh , đỉnh , biên của một đa giác Ta biểu diễn một đa giác lồi P bằng danh sách các đỉnh theo thứ tự ngược chiều kim đồng hồ: P = v 0 , v 1 ,..., v n 1 Cung (“chord”) của một đa giác Một phân tam giác của một đa giác là một tập hợp các cung của đa giác chia đa giác thành các tam giác rời nhau. 13.9.2004 29 Ch. 1: Dynamic Programming Bài toán phân tam giác tối ưu Cho: Một đa giác lồi P = v 0 , v 1 ,..., v n 1 Một h àm trọng số w (“weight function”) được định nghĩa trên các tam giác tạo bởi cạnh và cung của P . Bài toán : Tìm một phân tam giác cho P sao cho tổng các trọng số của các tam giác trong phân tam giác này là nhỏ nhất. Ví dụ một hàm trọng số: w (một tam giác) = tổng các chiều dài của các cạnh của tam giác. 13.9.2004 30 Ch. 1: Dynamic Programming Parse tree của một biễu thức Biễu thức (expression) Ví dụ một biễu thức: tích của một chuỗi ma trận đã được đóng ngoặc hoàn toàn (( A 1 ( A 2 A 3 ))( A 4 ( A 5 A 6 ))) Parse tree . Ví dụ: parse tree của biễu thức (( A 1 ( A 2 A 3 ))( A 4 ( A 5 A 6 ))) là A 1 A 2 A 3 A 4 A 5 A 6 13.9.2004 31 Ch. 1: Dynamic Programming Parse tree của một biễu thức Định nghĩa: parse tree của một biễu thức là một cây mà Lá : có nhản là một trong các nguyên tử (“atomic element”, ví dụ: A 1 ) tạo nên biễu thức. Nếu gốc của một cây con của parse tree có cây con bên trái tượng trưng biễu thức E l và có cây con bên phải tượng trưng biễu thức E r , thì cây con này tượng trưng biễu thức ( E l E r ). 13.9.2004 32 Ch. 1: Dynamic Programming Từ phân tam giác sinh ra parse tree Ví dụ: Parse tree cho đa giác P = v 0 , v 1 ,, v 6 sau. A 1 A 2 A 3 A 4 A 5 A 6 v 0 v 1 v 2 v 3 v 4 v 6 v 5 13.9.2004 33 Ch. 1: Dynamic Programming Từ parse tree sinh ra phân tam giác Cho parse tree biểu diễn bởi ((( A 1 ( A 2 A 3 )) A 4 )( A 5 A 6 )). Phân tam giác tương ứng: A 1 A 2 A 3 A 4 A 5 A 6 v 0 v 1 v 2 v 3 v 4 v 6 v 5 A 1 A 2 A 3 A 5 A 6 A 4 13.9.2004 34 Ch. 1: Dynamic Programming Tương ứng giữa parse tree và phân chia tam giác Tương ứng giữa parse trees và các phân chia tam giác là tương ứng một-đối-một : Mỗi phân tam giác của một đa giác lồi có n + 1 cạnh tương ứng với parse tree cho một biễu thức gồm n nguyên tử. Mỗi parse tree có n lá tương ứng với phân tam giác của một đa giác lồi có n + 1 cạnh. 13.9.2004 35 Ch. 1: Dynamic Programming Tương ứng giữa đóng ngoặc hoàn toàn của tích của n ma trận và phân chia tam giác Đóng ngoặc hoàn toàn của tích của n ma trận tương ứng với phân tam giác của một đa giác lồi có n + 1 đỉnh. Mỗi ma trận A i trong tích A 1 A 2 A n tương ứng với cạnh v i - 1 v i của đa giác lồi. Cung v i v j , với i < j , tương ứng với ma trận A i + 1.. j . 13.9.2004 36 Ch. 1: Dynamic Programming Nhân chuỗi ma trận và phân tam giác tối ưu Bài toán nhân chuỗi ma trận là một trường hợp đặc biệt của bài toán phân tam giác tối ưu. Tính tích A 1 A 2 A n thông qua một bài toán phân tam giác tối ưu: Định nghĩa một đa giác lồi có n + 1 đỉnh P = v 0 , v 1 ,, v n Nếu ma trận A i có dimension p i 1 p i , với i = 1, 2,..., n , định nghĩa hàm trọng số w cho phân tam giác là w ( v i v j v k ) = p i p j p k Một phân tam giác tối ưu của P cho ta parse tree của một đóng ngoặc tối ưu của A 1 A 2 A n . 13.9.2004 37 Ch. 1: Dynamic Programming Nhân chuỗi ma trận và phân tam giác tối ưu (tiếp) Ngược lại là không đúng: bài toán phân tam giác tối ưu không là trường hợp đặc biệt của bài toán nhân chuỗi ma trận. Mặc dù vậy, có thể chỉnh lại M ATRIX -C HAIN -O RDER để giải bài toán phân tam giác tối ưu cho một đa giác có n + 1 đỉnh như sau Thay chuỗi p = của các chiều của ma trận bằng chuỗi v 0 , v 1 ,..., v n của các đỉnh. Thay các truy cập đến p bằng các truy cập đến v và thay dòng 9 bởi 9 do q m [ i , k ] + m [ k + 1, j ] + w ( D v i 1 v k v j ) Khi giải thuật thực thi xong, m [1, n ] chứa trọng số của một phân tam giác tối ưu. Phần sau cho thấy tại sao làm được như vậy. 13.9.2004 38 Ch. 1: Dynamic Programming Bước 1: Cấu trúc con của một phân tam giác tối ưu Cho T là một phân tam giác tối ưu của một đa giác P = v 0 , v 1 ,, v n , T chứa tam giác D v 0 v k v n với k nào đó, 1 k n 1. Trọng số của T là tổng của các trọng số của tam giác D v 0 v k v n và các tam giác chứa trong phân tam giác của hai đa giác con v 0 , v 1 ,, v k và v k , v k + 1 ,, v n . Một đa giác con suy thoái có trọng số là 0. Do đó các phân tam giác (xác định bởi T ) của các đa giác con trên cũng phải là tối ưu. (Chứng minh bằng phản chứng.) v 0 v 1 v k v n v 2 13.9.2004 39 Ch. 1: Dynamic Programming Bước 2: Lời giải đệ quy Định nghĩa t [ i , j ] là trọng số của một phân tam giác tối ưu của đa giác v i 1 , v i ,, v j . Như vậy trọng số của một phân tam giác tối ưu của đa giác P là t [1, n ]. Xác định t [ , ] nếu đa giác chỉ có 2 đỉnh (đa giác suy thoái) t [ i , i ] = 0 cho i = 1,..., n nếu đa giác có ít nhất 3 đỉnh, i < j t [ i , j ] = t [ i , k ] + t [ k + 1, j ] + w ( v i 1 v k v j ) . Nhưng trị của k ? 13.9.2004 40 Ch. 1: Dynamic Programming Bước 2: Lời giải đệ quy (tiếp) Bằng cách duyệt qua tất cả các trị của k , i k j - 1, ta nhận được t [ i , i ] = 0, i = 1,..., n t [ i , j ] = min i k j 1 { t [ i , k ] + t [ k + 1, j ] + w ( v i 1 v k v j ) } nếu i < j . Hàm đệ quy này tương tự hàm đệ quy m [ , ] cho số phép nhân vô hướng tối thiểu để tính A i A i+ 1 A j . Do đó có thể chỉnh lại thủ tục M ATRIX -C HAIN -O RDER (như đã nói) để tính trọng số của một phân tam giác tối ưu. Vậy thủ tục phân tam giác tối ưu chạy trong thời gian O ( n 3 ) và cần bộ nhớ ( n 2 ). 13.9.2004 41 Ch. 1: Dynamic Programming
File đính kèm:
- bai_giang_giai_thuat_chuong_1_dynamic_programming.ppt