最短路徑動態(tài)規(guī)劃問題及C語言實現(xiàn)探討

王學(xué)軍

摘要：動態(tài)規(guī)劃算法是一種研究多階段決策問題的算法.用動態(tài)規(guī)劃方法求最短路問題，要求所求問題具有明顯的階段。該文以動態(tài)規(guī)劃理論為指導(dǎo)，研究了動態(tài)規(guī)劃算法求解最短路徑的基本原理及步驟，編寫了基于動態(tài)規(guī)劃算法的C語言程序，輔助完成最短路徑的求解。

關(guān)鍵詞：最短路徑；動態(tài)規(guī)劃；C 語言編程

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2191-03

1 概述

數(shù)學(xué)源于生活，又服務(wù)于生活.它是一門研究現(xiàn)實世界中的數(shù)量關(guān)系與空間形式的學(xué)科.當(dāng)今社會，隨著物質(zhì)水平的不斷提高，生活需求的不斷擴大，自然資源的不斷開發(fā)利用.像天然氣管道鋪設(shè)問題，廠區(qū)布局問題，旅行費用最小問題等都已成為我們平時經(jīng)濟生活中的普遍問題.它們其實都可以化歸為最短路線問題，而最短路問題實質(zhì)上是一個組合優(yōu)化問題[1]。

動態(tài)規(guī)劃方法主要是研究與解決多階段決策過程的最優(yōu)化問題，它將求解分成多階段進(jìn)行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實際問題時，更顯其優(yōu)越性。為了快速、簡單的計算最短路徑，節(jié)約運輸時間與成本，該文利用動態(tài)規(guī)劃的思想編寫了C語言程序，解決物流運輸過程中多地點的最短路徑的選擇問題。

2 最短路徑問題

2.1 最短路徑問題算法的基本思想

在求解網(wǎng)絡(luò)圖上節(jié)點間最短路徑的方法中，目前國內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網(wǎng)絡(luò)被抽象為一個圖論中定義的有向或無向圖，并利用圖的節(jié)點鄰接矩陣記錄點間的關(guān)聯(lián)信息。在進(jìn)行圖的遍歷以搜索最短路徑時，以該矩陣為基礎(chǔ)不斷進(jìn)行目標(biāo)值的最小性判別，直到獲得最后的優(yōu)化路徑[2]。

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結(jié)點為源點，重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復(fù)雜度為[On3]，雖然與重復(fù)執(zhí)行Dijkstra算法n次的時間復(fù)雜度相同，但其形式上略為簡單，且實際運算效果要好于前者。

2.2 最短路徑問題算法的基本步驟[3]

這樣經(jīng)過有限次迭代則可以求出[v1]到[vn]的最短路線。

（2）Floyd算法的基本步驟

（3）動態(tài)規(guī)劃算法基本步驟

我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃[1]。在解決多個階段決策問題時采用動態(tài)規(guī)劃法是一個很有效的措施，同時易于實現(xiàn)。

根據(jù)動態(tài)規(guī)劃的基本概念，可以得到動態(tài)規(guī)劃的基本步驟：1）確定問題的決策對象。2）對決策過程劃分階段。3）對各階段確定狀態(tài)變量。4）根據(jù)狀態(tài)變量確定費用函數(shù)和目標(biāo)函數(shù)。5）建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程。

根據(jù)動態(tài)規(guī)劃的基本模型，確定用動態(tài)規(guī)劃方法解題的基本思路，是將一個[n]階段決策問題轉(zhuǎn)化為一次求解[n]個具有遞推關(guān)系的單階段的決策問題，以此來簡化計算過程.其一般步驟如下：

用于衡量所選決策優(yōu)劣的函數(shù)稱為指標(biāo)函數(shù).指標(biāo)函數(shù)有有階段的指標(biāo)函數(shù)和過程的指標(biāo)函數(shù)之分.階段的指標(biāo)函數(shù)是對應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個階段的某種效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]來表示某一階段的決策的最短路徑。過程的指標(biāo)函數(shù)是指從狀態(tài)[xn（k=1，2，...，n）]出發(fā)至過程最終，當(dāng)采取某種子策略時，按預(yù)定的標(biāo)準(zhǔn)得到的效益值。這個值既與[xk]本身的狀態(tài)值有關(guān)，又與[xk]以后所選取的策略有關(guān)，它是兩者的函數(shù)值，記作[dk，nxk，uk，xk+1，uk+1，…xn，un]。過程的指標(biāo)函數(shù)又是它所包含的各階段指標(biāo)函數(shù)的函數(shù)。本文研究的過程的的指標(biāo)函數(shù)是其各階段指標(biāo)函數(shù)的和的形式.當(dāng)[xk]的值確定后，指標(biāo)函數(shù)的值就只同k階段起的子策略有關(guān)。對應(yīng)于從狀態(tài)[xk]出發(fā)的最優(yōu)子策略的效益值記作[fkxk]，于是在最短路問題中，有[fkxk=mindk，n]。動態(tài)規(guī)劃求解最短路徑程序流程圖如圖2所示。

3 最短路徑態(tài)規(guī)劃實際應(yīng)用舉例

設(shè)某物流配送網(wǎng)絡(luò)圖由12個配送點組成，點1為配送中心起點，12為終點，試求自終點到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標(biāo)有兩點間的距離[4]。

首先用動態(tài)規(guī)劃法來討論圖3的最短路徑，由圖可知：

1）集合[ξ4]中有點9、10、11，它們在一步之內(nèi)可到達(dá)點12；

2）集合[ξ3]中有點6，7，8，它們不超過兩步就可達(dá)到點12；

3）集合[ξ2]中包括點 2、3、4、5，不超過三步就可到達(dá)點12；

4）集合[ξ1]中包括點1，不超過四步可到達(dá)點12；

按照動態(tài)規(guī)劃法類推，得到最優(yōu)路徑長為16，徑路通過點為1，2，7，10，12和1，3，6，10，12。

根據(jù)動態(tài)規(guī)劃算法編寫C語言計算程序[5] [6]，計算得到實驗結(jié)果如下圖4所示：

由圖4可以看出程序得到的結(jié)果與本文推出的結(jié)果一樣。證明了本文編寫的C語言程序是正確的。

4 結(jié)束語

綜上所述，用動態(tài)規(guī)劃解決多階段決策問題效率高，而且思路清晰簡便，同時易于實現(xiàn).我們可以看到，動態(tài)規(guī)劃方法的應(yīng)用很廣泛，已成功解決了許多實際問題，具有一定的實用性。此種算法我們用動態(tài)規(guī)劃思想來編程，并解決相應(yīng)的問題，其在 VC 環(huán)境下實現(xiàn)，能方便快速的計算出到達(dá)目的地的最短距離及路徑，節(jié)省更多的運輸時間與成本。不過，該文只考慮了動態(tài)規(guī)劃算法在生活中的簡單運用，在實際生活中可能存在多個目的地或者更復(fù)雜的情況.因此我們可以考慮將其進(jìn)行改進(jìn)或者結(jié)合啟發(fā)式算法，使之更好的運用在實際生活中，這有待于以后的繼續(xù)研究。

參考文獻(xiàn)：

[1] 杜彥娟.利用動態(tài)規(guī)劃數(shù)學(xué)模型求解最短路徑[J].煤炭技術(shù)，2005（1）：94-95.

[2] 蔣琦瑋，陳治亞.物流配送最短徑路的動態(tài)規(guī)劃方法研究[J].系統(tǒng)工程，2007（25）：27-29.

[3] 朱建民.運籌學(xué)——典型例題與解法[EB/OL].http：//www.zytxs.com/，2003.