資源描述：
《最短路徑問(wèn)題的幾個(gè)算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、最短路徑問(wèn)題)r+gv%[5p)W)J最短路徑問(wèn)題是一個(gè)非常能聯(lián)系實(shí)際的問(wèn)題，某人想從城市A出發(fā)游覽各城市一遍，而所用費(fèi)用最少。試編程序輸出結(jié)果。/c+r2x8S7j!N4z 解這類題時(shí)同學(xué)們往往不得要領(lǐng)，不少同學(xué)采用窮舉法把所有可能的情況全部列出，再找出其中最短的那條路徑；或是采用遞歸或深度搜索，找出所有路徑，再找出最短的那條。這兩種方法可見(jiàn)都是費(fèi)時(shí)非常多的解法，如果城市數(shù)目多的話則很可能要超時(shí)了。/N%M0K*[&X2A&U4l.}/f 實(shí)際上我們知道，遞歸、深度搜索等算法一般用于求所有解問(wèn)題（例如求A出發(fā)
2、每個(gè)城市走一遍一共有哪幾種走法），而這幾種算法對(duì)于求最短路徑這類最優(yōu)解問(wèn)題顯然是不合適的，以下介紹的幾種算法就要優(yōu)越很多。:V7@)v"g3 首先，對(duì)于這類圖我們都應(yīng)該先建立一個(gè)鄰接矩陣來(lái)存放任意兩點(diǎn)間的距離數(shù)據(jù)，以便在程序中方便調(diào)用，如下：(N8b.x+V/e3Z%Y;yconstdis:array[1..5,1..5]ofinteger=((0,7,3,10,15),0u;Y0Oi2L/i" (7,0,5,13,12),%U5D#I&L/F([)y(j9x6o
3、 (3,5,0,5,10),8I-f"E:D1J (10,13,5,0,11),$W"P1}8T,}+px.S-Z!a (15,12,10,11,0));#p!L4
4、+b;c)V 以下是幾種解法：3G3c#u'e-I7y 一、寬度優(yōu)先搜索%O9O4G3W,L9l3Q9O 寬度優(yōu)先搜索并不是一種很優(yōu)秀的算法，只里只是簡(jiǎn)單介紹一下它的算法。$Q"s5d,b$N/c3V,?+Z 具體方法是：2
5、cd6Y)/t9h3c/i 1、從A點(diǎn)開(kāi)始依次展開(kāi)得到AB、AC、AD、AE四個(gè)新結(jié)點(diǎn)（第二層結(jié)點(diǎn)），當(dāng)然每個(gè)新結(jié)點(diǎn)要記錄下其距離；1?1g,G.
6、'n#D*O)^8A 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)也須記錄下其距離；5n.d+^"B5`7A;v 3、再把第三層結(jié)點(diǎn)全部展開(kāi)，得到所有的第四層結(jié)點(diǎn)：ABCD、AB
7、CE、ABDC、ABDE、BEC、ABED……AEDB、AEDC，每個(gè)結(jié)點(diǎn)也需記錄下其距離；$u)]%i;V8m0~0m6p 4、再把第四層結(jié)點(diǎn)全部展開(kāi)，得到所有的第五層結(jié)點(diǎn)：ABCDE、ABCED、……、AE15{2`0r:IV*hDBC、AEDCB，每個(gè)結(jié)點(diǎn)也需記錄下其距離；"@;v2Y/T.[(]1r9Y 5、到此，所有可能的結(jié)點(diǎn)均已展開(kāi)，而第五層結(jié)點(diǎn)中最小的那個(gè)就是題目的解了。2w3R4O"Q.c+q;R+R7q3] 由上可見(jiàn)，這種算法也是把所有的可能路徑都列出來(lái)再找最短的那條，顯而易見(jiàn)這也是一種很
8、費(fèi)時(shí)的算法。)p.?+X5c:B*`5u4j7O 二、A＊算法#K4e4
9、-I$x+O1y#@8} A＊算法是在寬度優(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)為止。2_0Z.d;G*A(E+[&W9V*[ 這種算法最關(guān)鍵的問(wèn)題就是如何確定估價(jià)函數(shù)，估價(jià)函數(shù)越準(zhǔn)則越快找到答案。A＊算法實(shí)現(xiàn)起來(lái)并不難，只不過(guò)難在找準(zhǔn)
10、估價(jià)函數(shù)，大家可以自已找資料看看。/D1T7[1u+E8b 三、等代價(jià)搜索法 0J3J$W(z%c/m5?:lk)?'K 等代價(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)化版本。它的大體思路是：:}E!kOp 1、從A點(diǎn)開(kāi)始依次展開(kāi)得到AB（7）、AC（3）、AD（10）、AE（15）四個(gè)新結(jié)點(diǎn)，把第一層結(jié)點(diǎn)A
11、標(biāo)記為已展開(kāi)，并且每個(gè)新結(jié)點(diǎn)要記錄下其距離（括號(hào)中的數(shù)字）； 0zG0p3V(K"X2、把未展開(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)；)B+
