選修了cs的AI課，開(kāi)始有點(diǎn)不適應(yīng)，只能用matlab硬著頭皮上了，不過(guò)matlab代碼全網(wǎng)僅此一份，倒有點(diǎn)小自豪。

一、練習(xí)題目

分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和 A*算法求解“羅馬利亞度假問(wèn)題”。具體地圖我這里不給出了，有興趣的可以去搜索。即找到從初始地點(diǎn) Arad到 目的地點(diǎn) Bucharest 的一條路徑。

要求：分別用文件存儲(chǔ)地圖和啟發(fā)函數(shù)表，用生成節(jié)點(diǎn)數(shù)比較以上四種算法在同一問(wèn)題求解時(shí)的效率，列表給出結(jié)果。

附：羅馬尼亞度假問(wèn)題圖（圖1.1）

?

圖1.1 羅馬尼亞度假問(wèn)題

1.2 題目分析

本題要求分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和 A*算法求解“羅馬利亞度假問(wèn)題”。羅馬尼亞度假問(wèn)題本質(zhì)上屬于“圖類”問(wèn)題，該地圖上共有20個(gè)地點(diǎn)，要求從Arad出發(fā)，到達(dá)Bucharest，從圖中搜索到達(dá)路徑，并比較四種方法的優(yōu)缺點(diǎn)。因此主要的數(shù)據(jù)結(jié)構(gòu)可以采用圖存儲(chǔ)的方法，搜索方法題目已經(jīng)給出。

二、數(shù)據(jù)結(jié)構(gòu)

2.1 圖結(jié)構(gòu)

圖：由有窮、非空點(diǎn)集和邊集合組成，簡(jiǎn)寫(xiě)成G(V,E)，其中，G表示一個(gè)圖，V表示圖中的頂點(diǎn)，E表示圖中的邊。在本題，頂點(diǎn)為20個(gè)羅馬尼亞城市，邊則為相鄰城市之間的距離。邊之間有方向，圖為有向圖，無(wú)方向的圖為無(wú)向圖。本題所用的圖為無(wú)向圖。

盡管二維數(shù)組比較占用內(nèi)存，但是由于MATLAB對(duì)矩陣運(yùn)算非常方便，運(yùn)算速度也很快，我采用二維數(shù)組的方法存儲(chǔ)鄰接矩陣。對(duì)20個(gè)地點(diǎn)編號(hào)1-20，其中Arad為3號(hào)地點(diǎn)，對(duì)邊采用數(shù)值的方法，例如3號(hào)到4號(hào)距離為75，則令矩陣中點(diǎn)（3，4）的值為75。并令自身距離為0，不相鄰的點(diǎn)之間也設(shè)為0。

2.2 隊(duì)列結(jié)構(gòu)

隊(duì)列（Queue）：是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。隊(duì)列也是一種特殊的線性表，是一種先進(jìn)先出的線性表。允許插入的一端稱為表尾，允許刪除的一端稱為表頭。我們將在廣度優(yōu)先搜索中使用到這個(gè)結(jié)構(gòu)存儲(chǔ)已搜索過(guò)的節(jié)點(diǎn)。其結(jié)構(gòu)如圖2.2所示。

?

圖2.2 隊(duì)列結(jié)構(gòu)圖

2.3 棧結(jié)構(gòu)

棧(Stack)：也是一種線性存儲(chǔ)結(jié)構(gòu)，棧中的數(shù)據(jù)元素遵守“先進(jìn)后出”(First In Last Out)的原則，簡(jiǎn)稱FILO結(jié)構(gòu)。只能在棧頂進(jìn)行插入和刪除操作。我們將在深度優(yōu)先搜索中使用到這個(gè)結(jié)構(gòu)存儲(chǔ)已搜索過(guò)的節(jié)點(diǎn)。其結(jié)構(gòu)如圖2.3所示。

?

圖2.3 棧結(jié)構(gòu)圖

三、算法思想

3.1 寬度優(yōu)先

寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）其別名又叫BFS（ Breadth First Search）。屬于一種盲目搜尋法，目的是系統(tǒng)地展開(kāi)并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。算法采用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，所有因?yàn)檎归_(kāi)節(jié)點(diǎn)而得到的子節(jié)點(diǎn)都會(huì)被加進(jìn)一個(gè)先進(jìn)先出的隊(duì)列中。其鄰居節(jié)點(diǎn)尚未被檢驗(yàn)過(guò)的節(jié)點(diǎn)會(huì)被放置在一個(gè)被稱為 open 的隊(duì)列，而被檢驗(yàn)過(guò)的節(jié)點(diǎn)則被放置在被稱為 closed 的容器中（open-closed表）算法自始至終一直通過(guò)已找到和未找到頂點(diǎn)之間的邊界向外擴(kuò)展，首先搜索和s距離為k的所有頂點(diǎn)，然后再去搜索和S距離為k+l的其他頂點(diǎn)。算法流程圖如圖3.1所示。

