動態(tài)規(guī)劃算法實現(xiàn)多段圖的最短路徑問題算法設(shè)計與分析實驗報告-免費閱讀
【正文】 coutendl最短路徑為長度:bcost[12]endl。 coutendl最短路徑為長度:cost[1]endl。 cout\n\n。 for(int i=4。 //初始化最小值 for(r=0。}void bgraph(int bcost[],int path1[],int d[])//使用向后遞推算法求多段圖的最短路徑{ int r,j,temp,min。 temp=r。j++) cost[j]=0。 c[8][10]=5。 c[3][7]=7。 } } c[1][2]=9。repeat。多段圖算法：Procedure FGRAPH（E,k,n,P）//輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。Us 初始值，uj第j段的最優(yōu)值。在50年代，貝爾曼（Richard Bellman）等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法－動態(tài)規(guī)劃。對于一個多階段過程問題，是否可以分段實現(xiàn)最優(yōu)決策，依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2） 遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3） 以自底向上的方式計算出最優(yōu)值；4） 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。E是邊集，c（i，j）是邊i，j的成本。end FGRAPH4. 程序代碼include include
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1