動(dòng)態(tài)規(guī)劃入門(論文)-資料下載頁(yè)
2025-08-03 00:55本頁(yè)面
【正文】 1。 else//沒(méi)傳到1 f[p][t]=0。 return。 } if(f[p][t]!=1) return。//如果這個(gè)狀態(tài)搜到過(guò)了，沒(méi)必要再搜 f[p][t]=0。//標(biāo)記該狀態(tài)被搜過(guò)了 find(p%n+1,t+1)。//搜把球傳給P右邊的同學(xué)的狀態(tài) f[p][t]+=f[p%n+1][t+1]。 int p1=p1。 if(p1==0)p1=n。 find(p1,t+1)。//搜把球傳給P左邊的同學(xué)的狀態(tài) f[p][t]+=f[p1][t+1]。}main(){ int i,j。 //一開(kāi)始所有狀態(tài)都沒(méi)到過(guò) for(i=0。imaxn。i++) for(j=0。jmaxm。j++) f[i][j]=1。 scanf(%d%d,amp。n,amp。m)。 find(1,0)。 printf(%ld,f[1][0])。}代入數(shù)據(jù)測(cè)算例：input：3 3F[1,0]=2F[2,1]=1F[3,1]=1F[1,2]=0F[3,2]=1F[1,2]=0F[2,2]=1F[3,3]=0F[2,3]=0F[1,3]=1F[2,3]=0F[1,3]=1F[3,3]=0數(shù)據(jù)模型如下： ：可以從記憶數(shù)組中直接獲取；：需搜索記憶的狀態(tài)；由于采用了記憶化搜索，處于不同位置的相同狀態(tài)不會(huì)被多次搜索，因此可以在O(mn)的時(shí)間復(fù)雜度內(nèi)完成任務(wù)，同樣避免了子問(wèn)題被重復(fù)計(jì)算的情況。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。貪心法：當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇；分治法：各個(gè)子問(wèn)題是獨(dú)立的 (即不包含公共的子子問(wèn)題)，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。但不足的是，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。動(dòng)態(tài)規(guī)劃：利用分治思想把問(wèn)題劃分成規(guī)模更小的子問(wèn)題，并且原問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解；動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，(亦即各子問(wèn)題可包含公共的子子問(wèn)題)也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算，從而解決解決冗余因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹(shù)中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解?？偨Y(jié)：任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是萬(wàn)能的。適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化子結(jié)構(gòu)性質(zhì)。特點(diǎn)：1. 以長(zhǎng)遠(yuǎn)利益為目標(biāo)的一些列決策，一般用來(lái)求解最優(yōu)的問(wèn)題解2. 符合最優(yōu)化原理，可歸結(jié)為一個(gè)遞推式3. 也成為多階段規(guī)劃，特點(diǎn)體現(xiàn)在多階
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1