算法設(shè)計(jì)與分析論文

1、任意結(jié)點(diǎn)間的最短路徑方法的分析與研究摘要dijkstra算法是圖論中的著名算法，可用于計(jì)算網(wǎng)絡(luò)圖中某一點(diǎn)到各點(diǎn)的最短距離，但實(shí)際問題中有時(shí)需要求網(wǎng)絡(luò)中所有各點(diǎn)之間的最短距離，如果仍采用dijkstra算法分別計(jì)算，則需要對(duì)其執(zhí)行多次，效率低。動(dòng)態(tài)規(guī)劃方法主要是研究與解決多階段決策過程的最優(yōu)化問題，也是求最短路問題的好算法。動(dòng)態(tài)規(guī)劃方法是將求解分成多階段進(jìn)行，求出的不但是全過程的解，而且包括后部子過程的一族解，在某些情況下，實(shí)際問題需要族解時(shí)，更顯優(yōu)越性。用動(dòng)態(tài)規(guī)劃方法求解最短路問題時(shí)，要求所求問題具有明顯的階段。本文分別討論了這兩種算法，論證了動(dòng)態(tài)規(guī)劃方法在求解所有結(jié)點(diǎn)之間最短距離問題的優(yōu)越性

2、。關(guān)鍵字：最短路 dijkstra算法 動(dòng)態(tài)規(guī)劃 abstractdijkstra algorithm is a well-known algorithms in graph theory can be used to calculate the network diagram to a point in the shortest distance between points, but the real question to be asked sometimes all of the network the shortest distance between points, respect

3、ively, if the still use the dijkstra algorithm for computing , you need to perform several times and low efficiency. dynamic programming method is to study multi-stage decision-making process and resolving the optimization problem, find the shortest path problem is a good algorithm. solve the dynami

4、c programming approach is to be divided into multiple stages, find the only solution of the whole process, but also the process of the rear sub-family of solutions, in some cases, the family of solutions of practical problems, the more advantages. dynamic programming method for solving the shortest

5、path problem, ask the obvious question seeking stage. this paper discusses the two algorithms, dynamic programming method demonstrated in solving the shortest distance between all nodes in the superiority of the problem.keywords: shortet route , dijkstra algorithm, dynamic programming 1 引言生產(chǎn)實(shí)踐，運(yùn)輸管理以

6、及工程建設(shè)的許多方面，諸如各種工藝路線的安排，廠區(qū)及貨場(chǎng) 的布局，管道線網(wǎng)的鋪設(shè)等問題，都與尋找一個(gè)圖的最短路徑問題密切相關(guān)。目前最短路徑算法在智能系統(tǒng)的代價(jià)驅(qū)動(dòng)搜索，神經(jīng)元網(wǎng)絡(luò)等研究領(lǐng)域也越來越受到重視。在這些研究中，不僅要尋找一個(gè)圖的最短路徑，而且要不斷生成新圖，不斷尋找新的最短路徑。先來看一下常見的問題：要從甲地到乙地去，而甲乙兩地之間有多條交通線相連，這些交通線可以是公路、水路、鐵路、航空線等，走哪條交通線才最好呢？這“最好”在不同的情況下有著不通過的含義，或者是距離最短，或者是時(shí)間最少，或者是旅費(fèi)最省等，但抽象起來則都是在有向圖中求兩指定結(jié)點(diǎn)最短路徑問題。設(shè)用一個(gè)帶權(quán)的圖來表示一個(gè)交

7、通運(yùn)輸網(wǎng)絡(luò)，用圖的頂點(diǎn)表示城市，用圖中的各條邊表示城市之間的交通運(yùn)輸路線，每條邊上所附的權(quán)值表示該路線的長度或沿此路線運(yùn)輸所花費(fèi)的時(shí)間或運(yùn)費(fèi)等。這種運(yùn)輸路線往往有方向性，例如汽車的上山和下山，輪船的順?biāo)湍嫠ㄙM(fèi)的時(shí)間或代價(jià)就不相同。所以交通運(yùn)輸網(wǎng)絡(luò)往往是用帶權(quán)有向圖表示。所謂最短路徑問題是指：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上個(gè)邊上的權(quán)值和達(dá)到最小。2 貪心方法 有這樣一類問題：它有n個(gè)輸入，而它的解就由這n個(gè)輸入的某個(gè)子集組成，只是這個(gè)子集必須滿足某些事先給定的條件(約束條件)。把滿足約束條件的子集稱為該問題的可行解

