動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問題算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-在線瀏覽
2024-09-01 09:46本頁面
【正文】 階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。在50年代，貝爾曼（Richard Bellman）等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計(jì)方法－動(dòng)態(tài)規(guī)劃。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長(zhǎng)度。Us 初始值，uj第j段的最優(yōu)值。步驟13是動(dòng)態(tài)規(guī)劃算法的基本步驟。，編寫從文件到鄰接表的函數(shù)。多段圖算法：Procedure FGRAPH（E,k,n,P）//輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，有n個(gè)結(jié)點(diǎn)的k段圖。P（1：k）是最小成本路徑。D(j)r。 P（k）n。repeat。void init(int cost[]) //初始化圖{ int i,j。i13。j13。 } } c[1][2]=9。 c[1][4]=3。 c[2][6]=4。 c[2][8]=1。 c[3][7]=7。 c[5][7]=11。 c[6][9]=6。 c[7][9]=4。 c[8][10]=5。 c[9][12]=4。c[11][12]=5。 for(j=0。j++) cost[j]=0。j=1。 min=c[j][temp]+cost[temp]。r=n。 temp=r。 d[j]=temp。 path[k]=n。jk。}void bgraph(int b
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1