Dynamic Programming

10.2.2004

Ch. 1: Dynamic Programming

1

ớ

Gi

ệ i thi u

° Dynamic programming

ằ ế ợ ờ i bài toán b ng cách k t h p các l i c a các bài toán con. i gi

°

ả ủ ậ

ị

ị ậ ả — gi ở — (  đâ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

ệ

— Gi

ằ i chúng b ng đ  quy, ờ ể ả ầ i gi i cho bài toán ban đ u.

ớ ả ộ ậ  , ° chia bài toán thành các bài toán con đ c l p ả ° gi ế ợ ° k t h p chúng đ  có l ậ ả 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 gi i đó

10.2.2004

Ch. 1: Dynamic Programming

2

ỉ ộ ầ i m i bài toán con ch  m t l n, và ghi nh  l ậ ỗ ộ ả ể ế ầ trong m t b ng đ  truy c p khi c n đ n.

Bài toán t

i  uố ư

° Tìm l

10.2.2004

Ch. 1: Dynamic Programming

3

ự ể ự ạ i  uố ư ° Bài toán t ể — có th  có nhi u l ả ỗ ờ — m i l i gi ả ờ i có tr  t i gi ả ề ờ i gi i ộ ị i có m t tr ị ố ư i  u (c c ti u hay c c đ i).

ắ ủ

Nguyên t c c a dynamic programming

ố ướ ự ộ ° M t gi c xây d ng qua b n b c:

ủ ả i thu t dynamic programming đ ị i t

ị ả ố ư i gi i t

i  u. i lên (“bottom­up”).

10.2.2004

Ch. 1: Dynamic Programming

4

ờ ậ ấ 1. Xác đ nh c u trúc c a m t l ệ 2. Đ nh nghĩa đ  quy cho  ộ ờ ủ 3. Tính giá trị c a m t l ả  t 4. Xây d ng ự l i i gi ượ ả ố ư ộ ờ i gi i  u. ộ ờ ủ giá trị c a m t l ả ố ư ừ ướ i gi i t  d i  u t ố ư ừ  các thông tin đã tính. i  u t

ậ Nhân m t chu i ma tr n

° Cho m t chu i ma tr n

ộ ỗ

(cid:0) (cid:0) (cid:0) ủ ậ ị ị ° Xác đ nh tích i thu t xác đ nh tích c a hai ma

ỗ ộ ậ (cid:0) A1, A2,..., An (cid:0) . ả ự  An d a trên gi

A1A2

° Bi u di n cách tính tích c a m t chu i ma tr n b ng cách “ ặ

tr n.ậ ể ủ ễ ộ ỗ ằ ữ đ t gi a

ủ ậ ậ ặ ớ ậ ẽ ượ c nhân v i nhau. ế fully parenthesized n u nó là ộ ° M t tích c a m t chu i ma tr n là

ậ ộ

ủ ỗ ngo cặ ” (parenthesize) các c p ma tr n s  đ ỗ ộ ặ — m t ma tr n ho c là — tích c a hai tích c a chu i ma tr n ậ fully parenthesized khác, và

ặ

Ví d : m t vài tích c a chu i ma tr n đ

ậ ượ ủ ỗ c fully parenthesized

10.2.2004

Ch. 1: Dynamic Programming

5

ủ ữ ượ ặ c đ t gi a ngo c. đ ộ ụ — A — (AB) — ((AB)C).

ỗ

ụ ỗ

Chu i ma tr n fully parenthesized ộ ° Ví d : Cho m t chu i ma tr n

ậ ậ (cid:0) A1 , A2 , A3 , A4

(cid:0) . Tích A1A2A3A4 có th  ể

đ c ượ fully parenthesized theo đúng 5 cách khác nhau:

10.2.2004

Ch. 1: Dynamic Programming

6

(A1(A2(A3A4))) (A1((A2A3)A4)) ((A1A2)(A3A4)) ((A1(A2A3))A4) (((A1A2)A3)A4)

Nhân hai ma tr nậ

ủ

ậ A và B v iớ p (cid:0) q (cid:0) q  r

° Tích c a hai ma tr n  — A có chi u là  — B có chi u là  là m t ma tr n

ươ

rows[B] ề

ng thích”

1 to rows[A]

1 to columns[B]   0  1 to columns[A]

C[i, j] + A[i, k](cid:0) B[k, j]

MATRIX­MULTIPLY(A, B) 1   if columns[A] (cid:0) 2       then error “các chi u không t 3       else for i (cid:0) 4                     do for j (cid:0) 5                                do C[i, j] (cid:0) 6                                     for k (cid:0) 7                                           do C[i, j] (cid:0) 8               return C

ề ộ ề ề ậ C có chi u là p (cid:0) r.

ờ ể ỷ ệ ớ ố ướ ự v i s  phép nhân vô h ng th c thi trong

° Th i gian đ  tính  dòng 7, t c là

10.2.2004

Ch. 1: Dynamic Programming

7

ứ p (cid:0) C t  q (cid:0) l  r .

ể

ổ

ộ

ỗ

ậ Phí t n đ  nhân m t chu i ma tr n

ậ ặ ỗ ộ ộ

ậ ° Nh n xét : Phí t n nhân m t chu i ma tr n tùy thu c vào cách đ t  ặ ữ

ổ gi a ngo c (parenthesization). ỗ ụ

° Ví d : Cho chu i ma tr n  ủ c a các ma tr n là 10

(cid:0) ậ (cid:0)  trong đó các chi u (dimension)  ề  5, và 5 (cid:0)

Có đúng 2 cách đ  đóng ngo c hoàn toàn tích

ậ (cid:0) A1 , A2 , A3  100, 100 (cid:0) ặ ể 50 A1A2A3 :

— Cách 1: ((A1A2)A3) ầ

5 = 5000 phép nhân vô h

ngướ

(cid:0)

ế

ầ

° Tính A1A2 c n 10  ° K  đó nhân

50 = 2500 phép nhân vô h

ngướ

100 (cid:0) A1A2 v iớ  A3 c n 10

ộ

5 (cid:0) ướ

° T ng c ng: 7500 phép nhân vô h

ng

(cid:0)

ổ — Cách 2: (A1(A2A3)) ầ

50 = 25000 phép nhân vô h

ngướ

(cid:0)

ầ

100 (cid:0)

50 = 50000 phép nhân vô

5 (cid:0) A1 v iớ  A2A3 c n 10

h

° Tính A2A3 c n 100  ế ° K  đó nhân  ngướ ổ

ộ

ướ

° T ng c ng: 75000 phép nhân vô h

ng.

10.2.2004

Ch. 1: Dynamic Programming

8

(cid:0)

ỗ

ậ Bài toán nhân chu i ma tr n

ề ủ ậ (cid:0)  g m ồ n ma tr n, trong đó chi u c a ỗ ° Cho chu i ma tr n

(cid:0) Ai là pi(cid:0) 1

° Bài toán: Xác đ nh m t đóng ngo c hoàn toàn cho tích

(cid:0) (cid:0) ị (cid:0) An sao A1A2

ướ ố ậ (cid:0) A1, A2,..., An  pi , v i ớ i = 1, 2,…, n. ộ cho s  phép nhân vô h ng là t

° Gi

10.2.2004

Ch. 1: Dynamic Programming

9

ả ặ ố ể i thi u. ạ ằ i bài toán trên b ng cách vét c n?

ế

ố

ặ Đ m s  cách đóng ngo c

° Cho m t chu i g m

ộ

ộ ạ ặ ằ ậ ° Nh n xét

(cid:0) (cid:0) (cid:0) ỗ tách (split) gi a ữ Ak   Ak và Ak+1  A1A2

(cid:0) (cid:0) (cid:0) ỗ

ặ ố

— n u ế n = 1 thì ch  có m t cách đóng ngo c (không c n d u ngo c

ỗ ồ n ma tr n ậ (cid:0) A1 , A2 , A3 ,..., An (cid:0) . : t o ra m t cách đóng ngo c b ng cách  ạ và Ak+1 , v i ớ k = 1, 2,..., n ­ 1, t o ra hai chu i con  ỗ ặ  An , sau đó đóng ngo c m i chu i con. ộ ° G i ọ P(n) là s  các cách đóng ngo c cho m t chu i  ặ ỗ n ma tr nậ ấ ầ ặ

n

(cid:0)

(cid:0) (cid:0) (cid:0) ỉ ộ ậ P(1) = 1. ừ ậ  nh n xét trên ta có knPkP ( ng minh). V y   2 thì t 1 )( ườ t — n u ế n (cid:0) nP )(

)

k

1

(cid:0)

n /4(

ừ c: (cid:0) (cid:0) ứ T  đó ch ng minh đ 2/3n

nP )(

ượ )

° V y dùng ph

ậ ươ ệ

10.2.2004

Ch. 1: Dynamic Programming

10

ặ ố ư ầ ặ ể ấ ả t c  các cách đóng  ừ ạ ờ ạ ng pháp vét c n duy t qua t ộ ngo c đ  tìm m t đóng ngo c t i  u c n th i gian ch y lũy th a.

ặ ố ư

ướ

ấ

ộ

ủ B c 1: C u trúc c a m t đóng ngo c t

i  u

° B c 1 c a ph

ươ ng pháp dynamic programming là

ủ ị ấ i  u

ấ c u trúc con t ờ ả ố ư ừ ờ ả ướ — xác đ nh tính ch t  ự — d a vào đó xây d ng l i t ố ư i  u cho bài toán t các l i gi i

ự i gi ố ư i  u cho các bài toán con. t

Aj .

(cid:0) (cid:0) (cid:0) ậ ượ ừ c t tích Ai Ai+1

(cid:0) (cid:0) ộ ặ ố ư ấ ỳ ủ đây:Ở ° G iọ  Ai.. j là ma tr n có đ ậ ° Nh n xét (cid:0) Aj tách Ai Ai+1

i  u b t k  c a tích   k (cid:0) j :

(cid:0) (cid:0) (cid:0) (cid:0) Aj) : M t đóng ngo c t nó gi a ữ Ak và Ak+1, v i ớ k nào đó thõa i (cid:0)  Ak)(Ak+1 (cid:0)

(Ai Ai+1 (cid:0) ầ ậ Ai..k và Ak+1..j , sau đó ta nhân

ể

ặ ố ư ể ể ổ ộ ổ Ai..j . Do đó phí t n đ  tính tích  A1..k , c ng phí t n đ  tính

Nghĩa là đ u tiên ta tính các ma tr n  ố ể chúng v i nhau đ  có tích cu i cùng  ổ ừ i  u là phí t n đ  tính  t ể ổ Ak+1..n , c ng phí t n đ  nhân chúng v i nhau.

10.2.2004

Ch. 1: Dynamic Programming

11

ớ  đóng ngo c t ộ ớ

ặ ố ư

ướ

ế

ấ

ộ

ủ B c 1: C u trúc c a m t đóng ngo c t

i  u (ti p)

° C u trúc con t

(cid:0) (cid:0) ỗ ấ — Đóng ngo c c a chu i con “ti n t ” ề ố Ai Ai+1 (cid:0)

(cid:0) (cid:0) i

(cid:0) (cid:0) ượ ừ  Ak có đ   c t ặ ố ộ  Aj ph i là m t đóng ngo c t ả ả ằ ố ư i  u ặ ủ ặ ố ư ủ Ai Ai+1 (cid:0) i  u c a  ứ Ak . (Ch ng minh b ng ph n ch ng).

(cid:0) (cid:0) ặ ủ , đóng ngo c c a chu i con còn l

(cid:0) (cid:0) ộ ứ ạ Ak+1 Ak+2 (cid:0)  Aj có  i  ả  Aj ph i là m t đóng ỗ ặ ố ư ủ Ai Ai+1 (cid:0) i  u c a

(cid:0) (cid:0)

° Đ  cho g n, s  nói “phí t n c a m t đóng ngo c” thay vì nói “phí

ặ ọ

ặ

° Xây d ng l

ể ự ờ ẽ ể ổ t n đ  tính tích t i gi i  u

i gi

ả

C n tìm v  trí thích h p (tr  c a

(cid:0) (cid:0) (cid:0) ả ố ư i  u cho m i bài toán con ờ i gi ợ ỗ ượ ở  trên. c  i tìm đ ể ỗ ị ủ k) đ  tách chu i ma tr n ậ Ai Ai+1

Ch. 1: Dynamic Programming

12

đóng ngo c t ư ủ Ai Ai+1 (cid:0) u c a   ự ươ ng t — T ượ ừ  đóng ngo c t đ c t ặ ố ư ủ Ak+1 Ak+2 (cid:0)  Aj . i  u c a  ngo c t ộ ổ ủ ừ ộ  m t đóng ngo c”. ả ố ư i t — Chia bài toán thành hai bài toán con ờ i t — Tìm l ế ợ — K t h p các l ị ầ Aj ! 10.2.2004

ướ

ả ệ

B c 2: Gi

i đ  quy

ủ

ng pháp dynamic programming là ị ủ ộ ờ ổ ả ố ư i gi i  u tùy theo i t

° B c 2 c a ph ị các l

ờ

ị ặ i gi ° Bài toán con

(cid:0) (cid:0) (cid:0) (cid:0) ươ ệ ả ố ư ủ i t  đâyở ỗ ủ c a chu i ma tr n n. ậ Ai Ai+1

° Đ nh nghĩa

ị ộ i thi u cho m t đóng ngo c   i (cid:0) ướ ể ướ — đ nh nghĩa đ  quy phí t n (tr ) c a m t l i  u c a các bài toán con. ổ ố : Xác đ nh phí t n t  Aj  v i 1 ớ m[i, j] là s  phép nhân vô h ể  j (cid:0) ố t ng ể  đ  tính ma i thi u

ệ ố t hai tr

(cid:0) (cid:0) ậ ớ i = 1,..., n, ườ ợ ng h p: (cid:0) Aj = Ai . V y, v i

m[i, j] = m[i, k] + m[k + 1, j] + pi(cid:0) 1 pk pj .

tr n ậ Ai..j . Phân bi — n u ế i = j thì Ai Ai+1   m[i, i] = 0. — n u ế i < j thì t ừ ướ  b c 1 ta có

10.2.2004

Ch. 1: Dynamic Programming

13

ạ ư   Nh ng l ư i ch a bi ế ị ủ k! t tr  c a

ướ

ả ệ

ế

B c 2: Gi

i đ  quy (ti p)

B ng cách duy t qua t

ấ ả ệ t c  các tr  c a ị ủ k, i (cid:0) k (cid:0) j ­ 1, ta tìm

đ

j (cid:0) 1 {m[i, k] + m[k + 1, j] + pi(cid:0) 1 pk pj}.

k (cid:0)

ằ cượ   m[i, j] = mini (cid:0)

ạ ả ố ư i t

(cid:0) (cid:0) ể ° Đ  ghi l ị ể ộ ị ủ s[i, j] là tr  c a  ặ ố ư i  u. ị i  u ta đ nh nghĩa   Aj đ  có m t đóng ngo c t

ờ ự i gi ỗ Ai Ai+1 (cid:0) ộ ị k sao cho

10.2.2004

Ch. 1: Dynamic Programming

14

i cách xây d ng l ơ k xác đ nh n i tách chu i  Nghĩa là s[i, j] là m t tr     m[i, j] = m[i, k] + m[k + 1, j] + pi(cid:0) 1 pk pj .

ướ

B c 3: Tính các chi phí t

ố ư i  u

° B c 3 c a ph

ươ

ng pháp dynamic programming là tính chi phí t ả ộ ươ ố i  i lên (bottom­up) và dùng b ng. ng pháp t ừ ướ  d

— Có th  vi

ự ộ

ể

(cid:0) (cid:0) (cid:0) ậ ệ i  u  ẽ ấ ậ ạ ệ ả i thu t đ  quy (d a trên hàm đ   ổ ố ư m[1, n] cho tính tích A1A2  ả i thu t này ch y c ngay m t gi c) đ  tính phí t n t  An . Nh ng sau này chúng ta s  th y là gi

10.2.2004

Ch. 1: Dynamic Programming

15

ừ ờ ướ ủ ư ằ u b ng m t ph ậ : ° Nh n xét ể ế ượ t đ ượ quy đã tìm đ ư trong th i gian lũy th a.

ướ

ố ư

ế

B c 3: Tính các chi phí t

i  u (ti p)

°

° Ma tr n ậ Ai có chi u là  ộ Input là m t chu i

(cid:0) ề pi(cid:0) 1 pi , v i ớ i = 1, 2,..., n .

ỗ p = < p0 , p1,..., pn >

° Gi

0

1 to n (cid:0)  l + 1  i + l (cid:0)  1  (cid:0)  i to j (cid:0)  1

m[i, k] + m[k + 1, j] + pi(cid:0) 1 pk pj

q  k

MATRIX­CHAIN­ORDER(p) n (cid:0)  length[p] (cid:0)  1   1 for i (cid:0)  1 to n   2         do m[i, i] (cid:0)   3 for l (cid:0)  2 to n   4         do for i (cid:0)   5                     do j (cid:0)   6                          m[i, j] (cid:0)   7                          for k (cid:0)   8                                do q (cid:0)   9                                     if q < m[i, j] 10                                         then m[i, j] (cid:0) 11                                                  s[i, j] (cid:0) 12 return m and s 13

10.2.2004

Ch. 1: Dynamic Programming

16

ả ậ ả ề i thu t tr  v  hai b ng ả m[1..n, 1..n] và s[1..n, 1..n].

Phân tích MATRIX­CHAIN­ORDER

10.2.2004

Ch. 1: Dynamic Programming

17

ạ ủ ộ ậ ầ ờ ATRIX­CHAIN­ORDER là O(n3). ° Th i gian ch y c a M ớ (cid:0) (n2) cho các b ng ả m và s. ả i thu t c n b  nh   ° Gi

ụ

ộ

Ch y Mạ

35  15  5  10

ATRIX­CHAIN­ORDER lên m t ví d chi uề 30 (cid:0) 35 (cid:0) 15 (cid:0) 5 (cid:0) 10 (cid:0) 20 (cid:0)

20  25

ma tr nậ A1 A2 A3  A4  A5  A6  c:ượ

° Các b ng ả m và s tính đ

s

m

15,125

3

j

i

11,875

10,500

3

3

j

i

9,375

7,125

5,375

3

3

3

7,875

4,375

2,500

3,500

1

3

3

5

15,750

2,625

750

1,000

5,000

1

3

2

4

5

0

0

0

0

0

0

A1        A2       A3       A4        A5       A6

10.2.2004

Ch. 1: Dynamic Programming

18

ộ ờ

ướ

ự

B c 4: Xây d ng m t l

i gi

ả ố ư i  u

i t

° B ng ả

ATRIX­

ữ ộ ặ ố ư s[1..n, 1..n] tr  m t cách đóng ngo c t i  u do M

CHAIN­ORDER tìm ra.

ả ề ủ ụ ° Th  t c sau, M

ỗ ủ ATRIX­CHAIN­MULTIPLY, tr  v  tích c a chu i ma  (cid:0) , b ng ả ỉ ố i và j. s, và các ch  s tr n ậ Ai..j khi cho A = (cid:0) A1 , A2 , A3 ,..., An

MATRIX­CHAIN­MULTIPLY(A, s, i, s[i, j])  MATRIX­CHAIN­MULTIPLY(A, s, s[i, j] + 1, j)

MATRIX­CHAIN­MULTIPLY(A, s, i, j) 1 2 3 4 5 if j > i     then X (cid:0)              Y (cid:0)              return MATRIX­MULTIPLY(X, Y)     else return Ai

ATRIX­CHAIN­MULTIPLY(A, s, 1, n) đ  tính tích c a chu i ma

° G i Mọ tr n ậ A.

10.2.2004

Ch. 1: Dynamic Programming

19

ủ ể ỗ

ế ố ể

ụ

Các y u t

đ  áp d ng dynamic programming

° Hai y u t

ươ ượ ng pháp dynamic programming c ph đ  áp d ng đ

ụ ố ư i  u ố ư i  u”

10.2.2004

Ch. 1: Dynamic Programming

20

ế ố ể ộ vào m t bài toán t ấ — “C u trúc con t — “Các bài toán con trùng nhau”.

ộ ờ

ả

ố ư

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.

RECURSIVE­MATRIX­CHAIN(p, i, j) 1 2 3 4 5

q

10.2.2004

Ch. 1: Dynamic Programming

21

6 7 8 if i = j      then return 0  (cid:0) m[i, j] (cid:0)  i to j (cid:0)  1 for k (cid:0) do q (cid:0)  RECURSIVE­MATRIX­CHAIN(p, i, k)                    + RECURSIVE­MATRIX­CHAIN(p, k + 1, j) + pi(cid:0) 1 pk pj      if q < m[i, j]          then m[i, j] (cid:0) return m[i, j]

Phân tích RECURSIVE­MATRIX­CHAIN

ECURSIVE­MATRIX­CHAIN(p, 1, n),

° G i ọ T(n) là th i gian ch y c a R ạ ủ ờ ỏ thì T(n) ph i th a (xem code) 1)1(

(cid:0) ả T

n

1

(cid:0)

nT

knT

1)(

kT )((

(

)1)

n for

1.

k

1

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

ượ T(n) = (cid:0) c:

(cid:0) (2n). ạ ờ (2n) còn

ố ứ ậ ệ i thu t đ  quy t trên xu ng

ả ượ ậ ụ ấ ừ c tính ch t “các bài toán con

ứ ừ T  đó ch ng minh đ ạ ECURSIVE­MATRIX­CHAIN ch y trong th i gian  ° T i sao R ờ ỉ ầ MATRIX­CHAIN­ORDER ch  c n th i gian đa th c? Đó là vì — RECURSIVE­MATRIX­CHAIN là gi (top­down) và không t n d ng đ trùng nhau” (overlapping subproblems).

ừ

ả — MATRIX­CHAIN­ORDER là gi ậ ụ i thu t dynamic­programming t ấ ậ ượ ướ i lên (bottom­up), t n d ng đ c tính ch t “các bài toán con

10.2.2004

Ch. 1: Dynamic Programming

22

d trùng nhau”.

ệ Cây đ  quy

ECURSIVE­MATRIX­CHAIN(p, 1, 4)

1..4

1..1

2..4

1..2

3..4

1..3

4..4

4..4

1..1

2..3

1..2

3..3

3..4

2..3

4..4

1..1

2..2

3..3

2..2

3..3

4..4

2..2

3..3

2..2

3..3

1..1

2..2

10.2.2004

Ch. 1: Dynamic Programming

23

ệ ° Cây đ  quy cho R

ủ

ế

ạ

ộ

memoization

M t bi n d ng c a dynamic programming:

° Memoization là ph

ấ

ằ

ng pháp t n d ng tính ch t “các bài toán con  ừ  trên xu ng b ng cách  ọ ủ ậ ụ ậ ệ i thu t đ  quy t ỗ ươ ể ả ế ộ ả ệ ả ố ả trùng nhau” đ  c i ti n gi — s  d ng m t b ng chung mà m i tri u g i c a gi ậ ệ i thu t đ

ậ ể

ả ộ

10.2.2004

Ch. 1: Dynamic Programming

24

ử ụ ể quy có th  truy c p đ ế ọ ế ượ ả ồ ả ° ghi k t qu  sau khi gi ộ ả ủ ° đ c k t qu  c a m t bài toán con đã đ ớ i m t bài toán con m i c gi i r i.

ả

Memoize gi

i thu t R

ậ ECURSIVE­MATRIX­CHAIN

° Memoize gi

ả ử ụ ằ i thu t R ậ ECURSIVE­MATRIX­CHAIN b ng cách s  d ng

b ng ả m[1..n, 1..n].

° MEMOIZED­MATRIX­CHAIN có input là m t chu i

ộ ỗ p = < p0 , p1,..., pn >

(cid:0)

10.2.2004

Ch. 1: Dynamic Programming

25

MEMOIZED­MATRIX­CHAIN(p) 1 2 3 4 5 n (cid:0)  length[p] (cid:0)  1 for i (cid:0)  1 to n        do for j (cid:0)  i to n                   do m[i, j] (cid:0) return LOOKUP­CHAIN(p, 1, n)

Memoization

° LOOKUP­CHAIN bao gi

ỉ cũng tr  v m[i, j]

ầ ờ ọ ầ khi nào đó là l n g i đ u tiên v i các tham s ư ả ề m[i, j]. Nh ng nó ch  tính  ố i và j. ớ

0

i to j (cid:0)  1

LOOKUP­CHAIN(p, i, j) 1 2 3 4 5 6

q

10.2.2004

Ch. 1: Dynamic Programming

26

7 8 9 if m[i, j] < (cid:0)     then return m[i, j]  if i = j      then m[i, j] (cid:0) else for k (cid:0)               do q (cid:0)  LOOKUP­CHAIN(p, i, k)                            + LOOKUP­CHAIN(p, k + 1, j) + pi(cid:0) 1 pk pj                     if q < m[i, j]                         then m[i, j] (cid:0) return m[i, j]

Phân tích MEMOIZED­MATRIX­CHAIN

° MEMOIZED­MATRIX­CHAIN ch y trong th i gian  ậ : ° Nh n xét

ạ ờ O(n3).

— MEMOIZED­MATRIX­CHAIN t n d ng đ

ậ ụ ượ ấ c tính ch t “các bài

toán con trùng nhau”,

— còn RECURSIVE­MATRIX­CHAIN ch y trong th i gian

(cid:0) ạ ờ

ể

10.2.2004

Ch. 1: Dynamic Programming

27

ư (2n) vì nó  ả i các bài toán con mà không đ  ý xem bài toán con  ả ồ i r i hay ch a. luôn luôn gi ượ c gi đã đ

Phân tam giác

° Đa giác

° Đa giác đ nơ  (“simple”)

° Đa giác l

° Phân tam giác (triangulation)

10.2.2004

Ch. 1: Dynamic Programming

28

iồ

ơ ả ệ Các khái ni m c  b n

ủ ộ

ỉ i ứ ự

° C nhạ , đ nhỉ , biên c a m t đa giác ồ P b ng danh sách các đ nh theo th  t ằ ộ ễ ể ° Ta bi u di n m t đa giác l ồ P = (cid:0) v0 , v1,..., vn(cid:0) 1 ề ượ c chi u kim đ ng h :

(cid:0) ồ ng

ủ ộ

° 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

ủ ợ ộ

10.2.2004

Ch. 1: Dynamic Programming

29

ờ ộ ậ ủ giác chia đa giác thành các tam giác r i nhau.

Bài toán phân tam giác t

i  uố ư

° Cho:

— M t đa giác

ộ l (cid:0) iồ  P = (cid:0) v0 , v1 ,..., vn(cid:0) 1

— M t hộ àm tr ng s

ọ ượ ị c đ nh nghĩa trên

ố w (“weight function”) đ ủ P. ở ạ các tam giác t o b i c nh và cung c a

ố ủ ọ ạ ộ ° 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

ấ ỏ

ọ

10.2.2004

Ch. 1: Dynamic Programming

30

ổ 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.

ủ

ễ

ộ

ứ Parse tree c a m t bi u th c

ễ ậ ỗ ộ ượ ễ ° Bi u th c. — Ví d  m t bi u th c: tích c a m t chu i ma tr n đã đ c đóng

° Parse tree. ụ

ứ ụ ộ ặ ủ ứ A1(A2A3))(A4(A5 A6))) ngo c hoàn toàn ((

— Ví d : parse tree c a bi u th c ((

ứ ủ ễ A1(A2A3))(A4(A5 A6))) là

A1 A4

10.2.2004

Ch. 1: Dynamic Programming

31

A2 A3 A5 A6

ủ

ễ

ộ

ứ Parse tree c a m t bi u th c

° Đ nh nghĩa:

ủ ễ ộ ộ ứ  là m t cây mà

ử ụ (“atomic element”, ví d :

ứ ễ ạ ị parse tree c a m t bi u th c ộ ả — Lá: có nh n là m t trong các nguyên t A1) t o nên bi u th c.

ộ ễ ng tr ng bi u th c ứ El và có cây con bên ph i t

10.2.2004

Ch. 1: Dynamic Programming

32

ượ ư ễ ả ượ ng tr ng 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  ư ng tr ng  ứ ElEr). ố ủ ế ư ượ t ứ Er , thì cây con này t ễ bi u th c

ừ

T  phân tam giác sinh ra parse tree

° Ví d : Parse tree cho đa giác

ụ (cid:0)  sau. P = (cid:0) v0 , v1,…, v6

v0

A1

v1 v6

A6 A2

v5 v2

A3 A5

v3

10.2.2004

Ch. 1: Dynamic Programming

33

A4 v4

ừ

T  parse tree sinh ra phân tam giác

° Cho parse tree bi u di n b i (((

ể ễ ở A1(A2A3))A4)(A5 A6)). Phân tam giác

ươ ứ t ng  ng:

v0

A1

v1 v6

A6 A2

v5 v2

A3 A5

10.2.2004

Ch. 1: Dynamic Programming

34

v3 A4 v4

ươ ứ

ữ

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

ủ ộ ồ ạ ươ ứ i có n + 1 c nh t ng  ng

ươ ứ ớ ủ ộ ộ v i m t parse tree. — M i parse tree có ng  ng v i phân tam giác c a m t đa

10.2.2004

Ch. 1: Dynamic Programming

35

ồ ươ ứ ộ : ộ ố m t­đ i­m t ỗ — M i phân tam giác c a m t đa giác l ớ ỗ giác l n lá t n + 1 c nh.ạ i có

ươ ứ

ữ

ặ

T

ủ n ma

ậ

ủ ng  ng gi a đóng ngo c hoàn toàn c a tích c a  tr n và phân chia tam giác

ặ ủ ậ ươ ứ ớ ng  ng v i phân

ộ

(cid:0) (cid:0) (cid:0) ươ ứ ớ ạ ng  ng v i c nh ủ n ma tr n t ỉ n + 1 đ nh.  An t vi­1vi

° Đóng ngo c hoàn toàn c a tích c a  ủ chia tam giác c a m t đa giác có  ậ Ai trong tích A1A2  — M i ma tr n   n + 1 đ nh. ươ ứ

ộ ỉ

10.2.2004

Ch. 1: Dynamic Programming

36

ớ ng  ng v i ma tr n ỗ ủ c a m t đa giác có — Cung vivj  , v iớ  i <  j, t ậ Ai +1.. j .

ậ

ỗ

ố ư

Nhân chu i ma tr n và phân tam giác t

i  u

ậ ộ ườ ặ ợ ệ ủ ng h p đ c bi t c a bài toán

An thông qua m t bài toán phân tam giác t

(cid:0) (cid:0) (cid:0) ộ ố i ỗ ° Bài toán nhân chu i ma tr n là m t tr ố ư phân tam giác t i  u. — Tính tích A1A2

u:ư

° Đ nh nghĩa m t đa giác l

(cid:0) ỉ ộ ị ồ i có n + 1 đ nh

(cid:0) ị ế P = (cid:0) v0 , v1,…, vn  pi , v i ớ i = 1, 2,..., n, đ nh ậ Ai có dimension pi(cid:0) 1

ố w cho phân tam giác là nghĩa hàm tr ng s

ố ư ủ P cho ta parse tree c a ủ i  u c a

° N u ma tr n  ọ   w((cid:0) vivjvk ) = pi pj pk ộ ° M t phân chia tam giác t ộ

An .

10.2.2004

Ch. 1: Dynamic Programming

37

(cid:0) (cid:0) (cid:0) m t đóng ngo c t ặ ố ư ủ A1A2  i  u c a

ậ

ỗ

ố ư

ế

Nhân chu i ma tr n và phân tam giác t

i  u (ti p)

ượ ạ c l i là không đúng: bài toán phân tam giác t ợ ệ ủ ỗ ố ư i  u không là  ậ t c a bài toán nhân chu i ma tr n. ng h p đ c bi

° Ng ườ tr — M c dù v y, có th  ch nh l

ặ ạ i M i bài

ể ỉ ố ư ỉ ặ ậ toán phân tam giác t

n + 1 đ nh nh  sau ề ủ

ể ả ATRIX­CHAIN­ORDER đ  gi ư ộ i  u cho m t đa giác có  ậ ° Thay chu i ỗ p = < p0 , p1,..., pn > c a các chi u c a ma tr n  ủ ỉ ằ ủ (cid:0)  c a các đ nh. b ng chu i

9

ằ ậ ỗ (cid:0) v0 , v1 ,..., vn  ậ ° Thay các truy c p đ n ế p b ng các truy c p đ n ế v và thay

m[i, k] + m[k + 1, j] + w(Dvi(cid:0) 1 vk vj )

° Khi gi

ậ ố ủ ứ ộ ọ m[1, n] ch a tr ng s  c a m t

10.2.2004

Ch. 1: Dynamic Programming

38

ấ ạ ầ ượ dòng 9 b iở do q (cid:0) ự ả i thu t th c thi xong,  ố ư i  u. phân tam giác t i sao làm đ — Ph n sau cho th y t ư ậ c nh  v y.

ướ

ấ

ộ

ố ư

ủ B c 1: C u trúc con c a m t phân tam giác t

i  u

ủ i  uố ư  c a m t đa giác  t

v0

vn

v1

v2

vk

ứ ộ ° Cho T là m t phân tam giác  (cid:0)  , T ch a tam giác D k (cid:0) P = (cid:0) v0 , v1,…,   n (cid:0)  1. vn ộ v0vkvn v i ớ k nào đó, 1 (cid:0)

° Tr ng s  c a

ố ủ ủ ọ ọ ổ ố ủ T là t ng c a các tr ng s  c a tam giác D

ứ ủ v0vkvn và các  (cid:0)

ọ ộ (cid:0) v0, v1,…, vk ố (cid:0) . M t đa giác con suy thoái có tr ng s  là 0. tam giác ch a trong phân tam giác c a hai đa giác con  và (cid:0) vk , vk+1,…, vn

° Do đó các phân tam giác (xác đ nh b i

ị

10.2.2004

Ch. 1: Dynamic Programming

39

ả ố ư ứ ở 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.)

ướ

ờ

ả ệ

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

° Xác đ nh

i  u c a đa  ố ư ọ ư ậ ố ủ ọ ộ ộ ố ư ủ (cid:0) . Nh  v y tr ng s  c a m t phân tam giác t ố ủ i  u

P là t[1, n]. ,(cid:0) ]

