［摘要］**以最短路徑問題為例，在給出佛洛伊德演算法的基礎上，設計了求解該演算法的計算程式，這樣可大大提高最短路徑計算的效率。
［關鍵字］最短路徑，動態規劃，程式設計
1佛洛伊德演算法
2.動態規劃求解的佛洛伊德演算法程式設計
如下圖所示：給定乙個線路網路，兩點之間連線上的數字表示兩點間的距離，求一條從a到e的路線，使總距離為最短。
為了減少上述問題的計算工作量，我們編制求解動態規劃演算法的vba程式如下：
sub js()
dim n, i, j, k as integer
n = 9
dim d(9, 9), p(9, 9), path(9), distance as integer
rem 將資料存於陣列d(i,j)中
for i = 1 to n
for j = 1 to n
d(i, j) = cells(i, j)
next j
next i
for i = 1 to n
for j = i + 1 to n
if d(i, j) j then
if d(i, k) + d(k, j) 1
path(i) = p(1, count)
i = i + 1
count = p(1, count)
wend
cells(20, 1) = distance
for i = 1 to n
cells(21, i) = path(i)
next i
end sub
主要參考文獻
[1]朱順泉.管理科學研究方法[m].北京：清華大學出版社，2007
[2]運籌學編寫組.運籌學[m].清華大學出版社，1992
[3]丁以中等.管理科學[m].清華大學出版社，2003
[4]楊世勝.計算機在企業管理中應用[m].上海交通大學出版社，1985
動態規劃最短路徑問題
首先，我們來觀察上述演算法。在求b1到e的最短路徑的時候，先求出從c2到e的最短路徑 而在求從b2剄e的最短路徑的時候，又求了一遍從c2剄e的最短路徑。也就是說，從c2到e的最短路徑求了兩遍。同樣可以發現，在求從cl c2剄e的最短路徑的過程中，從dl到e的最短路徑也被求了兩遍。而在整個程式中，從d...
例動態規劃解最短路徑問題
步驟 1 2 已實現。最優子結構 從起點到終點的最短路徑包含了該路徑上各點到終點的最短路徑。遞迴公式 設v為圖中乙個頂點，v1,v2,vm為v的直接後繼，cost v 表示v到終點的最短路徑長度，c u,w 表示邊上的權，t為終點，則cost滿足如下遞迴公式 步驟 3 計算最優值 求最短路徑長度 設...
最短路徑問題 專題
初中數學中最短路徑問題雖然只是乙個課題學習，但它在中學數學中的地位很重要，是大考 小考 競賽中經常涉及的乙個考點。所以我們要對它有足夠的重視。初中最短路徑問題主要針對軸對稱圖形考慮的。那麼只要涉及軸對稱圖形就有可能產生最短路徑問題。在此之前，我們接觸過的最短距離問題是 1 兩點間直線段最短 2 點到...