動(dòng)態(tài)規(guī)劃法地基本思想

1、實(shí)用標(biāo)準(zhǔn)文案一、動(dòng)態(tài)規(guī)劃的基本思想在比較基本的算法設(shè)計(jì)思想里， 動(dòng)態(tài)規(guī)劃是比較難于理解， 難于抽象的一種，但是卻又十分 重要。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余， 因此它與分治法和貪心法類似， 它們都是將 問(wèn)題的實(shí)例分解為更小的、相似的子問(wèn)題，但是動(dòng)態(tài)規(guī)劃又有自己的特點(diǎn)。貪心法的當(dāng)前選擇可能要依賴于已經(jīng)作出的選擇，但不依賴于還未做出的選擇和子問(wèn)題，因此它的特征是由頂向下， 一步一步地做出貪心選擇，但不足的是，如果當(dāng)前選擇可能要依賴子問(wèn)題的解時(shí)，則難以通過(guò)局部的貪心策略達(dá)到全局最優(yōu)解。相比而言，動(dòng)態(tài)規(guī)劃則可以處理不具有貪心實(shí)質(zhì)的問(wèn)題。在用分治法解決問(wèn)題時(shí)，由于子問(wèn)題的數(shù)目往往是問(wèn)題規(guī)模的指數(shù)函數(shù)

2、，因此對(duì)時(shí)間的消耗太大。動(dòng)態(tài)規(guī)劃的思想在于， 如果各個(gè)子問(wèn)題不是獨(dú)立的， 不同的子問(wèn)題的個(gè)數(shù)只是多項(xiàng)式 量級(jí)，如果我們能夠保存已經(jīng)解決的子問(wèn)題的答案，而在需要的時(shí)候再找出已求得的答案， 這樣就可以避免大量的重復(fù)計(jì)算。由此而來(lái)的基本思路是， 用一個(gè)表記錄所有已解決的子問(wèn)題的答案，不管該問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。比較感性的說(shuō)，其實(shí)動(dòng)態(tài)規(guī)劃的思想是對(duì)貪心算法和分治法的一種折衷， 它所解決的問(wèn)題往 往不具有可愛(ài)的貪心實(shí)質(zhì)，但是各個(gè)子問(wèn)題又不是完全零散的， 這時(shí)候我們用一定的空間來(lái) 換取時(shí)間，就可以提高解題的效率。、動(dòng)態(tài)規(guī)劃的基本步驟動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)

3、的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個(gè)解。設(shè)計(jì)一 個(gè)動(dòng)態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€(gè)步驟進(jìn)行：（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。（2 ）遞歸地定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4 ）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。其中（1）（ 3）步是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省去。若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4 ）。此時(shí)，在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個(gè)最優(yōu)解。三、典型的動(dòng)態(tài)規(guī)

4、劃舉例一一矩陣連乘問(wèn)題作為經(jīng)典的動(dòng)態(tài)規(guī)劃算法舉例，矩陣連乘問(wèn)題很好地展現(xiàn)了動(dòng)態(tài)規(guī)劃的特點(diǎn)和實(shí)用價(jià)值。給定n個(gè)矩陣A1,A2,.,An,其中Ai與Ai+1是可乘的，i=1,2,n-1 ?，F(xiàn)在要計(jì)算這n個(gè)矩陣 的連乘積。由于矩陣的乘法滿足結(jié)合律，所以通過(guò)加括號(hào)可以使得計(jì)算矩陣的連乘積有許多不同的計(jì)算次序。然而采用不同的加擴(kuò)號(hào)方式，所需要的總計(jì)算量是不一樣的。若A是一個(gè)p*q矩陣，B是一個(gè)q*r矩陣，則其乘積C=AB是一個(gè)p*r矩陣。如果用標(biāo)準(zhǔn)算法計(jì)算 C， 總共需要pqr次數(shù)乘?，F(xiàn)在來(lái)看一個(gè)例子。A1 ,A2 ,A3分別是10*100,100*5 和5*50的矩陣。如果按照(A1A2)A3) 來(lái)計(jì)

