Bài giảng Phân tích và thiết kế giải thuật - Chương 5: Qui hoạch động và giải thuật tham lam

Chương 4

Qui hoạch động và giải thuật

tham lam

Qui hoạch động

Giải thuật tham lam

1

1. Qui hoạch động

Quy hoạch động (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ó dùng chung

những bài toán “cháu” (subsubproblem).

Qui hoạch động giải các bài toán “cháu” dùng 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 lại bài toán cháu đó.

Qui hoạch động được áp dụng cho những bài toán tối ưu

hóa (optimization problem).

2

Bốn bước của qui hoạch động

Sự xây dựng một giải thuật qui hoạch động có thể được chia

làm bốn bước:

3. Đặ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.

3

Thí dụ1: Nhân xâu ma trận

Cho một chuỗi <A₁, A₂, …, A_n> gồm n matrận, và ta muốn

tính tích các ma trận.

A₁A₂… A_n

(5.1)

Tích của xâu ma trận này được gọi là mở-đóng-ngoặc-đầy-đủ

(fully parenthesized ) nếu nó là một ma trận đơn hoặc là tích

của hai xâu ma trận mở-đóng-ngoặc-đầy-đủ .

Thí dụ: A₁A₂A₃A₄có thể được mở-đóng-ngoặc-đầy-đủ theo 5

cách:

(A₁(A₂(A₃A₄)))

(A₁((A₂A₃)A₄)

((A₁A₂)(A₃A₄))

(A₁(A₂A₃))A₄)

(((A₁A₂)A₃)A₄)

4

Cách mà ta mở đóng ngoặc một xâu ma trận có ảnh hưởng

rất lớn đến chi phí tính tích xâu ma trận.

Thí dụ:

A₁

A₂

A₃

10 × 100

100 × 5

5 × 50

((A₁A₂)A₃)) thực hiện

10.100.5 + 10.5.50 = 5000 + 2500

= 7500 phép nhân vô hướng.

(A₁(A₂A₃)) thực hiện

100.5.50 + 10.100.50 = 25000 + 50000 = 75000 phép nhân vô

hướng.

Hai chi phí trên rất khác biệt nhau.

5

Phát biểu bài toán nhân xâu ma trận

Bài toán tính tích xâu ma trận:

'‘Cho một chuỗi <A₁, A₂, …, A_n> gồm n matrận, với mỗi

i = 1, 2, …, n, ma trận A_icó kích thước p_i-1× p_i, ta mở-đóng-

ngoặc tích này sao cho tối thiểu hóa tổng số phép nhân vô

hướng”.

Đây là một bài toán tối ưu hóa thuộc loại khó.

6

Cấu trúc của một cách mở đóng ngoặc tối ưu

Bước 1: Đặc trưng hóa cấu trúc của một lời giải tối ưu.

Dùng A_i..jđể ký hiệu ma trận kết quả của việc tính

A_iA_i+1…A_j.

Một sự mở đóng ngoặc tối ưu của tích xâu ma trận A₁.A₂… A_n

Tách xâu ngay tại vị trí nằm giữa A_kvà A_k+1với một trị nguyên

k, 1 ≤ k < n. Nghĩa là, trước tiên ta tính các chuỗi ma trận A_1..k

and A_k+1..nvà rồi nhân chúng với nhau để cho ra A_1.n.

Chi phí của sự mở đóng ngoặc tối ưu này = chi phí tính A_l..k+

chí phí tính A_k+1..n, + chi phí nhân chúng lại với nhau.

7

Diễn tả lời giải một cách đệ quy

Ở đây, những bài toán con của ta là bài toán xác định chi phí

tối ưu ứng với sự mở đóng ngoặc cho chuỗi A_i.A_i+1… A_jvới

1 ≤ i ≤ j ≤ n.

Đặt m[i, j] là tổng số tối thiểu các phép nhân vô hướng được

đòi hỏi để tính ma trận A_i..j. Chi phí của cách rẻ nhất để tính

A_1..nsẽ được ghi ở m[1, n].