8、。顯然，滿足約束條件的子集可能不止一個(gè)，因此可行解一般來說不是唯一的。為了衡量可行解的優(yōu)劣，事先也給出了一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)一般以函數(shù)的形式給出，這些函數(shù)稱為目標(biāo)函數(shù)。使目標(biāo)函數(shù)取極大值或極小值的可行解稱為最優(yōu)解。貪心方法是一種改進(jìn)了的分級(jí)處理方法，它首先根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序，并按序依次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法稱為貪心方法。要注意的是，對(duì)于一個(gè)給定的問題，往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來這些量度標(biāo)準(zhǔn)似乎都是可

9、取的。但實(shí)際上，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪心處理所得到該量度意義下的解不一定是問題的最優(yōu)解。因此，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法設(shè)計(jì)求解的核心問題。在一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，不過，一旦能選擇出某個(gè)問題的最優(yōu)量度標(biāo)準(zhǔn)，那么用貪心方法求解這個(gè)問題則特別有效。貪心方法和動(dòng)態(tài)規(guī)劃的的主要區(qū)別是：貪心方法的每一步的最優(yōu)解一定依賴上一步的最優(yōu)解。而動(dòng)態(tài)規(guī)劃全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此動(dòng)態(tài)規(guī)劃需要記錄之前的所有最優(yōu)解。3 貪心策略的最短路徑問題的提法是：給定一個(gè)帶權(quán)有向圖d與源點(diǎn)v，求從v到d中其他頂點(diǎn)的最短路徑，若求所有頂

10、點(diǎn)之間的最短路徑，則加一個(gè)外重循環(huán)，將每一個(gè)頂點(diǎn)依次作為源點(diǎn)考慮。為了求得這些最短路徑，dijkstra提出了按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。為了制定產(chǎn)生最短路徑的貪心基礎(chǔ)算法，對(duì)于這個(gè)問題應(yīng)該相處一個(gè)多級(jí)解決辦法和一種最優(yōu)的量度標(biāo)準(zhǔn)。方法是構(gòu)造這些最短路徑，可以使用迄今已生成的所有路徑長度之和作為一種量度，為了使這一量度達(dá)到最小，其單獨(dú)的每一條路徑都必須具有最小長度。使用這一量度標(biāo)準(zhǔn)時(shí)，假定已經(jīng)構(gòu)造了i條最短路徑，則下面要構(gòu)造的祿紀(jì)念館應(yīng)該是下一條最短的最小程度路徑。生成從v到所有其它結(jié)點(diǎn)的最短路徑的貪心方法就是按照路徑長度的非降次序生成這些路徑。作為一個(gè)例子，考慮如圖1所示的

11、帶權(quán)有向圖。邊上的數(shù)字即為該邊的長度，并設(shè)源點(diǎn)位頂點(diǎn)0。按照dijkstra算法，首先應(yīng)用其鄰接矩陣的第0行，求出從頂點(diǎn)0到其它各頂點(diǎn)最短路徑的初步結(jié)果；以后逐步求最短路徑的過程如圖2所示。具體做法是：設(shè)集合s存放已經(jīng)求出的最短路徑的終點(diǎn)，初始狀態(tài)時(shí)，集合s中只有一個(gè)源點(diǎn)，不妨設(shè)為v。以后每求得一條最短路徑(v,v),就將v加入到集合s中，知道全部頂點(diǎn)都加入到集合s中算法就可以結(jié)束了。01423105020601003010(a) 帶權(quán)有向圖圖1 帶權(quán)有向圖及其鄰接矩陣表示 0 1 2 3 4(b) 鄰接矩陣為了找到當(dāng)前找到的從源點(diǎn)v到其它頂點(diǎn)的最短路徑長度，再引入一個(gè)輔助數(shù)組dist。它的每

