最短路徑動態(tài)規(guī)劃問題及其程序設(shè)計(jì)

［摘要］論文以最短路徑問題為例，在給出佛洛伊德算法的基礎(chǔ)上，設(shè)計(jì)了求解該算法的計(jì)算程序，這樣可大大提高最短路徑計(jì)算的效率。

［關(guān)鍵字］最短路徑，動態(tài)規(guī)劃，程序設(shè)計(jì)

1佛洛伊德算法

2.動態(tài)規(guī)劃求解的佛洛伊德算法程序設(shè)計(jì)

如下圖所示：給定一個(gè)線路網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離，求一條從A到E的路線，使總距離為最短。

為了減少上述問題的計(jì)算工作量，我們編制求解動態(tài)規(guī)劃算法的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 將數(shù)據(jù)存于數(shù)組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) < 99999 Then

d(j， i) = d(i， j)

End If

Next j

Next i

Rem 定義距離矩陣

For i = 1 To n

For j = 1 To n

p(i， j) = 0

Next j

Next i

For i = 1 To n

For j = 1 To n

If i = j Then

p(i， j) = 99999

Else

p(i， j) = i

End If

Next j

Next i

Rem 計(jì)算距離和路徑

For k = 1 To n

For i = 1 To n

For j = 1 To n

If i <> j Then

If d(i， k) + d(k， j) < d(i， j) Then

d(i， j) = d(i， k) + d(k， j)

p(i， j) = k

End If

End If

Next j

Next i

Next k

Rem 輸出距離和路徑

distance = d(1， n)

For i = 1 To n

path(i) = 0

Next i

Count = 9

i = 1

While Count > 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

主要參考文獻(xiàn)

[1]朱順泉.管理科學(xué)研究方法[M].北京：清華大學(xué)出版社，2007

[2]運(yùn)籌學(xué)編寫組.運(yùn)籌學(xué)[M].清華大學(xué)出版社，1992

[3]丁以中等.管理科學(xué)[M].清華大學(xué)出版社，2003

[4]楊世勝.計(jì)算機(jī)在企業(yè)管理中應(yīng)用[M].上海交通大學(xué)出版社，1985

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”