?

圖3.1 DFS算法流程圖

3.2 深度優(yōu)先

深度優(yōu)先搜索方法，又稱DFS(Depth First Search)，和樹(shù)的先序遍歷比較類似。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問(wèn)，則從某個(gè)頂點(diǎn)v出發(fā)，首先訪問(wèn)該頂點(diǎn)，然后依次從它的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。 若此時(shí)尚有其他頂點(diǎn)未被訪問(wèn)到，則另選一個(gè)未被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。算法流程圖如圖3.2所示。

?

圖3.2 BFS算法流程圖

3.3 貪婪方法

貪婪算法（又稱貪心算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。為了解決問(wèn)題，需要尋找一個(gè)構(gòu)成解的候選對(duì)象集合，起初，算法選出的候選對(duì)象的集合為空。接下來(lái)的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對(duì)象中選出最有希望構(gòu)成解的對(duì)象。如果集合中加上該對(duì)象后不可行，那么該對(duì)象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。

本題中具體實(shí)現(xiàn)方法為，先進(jìn)行深度搜索，但是不急進(jìn)入堆棧操作，而是存儲(chǔ)當(dāng)前所有搜索到的點(diǎn)的距離，選擇距離最短的點(diǎn)，并放棄搜索其他同一深度的點(diǎn)，進(jìn)入堆棧操作。算法流程圖如圖3.3所示。

?

圖3.3 貪婪算法流程圖

3.4 A*方法

A*搜尋算法俗稱A星算法。A*算法是比較流行的啟發(fā)式搜索算法之一，被廣泛應(yīng)用于路徑優(yōu)化領(lǐng)域。它的獨(dú)特之處是檢查最短路徑中每個(gè)可能的節(jié)點(diǎn)時(shí)引入了全局信息，對(duì)當(dāng)前節(jié)點(diǎn)距終點(diǎn)的距離做出估計(jì)，并作為評(píng)價(jià)該節(jié)點(diǎn)處于最短路線上的可能性的量度。

本題中的實(shí)現(xiàn)方法為，同貪婪類似，A*就相當(dāng)于有一個(gè)智慧的老人為搜尋的對(duì)象打分，搜索過(guò)程中將距離和打分值相加，作為新的距離即可。其算法流程圖如3.4所示。

?

圖3.3 A*算法流程圖

四、關(guān)鍵代碼

4.1 BFS方法

while tail~=head %判斷 i=queue(tail); %取點(diǎn)for j=1:20 %搜索所有適合的節(jié)點(diǎn)if A(i,j)>=1 && isempty(find(flag==j,1))queue(head)=j; head=head+1; %數(shù)數(shù) flag=[flag j]; %擴(kuò)容 result=[result;i,j,A(i,j)]; %記錄endendtail=tail+1; %隊(duì)列增加 end

　　

?

4.2 DFS方法

while top~=0 %判斷 pre_len=length(stack); %記錄棧長(zhǎng)度i=stack(top); %取棧頂for j=1:20if A(i,j)>=1 && isempty(find(flag==j,1)) top=top+1; stack(top)=j; flag=[flag j]; re=[re;i,j,A(i,j)]; %記錄
　　　　　　　break; endend if length(stack)==pre_len %如果棧未增加，則出棧stack(top)=[];top=top-1;end end

4.3 貪婪方法

while top~=0 pre_len=length(stack); i=stack(top); record=[]; for j=1:20if A(i,j)>=1 && isempty(find(flag==j,1)) %記錄所有相鄰節(jié)點(diǎn)record=[record;i,j,A(i,j)] endendif isempty(record)breakend[s,k]= min(record(:,3,:)) %取距離最小節(jié)點(diǎn)i=record(k,1,:);j=record(k,2,:); if isempty(find(flag==j,1))top=top+1; stack(top)=j; flag=[flag j]; re=[re;i,j,A(i,j)]; endif length(stack)==pre_len stack(top)=[];top=top-1;end end

　　

4.4 A*方法

