Bài giảng Phân tích thiết kế giải thuật - Chương 1: Dynamic Programming

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