— n u đa giác ch  có 2 đ nh (đa giác suy thoái)

giác (cid:0) vi(cid:0) 1,vi ,…, vj ủ c a đa giác  t[(cid:0) ị ế ỉ ỉ

t[i, i] = 0

— n u đa giác có ít nh t 3 đ nh,

ế cho i = 1,..., n ỉ ấ i < j

t[i, j] = t[i, k] + t[k + 1, j] + w((cid:0) vi(cid:0) 1vkvj) .

10.2.2004

Ch. 1: Dynamic Programming

40

ạ ư   Nh ng l ư i ch a bi ế ị ủ k! t tr  c a

ướ

ờ

ả ệ

ế

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 (cid:0) k (cid:0) j ­ 1, ta nh n ậ

i = 1,..., n

ệ  hàm đ  quy m[(cid:0)

j(cid:0) 1 {t[i, k] + t[k + 1, j] + w((cid:0) vi(cid:0) 1vkvj)} ng t i thi u đ  tính

(cid:0) (cid:0) (cid:0) ướ ố ể ằ cượ đ t[i, i] = 0, t[i, j] = min i (cid:0)  k (cid:0) ươ ệ ° Hàm đ  quy này t ể ng t

Aj . Do đó có th  ch nh l ọ ố ể ỉ ố ủ ự Ai Ai+1 ư ể

n u ế i < j . ,(cid:0) ] cho s  phép nhân vô  ủ ụ ạ i th  t c  h ộ MATRIX­CHAIN­ORDER (nh  đã nói) đ  tính tr ng s  c a m t phân  tam giác t

ố ư ạ ờ i  u ch y trong th i gian O(n3) và c n ầ

10.2.2004

Ch. 1: Dynamic Programming

41

ậ ộ ố ư i  u. ° V y th  t c phân tam giác t (n2). ủ ụ ớ (cid:0) b  nh