絕大部分與貪婪算法相同，只是更新了距離值。

for j=1:20if A(i,j)>=1 && isempty(find(flag==j,1)) F(i,j)=A(i,j)+H(j);record=[record;i,j,F(i,j)]; %啟發(fā)值endendif isempty(record)break end

　　

4.5 反向?qū)ぶ?/h2>

所有的算法均采用相同的反向?qū)ぶ贩椒ā?/p> while (1)x=find(re(:,2,:)==m) %找到到達(dá)目的地所有的經(jīng)過(guò)地m=re(x,1,:) %迭代法反向?qū)ふ襾?lái)的路徑if 1-isempty(x)lujin=[city{re(x,1,:)},lujin];juli=juli+re(x,3,:)elsebreak end end

　　

4.6 讀取EXCEL

city={'Oradea','Zerind','Arad','Timisonra','Lugoj','Mehadia','Dobreta','Craiova','Rimmicu Vikea','Sibiu',...'Fagaras','Pitesti','Bucharest','Giurglu','Uiziceni','Hirsova','Eforie','Vaslui','Lasi','Neamt'}; %存儲(chǔ)城市名 filename = 'mymap.xlsx'; sheet = 1; xlRange = 'C3:V22'; map = xlsread(filename,sheet,xlRange); %讀取excel map(isnan(map)) = 0; %將不相鄰的點(diǎn)之間也設(shè)為0

　　

五、運(yùn)行結(jié)果

BFS方法的運(yùn)行結(jié)果顯示路徑為：{'Arad'??? 'Sibiu'??? 'Fagaras'??? 'Bucharest'}

DFS方法的運(yùn)行結(jié)果顯示路徑為：{ 'Arad'??? 'Zerind'??? 'Oradea'??? 'Sibiu'??? 'Rimmicu Vikea'??? 'Craiova'??? 'Pitesti'??? 'Bucharest'}

貪婪方法的運(yùn)行結(jié)果顯示路徑為：{ 'Arad'??? 'Zerind'??? 'Oradea'??? 'Sibiu'??? 'Rimmicu Vikea'??? 'Pitesti'??? 'Bucharest'}

A*方法的運(yùn)行結(jié)果顯示路徑為：{ 'Arad'??? 'Sibiu'??? 'Rimmicu Vikea'??? 'Pitesti'??? 'Bucharest'}

比較見(jiàn)表5.1

表5.1 四種算法的運(yùn)行結(jié)果

算法	生成節(jié)點(diǎn)數(shù)	求解時(shí)間	距離
BFS方法	11	3.725s	450
DFS方法	12	3.057s	762
貪婪方法	7	3.606s	575
A*方法	7	3.049s	418

注：求解時(shí)間包括計(jì)時(shí)函數(shù)自用時(shí)間

六、比較結(jié)論

得益于MATLAB高速的矩陣運(yùn)算能力，四種方法均在3-4秒之間完成，速度相差不大，但是在生成節(jié)點(diǎn)數(shù)上，DFS方法搜索了12個(gè)節(jié)點(diǎn)最多，貪婪方法和A*方法均為7最少。比較四種搜索方法得到的搜索路徑，有啟發(fā)值的A*方法搜索到的路徑距離最短，為418，其次是寬度優(yōu)先搜索，距離為450，距離最長(zhǎng)的路徑是由DFS方法產(chǎn)生，為762，貪婪方法為575。通過(guò)比較我們可以得出如下結(jié)論：

四種搜索方法在處理小型網(wǎng)絡(luò)的搜索問(wèn)題時(shí)，速度相差不大。

貪婪方法和A*方法生成節(jié)點(diǎn)數(shù)較少，理論上能夠更快搜索出到達(dá)路徑，在處理大型圖的問(wèn)題時(shí)，會(huì)表現(xiàn)得比較明顯。

貪婪方法每一步都是選擇當(dāng)前狀態(tài)下的最優(yōu)解進(jìn)行搜索，很容易陷入局部最優(yōu)，從而使得搜索時(shí)間延長(zhǎng)。

盡管BFS方法和DFS方法都一定可以找到路徑，但是BFS方法搜索到的路徑距離要明顯優(yōu)于DFS方法。

?

---恢復(fù)內(nèi)容結(jié)束---

轉(zhuǎn)載于:https://www.cnblogs.com/Hangingter/p/7784042.html

總結(jié)

以上是生活随笔為你收集整理的用MATLAB结合四种方法搜寻罗马尼亚度假问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。