《算法設(shè)計(jì)與分析》-第三章-動(dòng)態(tài)規(guī)劃-文庫(kù)吧
2025-07-20 10:38 本頁(yè)面
【正文】 有向圖，若 G中從頂點(diǎn) i到頂點(diǎn) j有路徑存在，找出最短的一條。 下面證明最短路徑問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 動(dòng)態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) ?證明： ? 設(shè) i,i1,i2,…,i k,j是從 i到 j的一條最短路徑。從初始頂點(diǎn) i開(kāi)始，設(shè)從 i到下一頂點(diǎn) i1的判定已經(jīng)做出。接下去，問(wèn)題就轉(zhuǎn)化為用 i1替代 i，重復(fù)原來(lái)的問(wèn)題，找出一條從 i1到 j的路徑。顯然， i1,i2,…,i k,j一定構(gòu)成了從從 i1到 j的最短路徑（與原問(wèn)題相同的最優(yōu)子序列） 動(dòng)態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) ?證明： 若不然，設(shè) i1, r1,r2,…,r p,j是一條從 i1 到 j的最短路徑，則 i,i1, r1,r2,…,r p,j將是一條從 i到 j的路徑且比路徑 i,i1,i2,…,i k,j要短，得出矛盾。 所以，最短路徑問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 動(dòng)態(tài)規(guī)劃法的適用條件 一、最優(yōu)子結(jié)構(gòu)性質(zhì) ?利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。 動(dòng)態(tài)規(guī)劃法的適用條件 二、重疊子問(wèn)題性質(zhì) 遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。 這種性質(zhì)稱為 子問(wèn)題的重疊性質(zhì) 。 動(dòng)態(tài)規(guī)劃法的適用條件 二、重疊子問(wèn)題性質(zhì) 例 1： Fibonacci數(shù)問(wèn)題的遞歸樹(shù) Fib(5) Fib(4) Fib(3) Fib(3) Fib(2) Fib(2) Fib(1) Fib(2) Fib(1) T(n)=O(Fib(n)) 動(dòng)態(tài)規(guī)劃法的適用條件 二、重疊子問(wèn)題性質(zhì) 例 2： 求解二項(xiàng)式系數(shù)的遞歸樹(shù) ????????1734????????1633????????1733????????1632????????1732????????1632 ????????1532????????1731????????1631????????1631????????1531????????1531????????1531 ????????1431????????1631T(n)=O( ) ????????mn 動(dòng)態(tài)規(guī)劃法的基本步驟 ? 找出最優(yōu)解的性質(zhì)，并刻
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1