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