基于動態(tài)規(guī)劃的最短路線問題研究

羅鑫 深圳市科學(xué)高中

引言：動態(tài)規(guī)劃從1951年提出由貝爾曼先生提出以來，經(jīng)過幾十年的發(fā)展，動態(tài)規(guī)劃已經(jīng)成為運(yùn)籌學(xué)研究中必不可少的一個部分。并廣泛應(yīng)用于管理科學(xué)，生產(chǎn)規(guī)劃等領(lǐng)域。經(jīng)驗表明，應(yīng)用動態(tài)規(guī)劃法對這些復(fù)雜問題進(jìn)行求解，比起其他方法能取得更好的效果。

最短路線問題則是圖和網(wǎng)絡(luò)中一個非常經(jīng)典的問題，前人做了很多相關(guān)的研究工作，最短路徑問題能夠涵蓋現(xiàn)實(shí)生活中的很多方面，比如研究網(wǎng)絡(luò)圖中每個點(diǎn)間的最短路線，或者研究所有的點(diǎn)到某一個點(diǎn)的最短路線。而構(gòu)成這些網(wǎng)絡(luò)圖的可以是有向圖，也可以是無向圖，并且還可以帶有負(fù)的權(quán)值。而最短路線的解法也多種多樣，有動態(tài)規(guī)劃法，0-1整數(shù)規(guī)劃法，F(xiàn)loyd法等。本文主要對動態(tài)規(guī)劃法怎樣求解有向圖無負(fù)權(quán)值的最短路線問題進(jìn)行研究。

眾多研究當(dāng)中，蔣琦瑋等在解決最短路徑問題時，將整個求解問題分為若干個階段，利用貝爾曼方程和狀態(tài)方程求得當(dāng)前階段的最優(yōu)決策，并將最優(yōu)決策代入下一個階段繼續(xù)求解，如此類推得到最優(yōu)路徑。經(jīng)過標(biāo)號法驗證，求得的結(jié)論正確，此方法思路清晰，也比較簡便[1]。孫曉燕等基于運(yùn)輸路徑問題建立了一個數(shù)學(xué)模型，將實(shí)際問題分為恰當(dāng)?shù)碾A段，設(shè)置狀態(tài)變量，列出決策變量，根據(jù)變量寫出具有可分離性和遞推性的指標(biāo)函數(shù)，最后利用動態(tài)規(guī)劃函數(shù)基本方程求得最優(yōu)決策[2]。

本文也將利用LINGO對動態(tài)規(guī)劃求解最短路線問題進(jìn)行建模，并且對比我們手工計算的過程，可以看出軟件的計算效率遠(yuǎn)遠(yuǎn)高于手工計算。

一、動態(tài)規(guī)劃

動態(tài)規(guī)劃法用于求解最短路徑問題的過程如下：

（1）首先是將整個問題恰當(dāng)?shù)貏澐譃槎鄠€階段，每個階段都是同類型的子問題，并且定義每個階段的狀態(tài)變量，選擇合適的決策變量和定義最短路線函數(shù)。

（2）多階段決策中，我們從最后一個階段開始進(jìn)行決策的選擇，依次遞推到第一個階段。每個階段的最優(yōu)決策都要代入到上一個階段的決策過程中去，遞推到第一階段，即初始階段的最優(yōu)決策就是整個問題的最優(yōu)解。

（3）動態(tài)規(guī)劃的多階段決策過程和每一個單獨(dú)的階段決策過程相聯(lián)系，這樣可以使得求出的最后結(jié)果得到的是全局最優(yōu)值，而不是單獨(dú)的局部最優(yōu)值。這也是動態(tài)規(guī)劃法得以廣泛應(yīng)用的一大原因。動態(tài)規(guī)劃的基本形式可以簡寫成：

其中i表示網(wǎng)絡(luò)圖中的任意一點(diǎn)，j表示從i出發(fā)的到終點(diǎn)n的點(diǎn)，1表示是起點(diǎn)，且終點(diǎn)。比如在最后一個階段中，。i為與終點(diǎn)n相連接的點(diǎn)。表示這一階段的階段指標(biāo)或者叫做這一階段狀態(tài)取某一決策時的指標(biāo)函數(shù)值。最短路問題中最優(yōu)函數(shù)取最小值。

二、最短路問題

（一）最短路問題定義

最短路問題常在物流配送問題，運(yùn)輸問題等領(lǐng)域出現(xiàn)，由于時間空間或成本的限制，需要選擇一條最優(yōu)路線，通常就是最短路線，因此，選擇最短路線是提高商品貨物時空價值的重要環(huán)節(jié)。關(guān)于最短路問題，Dijstra算法和Floyd算法相對來說求解比較簡單，而且思路也很清晰。但是隨著節(jié)點(diǎn)的增加，求解的復(fù)雜程度也會大大增加，有著一定的局限性。本文基于動態(tài)規(guī)劃法研究了最短路線的求解問題，并使用了計算機(jī)軟件LINGO，思路清晰，方法簡便且不復(fù)雜。如下將會用一個例子來說明這類問題。

（二）最短路問題舉例

如下圖1所示，A,B,…K,L表示已知的10個城市，連線表示城市間有路直接相通，其中的數(shù)字表示路的長度，用Wij表示。假設(shè)有一個旅客，要從城市A到L，請求找出一條最短路線。

