|
最短路徑動態(tài)規(guī)劃問題及C語言實現(xiàn)探討
阜寧高等師范學校 王學軍 2013/8/30 12:50:19
（接上頁）序流程圖如圖2所示。
圖2 動態(tài)規(guī)劃求解最短路徑程序流程圖
4.最短路徑態(tài)規(guī)劃實際應用舉例
設某物流配送網(wǎng)絡圖由12個配送點組成，點1為配送中心起點，12為終點，試求自終點到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標有兩點間的距離[4]。
首先用動態(tài)規(guī)劃法來討論圖3的最短路徑，由圖可知：
(1)集合 中有點9、10、11，它們在一步之內可到達點12；
(2)集合 中有點6,7,8，它們不超過兩步就可達到點12；
(3)集合 中包括點 2、3、4、5，不超過三步就可到達點12；
(4)集合 中包括點1，不超過四步可到達點12；
按照動態(tài)規(guī)劃法類推，得到最優(yōu)路徑長為16，徑路通過點為1,2,7,10,12和1,3,6,10,12。
根據(jù)動態(tài)規(guī)劃算法編寫C語言計算程序[5] [6]，計算得到實驗結果如下圖4所示：
圖4 動態(tài)規(guī)劃算法C語言程序計算結果
由圖4可以看出程序得到的結果與本文推出的結果一樣。證明了本文編寫的C語言程序是正確的。
5．結語
綜上所述，用動態(tài)規(guī)劃解決多階段決策問題效率高，而且思路清晰簡便，同時易于實現(xiàn).我們可以看到，動態(tài)規(guī)劃方法的應用很廣泛，已成功解決了許多實際問題，具有一定的實用性。此種算法我們用動態(tài)規(guī)劃思想來編程，并解決相應的問題，其在 VC 環(huán)境下實現(xiàn)，能方便快速的計算出到達目的地的最短距離及路徑，節(jié)省更多的運輸時間與成本。不過，本文只考慮了動態(tài)規(guī)劃算法在生活中的簡單運用，在實際生活中可能存在多個目的地或者更復雜的情況.因此我們可以考慮將其進行改進或者結合啟發(fā)式算法，使之更好的運用在實際生活中，這有待于以后的繼續(xù)研究。
參考文獻
［1］杜彥娟.利用動態(tài)規(guī)劃數(shù)學模型求解最短路徑[J].煤炭技術,2005(1):94-95.
［2］蔣琦瑋,陳治亞.物流配送最短徑路的動態(tài)規(guī)劃方法研究[J].系統(tǒng)工程，2007(25):27-29.
［3］朱建民.運籌學—典型例題與解法. http://sdhuihe.com/,2003.
|