動態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問題算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-wenkub
2022-08-19 09:46:53 本頁面
【正文】 式無關(guān)。這類問題的解決是多階段的決策過程。子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。即當(dāng)前最優(yōu)只與上一步有關(guān)。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。//real COST(n),integer(n1),P(k),r,j,k,nCOST(n)0for jn1 to 1 by 1 do //計(jì)算COST（j）//設(shè)r是一個(gè)這樣的結(jié)點(diǎn)，（j，r）E且使c（j，r）+COST（r）取最小值COST（j） c（j，r）+COST（r）。for j2 to k1 do // 找路徑上的第j個(gè)節(jié)點(diǎn)// P（j）D(P(j1))。 for(i=0。j++) { c[i][j]=MAX。 c[1][5]=2。 c[3][6]=2。 c[5][8]=8。 c[7][10]=3。 c[10][12]=2。j=n。j) { temp=0。r++) { if(c[j][r]!=MAX) { if((c[j][r]+cost[r])min) //找到最小的r { min=c[j][r]+cost[r]。 } path[1]=1。j++) path[j]=d[path[j1]]。j++) bcost[j]=0。 min=c[temp][j]+bcost[
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1