Giả sử rằng sự mở đóng ngoặc tối ưu tách đôi tích chuỗi A_i

A_i+l… A_jtại giữa A_kand A_k+l, với i ≤ k < j. Thì m[i, j] bằng với

chí phí tối thiểu để tính A_i..kvà A_k+1..j, cọng với chi phí để nhân

hai ma trận này lại với nhau.

m[i, j] = m[i, k] + m[k+1, j] + p_i-1p_kp_j.

8

Một công thức đệ quy

Như vậy, định nghĩa đệ quy cho chi phí tối thiểu của một

sự mở đóng ngoặc cho A_iA_i+l… A_jlà như sau:

m[i, j] = 0

nếu i = j,

= min {m[i, k] + m[k + 1, j] + p_i-1p_kp_j.}

nếu i < j.

(5.2)

Để giúp theo dõi cách tạo một lời giải tối ưu, hãy định

nghĩa:

s[i, j]: trị của k tại đó chúng ta tách tích xâu ma trận

A_iA_i+1…A_jđể đạt đến một sự mở đóng ngoặc tối ưu.

9

Một nhận xét quan trọng

Một nhận xét quan trọng là

''Sự mở đóng ngoặc của xâu con A₁A₂....A_kbên trong sự mở

đóng ngoặc tối ưu của xâu A₁A₂…A_ncũng phải là một sự mở

đóng ngoặc tối ưu''.

Như vậy, một lời giải tối ưu cho bài tóan tích xâu ma trận

chứa đựng trong nó những lời giải tối ưu của những bài toán

con.

Bước thứ hai của phương pháp qui hoạch động là định nghĩa

trị của lời giải tối ưu một cách đệ quy theo những lời giải tối

ưu của những bài toán con.

10

Tính những chi phí tối ưu

Thay vì tính lời giải dựa vào công thức cho ở (5.2) bằng một

giải thuật đệ quy, chúng ta đi thực hiện Bước 3 của qui hoạch

động: tính chi phí tối ưu bằng cách tiếp cận từ dưới lên.

Giả sử ma trận A_icó kích thước p_i-1× p_ivới

i = 1, 2 ,.., n.

Đầu vào là chuỗi trị số <p₀, p₁, …, p_m>.

Thủ tục dùng một bảng m[1..n, 1..n] để lưu các chi phí m[i, j]

và bảng s[1..n, 1..n] để lưu giá trị nào của vị trí k mà thực

hiện được chi phí tối ưu khi tính m[i, j].

Thủ tục MATRIX-CHAIN-ORDER trả về hai mảng m và s.

11

Thủ tục tính hai bảng m và s

procedure MATRIX-CHAIN-ORDER(p, m, s);

begin

n:= length[p] - 1;

for i: = 1 to n do m[i, i] := 0;

for l:= 2 to n do /* l: length of the chain */

for i:= 1 to n – l + 1 do

begin

j:= i + l – 1;

m[i, j]:= ∞;

/* initialization */

for k:= i to j-1 do

begin

q:= m[i, k] + m[k + 1, j] + p_i-1p_kp_j;

if q < m[i, j] then

begin m[i, j]: = q; s[i, j]: = k end

end

12

Một thí dụ: Tính tích xâu ma trận

Vì ta định nghĩa m[i, j] chỉ cho i < j, chỉ phần của bảng m ở

trên đường chéo chính mới được dùng.

Cho các ma trận với kích thước như sau:

A₁

A₂

A₃

A₄

A₅

A₆

30 × 35

35 × 15

15 × 5

5 × 10

10 × 20

20 × 25

Hình 4.1 trình bày bảng m và s được tính bởi thủ tục

MATRIX-CHAIN-ORDER với n = 6.

13

Một thí dụ về tính tích xâu ma trân (tt.)

Mảng m

i

1

2

3

4

5

6

6 15125 10500 51375 3500 5000

5 11875 7125 2500 1000

0

j 4 9357 4375

3 7875 2625

750 0

0

2 15750

0

1

0

Mảng s

Hình 5.1

i

1

3

1

2

3

2

3

4

5

4

5

6

5

j 4

3

