動態(tài)規(guī)劃算法實現(xiàn)多段圖的最短路徑問題算法設計與分析實驗報告-文庫吧
2025-07-07 09:46 本頁面
【正文】 解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2） 遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3） 以自底向上的方式計算出最優(yōu)值；4） 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。步驟13是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。，編寫從文件到鄰接表的函數(shù)。多段圖算法：Procedure FGRAPH（E,k,n,P）//輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。E是邊集，c（i，j）是邊i，j的成本。P（1：k）是最小成本路徑。//real COST(n),integer(n1),P(k),r,j,k,nCOST(n)0for jn1 to 1 by 1 do //計算COST（j）//設r是一個這樣的結(jié)點，（j，r）E且使c（j，r）+COST（r）取最小值COST（j） c（j，r）+COST（r）。D(j)r。Repeat //向前對j1進行決策//P（1）1。 P（k）n。for j2 to k1 do // 找路徑上的第j個節(jié)點// P（j）D(P(j1))。repeat。end FGRAPH4. 程序代碼include include include include define MAX 100 define n 12 /*頂點數(shù)*/define k 5 /*段數(shù)*/
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1