最短路徑問題的幾個算法.doc

《最短路徑問題的幾個算法.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、個人收集整理勿做商業(yè)用途　　　　　　最短路徑問題)r+g　?。?［５p）　W）J　最短路徑問題是一個非常能聯(lián)系實際的問題,某人想從城市Ａ出發(fā)游覽各城市一遍，而所用費用最少。試編程序輸出結(jié)果。?/c+ｒ2ｘ8　S7j!N４z　　解這類題時同學(xué)們往往不得要領(lǐng),不少同學(xué)采用窮舉法把所有可能的情況全部列出，再找出其中最短的那條路徑；或是采用遞歸或深度搜索,找出所有路徑，再找出最短的那條。這兩種方法可見都是費時非常多的解法，如果城市數(shù)目多的話則很可能要超時了。?/　N%M0K＊[&X2　A&Ｕ4ｌ.}/f實際上我們知道,遞歸、深度搜索

2、等算法一般用于求所有解問題(例如求A出發(fā)每個城市走一遍一共有哪幾種走法),而這幾種算法對于求最短路徑這類最優(yōu)解問題顯然是不合適的，以下介紹的幾種算法就要優(yōu)越很多。:V７　@）ｖ"g3＼　首先,對于這類圖我們都應(yīng)該先建立一個鄰接矩陣來存放任意兩點間的距離數(shù)據(jù)，以便在程序中方便調(diào)用,如下：?(?。?ｂ．x＋V／e3Z％Ｙ;ｙconstdis:array[1..５,1．.5]ofintegｅr=（（?。埃?　3,10,15），0　ｕ;　Y０Oi２Ｌ/i"　?　　　　　　　　　　　　(?。?　0,5,１３,1２)，?％　U５D#

3、I&L/　F（[）y（　ｊ9ｘ6　o　　　　　　　　　　(3,5,　0，　5，10），８I－　f"　E:D1　J?　　　　　　　　　　　　(１０,1３,５,　0,１1）,$W"P1｝8T,}+　px．　S-　Z!a　　　　　　　　　　　(15,１2，１0,11,?。?）;#p！L４　

4、＋　b;c)V　以下是幾種解法:３G３　ｃ#u'e－I７ｙ?一、寬度優(yōu)先搜索%O9Ｏ４　G３W,L９?。?Ｑ９O?　　寬度優(yōu)先搜索并不是一種很優(yōu)秀的算法,只里只是簡單介紹一下它的算法。$Q＂ｓ５d，b＄N／c３V，？+Z具體方法是:2　c　d6

5、Y)/　t9ｈ3ｃ/i１、從Ａ點開始依次展開得到AB、AC、AD、AE四個新結(jié)點（第二層結(jié)點）,當(dāng)然每個新結(jié)點要記錄下其距離；?1?1ｇ,G.

6、'ｎ＃D＊O）　^8　A　　2、個人收集整理勿做商業(yè)用途再次以AＢ展開得到ABC、ABD、AＢE三個新結(jié)點(第三層結(jié)點),而由ＡC結(jié)點可展開得到ＡCB、ACＤ、ACE三個新結(jié)點,自然AD可以展開得到ADB、AＤＣ、ADE，AE可以展開得到AEB、AEC、AＥＤ等新結(jié)點，對于每個結(jié)點也須記錄下其距離;５ｎ．?。?　^"Ｂ5`7A；v　3、　再把第三層結(jié)點全部展開,得到所有的第四層結(jié)點

7、：ABCＤ、ＡBCＥ、ABDC、AＢＤＥ、BEＣ、ABED……ＡＥDB、AEDＣ，每個結(jié)點也需記錄下其距離；?$u)　］%ｉ；V8m０　～0m6p　　4、再把第四層結(jié)點全部展開,得到所有的第五層結(jié)點:ABＣDE、ＡＢCED、……、AE　１＼5　{2`0?。?　ＩＶ*h?DBC、ＡＥDCB，每個結(jié)點也需記錄下其距離;"@;v2Y/　T.[（]1r9Ｙ　　5、到此，所有可能的結(jié)點均已展開，而第五層結(jié)點中最小的那個就是題目的解了。?２w３R4　O＂Ｑ.　c+q;Ｒ＋R７q3]　　由上可見,這種算法也是把所有的可能路徑都列出來再找最

8、短的那條，顯而易見這也是一種很費時的算法。)p.？+X5　c:?。拢?　ｕ4　j7O　二、A＊算法#K4e４

9、-I$ｘ+Ｏ１y#@８　}Ａ＊算法是在寬度優(yōu)先搜索算法的基礎(chǔ)上，每次并不是把所有可展的結(jié)點展開，而是對所有沒有展開的結(jié)點,利用一個自己確定的估價函數(shù)對所有沒展開的結(jié)點進(jìn)行估價,從而找出最應(yīng)該被展開的結(jié)點(也就是說我們要找的答案最有可能是從該結(jié)點展開），而把該結(jié)點展開,直到找到目標(biāo)結(jié)點為止。2_0Z．d；G*　A(?。?　[&W9Ｖ*　[?這種算法最關(guān)鍵的問題就是如何確定估價函數(shù)，估價函數(shù)越準(zhǔn)則越快找到答案。A*算法

10、實現(xiàn)起來并不難,只不過難在找準(zhǔn)估價函數(shù)，大家可以自已找資料看看。/　D1T7　[1u+　E8ｂ　三、等代價搜索法　　0Ｊ3Ｊ$W（z%c/ｍ5?：lk）?。?K個人收集整理勿做商業(yè)用途　等代價搜索法也是基于寬度優(yōu)先搜索上進(jìn)行了部分優(yōu)化的一種算法，它與A＊算法的相似之處都是每次只展開某一個結(jié)點（不是展開所有結(jié)點），不同之處在于:它不需要去另找專門的估價函數(shù)，而是以該結(jié)點到A點的距離作為估價值，也就是說，等代價搜索法是Ａ＊算法的一種簡化版本。它的大體思路是:?:}E!　kO　p　　1、從A點開始依次展開得到AB（7）、AＣ（3）

11、、AD(１0)、AE（1５）四個新結(jié)點,把第一層結(jié)點A標(biāo)記為已展開，并且每個新結(jié)點要記錄下其距離(括號中的數(shù)字)；0　z　G０p3V（K"Ｘ?　2、把未展開過的AＢ、AC、AD、AE四個結(jié)點中距離最小的一個展開,即展開ＡC（3）結(jié)點,得到AＣＢ(8）、ACD（16)、ＡCE(13）三個結(jié)點