2

14

Một thí dụ về tính tích xâu ma trân (tt.)

m[2,2]

m[2,3]

m[2,4]

+

m[3,5]

m[4,5]

m[5m5]

+

p.p₂p₅

p₁p₂p₅

=

0

+

2500

2625 100

4375

+

35.15.20

35.5.30

35.10.20

=

13000

m[2,5] = min

+

=

7125

+

p₁p₄p₅

=

+

0

+

=

11375

= 7125

k = 3 for A_2..5

Bước 4 của phương pháp qui hoạch động là tạo một lời giải

tối ưu từ những thông tin đã tính toán.

15

Bước 4: Tạo một lời giải tối ưu

Ta dùng mảng s[1..n, 1..n] để xác định cách tốt nhất để tính

tích xâu ma trận. Mỗi phần tử s[i, j] ghi trị of k sao cho tại

đó sự mở đóng ngoặc tối ưu tách đôi xâu A_iA_i+1… A_jthành

hai đoạn tại A_kvà A_k+1.

Cho trước chuỗi ma trận A = <A₁, A₂…, A_n>, bảng s và các

chỉ số i và j, thủ tục đệ quy MATRIX-CHAIN-MULTIPLY sau

đây tính tích xâu ma trận A_i..j,. Thủ tục trả về kết quả qua

tham số AIJ.

Vơi lệnh gọi ban đầu là

MATRIX-CHAIN-MULTIPLY(A,s, 1, n, A1N)

Thủ tục sẽ trả về kết quả ma trận tích sau cùng với mảng

A1N.

16

Tính lời giải

procedure MATRIX-CHAIN-MULTIPLY(A, s, i, j, AIJ);

begin

if j > i then

begin

MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j], X);

MATRIX-CHAIN-MULTIPLY(A,s, s[i, j]+1, j, Y);

MATRIX-MULTIPLY(X, Y, AIJ);

end

else

assign Ai to AIJ;

end;

17

Các thành phần của quy hoạch động

Có hai thành phần then chốt mà một bài toán tối ưu hóa phải

có để có thể áp dụng qui hoạch động:

(1) tiểu cấu trúc tối ưu (optimal substructure) và

(2) các bài toán con trùng lắp (overlapping subproblems).

Tiểu cấu trúc tối ưu

Một bài toán có tính chất tiểu cấu trúc tối ưu nếu lời giải tối

ưu chứa trong nó những lời giải tối ưu của những bài toán

con.

18

Những bài toán con trùng lắp

Khi một giải thuật đệ quy gặp lại cùng một bài toán con

nhiều lần, ta bảo rằng bài toán tối ưu hóa có những bài toán

con trùng lắp.

Giải thuật quy hoạch động lợi dụng những bài toán con

trùng lắp bằng cách giải mỗi bài toán con một lần, cất lời

giải vào trong một bảng mà bảng này sẽ được tham khảo

đến khi cần.

Các giải thuật đệ quy làm việc từ trên xuống trong khi các

giải thuật quy hoạch động làm việc từ dưới lên, Cách sau

hữu hiệu hơn .

19

Thí dụ 2: Bài toán chuỗi con chung dài nhất

Một chuỗi con (subsequence) của một chuỗi (sequence) là

chuỗi ấy sau khi bỏ đi một vài phần tử.

Thí dụ: Z = <B, C, D, B> là một chuỗi con của

X = <A, B, C, B, D, A, B> với chuỗi chỉ số <2, 3, 5, 7>.

Cho hai chuỗi X và Y, ta bảo Z là chuỗi con chung (common

subsequence) của X và Y nếu Z là một chuỗi con của cả hai

chuỗi X và Y.

Trong bài toán chuỗi con chung dài nhất, ta được cho hai

chuỗi X = <x₁, x₂, …, x_m> và Y = <y₁, y₂,…, y_n> và muốn tìm

chuỗi con chung dài nhất (LCS) của X và Y.

20

Bài giảng Phân tích và thiết kế giải thuật - Chương 5: Qui hoạch động và giải thuật tham lam - Dương Tuấn Anh