12、一個(gè)分量disti表示當(dāng)前找到的從源點(diǎn)v到終點(diǎn)v的最短路徑的長度。它的初始狀態(tài)是：若從源點(diǎn)v到頂點(diǎn)v有邊，則disti為該邊上的權(quán)值；若從源點(diǎn)v到頂點(diǎn)v沒有邊，則disti為(在程序中用機(jī)器可表示的最大正數(shù)maxnum代表)。設(shè)一條最短路徑為(v，v)，其中k滿足： distk= 其中v是d的頂點(diǎn)集合源點(diǎn)終點(diǎn)最短路徑路徑長度圖2 dijkstra算法逐步求解的過程vv(v, v)90v(v, v，v)(v, v，v)6050v(v, v )v(v, v) )(v, v，v)(v, v，v，v)10060那么下一最短路徑是哪一條呢？ 假設(shè)下次最短路徑的重點(diǎn)是v，則可想而知，它或者是(v,v),或

13、者是(v,v,v)，其長度或者是從v到v的有向邊上的權(quán)值，或者是distk與從v到v的有向邊上的權(quán)值之和。一般情況下，假設(shè)s是以求得的最短路徑的終點(diǎn)的集合，則可以證明：下一條最短路徑必然是從v出發(fā)，中間只經(jīng)過s中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)v(vv-s)的路徑中的一條。這可以用反證法證明。設(shè)在此路徑上存在一個(gè)頂點(diǎn)vv-s，則說明還存在一條終點(diǎn)不再s而長度比此路徑短的路徑，然而這時(shí)不可能的。因?yàn)閐ijkstra方法是按照最短路徑的長度遞增的次序來逐次產(chǎn)生各條最短路徑的，因此，長度比這條路徑短的所有路徑均已產(chǎn)生，而且它們的終點(diǎn)也一定已在集合s中，故假設(shè)不成立。因此在一般情況下，下一條長度次短的最短路徑

14、長度必是： distk=在每一次求得一條最短路徑之后，其終點(diǎn)v加入集合s，然后對(duì)所有的vv-s，修改其disti: disti=mindisti,distk+edgeki其中，edgeki是邊(v,v)上的權(quán)值。上述方法只是求得了一個(gè)結(jié)點(diǎn)到所有的其他結(jié)點(diǎn)的最短距離，在此方法上對(duì)圖中的每一個(gè)結(jié)點(diǎn)依次選取為源點(diǎn)，即可求出所有結(jié)點(diǎn)之間的最短路徑。其總的時(shí)間復(fù)雜度為o(n)。此方法較為復(fù)雜，而且還存在一些問題，例如，假若從源點(diǎn)到某結(jié)點(diǎn)的有多條路，而且這幾條路權(quán)值和相等，那么此時(shí)dijkstra算法將只會(huì)找到其中一條路，另外的路被舍去了，這在實(shí)際中會(huì)丟失參考一些的價(jià)值。下面將介紹另一種用動(dòng)態(tài)規(guī)劃的方法求

15、得所有結(jié)點(diǎn)之間最短路徑的方法。4 動(dòng)態(tài)規(guī)劃我們?cè)诠ぷ鲗W(xué)習(xí)中，遇見過這樣的問題，它的活動(dòng)過程可以分為若干個(gè)階段，而且在任一階段后的行為都僅依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)，這樣的過程就構(gòu)成一個(gè)多階段決策過程。50年代，貝爾曼等人根據(jù)這類問題的多階段決策的特性，提出了解決這類問題的“最優(yōu)性原理”，創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計(jì)方法-動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃的目標(biāo)是要在所有容許選擇決策序列中選取一個(gè)會(huì)獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。用枚舉的方法從所有可能的決策序列中選取最優(yōu)決策序列是一種最笨拙的方法。利用最優(yōu)性原理以及所獲得的遞推關(guān)系式去求取最優(yōu)決策序列

16、可以使枚舉量急劇下降。這個(gè)原理指出：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。如果所求解問題的最優(yōu)性原理成立，則說明用動(dòng)態(tài)規(guī)劃的方法有可能解決該問題，而解決問題的關(guān)鍵在于獲取各階段間的遞推關(guān)系式。5 每對(duì)結(jié)點(diǎn)間最短路徑的動(dòng)態(tài)規(guī)劃方法前面研究討論了在dijkstra方法的基礎(chǔ)上求得每對(duì)結(jié)點(diǎn)間的最短路徑長度，就是輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行dijkstra算法n次，就可求得每一對(duì)頂點(diǎn)之間的最短路徑長度，總的執(zhí)行時(shí)間是o(n)下面利用動(dòng)態(tài)規(guī)劃方法來設(shè)計(jì)這個(gè)問題的另一種算法，雖然它要求的計(jì)算時(shí)間仍是o(n),但在邊成本上要求的約束條件要弱些

