最短路徑數(shù)學(xué)建模

最短路徑問(wèn)題是一個(gè)非常能聯(lián)系實(shí)際的問(wèn)題，下面我們以具體例題來(lái)看看這類問(wèn)題的解法例1、假設(shè)A、B、C、D、E各個(gè)城市之間旅費(fèi)如下圖所示。某人想從城市A出發(fā)游覽各 2 & 0 v/ M( T9 A% V- N) e! - 城市一遍，而所用費(fèi)用最少。試編程序輸出結(jié)果。 ) H9 n# r2 w9 u$ O; U解這類題時(shí)同學(xué)們往往不得要領(lǐng)，不少同學(xué)采用窮舉法把所有可能的情況全部列出，再找出其中最短的那條路徑；或是采用遞歸或深度搜索，找出所有路徑，再找出最短的那條。這兩種方法可見(jiàn)都是費(fèi)時(shí)非常多的解法，如果城市數(shù)目多的話則很可能要超時(shí)了。 _4 M5 G: M# , 7 實(shí)際上我們知道，遞歸、深度搜索等算法一般用于求所有解問(wèn)題（例如求A出發(fā)每個(gè)城市走一遍一共有哪幾種走法），而這幾種算法對(duì)于求最短路徑這類最優(yōu)解問(wèn)題顯然是不合適的，以下介紹的幾種算法就要優(yōu)越很多。 / w: L6 |3 R5 D8 J6 F首先，對(duì)于這類圖我們都應(yīng)該先建立一個(gè)鄰接矩陣來(lái)存放任意兩點(diǎn)間的距離數(shù)據(jù)，以便在程序中方便調(diào)用，如下： / m# K! x& s* jconst dis:array1.5,1.5 of integer =( ( 0, 7, 3,10,15), 1 _1 w( , j$ , a e, x& U) L( 7, 0, 5,13,12), . m. A5 I C3 ?% _$ e( 3, 5, 0, 5,10), w, t7 R. M7 Y i(10,13, 5, 0,11), / d. P, Y a- d% O j(15,12,10,11, 0); ; 1 & k0 H6 Y以下是幾種解法： + 1 I0 D5 a( r: L# m5 A4 L( n一、 寬度優(yōu)先搜索 S2 y0 v6 E 寬度優(yōu)先搜索并不是一種很優(yōu)秀的算法，只里只是簡(jiǎn)單介紹一下它的算法。 S8 I A% k3 e, n0 F. C具體方法是： ; J o- J$ _: o8 I1、 從A點(diǎn)開(kāi)始依次展開(kāi)得到AB、AC、AD、AE四個(gè)新結(jié)點(diǎn)（第二層結(jié)點(diǎn)），當(dāng)然每個(gè)新結(jié)點(diǎn)要記錄下其距離； 2 p. o% k$ K3 * F j. $ 4 2、 再次以AB展開(kāi)得到ABC、ABD、ABE三個(gè)新結(jié)點(diǎn)（第三層結(jié)點(diǎn)），而由AC結(jié)點(diǎn)可展開(kāi)得到ACB、ACD、ACE三個(gè)新結(jié)點(diǎn)，自然AD可以展開(kāi)得到ADB、ADC、ADE，AE可以展開(kāi)得到AEB、AEC、AED等新結(jié)點(diǎn)，對(duì)于每個(gè)結(jié)點(diǎn)也須記錄下其距離； 0 |* c# S9 h2 N/ j% E0 u l3、 再把第三層結(jié)點(diǎn)全部展開(kāi)，得到所有的第四層結(jié)點(diǎn)：ABCD、ABCE、ABDC、ABDE、BEC、ABEDAEDB、AEDC，每個(gè)結(jié)點(diǎn)也需記錄下其距離； y& p) $ Z) k2 ?4、 再把第四層結(jié)點(diǎn)全部展開(kāi)，得到所有的第五層結(jié)點(diǎn)：ABCDE、ABCED、AE ! n+ n8 # F; 5 Q1 G! T/ dDBC、AEDCB，每個(gè)結(jié)點(diǎn)也需記錄下其距離； . M! f# Q. F+ a; h$ P+ K1 Q! p+ Y5、 到此，所有可能的結(jié)點(diǎn)均已展開(kāi)，而第五層結(jié)點(diǎn)中最小的那個(gè)就是題目的解了。 7 I7 : w2 ) R% a2 U1 R由上可見(jiàn)，這種算法也是把所有的可能路徑都列出來(lái)再找最短的那條，顯而易見(jiàn)這也是一種很費(fèi)時(shí)的算法。 ( h/ e$ 3 D8 7 V9 B- b: G二、 A算法 . D0 e# _9 G CA算法是在寬度優(yōu)先搜索算法的基礎(chǔ)上，每次并不是把所有可展的結(jié)點(diǎn)展開(kāi)，而是對(duì)所有沒(méi)有展開(kāi)的結(jié)點(diǎn)，利用一個(gè)自己確定的估價(jià)函數(shù)對(duì)所有沒(méi)展開(kāi)的結(jié)點(diǎn)進(jìn)行估價(jià)，從而找出最應(yīng)該被展開(kāi)的結(jié)點(diǎn)（也就是說(shuō)我們要找的答案最有可能是從該結(jié)點(diǎn)展開(kāi)），而把該結(jié)點(diǎn)展開(kāi)，直到找到目標(biāo)結(jié)點(diǎn)為止。 z2 8 e5 A4 4 g這種算法最關(guān)鍵的問(wèn)題就是如何確定估價(jià)函數(shù)，估價(jià)函數(shù)越準(zhǔn)則越快找到答案。A算法實(shí)現(xiàn)起來(lái)并不難，只不過(guò)難在找準(zhǔn)估價(jià)函數(shù)，大家可以自已找資料看看。 * z: s P m% ?三、等代價(jià)搜索法 6 G* V * D f! M; L( w _等代價(jià)搜索法也是基于寬度優(yōu)先搜索上進(jìn)行了部分優(yōu)化的一種算法，它與A算法的相似之處都是每次只展開(kāi)某一個(gè)結(jié)點(diǎn)（不是展開(kāi)所有結(jié)點(diǎn)），不同之處在于：它不需要去另找專門的估價(jià)函數(shù)，而是以該結(jié)點(diǎn)到A點(diǎn)的距離作為估價(jià)值，也就是說(shuō)，等代價(jià)搜索法是A算法的一種簡(jiǎn)化版本。它的大體思路是： 0 l2 Y- r! ! w 7 t1、 從A點(diǎn)開(kāi)始依次展開(kāi)得到AB（7）、AC（3）、AD（10）、AE（15）四個(gè)新結(jié)點(diǎn)，把第一層結(jié)點(diǎn)A標(biāo)記為已展開(kāi)，并且每個(gè)新結(jié)點(diǎn)要記錄下其距離（括號(hào)中的數(shù)字）； , B j; N- W1 R2、 把未展開(kāi)過(guò)的AB、AC、AD、AE四個(gè)結(jié)點(diǎn)中距離最小的一個(gè)展開(kāi)，即展開(kāi)AC（3）結(jié)點(diǎn)，得到ACB（8）、ACD（16）、ACE（13）三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)AC標(biāo)記為已展開(kāi)；! l- k3 Z/ F, Q1 A6 U. C! g3、 再?gòu)奈凑归_(kāi)的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開(kāi)，即展開(kāi)AB（7）結(jié)點(diǎn)，得到ABC（12）、ABD（20）、ABE（19）三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)AB標(biāo)記為已展開(kāi)； + c0 z- t& R Z+ j Z4、 再次從未展開(kāi)的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開(kāi)，即展開(kāi)ACB（8）結(jié)點(diǎn)； / S4 j* H5 e9 o9 G+ N5、 每次展開(kāi)所有未展開(kāi)的結(jié)點(diǎn)中距離最小的那個(gè)結(jié)點(diǎn)，直到展開(kāi)的新結(jié)點(diǎn)中出現(xiàn)目標(biāo)情況（結(jié)點(diǎn)含有5個(gè)字母）時(shí)，即得到了結(jié)果。 : Q( u) 7 z7 O由上可見(jiàn)，A算法和等代價(jià)搜索法并沒(méi)有象寬度優(yōu)先搜索一樣展開(kāi)所有結(jié)點(diǎn)，只是根據(jù)某一原則（或某一估價(jià)函數(shù)值）每次展開(kāi)距離A點(diǎn)最近的那個(gè)結(jié)點(diǎn)（或是估價(jià)函數(shù)計(jì)算出的最可能的那個(gè)結(jié)點(diǎn)），反復(fù)下去即可最終得到答案。雖然中途有時(shí)也展開(kāi)了一些并不是答案的結(jié)點(diǎn)，但這種展開(kāi)并不是大規(guī)模的，不是全部展開(kāi)，因而耗時(shí)要比寬度優(yōu)先搜索小得多。 7 v8 i+ C. T) l. Y* g; n% . s例2、題目基本同例1、但只要求求A到E點(diǎn)的最短路徑（并不要求每個(gè)城市都要走一遍）。 : A& : i+ V3 Q+ w6 w+ X% I j5 L: w* b# p題目一改，問(wèn)題的關(guān)鍵變了，所要求的結(jié)果并不是要求每個(gè)點(diǎn)都要走一遍，而是不管走哪幾個(gè)點(diǎn)，只要距離最短即可。再用寬度優(yōu)先搜索已經(jīng)沒(méi)有什么意義了，那么等代價(jià)搜索能不能再用在這題上呢？ . d( 5 x, e& t w答案是肯定的，但到底搜索到什么時(shí)候才能得到答案呢？這可是個(gè)很荊手的問(wèn)題。 6 |& V: ? 1 n + p% i! T7 D是不是搜索到一個(gè)結(jié)點(diǎn)是以E結(jié)束時(shí)就停止呢？顯然不對(duì)。 ) B4 E7 i, E, t* W- Y那么是不是要把所有以E為結(jié)束的結(jié)點(diǎn)全部搜索出來(lái)呢？這簡(jiǎn)直就是寬度優(yōu)先搜索了，顯然不對(duì)。 6 Z* D ?( k: o3 o) l實(shí)際上，應(yīng)該是搜索到：當(dāng)我們確定將要展開(kāi)的某個(gè)結(jié)點(diǎn)（即所有未展開(kāi)的結(jié)點(diǎn)中距離最小的那個(gè)點(diǎn)）的最后一個(gè)字母是E時(shí)，這個(gè)結(jié)點(diǎn)就是我們所要求的答案！ : R+ B - % |8 q0 n: U那么，除了等代價(jià)搜索外，有沒(méi)有其它辦法了呢？下面就介紹求最短路徑問(wèn)題的第四種算法： ; y. R& Z- P O/ q5 M. % U: _四、Warshall算法 % o A( B! , i: A/ c4 m; q0 _ _0 C該算法的中心思想是：任意兩點(diǎn)i,j間的最短距離（記為Dij）會(huì)等于從i點(diǎn)出發(fā)到達(dá)j點(diǎn)的以任一點(diǎn)為中轉(zhuǎn)點(diǎn)的所有可能的方案中，距離最短的一個(gè)。即： 1 H8 a- - M5 K+ Dij=min(Dij,Dik+Dkj，)，1=k=5。 6 _& b5 T3 C, 這樣，我所就找到了一個(gè)類似動(dòng)態(tài)規(guī)劃的表達(dá)式，只不過(guò)這里我們不把它當(dāng)作動(dòng)態(tài)規(guī)劃去處理，而是做一個(gè)二維數(shù)組用以存放任意兩點(diǎn)間的最短距離，利用上述公式不斷地對(duì)數(shù)組中的數(shù)據(jù)進(jìn)行處理，直到各數(shù)據(jù)不再變化為止，這時(shí)即可得到A到E的最短路徑。 7 k& t% I- O3 S% l9 z- B# 算法如下： 4 o0 b; * U. a% N- M, q2 1、 把上述鄰接矩陣直接賦值給最短距離矩陣D； - e! V( G/ i+ w% V2、 i=1; 5 B) L/ . K0 d7 Z9 c3、 j=1； I+ I7 m$ D8 O$ e1 x0 N, I4、 repeat * o! U- G2 G8 X, O( s1 Y$ P7 t5、 c=false; 用以判斷第6步是否有某個(gè)Dij值被修改過(guò) : P5 b3 I. Q ( S6、 Dij=min(Dij,Dik+Dkj，), k=1 to 5 如果Dij被修改則c=true % h0 Y* t, a1 z7 a; q& A7、 I=I+1 3 Z6 L- L4 0 f% K B8、 J=j+1 ! j+ o) h1 T5 m M/ i2 k9 G5 R9、 Until not c 8 U2 v) W- Y/ n% C5 I10、 打印D15 # L6 O* A* t/ f這種算法是產(chǎn)生這樣一個(gè)過(guò)程：不斷地求一個(gè)數(shù)字最短距離矩陣中的數(shù)據(jù)的值，而當(dāng)所有數(shù)據(jù)都已經(jīng)不能再變化時(shí)，就已經(jīng)達(dá)到了目標(biāo)的平衡狀態(tài)，這時(shí)最短距離矩陣中的值就是對(duì)應(yīng)的兩點(diǎn)間的最短距離。 9 o + / K5 ( * j e五、動(dòng)態(tài)規(guī)劃 & M. , G; t+ J3 動(dòng)態(tài)規(guī)劃算法已經(jīng)成為了許多難題的首選算法，只不過(guò)在很多的題目中動(dòng)態(tài)規(guī)劃的算法表達(dá)式比較難找準(zhǔn)，而恰恰最短距離問(wèn)題如果用動(dòng)態(tài)規(guī)劃算法考慮則可以非常容易地找準(zhǔn)那個(gè)算法表達(dá)式。 * x( _* h! M9 F$ e c我們知道，動(dòng)態(tài)規(guī)劃算法與遞歸算法的不同之處在于它們的算法表達(dá)式： 6 o T2 i9 c/ I5 O8 U: h4 R遞歸：類似f(n)=x1*f(n-1)+x2*f(n-2)，即可以找到一個(gè)確定的關(guān)系的表達(dá)式； K0 P7 Z8 D J& V9 k m. O W* x$ n動(dòng)態(tài)規(guī)劃：類似f(n)=min(f(n-1)+x1,f(n-2)+x2)，即我們無(wú)法找到確定關(guān)系的表達(dá)式，只能找到這樣一個(gè)不確定關(guān)系的表達(dá)式，f(n)的值是動(dòng)態(tài)的，隨著f(n-1),f(n-2)等值的改變而確定跟誰(shuí)相關(guān)。 7 Z9 E / s1 - b就本題來(lái)說(shuō)，我們記f(5)為A到E點(diǎn)的最短距離，則f(4)為A到D點(diǎn)的最短距離，f(1)為A到A點(diǎn)的最短距離（為0）。 ; D# u R$ |1 _- I: d于是，f(5)的值應(yīng)該是所有與E點(diǎn)相鄰的點(diǎn)的最短距離值再加上該點(diǎn)到E點(diǎn)的直接距離（dis矩陣中的值）所得到的值中最小的一個(gè)