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

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

2、。關(guān)鍵字：最短路 dijkstra算法 動態(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)實踐，運輸管理以

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

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

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

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

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

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

12、一個分量disti表示當(dāng)前找到的從源點v到終點v的最短路徑的長度。它的初始狀態(tài)是：若從源點v到頂點v有邊，則disti為該邊上的權(quán)值；若從源點v到頂點v沒有邊，則disti為(在程序中用機器可表示的最大正數(shù)maxnum代表)。設(shè)一條最短路徑為(v，v)，其中k滿足： distk= 其中v是d的頂點集合源點終點最短路徑路徑長度圖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è)下次最短路徑的重點是v，則可想而知，它或者是(v,v),或

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

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

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

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

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

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

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