最短路徑問題的求解

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

1、
第12卷增刊鄭州紡織工學(xué)院學(xué)報(bào)Vol.12
Supplement2001年6月JOURNALOFZHENGZHOUTEXTILEINSTITUTEJune,2001

文章編號(hào):1007
4945(2001)增刊
0119
03最短路徑問題的求解王
軍,王連圭(廣東省中山市中山學(xué)院信息與電子工程系,廣東中山
528402)*摘要:
文中就最短路徑問題進(jìn)行了研究,針對(duì)具體的引例提出了六種算法:寬度優(yōu)先搜索法、A算法、等代價(jià)搜索法、Warshall算法、動(dòng)態(tài)規(guī)劃法、標(biāo)號(hào)法等,詳盡分析了每種算法的內(nèi)容、適用性及優(yōu)缺點(diǎn).關(guān)
鍵
詞:
最短路徑;解題方法

2、;算法分析中圖分類號(hào):
O245

文獻(xiàn)標(biāo)識(shí)碼:A

最短路徑問題是一種
最優(yōu)解
問題,是近年來全國(guó)在學(xué)生((0,7,3,10,15),(7,0,5,13,12),(3,5,0,6,5),(10,13,6,
挑戰(zhàn)杯
、
數(shù)學(xué)建模
等競(jìng)賽中常見的一類中等程度的難題,也0,11),(15,12,5,11,0));是一個(gè)在交通運(yùn)輸、城市規(guī)劃以及計(jì)算機(jī)網(wǎng)絡(luò)規(guī)劃等工程實(shí)際以下是幾種解法:中具有重要指導(dǎo)意義的問題,甚至有時(shí)一些看似跟最短路徑問1
寬度優(yōu)先搜索題無(wú)關(guān)的問題也可以歸結(jié)為最短路徑問題.下面就以具體引例來簡(jiǎn)要分析一下此類問題的算法.寬度優(yōu)先搜索并不是

3、一種很優(yōu)秀的算法,這里只是簡(jiǎn)單介引例1:假設(shè)A、B、C、D、E各個(gè)城市之間旅費(fèi)如圖1所紹一下它的算法.具體方法是:
從A點(diǎn)開始依次展開得到示.某人想從城市A出發(fā)游覽各城市一遍,而所用費(fèi)用最少.試AB、AC、AD、AE四個(gè)新結(jié)點(diǎn)(第二層結(jié)點(diǎn)),當(dāng)然每個(gè)新結(jié)點(diǎn)要編程序輸出結(jié)果.記錄下其距離;
再次以AB展開得到ABC、ABD、ABE三個(gè)新結(jié)點(diǎn)(第三層結(jié)點(diǎn)),而由AC結(jié)點(diǎn)可展開得到ACB、ACD、ACE三個(gè)新結(jié)點(diǎn),自然AD可以展開得到ADB、ADC、ADE,AE可以展開得到AEB、AEC、AED等新結(jié)點(diǎn),對(duì)于每個(gè)結(jié)點(diǎn)也須記錄下其距離;
再把第三層結(jié)點(diǎn)全

4、部展開,得到所有的第四層結(jié)點(diǎn):ABCD、ABCE、ABDC、ABDE、ABEC、ABED

AEDB、AEDC,每個(gè)結(jié)點(diǎn)也需記錄下其距離;
再把第四層結(jié)點(diǎn)全部展開,得到所有的第五層結(jié)點(diǎn):ABCDE、ABCED、

、AEDBC、AEDCB,每個(gè)結(jié)點(diǎn)也需記錄下其距離;
到此,所有可能的結(jié)點(diǎn)均已展開,而第五層結(jié)點(diǎn)中最小的那個(gè)就是題目的解了.由上可見,這種算法也是把所有的可能路徑都列出來再找最短的那條,圖1
游覽點(diǎn)分布示意圖顯而易見這也是一種很費(fèi)時(shí)的算法.解這類題時(shí)很多人往往不得要領(lǐng),不少人采用窮舉法把所有可能的情況全部列出,再找出其中最短的那條路徑;

5、或是采用2
A*算法遞歸或深度搜索,找出所有路徑,再找出最短的那條.這兩種方A*算法是在寬度優(yōu)先搜索算法的基礎(chǔ)上,每次都是利用法可見都是費(fèi)時(shí)非常多的解法,如果城市數(shù)目多的話則要花大一個(gè)自己確定的估價(jià)函數(shù)對(duì)所有沒展開的結(jié)點(diǎn)進(jìn)行估價(jià),從而量的運(yùn)行時(shí)間.實(shí)際上,遞歸、深度搜索等算法一般用于求所有找出最應(yīng)該被展開的結(jié)點(diǎn)(也就是說要找的答案最有可能是從解問題(例如求從A出發(fā)每個(gè)城市走一遍一共有哪幾種走法),[1]該結(jié)點(diǎn)展開),把該結(jié)點(diǎn)展開,直到找到目標(biāo)結(jié)點(diǎn)為止.而這幾種算法對(duì)于求最短路徑這類最優(yōu)解問題顯然是不合適的,以下介紹的幾種算法就要優(yōu)越很多.3
等代

6、價(jià)搜索法首先,應(yīng)該先建立一個(gè)鄰接矩陣來存放任意兩點(diǎn)間的距離等代價(jià)搜索法也是基于寬度優(yōu)先搜索上進(jìn)行優(yōu)化的一種算數(shù)據(jù),以便在程序中方便調(diào)用,如下:法,它與A*算法有點(diǎn)相似,只不過它不需要去另找估價(jià)函數(shù),constdis:array[1..5,1..5]ofinteger=而是以該結(jié)點(diǎn)到A點(diǎn)的距離作為估價(jià)值,每次展開估價(jià)值最小
收稿日期:2001
03
08
作者簡(jiǎn)介:王
軍(1971
),男,碩士,中山學(xué)院助教.王連圭為中山學(xué)院副教授,主要研究方向?yàn)榉蔷€性控制和魯棒控制.



1
20
















鄭州紡織工學(xué)院學(xué)報(bào)

7、











2001年
第12卷
的結(jié)點(diǎn).具體方法是:
從A點(diǎn)開始依次展開得到AB(7)、AC看,可用一個(gè)數(shù)軸簡(jiǎn)單地表示這種算法:(3)、AD(10)、AE(15)四個(gè)新結(jié)點(diǎn),把第一層結(jié)點(diǎn)A標(biāo)記為己(1)以A點(diǎn)為0點(diǎn),展開與其相鄰的點(diǎn),并在數(shù)軸中標(biāo)出.展開,并且每個(gè)新結(jié)點(diǎn)要記錄下其距離(括號(hào)中的數(shù)字);
把未展開過的AB、AC、AD、AE四個(gè)結(jié)點(diǎn)中距離最小的一個(gè)展開,即展開AC(3)結(jié)點(diǎn),得到ACB(8)、ACD(16)、ACE(13)三個(gè)結(jié)點(diǎn),并把結(jié)點(diǎn)AC標(biāo)記為己展開;
再?gòu)奈凑归_的所有結(jié)點(diǎn)中找(2)因?yàn)镃點(diǎn)離起點(diǎn)A最近,因此可以斷

8、定C點(diǎn)一定是由出距離最小的一個(gè)展開,即展開AB(7)結(jié)點(diǎn),得到ABC(12)、A直接到C點(diǎn)這條路徑是最短的(因?yàn)锳、C兩點(diǎn)間沒有其它AB