5、算，則計(jì)算所需的總數(shù)乘次數(shù)是10*100*5+10*5*50=7500。如果按照(A1(A2A3)來(lái)計(jì)算，則需要的數(shù)乘次數(shù)是 100*5*50+10*100*50=75000,整整是前者的10倍。由此可見(jiàn)，在計(jì)算矩陣連乘積時(shí)，不同的加括號(hào)方式所導(dǎo)致的不同的計(jì)算對(duì)計(jì)算量有很大的影響。如何確定計(jì)算矩陣連乘積 A1A2，,An的一個(gè)計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的 數(shù)乘次數(shù)最少便成為一個(gè)問(wèn)題。對(duì)于這個(gè)問(wèn)題，窮舉法雖然易于入手，但是經(jīng)過(guò)計(jì)算，它所需要的計(jì)算次數(shù)是n的指數(shù)函數(shù)，因此在效率上顯得過(guò)于低下?，F(xiàn)在我們按照動(dòng)態(tài)規(guī)劃的基本步驟來(lái)分析解決這個(gè)問(wèn)題， 并比較它與窮舉法在時(shí)間消耗上的差異。(1

6、 )分析最優(yōu)解的結(jié)構(gòu)?，F(xiàn)在，將矩陣連乘積 AiAi+1.Aj簡(jiǎn)記為Ai:j。對(duì)于A1:n的一個(gè)最優(yōu)次序，設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(1 =kn)，那么完全加括號(hào)的方式為(A1.Ak)(Ak+1.An)。依此次序，我們應(yīng)該先分別計(jì)算A1:k和Ak+1:n，然后將計(jì)算結(jié)果相乘得到 A1:n，總計(jì)算量為 A1:k的計(jì)算量加上 Ak+1:n的計(jì)算量，再加上 A1:k 和Ak+1:n相乘的計(jì)算量。通過(guò)反證法可以證明，問(wèn)題的關(guān)鍵特征在于，計(jì)算A1:n的一個(gè)最優(yōu)次序所包含的計(jì)算矩陣子鏈A1:k和Ak+1:n的次序也是最優(yōu)的。因此，矩陣連乘積計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。

7、這種最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可以用動(dòng)態(tài)規(guī)劃解決的重要特征。(2 )建立遞歸關(guān)系定義最優(yōu)值。設(shè)計(jì)算Ai:j(1 =i =j =n)所需的最少數(shù)乘次數(shù)為mij，則原問(wèn)題的最優(yōu)值為m1n而且易見(jiàn)，當(dāng)i=j時(shí)，mi j=0 。根據(jù)上述最優(yōu)子結(jié)構(gòu)性質(zhì)，當(dāng)i j時(shí)，若計(jì)算Ai:j的最優(yōu)次序在 Ak和Ak+1之間斷開，可以定義 mi j=mik+mk+1 j+pi-1*pk*pj( 其中，Ai 的維數(shù)為 pi-1*pi)。從而有：當(dāng) i=j 時(shí)，mi j=0 。當(dāng) i j 時(shí)，mi j=minmik+mk+1j+pi-1*pk*pj(i =k j)。除此之外，若將對(duì)應(yīng)于mij的斷開位置記為si j，在計(jì)算出最

8、優(yōu)值mi j后，可以遞歸地由si j構(gòu)造出相應(yīng)的最優(yōu)解。（3）計(jì)算最優(yōu)值。如果直接套用 mi j的計(jì)算公式，進(jìn)行簡(jiǎn)單的遞歸計(jì)算需要耗費(fèi)指數(shù)計(jì)算時(shí)間。然而，實(shí)際上不同的子問(wèn)題的個(gè)數(shù)只是n的平方項(xiàng)級(jí)（對(duì)于1 =i =j =n 不同的有序?qū)Γ╥,j）對(duì)應(yīng)于不同的子問(wèn)題）。用動(dòng)態(tài)規(guī)劃解決此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單 查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。下面給出計(jì)算mi j的動(dòng)態(tài)規(guī)劃算法：void matrixChain (i nt * p, int n, int * m, int

9、s)for ( int i=1;i =n ;i+)mii=0;for ( int r=2;r =n丁+)II 鏈長(zhǎng)度控制for ( int i=1;i =n-r+1;i+)II 鏈起始位置控制j；int 戸+r-1; II鏈終止位置 mi j=mi+1j+pi-1*pi*p sij=i；for ( int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if (t mij)mij=t;sij=k;算法首先設(shè)定mii=0(i=1,2,n)。然后再根據(jù)遞歸式按矩陣鏈長(zhǎng)的遞增方式依此計(jì)算出各個(gè)mi j，在計(jì)算某個(gè)固定的mi j時(shí)，只用到已計(jì)算出的 mik和mk+1 j。稍加分析就可以得出，這個(gè)算法以0(n2)的空間消耗大大降低了時(shí)間復(fù)雜度，計(jì)算時(shí)間的上界為0(nA3)。(4 )構(gòu)造最優(yōu)解。通過(guò)以上算法的計(jì)算，我們知道了要計(jì)算所給矩陣連乘積所需的最少數(shù)乘次數(shù)，但是還不知道具體應(yīng)該按照什么順序來(lái)做矩陣乘法才能達(dá)到這個(gè)次數(shù)。然而，si j已經(jīng)存儲(chǔ)了構(gòu)造最優(yōu)解所需要的足夠的信息。從s1n記錄的信息可知計(jì)算A1:n的最優(yōu)加括號(hào)方式為(A1：s1n)(As1n+1:n)。同理，每個(gè)部分的最優(yōu)加括號(hào)方式又可以根據(jù)數(shù)組s的相應(yīng)元素得出。照此遞