算法設計與分析-第三章-動態(tài)規(guī)劃(已修改)
2025-08-16 10:38 本頁面
【正文】 第 3章 動態(tài)規(guī)劃（ DynamicProgramming） ? 動態(tài)規(guī)劃法的基本思想 ? 動態(tài)規(guī)劃法的適用條件 ? 動態(tài)規(guī)劃法的基本步驟 ? 應用舉例－ 0/1背包問題 動態(tài)規(guī)劃法的基本思想 ? 為求解給定問題，有一系列子問題需要解答。對這些子問題按照某種方式仔細設計，使得其后的每一個子問題都可以通過上面已經(jīng)求出的一個或多個子問題的合并而獲得其解。 動態(tài)規(guī)劃法的基本思想 ? 動態(tài)規(guī)劃法與分治法的異同： – 與分治法類似，動態(tài)規(guī)劃法也是對問題進行遞歸分解。 – 而當遞歸分解得到的子問題不互相獨立時，用分治法求解，則有些子問題被重復計算了許多次。而動態(tài)規(guī)劃法通過保存已解決的子問題的解，在需要時再找出已求得的解，可以避免大量重復計算。 動態(tài)規(guī)劃法的適用條件 動態(tài)規(guī)劃法解所能解決的問題一般具有以下兩個基本因素： ? 一、最優(yōu)子結(jié)構(gòu)性質(zhì) 當 問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 ? 二、重疊子問題性質(zhì) 遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。 ? 其它同分治法 動態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) 當 問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 例 1： Fibonacci數(shù)問題 n n≤1 F(n)＝ F(n1)＋ F(n2) n1 動態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) 當 問題的最優(yōu)解包含著其子問題的最優(yōu)解時，稱該問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 例 2：求解二項式系數(shù) )!(!!mnmnmn??????????????????mn??????????????????? ?111mnmn1 1 m=0 n=m 其它 ＝ 動態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導致矛盾。 動態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) ?例 3 最短路徑問題 設 G是
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1