際際滷

際際滷Share a Scribd company logo

Qhd

Download as DOC, PDF
Th畛 Tuy畉t L棚 L棚
Th畛 Tuy畉t L棚 L棚

quy hoach dong

1 of 6
Download to read offline
1. Ph動董ng ph叩p quy ho畉ch 畛ng Ph動董ng ph叩p quy ho畉ch 畛ng c湛ng nguy棚n l箪 t畛i 動u 動畛c nh to叩n h畛c M畛 R.Bellman 畛 xu畉t vo nh畛ng nm 50 c畛a th畉 k畛 20. Ph動董ng ph叩p ny 達 動畛c 叩p d畛ng 畛 gi畉i hng lo畉t bi to叩n th畛c t畉 trong c叩c qu叩 tr狸nh k畛 thu畉t c畛ng ngh畛, t畛 ch畛c s畉n xu畉t, k畉 ho畉ch ho叩 kinh t畉垂 Tuy nhi棚n c畉n l動u 箪 r畉ng c坦 m畛t s畛 bi to叩n m c叩ch gi畉i b畉ng quy ho畉ch 畛ng t畛 ra kh担ng th鱈ch h畛p. Trong th畛c t畉, ta th動畛ng g畉p m畛t s畛 bi to叩n t畛i 動u lo畉i sau: C坦 m畛t 畉i l動畛ng f h狸nh thnh trong m畛t qu叩 tr狸nh g畛m nhi畛u giai o畉n v ta ch畛 quan t但m 畉n k畉t qu畉 cu畛i c湛ng l gi叩 tr畛 c畛a f ph畉i l畛n nh畉t ho畉c nh畛 nh畉t, ta g畛i chung l gi叩 tr畛 t畛i 動u c畛a f. Gi叩 tr畛 c畛a f ph畛 thu畛c vo nh畛ng 畉i l動畛ng xu畉t hi畛n trong bi to叩n m m畛i b畛 gi叩 tr畛 c畛a ch炭ng 動畛c g畛i l m畛t tr畉ng th叩i c畛a h畛 th畛ng v ph畛 thu畛c vo c叩ch th畛c 畉t 動畛c gi叩 tr畛 f trong t畛ng giai o畉n m m畛i c叩ch t畛 ch畛c 動畛c g畛i l m畛t i畛u khi畛n. 畉i l動畛ng f th動畛ng 動畛c g畛i l hm m畛c ti棚u v qu叩 tr狸nh 畉t 動畛c gi叩 tr畛 t畛i 動u c畛a f 動畛c g畛i l qu叩 tr狸nh i畛u khi畛n t畛i 動u. Bellman ph叩t bi畛u nguy棚n l箪 t畛i 動u (c滴ng g畛i l nguy棚n l箪 Bellman) m 箪 t動畛ng c董 b畉n l nh動 sau: V畛i m畛i qu叩 tr狸nh i畛u khi畛n t畛i 動u, 畛i v畛i tr畉ng th叩i b畉t 畉u A0, v畛i tr畉ng th叩i A trong qu叩 tr狸nh 坦, ph畉n qu叩 tr狸nh k畛 t畛 tr畉ng th叩i A xem nh動 tr畉ng th叩i b畉t 畉u c滴ng l t畛i 動u. Ch炭 箪 r畉ng nguy棚n l箪 ny 動畛c th畛a nh畉n m kh担ng ch畛ng minh. Ph動董ng ph叩p t狸m i畛u khi畛n t畛i 動u theo nguy棚n l箪 Bellman th動畛ng 動畛c g畛i l quy ho畉ch 畛ng. Thu畉t ng畛 ny n坦i l棚n th畛c ch畉t c畛a qu叩 tr狸nh i畛u khi畛n l 畛ng: c坦 th畛 trong m畛t s畛 b動畛c 畉u ti棚n l畛a ch畛n i畛u khi畛n t畛i 動u d動畛ng nh動 kh担ng t畛t nh動ng t畛u chung c畉 qu叩 tr狸nh l畉i l t畛t nh畉t. Ta c坦 th畛 gi畉i th鱈ch 箪 ny qua bi to叩n sau: Cho m畛t d達y N s畛 nguy棚n A1, A2,,AN. H達y t狸m c叩ch xo叩 i m畛t s畛 鱈t nh畉t s畛 h畉ng 畛 d達y c嘆n Trang 1
l畉i l 董n i畛u hay n坦i c叩ch kh叩c h達y ch畛n m畛t s畛 nhi畛u nh畉t c叩c s畛 h畉ng sao cho d達y B g畛m c叩c s畛 h畉ng 坦 theo tr狸nh t畛 xu畉t hi畛n trong d達y A l 董n i畛u. Qu叩 tr狸nh ch畛n B 動畛c i畛u khi畛n qua N giai o畉n 畛 畉t 動畛c m畛c ti棚u l s畛 l動畛ng s畛 h畉ng c畛a d達y B l nhi畛u nh畉t, i畛u khi畛n 畛 giai o畉n i th畛 hi畛n vi畛c ch畛n hay kh担ng ch畛n Ai vo d達y B. Gi畉 s畛 d達y 達 cho l 1 8 10 2 4 6 7. N畉u ta ch畛n l畉n l動畛t 1, 8, 10 th狸 ch畛 ch畛n 動畛c 3 s畛 h畉ng nh動ng n畉u b畛 qua 8 v 10 th狸 ta ch畛n 動畛c 5 s畛 h畉ng 1, 2, 4, 6, 7. Khi gi畉i m畛t bi to叩n b畉ng c叩ch chia 畛 tr畛 chuy畛n vi畛c gi畉i bi to叩n k鱈ch th動畛c l畛n v畛 vi畛c gi畉i nhi畛u bi to叩n c湛ng ki畛u c坦 k鱈ch th動畛c nh畛 h董n th狸 thu畉t to叩n ny th動畛ng 動畛c th畛 hi畛n b畉ng c叩c ch動董ng tr狸nh con 畛 quy. Khi 坦, tr棚n th畛c t畉, nhi畛u k畉t qu畉 trung gian ph畉i t鱈nh nhi畛u l畉n. V畉y 箪 t動畛ng c董 b畉n c畛a quy ho畉ch 畛ng th畉t 董n gi畉n: tr叩nh t鱈nh to叩n l畉i m畛i th畛 hai l畉n, m l動u gi畛 k畉t qu畉 達 t狸m ki畉m 動畛c vo m畛t b畉ng lm gi畉 thi畉t cho vi畛c t狸m ki畉m nh畛ng k畉t qu畉 c畛a tr動畛ng h畛p sau. Ch炭ng ta s畉 lm 畉y d畉n gi叩 tr畛 c畛a b畉ng ny b畛i c叩c k畉t qu畉 c畛a nh畛ng tr動畛ng h畛p tr動畛c 達 動畛c gi畉i. K畉t qu畉 cu畛i c湛ng ch鱈nh l k畉t qu畉 c畛a bi to叩n c畉n gi畉i. N坦i c叩ch kh叩c ph動董ng ph叩p quy ho畉ch 畛ng 達 th畛 hi畛n s畛c m畉nh c畛a nguy棚n l箪 chia 畛 tr畛 畉n cao 畛. Quy ho畉ch 畛ng l k畛 thu畉t thi畉t k畉 bottom-up (t畛 d動畛i l棚n). N坦 動畛c b畉t 畉u v畛i nh畛ng tr動畛ng h畛p con nh畛 nh畉t (th動畛ng l 董n gi畉i nh畉t v gi畉i 動畛c ngay). B畉ng c叩ch t畛 h畛p c叩c k畉t qu畉 達 c坦 (kh担ng ph畉i t鱈nh l畉i) c畛a c叩c tr動畛ng h畛p con, s畉 畉t 畉t t畛i k畉t qu畉 c畛a tr動畛ng h畛p c坦 k鱈ch th動畛c l畛n d畉n l棚n v t畛ng qu叩t h董n, cho 畉n khi cu畛i c湛ng 畉t t畛i l畛i gi畉i c畛a tr動畛ng h畛p t畛ng qu叩t nh畉t. Trang 2
Trong m畛t s畛 tr動畛ng h畛p, khi gi畉i m畛t bi to叩n A, tr動畛c h畉t ta t狸m h畛 bi to叩n A(p) ph畛 thu畛c tham s畛 p (c坦 th畛 p l m畛t v辿c t董) m A(p0)=A v畛i p0 l tr畉ng th叩i ban 畉u c畛a bi to叩n A. Sau 坦 t狸m c叩ch gi畉i h畛 bi to叩n A(p) v畛i tham s畛 p b畉ng c叩ch 叩p d畛ng nguy棚n l箪 t畛i 動u c畛a Bellman. Cu畛i c湛ng cho p=p0 s畉 nh畉n 動畛c k畉t qu畉 c畛a bi to叩n A ban 畉u. 2. C叩c b動畛c th畛c hi畛n quy ho畉ch 畛ng B動畛c 1: L畉p h畛 th畛c D畛a vo nguy棚n l箪 t畛i 動u t狸m c叩ch chia qu叩 tr狸nh gi畉i bi to叩n thnh t畛ng giai o畉n, sau 坦 t狸m h畛 th畛c bi畛u di畛n t動董ng quan quy畉t 畛nh c畛a b動畛c ang x畛 l箪 v畛i c叩c b動畛c 達 x畛 l箪 tr動畛c 坦. Ho畉c t狸m c叩ch ph但n r達 bi to叩n thnh c叩c bi to叩n con t動董ng t畛 c坦 k鱈ch th動畛c nh畛 h董n, t狸m h畛 th畛c n棚u quan h畛 gi畛a k畉t qu畉 bi to叩n k鱈ch th動畛c 達 cho v畛i k畉t qu畉 c畛a c叩c bi to叩n con c湛ng ki畛u c坦 k鱈ch th動畛c nh畛 h董n c畛a n坦 nh畉m x但y d畛ng ph動董ng tr狸nh truy to叩n (d畉ng hm ho畉c th畛 t畛c 畛 quy). V畛 m畛t c叩ch x但y d畛ng ph動董ng tr狸nh truy to叩n: Ta chia vi畛c gi畉i bi to叩n thnh n giai o畉n. M畛i giai o畉n i c坦 tr畉ng th叩i ban 畉u l t(i) v ch畛u t叩c 畛ng i畛u khi畛n d(i) s畉 bi畉n thnh tr畉ng th叩i ti畉p theo t(i+1) c畛a giai o畉n i+1 (i=1,2,,n-1). Theo nguy棚n l箪 t畛i 動u c畛a Bellman th狸 vi畛c t畛i 動u giai o畉n cu畛i c湛ng kh担ng lm 畉nh h動畛ng 畉n k畉t qu畉 ton bi to叩n. V畛i tr畉ng th叩i ban 畉u l t(n) sau khi lm giai o畉n n t畛t nh畉t ta c坦 tr畉ng th叩i ban 畉u c畛a giai o畉n n-1 l t(n-1) v t叩c 畛ng i畛u khi畛n c畛a giai o畉n n-1 l d(n-1), c坦 th畛 ti畉p t畛c x辿t 畉n giai o畉n n-1. Sau khi t畛i 動u giai o畉n n-1 ta l畉i c坦 t(n-2) v d(n-2) v l畉i c坦 th畛 t畛i 動u giai o畉n n-2 cho 畉n khi c叩c giai o畉n t畛 n gi畉m 畉n 1 動畛c t畛i 動u th狸 coi nh動 hon thnh bi to叩n. G畛i gi叩 tr畛 t畛i 動u c畛a bi to叩n t鱈nh 畉n giai o畉n k l Fk gi叩 tr畛 t畛i 動u c畛a bi to叩n t鱈nh ri棚ng 畛 giai o畉n k l Gk th狸 Fk = Fk-1 + Gk Trang 3
Hay l: (*)}))1(())(),(({G))(( 1k )( 1 += ktFkdktaxmktF k kd B動畛c 2: T畛 ch畛c d畛 li畛u v ch動董ng tr狸nh T畛 ch畛c d畛 li畛u sao cho 畉t c叩c y棚u c畉u sau: D畛 li畛u 動畛c t鱈nh to叩n d畉n theo c叩c b動畛c. D畛 li畛u 動畛c l動u tr畛 畛 gi畉m l動畛ng t鱈nh to叩n l畉p l畉i. K鱈ch th動畛c mi畛n nh畛 dnh cho l動u tr畛 d畛 li畛u cng nh畛 cng t畛t, ki畛u d畛 li畛u 動畛c ch畛n ph湛 h畛p, n棚n ch畛n 董n gi畉n d畛 truy c畉p. C畛 th畛 C叩c gi叩 tr畛 c畛a Fk th動畛ng 動畛c l動u tr畛 trong m畛t b畉ng (m畉ng m畛t chi畛u ho畉c hai, ba, v.v chi畛u). C畉n l動u 箪 kh畛i tr畛 c叩c gi叩 tr畛 ban 畉u c畛a b畉ng cho th鱈ch h畛p, 坦 l c叩c k畉t qu畉 c畛a c叩c bi to叩n con c坦 k鱈ch c畛 nh畛 nh畉t c畛a bi to叩n ang gi畉i: }))0(())1(),1(({G))1(( 01 )1( 1 tFdtaxmtF d += D畛a vo c担ng th畛c, ph動董ng tr狸nh truy to叩n (*) v c叩c gi叩 tr畛 達 c坦 trong b畉ng 畛 t狸m d畉n c叩c gi叩 tr畛 c嘆n l畉i c畛a b畉ng. Ngoi ra c嘆n c畉n m畉ng l動u tr畛 nghi畛m t動董ng 畛ng v畛i c叩c gi叩 tr畛 t畛i 動u trong t畛ng gian o畉n. D畛a vo b畉ng l動u tr畛 nghi畛m v b畉ng gi叩 tr畛 t畛i 動u trong t畛ng giai o畉n 達 x但y d畛ng, t狸m ra k畉t qu畉 bi to叩n. B動畛c 3: Lm t畛t Lm t畛t thu畉t to叩n b畉ng c叩ch thu g畛n h畛 th畛c (*) v gi畉m k鱈ch th動畛c mi畛n nh畛. Th動畛ng t狸m c叩ch d湛ng m畉ng m畛t chi畛u thay cho m畉ng hai chi畛u n畉u gi叩 tr畛 m畛t d嘆ng (ho畉c c畛t) c畛a m畉ng hai chi畛u ch畛 ph畛 thu畛c m畛t d嘆ng (ho畉c c畛t) k畛 tr動畛c. Trang 4
Trong m畛t s畛 tr動畛ng h畛p c坦 th畛 thay m畉ng hai chi畛u v畛i c叩c gi叩 tr畛 ph畉n t畛 ch畛 nh畉n gi叩 tr畛 0, 1 b畛i m畉ng hai chi畛u m畛i b畉ng c叩ch d湛ng k畛 thu畉t qu畉n l箪 bit. 3. H畉n ch畉 c畛a quy ho畉ch 畛ng Vi畛c t狸m c担ng th畛c, ph動董ng tr狸nh truy to叩n ho畉c t狸m c叩ch ph但n r達 bi to叩n nhi畛u khi 嘆i h畛i s畛 ph但n t鱈ch t畛ng h畛p r畉t c担ng phu,d畛 sai s坦t, kh坦 nh畉n ra nh動 th畉 no l th鱈ch h畛p, 嘆i h畛i nhi畛u th畛i gian suy ngh挑. 畛ng th畛i kh担ng ph畉i l炭c no k畉t h畛p l畛i gi畉i c畛a c叩c bi to叩n con c滴ng cho k畉t qu畉 c畛a bi to叩n l畛n h董n. Khi b畉ng l動u tr畛 嘆i h畛i m畉ng hai, ba chi畛u th狸 kh坦 c坦 th畛 x畛 l箪 d畛 li畛u v畛i k鱈ch c畛 m畛i chi畛u l畛n hng trm. C坦 nh畛ng bi to叩n kh担ng th畛 gi畉i 動畛c b畉ng quy ho畉ch 畛ng. Trang 5
Trong m畛t s畛 tr動畛ng h畛p c坦 th畛 thay m畉ng hai chi畛u v畛i c叩c gi叩 tr畛 ph畉n t畛 ch畛 nh畉n gi叩 tr畛 0, 1 b畛i m畉ng hai chi畛u m畛i b畉ng c叩ch d湛ng k畛 thu畉t qu畉n l箪 bit. 3. H畉n ch畉 c畛a quy ho畉ch 畛ng Vi畛c t狸m c担ng th畛c, ph動董ng tr狸nh truy to叩n ho畉c t狸m c叩ch ph但n r達 bi to叩n nhi畛u khi 嘆i h畛i s畛 ph但n t鱈ch t畛ng h畛p r畉t c担ng phu,d畛 sai s坦t, kh坦 nh畉n ra nh動 th畉 no l th鱈ch h畛p, 嘆i h畛i nhi畛u th畛i gian suy ngh挑. 畛ng th畛i kh担ng ph畉i l炭c no k畉t h畛p l畛i gi畉i c畛a c叩c bi to叩n con c滴ng cho k畉t qu畉 c畛a bi to叩n l畛n h董n. Khi b畉ng l動u tr畛 嘆i h畛i m畉ng hai, ba chi畛u th狸 kh坦 c坦 th畛 x畛 l箪 d畛 li畛u v畛i k鱈ch c畛 m畛i chi畛u l畛n hng trm. C坦 nh畛ng bi to叩n kh担ng th畛 gi畉i 動畛c b畉ng quy ho畉ch 畛ng. Trang 5

More Related Content

Qhd

  • 1. 1. Ph動董ng ph叩p quy ho畉ch 畛ng Ph動董ng ph叩p quy ho畉ch 畛ng c湛ng nguy棚n l箪 t畛i 動u 動畛c nh to叩n h畛c M畛 R.Bellman 畛 xu畉t vo nh畛ng nm 50 c畛a th畉 k畛 20. Ph動董ng ph叩p ny 達 動畛c 叩p d畛ng 畛 gi畉i hng lo畉t bi to叩n th畛c t畉 trong c叩c qu叩 tr狸nh k畛 thu畉t c畛ng ngh畛, t畛 ch畛c s畉n xu畉t, k畉 ho畉ch ho叩 kinh t畉垂 Tuy nhi棚n c畉n l動u 箪 r畉ng c坦 m畛t s畛 bi to叩n m c叩ch gi畉i b畉ng quy ho畉ch 畛ng t畛 ra kh担ng th鱈ch h畛p. Trong th畛c t畉, ta th動畛ng g畉p m畛t s畛 bi to叩n t畛i 動u lo畉i sau: C坦 m畛t 畉i l動畛ng f h狸nh thnh trong m畛t qu叩 tr狸nh g畛m nhi畛u giai o畉n v ta ch畛 quan t但m 畉n k畉t qu畉 cu畛i c湛ng l gi叩 tr畛 c畛a f ph畉i l畛n nh畉t ho畉c nh畛 nh畉t, ta g畛i chung l gi叩 tr畛 t畛i 動u c畛a f. Gi叩 tr畛 c畛a f ph畛 thu畛c vo nh畛ng 畉i l動畛ng xu畉t hi畛n trong bi to叩n m m畛i b畛 gi叩 tr畛 c畛a ch炭ng 動畛c g畛i l m畛t tr畉ng th叩i c畛a h畛 th畛ng v ph畛 thu畛c vo c叩ch th畛c 畉t 動畛c gi叩 tr畛 f trong t畛ng giai o畉n m m畛i c叩ch t畛 ch畛c 動畛c g畛i l m畛t i畛u khi畛n. 畉i l動畛ng f th動畛ng 動畛c g畛i l hm m畛c ti棚u v qu叩 tr狸nh 畉t 動畛c gi叩 tr畛 t畛i 動u c畛a f 動畛c g畛i l qu叩 tr狸nh i畛u khi畛n t畛i 動u. Bellman ph叩t bi畛u nguy棚n l箪 t畛i 動u (c滴ng g畛i l nguy棚n l箪 Bellman) m 箪 t動畛ng c董 b畉n l nh動 sau: V畛i m畛i qu叩 tr狸nh i畛u khi畛n t畛i 動u, 畛i v畛i tr畉ng th叩i b畉t 畉u A0, v畛i tr畉ng th叩i A trong qu叩 tr狸nh 坦, ph畉n qu叩 tr狸nh k畛 t畛 tr畉ng th叩i A xem nh動 tr畉ng th叩i b畉t 畉u c滴ng l t畛i 動u. Ch炭 箪 r畉ng nguy棚n l箪 ny 動畛c th畛a nh畉n m kh担ng ch畛ng minh. Ph動董ng ph叩p t狸m i畛u khi畛n t畛i 動u theo nguy棚n l箪 Bellman th動畛ng 動畛c g畛i l quy ho畉ch 畛ng. Thu畉t ng畛 ny n坦i l棚n th畛c ch畉t c畛a qu叩 tr狸nh i畛u khi畛n l 畛ng: c坦 th畛 trong m畛t s畛 b動畛c 畉u ti棚n l畛a ch畛n i畛u khi畛n t畛i 動u d動畛ng nh動 kh担ng t畛t nh動ng t畛u chung c畉 qu叩 tr狸nh l畉i l t畛t nh畉t. Ta c坦 th畛 gi畉i th鱈ch 箪 ny qua bi to叩n sau: Cho m畛t d達y N s畛 nguy棚n A1, A2,,AN. H達y t狸m c叩ch xo叩 i m畛t s畛 鱈t nh畉t s畛 h畉ng 畛 d達y c嘆n Trang 1
  • 2. l畉i l 董n i畛u hay n坦i c叩ch kh叩c h達y ch畛n m畛t s畛 nhi畛u nh畉t c叩c s畛 h畉ng sao cho d達y B g畛m c叩c s畛 h畉ng 坦 theo tr狸nh t畛 xu畉t hi畛n trong d達y A l 董n i畛u. Qu叩 tr狸nh ch畛n B 動畛c i畛u khi畛n qua N giai o畉n 畛 畉t 動畛c m畛c ti棚u l s畛 l動畛ng s畛 h畉ng c畛a d達y B l nhi畛u nh畉t, i畛u khi畛n 畛 giai o畉n i th畛 hi畛n vi畛c ch畛n hay kh担ng ch畛n Ai vo d達y B. Gi畉 s畛 d達y 達 cho l 1 8 10 2 4 6 7. N畉u ta ch畛n l畉n l動畛t 1, 8, 10 th狸 ch畛 ch畛n 動畛c 3 s畛 h畉ng nh動ng n畉u b畛 qua 8 v 10 th狸 ta ch畛n 動畛c 5 s畛 h畉ng 1, 2, 4, 6, 7. Khi gi畉i m畛t bi to叩n b畉ng c叩ch chia 畛 tr畛 chuy畛n vi畛c gi畉i bi to叩n k鱈ch th動畛c l畛n v畛 vi畛c gi畉i nhi畛u bi to叩n c湛ng ki畛u c坦 k鱈ch th動畛c nh畛 h董n th狸 thu畉t to叩n ny th動畛ng 動畛c th畛 hi畛n b畉ng c叩c ch動董ng tr狸nh con 畛 quy. Khi 坦, tr棚n th畛c t畉, nhi畛u k畉t qu畉 trung gian ph畉i t鱈nh nhi畛u l畉n. V畉y 箪 t動畛ng c董 b畉n c畛a quy ho畉ch 畛ng th畉t 董n gi畉n: tr叩nh t鱈nh to叩n l畉i m畛i th畛 hai l畉n, m l動u gi畛 k畉t qu畉 達 t狸m ki畉m 動畛c vo m畛t b畉ng lm gi畉 thi畉t cho vi畛c t狸m ki畉m nh畛ng k畉t qu畉 c畛a tr動畛ng h畛p sau. Ch炭ng ta s畉 lm 畉y d畉n gi叩 tr畛 c畛a b畉ng ny b畛i c叩c k畉t qu畉 c畛a nh畛ng tr動畛ng h畛p tr動畛c 達 動畛c gi畉i. K畉t qu畉 cu畛i c湛ng ch鱈nh l k畉t qu畉 c畛a bi to叩n c畉n gi畉i. N坦i c叩ch kh叩c ph動董ng ph叩p quy ho畉ch 畛ng 達 th畛 hi畛n s畛c m畉nh c畛a nguy棚n l箪 chia 畛 tr畛 畉n cao 畛. Quy ho畉ch 畛ng l k畛 thu畉t thi畉t k畉 bottom-up (t畛 d動畛i l棚n). N坦 動畛c b畉t 畉u v畛i nh畛ng tr動畛ng h畛p con nh畛 nh畉t (th動畛ng l 董n gi畉i nh畉t v gi畉i 動畛c ngay). B畉ng c叩ch t畛 h畛p c叩c k畉t qu畉 達 c坦 (kh担ng ph畉i t鱈nh l畉i) c畛a c叩c tr動畛ng h畛p con, s畉 畉t 畉t t畛i k畉t qu畉 c畛a tr動畛ng h畛p c坦 k鱈ch th動畛c l畛n d畉n l棚n v t畛ng qu叩t h董n, cho 畉n khi cu畛i c湛ng 畉t t畛i l畛i gi畉i c畛a tr動畛ng h畛p t畛ng qu叩t nh畉t. Trang 2
  • 3. Trong m畛t s畛 tr動畛ng h畛p, khi gi畉i m畛t bi to叩n A, tr動畛c h畉t ta t狸m h畛 bi to叩n A(p) ph畛 thu畛c tham s畛 p (c坦 th畛 p l m畛t v辿c t董) m A(p0)=A v畛i p0 l tr畉ng th叩i ban 畉u c畛a bi to叩n A. Sau 坦 t狸m c叩ch gi畉i h畛 bi to叩n A(p) v畛i tham s畛 p b畉ng c叩ch 叩p d畛ng nguy棚n l箪 t畛i 動u c畛a Bellman. Cu畛i c湛ng cho p=p0 s畉 nh畉n 動畛c k畉t qu畉 c畛a bi to叩n A ban 畉u. 2. C叩c b動畛c th畛c hi畛n quy ho畉ch 畛ng B動畛c 1: L畉p h畛 th畛c D畛a vo nguy棚n l箪 t畛i 動u t狸m c叩ch chia qu叩 tr狸nh gi畉i bi to叩n thnh t畛ng giai o畉n, sau 坦 t狸m h畛 th畛c bi畛u di畛n t動董ng quan quy畉t 畛nh c畛a b動畛c ang x畛 l箪 v畛i c叩c b動畛c 達 x畛 l箪 tr動畛c 坦. Ho畉c t狸m c叩ch ph但n r達 bi to叩n thnh c叩c bi to叩n con t動董ng t畛 c坦 k鱈ch th動畛c nh畛 h董n, t狸m h畛 th畛c n棚u quan h畛 gi畛a k畉t qu畉 bi to叩n k鱈ch th動畛c 達 cho v畛i k畉t qu畉 c畛a c叩c bi to叩n con c湛ng ki畛u c坦 k鱈ch th動畛c nh畛 h董n c畛a n坦 nh畉m x但y d畛ng ph動董ng tr狸nh truy to叩n (d畉ng hm ho畉c th畛 t畛c 畛 quy). V畛 m畛t c叩ch x但y d畛ng ph動董ng tr狸nh truy to叩n: Ta chia vi畛c gi畉i bi to叩n thnh n giai o畉n. M畛i giai o畉n i c坦 tr畉ng th叩i ban 畉u l t(i) v ch畛u t叩c 畛ng i畛u khi畛n d(i) s畉 bi畉n thnh tr畉ng th叩i ti畉p theo t(i+1) c畛a giai o畉n i+1 (i=1,2,,n-1). Theo nguy棚n l箪 t畛i 動u c畛a Bellman th狸 vi畛c t畛i 動u giai o畉n cu畛i c湛ng kh担ng lm 畉nh h動畛ng 畉n k畉t qu畉 ton bi to叩n. V畛i tr畉ng th叩i ban 畉u l t(n) sau khi lm giai o畉n n t畛t nh畉t ta c坦 tr畉ng th叩i ban 畉u c畛a giai o畉n n-1 l t(n-1) v t叩c 畛ng i畛u khi畛n c畛a giai o畉n n-1 l d(n-1), c坦 th畛 ti畉p t畛c x辿t 畉n giai o畉n n-1. Sau khi t畛i 動u giai o畉n n-1 ta l畉i c坦 t(n-2) v d(n-2) v l畉i c坦 th畛 t畛i 動u giai o畉n n-2 cho 畉n khi c叩c giai o畉n t畛 n gi畉m 畉n 1 動畛c t畛i 動u th狸 coi nh動 hon thnh bi to叩n. G畛i gi叩 tr畛 t畛i 動u c畛a bi to叩n t鱈nh 畉n giai o畉n k l Fk gi叩 tr畛 t畛i 動u c畛a bi to叩n t鱈nh ri棚ng 畛 giai o畉n k l Gk th狸 Fk = Fk-1 + Gk Trang 3
  • 4. Hay l: (*)}))1(())(),(({G))(( 1k )( 1 += ktFkdktaxmktF k kd B動畛c 2: T畛 ch畛c d畛 li畛u v ch動董ng tr狸nh T畛 ch畛c d畛 li畛u sao cho 畉t c叩c y棚u c畉u sau: D畛 li畛u 動畛c t鱈nh to叩n d畉n theo c叩c b動畛c. D畛 li畛u 動畛c l動u tr畛 畛 gi畉m l動畛ng t鱈nh to叩n l畉p l畉i. K鱈ch th動畛c mi畛n nh畛 dnh cho l動u tr畛 d畛 li畛u cng nh畛 cng t畛t, ki畛u d畛 li畛u 動畛c ch畛n ph湛 h畛p, n棚n ch畛n 董n gi畉n d畛 truy c畉p. C畛 th畛 C叩c gi叩 tr畛 c畛a Fk th動畛ng 動畛c l動u tr畛 trong m畛t b畉ng (m畉ng m畛t chi畛u ho畉c hai, ba, v.v chi畛u). C畉n l動u 箪 kh畛i tr畛 c叩c gi叩 tr畛 ban 畉u c畛a b畉ng cho th鱈ch h畛p, 坦 l c叩c k畉t qu畉 c畛a c叩c bi to叩n con c坦 k鱈ch c畛 nh畛 nh畉t c畛a bi to叩n ang gi畉i: }))0(())1(),1(({G))1(( 01 )1( 1 tFdtaxmtF d += D畛a vo c担ng th畛c, ph動董ng tr狸nh truy to叩n (*) v c叩c gi叩 tr畛 達 c坦 trong b畉ng 畛 t狸m d畉n c叩c gi叩 tr畛 c嘆n l畉i c畛a b畉ng. Ngoi ra c嘆n c畉n m畉ng l動u tr畛 nghi畛m t動董ng 畛ng v畛i c叩c gi叩 tr畛 t畛i 動u trong t畛ng gian o畉n. D畛a vo b畉ng l動u tr畛 nghi畛m v b畉ng gi叩 tr畛 t畛i 動u trong t畛ng giai o畉n 達 x但y d畛ng, t狸m ra k畉t qu畉 bi to叩n. B動畛c 3: Lm t畛t Lm t畛t thu畉t to叩n b畉ng c叩ch thu g畛n h畛 th畛c (*) v gi畉m k鱈ch th動畛c mi畛n nh畛. Th動畛ng t狸m c叩ch d湛ng m畉ng m畛t chi畛u thay cho m畉ng hai chi畛u n畉u gi叩 tr畛 m畛t d嘆ng (ho畉c c畛t) c畛a m畉ng hai chi畛u ch畛 ph畛 thu畛c m畛t d嘆ng (ho畉c c畛t) k畛 tr動畛c. Trang 4
  • 5. Trong m畛t s畛 tr動畛ng h畛p c坦 th畛 thay m畉ng hai chi畛u v畛i c叩c gi叩 tr畛 ph畉n t畛 ch畛 nh畉n gi叩 tr畛 0, 1 b畛i m畉ng hai chi畛u m畛i b畉ng c叩ch d湛ng k畛 thu畉t qu畉n l箪 bit. 3. H畉n ch畉 c畛a quy ho畉ch 畛ng Vi畛c t狸m c担ng th畛c, ph動董ng tr狸nh truy to叩n ho畉c t狸m c叩ch ph但n r達 bi to叩n nhi畛u khi 嘆i h畛i s畛 ph但n t鱈ch t畛ng h畛p r畉t c担ng phu,d畛 sai s坦t, kh坦 nh畉n ra nh動 th畉 no l th鱈ch h畛p, 嘆i h畛i nhi畛u th畛i gian suy ngh挑. 畛ng th畛i kh担ng ph畉i l炭c no k畉t h畛p l畛i gi畉i c畛a c叩c bi to叩n con c滴ng cho k畉t qu畉 c畛a bi to叩n l畛n h董n. Khi b畉ng l動u tr畛 嘆i h畛i m畉ng hai, ba chi畛u th狸 kh坦 c坦 th畛 x畛 l箪 d畛 li畛u v畛i k鱈ch c畛 m畛i chi畛u l畛n hng trm. C坦 nh畛ng bi to叩n kh担ng th畛 gi畉i 動畛c b畉ng quy ho畉ch 畛ng. Trang 5
  • 6. Trong m畛t s畛 tr動畛ng h畛p c坦 th畛 thay m畉ng hai chi畛u v畛i c叩c gi叩 tr畛 ph畉n t畛 ch畛 nh畉n gi叩 tr畛 0, 1 b畛i m畉ng hai chi畛u m畛i b畉ng c叩ch d湛ng k畛 thu畉t qu畉n l箪 bit. 3. H畉n ch畉 c畛a quy ho畉ch 畛ng Vi畛c t狸m c担ng th畛c, ph動董ng tr狸nh truy to叩n ho畉c t狸m c叩ch ph但n r達 bi to叩n nhi畛u khi 嘆i h畛i s畛 ph但n t鱈ch t畛ng h畛p r畉t c担ng phu,d畛 sai s坦t, kh坦 nh畉n ra nh動 th畉 no l th鱈ch h畛p, 嘆i h畛i nhi畛u th畛i gian suy ngh挑. 畛ng th畛i kh担ng ph畉i l炭c no k畉t h畛p l畛i gi畉i c畛a c叩c bi to叩n con c滴ng cho k畉t qu畉 c畛a bi to叩n l畛n h董n. Khi b畉ng l動u tr畛 嘆i h畛i m畉ng hai, ba chi畛u th狸 kh坦 c坦 th畛 x畛 l箪 d畛 li畛u v畛i k鱈ch c畛 m畛i chi畛u l畛n hng trm. C坦 nh畛ng bi to叩n kh担ng th畛 gi畉i 動畛c b畉ng quy ho畉ch 畛ng. Trang 5