最短路徑問題的求解.ppt

《最短路徑問題的求解.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、最短路徑問題的求解最短路徑是圖論中的一個重要問題，具有很高的實用價值，也是信息學(xué)競賽中常見的一類中等難度的題目，這類問題很能聯(lián)系實際，考察學(xué)生的建模能力，反映出學(xué)生的創(chuàng)造性思維，因為有些看似跟最短路徑毫無關(guān)系的問題，也可以歸結(jié)為最短路徑問題來求解。在帶權(quán)圖G=（V，E）中，若頂點Vi,Vj是圖G的兩個頂點，從頂點Vi到Vj的路徑長度定義為路徑上各條邊的權(quán)值之和。從頂點Vi到Vj可能有多條路徑，其中路徑長度最小的一條路徑稱為頂點Vi到Vj的最短路徑。一般有兩類最短路徑問題：一類是求從某個頂點（源點）到其它頂點（終

2、點）的最短路徑；另一類是求圖中每一對頂點間的最短路徑。對于不帶權(quán)的圖，只要人為的把每條邊加上權(quán)值1，即可當(dāng)作帶權(quán)圖一樣處理了。最短路徑問題的求解例1、假設(shè)A、B、C、D、E各個城市之間旅費如下圖紅色數(shù)字所示。某人想從城市A出發(fā)游覽各城市一遍，而所用旅費最少，試編程輸出結(jié)果。[問題分析]解這類問題時，很多同學(xué)往往不得要領(lǐng)，采用窮舉法把所有可能的情況全部列出，再找出其中旅費最少的那條路徑；或者采用遞歸（深搜）找出所有路徑，再找出旅費最少的那條。但這兩種方法都是費時非常多的解法，如果城市數(shù)目多的話則很可能要超時了。

3、　　實際上我們知道，遞歸（深搜）之類的算法一般用于求所有解問題（例如求從A出發(fā)每個城市都要走一遍一共有哪幾種走法？），所以這些算法對于求最短路徑這類最優(yōu)解問題顯然是不合適的。首先，對于這類圖，我們都應(yīng)該先建立一個鄰接矩陣，存放任意兩點間的數(shù)據(jù)（如距離、費用、時間等），以便在程序中方便調(diào)用，以下介紹幾種常見的、更好的求最短路徑問題的算法。最短路徑問題的求解一、寬度優(yōu)先搜索　　寬搜也并不是解決這類問題的優(yōu)秀算法，這里只是簡單介紹一下算法思路，為后面的優(yōu)秀算法做個鋪墊。具體如下：　　1、從A點開始依次展開得到AB

4、、AC、AD、AE四個新結(jié)點（第二層結(jié)點），當(dāng)然每個新結(jié)點要記錄下其旅費；　　2、再次由AB展開得到ABC、ABD、ABE三個新結(jié)點（第三層結(jié)點），而由AC結(jié)點可展開得到ACB、ACD、ACE三個新結(jié)點，自然由AD可以展開得到ADB、ADC、ADE，由AE可以展開得到AEB、AEC、AED等新結(jié)點，對于每個結(jié)點也須記錄下其旅費；　　3、再把第三層結(jié)點全部展開，得到所有的第四層結(jié)點：ABCD、ABCE、ABDC、ABDE、ABEC、ABED、……、AEDB、AEDC，每個結(jié)點也需記錄下其旅費；　　4、再把第

5、四層結(jié)點全部展開，得到所有的第五層結(jié)點：ABCDE、ABCED、……、AEDBC、AEDCB，每個結(jié)點也需記錄下其旅費；　　5、到此，所有可能的結(jié)點均已展開，而第五層結(jié)點中旅費最少的那個就是題目的解了。　　由上可見，這種算法也是把所有的可能路徑都列出來，再從中找出旅費最少的那條，顯而易見也是一種很費時的算法。最短路徑問題的求解二、啟發(fā)式搜索　　在寬度優(yōu)先搜索算法的基礎(chǔ)上，每次并不是把所有可展開的結(jié)點展開，而是對所有沒有展開的結(jié)點，利用一個自己確定的估價函數(shù)對所有沒展開的結(jié)點進(jìn)行估價，從而找出最應(yīng)該被展開的

6、結(jié)點（也就是說我們要找的答案最有可能是從該結(jié)點展開），而把該結(jié)點展開，直到找到目標(biāo)結(jié)點為止。　　這種算法最關(guān)鍵的問題就是如何確定估價函數(shù)，估價函數(shù)越準(zhǔn)，則能越快找到答案。這種算法實現(xiàn)起來并不難，只不過難在找準(zhǔn)估價函數(shù)，大家可以自已找相關(guān)資料學(xué)習(xí)和思考。最短路徑問題的求解三、等代價搜索法　　等代價搜索法也是在寬度優(yōu)先搜索的基礎(chǔ)上進(jìn)行了部分優(yōu)化的一種算法，它與啟發(fā)式搜索的相似之處都是每次只展開某一個結(jié)點（不是展開所有結(jié)點），不同之處在于：它不需要去另找專門的估價函數(shù)，而是以該結(jié)點到A點的距離作為估價值，也就是說

7、，等代價搜索法是啟發(fā)式搜索的一種簡化版本。它的大體思路是：　　1、從A點開始依次展開得到AB（7）、AC（3）、AD（10）、AE（15）四個新結(jié)點，把第一層結(jié)點A標(biāo)記為已展開，并且每個新結(jié)點要記錄下其旅費（括號中的數(shù)字）；　　2、把未展開過的AB、AC、AD、AE四個結(jié)點中距離最小的一個展開，即展開AC（3）結(jié)點，得到ACB（8）、ACD（16）、ACE（13）三個結(jié)點，并把結(jié)點AC標(biāo)記為已展開；　　3、再從未展開的所有結(jié)點中找出距離最小的一個展開，即展開AB（7）結(jié)點，得到ABC（12）、ABD（20

8、）、ABE（19）三個結(jié)點，并把結(jié)點AB標(biāo)記為已展開；　　4、再次從未展開的所有結(jié)點中找出距離最小的一個展開，即展開ACB（8）結(jié)點，……；　　5、每次展開所有未展開的結(jié)點中距離最小的那個結(jié)點，直到展開的新結(jié)點中出現(xiàn)目標(biāo)情況（結(jié)點含有5個字母）時，即得到了結(jié)果。最短路徑問題的求解小結(jié)：由上可見，啟發(fā)式搜索和等代價搜索法并沒有象寬度優(yōu)先搜索一樣展開所有結(jié)點，只是根據(jù)某一原則（或某一估