圖1 10個城市之間的道路網(wǎng)絡(luò)圖

分析：可以將該復(fù)雜問題分為四個簡單的階段，第一階段從A到B,C或D，屬于一類同質(zhì)問題，第二階段到E,F或G，第三階段到H或K，最后一階段到達(dá)終點(diǎn)G?，F(xiàn)在我們從終點(diǎn)L向前遞推。

解法：

第四階段：從H,K到G的最短路分別為8，10，記為f(H)=8，f(K)=10；

第三階段：與H,K有連線的出發(fā)點(diǎn)為E,F,G，從E出發(fā)分別經(jīng)過H,K，至終點(diǎn)L的里程分別為：

WEH+f(H)=18+8=26；

WEK+f(K)=10+10=20;

第二階段：與E,F,G相連的出發(fā)點(diǎn)有B,C,D，從B出發(fā)可以經(jīng)過E,F,G到達(dá)終點(diǎn)L的長度為：

故B到終點(diǎn)L的最短路是上述三者的最小值29，可以用f(B)=min{WBj+f(j) }=29表示；從C出發(fā)經(jīng)過E,G到終點(diǎn)L的里程分別為：

故C到終點(diǎn)L的最短路是上述二者的最小值27，可以用f(C)=min{WCj+f(j) }=27表示；從D出發(fā)經(jīng)過E,F,G到終點(diǎn)L的里程分別為：

故D到終點(diǎn)L的最短路是上述三者的最小值3 0，可用f(D)=min{WDj+f(j) }=30表示, j是上一步考察過的三個點(diǎn)E,F,G；

第一階段，現(xiàn)在的出發(fā)點(diǎn)只剩下A，則從A開始可以經(jīng)過B,C,D到達(dá)終點(diǎn)L的路線長度分別為：

故A到L的最短路是上述三者的最小值3 6，可以寫成f(A)=min{WAj+f(j) }=36， j是第二階段考察過的三個點(diǎn)B,C,D。則綜上，從A到L的最短路為36。

三、LINGO軟件

（一）LINGO軟件介紹

LINGO軟件是Lindo軟件公司開發(fā)，用于求解最優(yōu)化問題的規(guī)劃工具。它最初開發(fā)的目的是用于求解整數(shù)規(guī)劃問題，這是許多其他軟件都不能求解的。隨著時間的發(fā)展，它還可以用于求解其他的規(guī)劃問題，比如非線性規(guī)劃等。并且內(nèi)置多個函數(shù)，無需使用者自己開發(fā)這些函數(shù)，并且能和其他軟件進(jìn)行數(shù)據(jù)交互，這些特點(diǎn)，使得LINGO成為了廣受歡迎的數(shù)學(xué)計算軟件之一。

（二）動態(tài)規(guī)劃的代碼求解過程

model：

sets：

cities/A,B,C,D,E,F,G H K L/：FL; !定義10個城市;

roads(cities,cities)/A,B A,C A,D B,E B,F B,G C,E C,G D,E D,F D,G E,H E,K F,H F,K G,H G,K H,L K,L/：W,P;!列舉出所有的城市間相連的路徑，其中W表示路的長度，P用來存放最短路的路徑;

endsets

data：

W=11 9 7 9 16 20 7 7 12 8 10 18 10 15 12 20 22 8 10;

enddata

N=@size(cities);

FL(N)=0;!終點(diǎn)的F值為0;

@for(cities(i)|i#LT#N：FL(i)=@min(roads(i,j)：W(i,j)+FL(j)));!由此，我們可以計算出最短路;

@for(roads(i,j)：P(i,j)=@if(FL(i) #EQ# W(i,j)+FL(j),1,0));

end

由于不是每一個城市到其余的城市都有路直接連通，因此我們需要在代碼中特別標(biāo)明這些連通的路徑，得到的矩陣也就是一個稀疏的矩陣。

最后得到的計算結(jié)果如下表所示：

表1 求解結(jié)果

一行的N在這個問題中表示城市A,B,…,K,L，后面的數(shù)字表示城市個數(shù);FL(N)表示出發(fā)點(diǎn)到終點(diǎn)的里程，第三列為兩個城市之間的路線，后面的數(shù)字說明是否最優(yōu)決策，即指標(biāo)函數(shù)值，如P(D,E)的指標(biāo)函數(shù)值為0，則該路線不是最優(yōu)決策，不代入下一階段，而P(D,F)的指標(biāo)函數(shù)值取1，就代入到下一階段求解。P(A,C)中A為起始點(diǎn)，其指標(biāo)函數(shù)值為1，則可一一推出最佳路線為A→C→E→K→L，F(xiàn)L(A)的值為從A到L的最短里程。

四、結(jié)論

本文以動態(tài)規(guī)劃原理為基礎(chǔ)對最短路問題進(jìn)行研究，利用了計算機(jī)軟件LINGO結(jié)合動態(tài)規(guī)劃法建立相關(guān)的數(shù)學(xué)求解模型。該模型思路清晰，方法簡便，容易理解。實(shí)際生活中有很多類型的最短路問題，很多都轉(zhuǎn)換成多階段的決策問題，然后再利用動態(tài)規(guī)劃方法進(jìn)行求解。并且隨著計算機(jī)的發(fā)展，用軟件進(jìn)行計算是一種非常有效的方式。