17、。它只要求圖不含負(fù)長度的環(huán)即可，而不是要求圖中所有的邊權(quán)值都要是非負(fù)數(shù)。動(dòng)態(tài)規(guī)劃方法仍然使用前面定義的圖的鄰接矩陣edgenn來存儲(chǔ)帶權(quán)有向圖。算法的基本思想是：設(shè)置一個(gè)nn的方陣a,其中除對(duì)角線的矩陣元素都等于0外，其它元素aij(ij)表示從頂點(diǎn)v到頂點(diǎn)v的有向路徑長度，k表示運(yùn)算步驟。初始時(shí)，以任意兩個(gè)頂點(diǎn)之間的直接有向邊的權(quán)值作為路徑長度：對(duì)于任意兩個(gè)頂點(diǎn)v和v，若它們之間存在有向邊，則以此邊上的權(quán)值作為它們之間的最短路徑長度；若它們之間不存在有向邊，則以maxnum(機(jī)器可表示的在問題中不會(huì)遇到的最大數(shù))作為它們之間的最短路徑長度，因此a=edge。以后逐步嘗試在原路徑中加入其它頂點(diǎn)

18、作為中間頂點(diǎn)。如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素，代入新的更短的路徑長度。如圖3。從頂點(diǎn)v到頂點(diǎn)v的邊的權(quán)值為5，當(dāng)加入中間頂點(diǎn)v后，從v經(jīng)過v再到v的權(quán)值之和為4，小于原來的權(quán)值5，則以此新路徑的長度作為從頂點(diǎn)v到頂點(diǎn)v的距離, 并修改相應(yīng)地矩陣元素。需要加以說明的是，考慮頂點(diǎn)v作為中間頂點(diǎn)可能還會(huì)改變其它頂點(diǎn)之間的距離，例如，路徑的長度為7，小于原來有向邊上的權(quán)值8，矩陣元素也要修改，這種修改會(huì)對(duì)以后的運(yùn)算產(chǎn)生影響。如果在下一步又增加頂點(diǎn)v作為中間頂點(diǎn)，對(duì)于圖中的每一條有向邊,要比較從v到v的路徑長度加上從v到v的路徑長度是否小于原來

19、從v到v的路徑長度，即+？如果小，又需用此新值代替原值作為元素的值。這時(shí)，從v到v的路徑長度，以及從v到v的路徑長度已經(jīng)由于v作為中間頂點(diǎn)而修改過了，所以最新的值實(shí)際包含了頂點(diǎn)v，v，v，v的路徑的長度。如上圖3所示，元素在引入中間頂點(diǎn)v后，其值減為7，在引入中間頂點(diǎn)v后，其值又減為6。但有時(shí)加入中間頂點(diǎn)后的路徑較原路徑更長，這是就維持原來相應(yīng)地矩陣元素的值不變。依此類推，可以得到如下的遞推關(guān)系式：623014892130 1 2 3(a)(b)圖3 帶權(quán)有向圖及其鄰接矩陣定義一個(gè)n階方陣序列：a，a，a，a，其中：a=edge；a=mina,a+a,k=0,1,n-1從上述公式可以得知，a是從頂點(diǎn)v到v，中間頂點(diǎn)是v的最短路徑的長度，a是從頂點(diǎn)v到v，中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長度，那么最后a是從頂點(diǎn)v到v的最短路徑長度。下圖4為求解的矩陣的結(jié)果。aa0 1 2 3a0 1 2 3a0 1 2 3a0 1 2 30 1 2 3圖4 動(dòng)態(tài)規(guī)劃方法矩陣a求解結(jié)果動(dòng)態(tài)規(guī)劃的最短路徑方法允許圖中帶負(fù)權(quán)值的邊，但不允許有包含帶負(fù)權(quán)值的邊組成的回路，此方法不僅適用于帶權(quán)有向圖，對(duì)帶權(quán)無向圖也可以使用，因?yàn)閹?quán)無向圖可以看作是有往返