圖形搜尋簡介

在離散數學、演算法與人工智慧的領域，很多問題可以表示為「節點與連線所形成的 ... 圖形搜尋的方法大致可以分為「深度優先搜尋(Depth-First Search, DFS)、廣度優先 ... 程式人雜誌--2014年6月號(開放公益出版品) 圖形搜尋簡介 圖形搜尋簡介 簡介 在離散數學、演算法與人工智慧的領域，很多問題可以表示為「節點與連線所形成的圖形」，一個程式要解決某問題其實是在這個圖形裏把目標節點給找出來，於是問題求解就簡化成了圖形的搜尋，我們只要把解答給「找出來」就行了。

圖形搜尋的方法大致可以分為「深度優先搜尋(Depth-FirstSearch,DFS)、廣度優先搜尋(Breath-FirstSearch,BFS)、最佳優先搜尋(Best-FirstSearch,BestFS)等三類。

然後針對最佳優先搜尋的部份，還有一種具有理論背景，且較為強大好用的A*搜尋法可採用。

圖形的表達 圖形是由節點(node)與連線(edge)所組成的。

舉例而言，以下是一個包含六個節點與十條連線的簡單圖形。

圖、圖形Graph的範例 深度優先搜尋 所謂的「深度優先搜尋」(Depth-FirstSearch,DFS)，就是一直往尚未訪問過的第一個鄰居節點走去的一種方法，這種方法可以採用程式設計中的「遞迴技巧」完成，以下是深度搜尋的演算法： AlgorithmDFS(graph,node){//深度優先搜尋，graph:圖形,node:節點 if(node.visited)return;//如果已訪問過，就不再訪問 node.visited=1;//並設定為已訪問 foreach(neighborofnode)//對於每個鄰居 DFS(graph,neighbor);//逐一進行深度優先搜尋的訪問。

end 您可以看到上述的演算法中，我們單純採用遞迴的方式，就可以輕易的完成整個DFS演算法。

當然、實作為程式的時候，會稍微複雜一點，以下是使用Javascript的實作方式： functiondfs(g,node){//深度優先搜尋 if(g[node].v!=0)return;//如果已訪問過，就不再訪問 printf("%d=>",node);//否則、印出節點 g[node].v=1;//並設定為已訪問 varneighbors=g[node].n;//取出鄰居節點 for(variinneighbors){//對於每個鄰居 dfs(g,neighbors[i]);//逐一進行訪問 } } 針對上述的範例圖形，若採用深度優先搜尋，其結果可能如下所示(圖中紅色的數字代表訪問順序) 圖、深度優先搜尋的順序 廣度優先搜尋 雖然深度優先搜尋可以搜尋整個圖形，但是卻很可能繞了很久才找到目標，於是從起點到目標可能會花費很久的時間(或說路徑長度過長)。

如果我們想找出到達目標最少的步驟，那麼就可以採用「廣度優先搜尋」(Breath-FirstSearch,BFS)的方式。

廣度優先搜尋BFS是從一個節點開始，將每個鄰居節點都一層一層的拜訪下去，深度最淺的節點會優先被拜訪的方式。

舉例而言，針對上述的圖形範例，若採用「廣度優先搜尋BFS」的方式，那麼拜訪順序將會如下所示： 圖、廣度優先搜尋的順序 要能用程式進行廣度優先搜尋，必須採用「先進先出」(First-inFirst-Out,FIFO)的方式管理節點，因此通常在「廣度優先搜尋」裏會有個佇列(queue)結構，以下是BFS的演算法： AlgorithmBFS(graph,queue) ifqueue.empty()return; node=queue.dequeue(); if(!node.visited) node.visited=true else return; foreach(neighborofnode) if(!neighbor.visited) queue.push(neighbor) end 以下是使用Javascript的BFS程式實作片段： functionbfs(g,q){//廣度優先搜尋 if(q.length==0)return;//如果queue已空，則返回。

varnode=dequeue(q);//否則、取出queue的第一個節點。

if(g[node].v==0)//如果該節點尚未拜訪過。

g[node].v=1;//標示為已拜訪 else//否則(已訪問過) return;//不繼續搜尋，直接返回。

printf("%d=>",node);//印出節點 varneighbors=g[node].n;//取出鄰居。

for(variinneighbors){//對於每個鄰居 varn=neighbors[i]; if(!g[n].visited)//假如該鄰居還沒被拜訪過 q.push(n);//就放入queue中 } bfs(g,q); } 最佳優先搜尋 但是、上述兩個方法其實都還不夠好，深度搜尋會猛衝亂衝，而廣度搜尋則會耗費太多的記憶體，並且沒有效率，無法很快的找到目標點。

假如我們能夠知道哪些點距離目標點最近，也就是哪些點比較好的話，那就能採用「最佳優先搜尋(Best-FirstSearch)的方式來搜尋了。

最佳優先搜尋的實作方法與廣度優先搜尋類似，但是並不採用佇列(queue)，而是採用一種根據優先程度排序的結構，每次都取出最好的那個繼續進行搜尋。

但是、節點的好壞通常很難評估，單純採用某種距離去評估往往會過度簡化問題，這點往往是最佳優先搜尋的困難之所在。

還好、有時我們不需要非常精確的評估，只要問題符合這樣的單調(monotone)特性，就可以使用A*演算法來進行較快速的搜尋，這種方法比廣度優先搜尋通常快很多，因為A*不會搜尋所有節點，而是有系統的朝著整體較好的方向前進，這種方法在電腦遊戲(Game)上常被用在NPC(非人類角色)的智慧型搜尋行為設計上面，是人工智慧搜尋方法中較強大的一種。

參考文獻 Wikipedia:A*searchalgorithm 維基百科:A*搜尋演算法 維基百科:廣度優先搜索 維基百科:深度優先搜索 【本文由陳鍾誠取材並修改自維基百科，採用創作共用的姓名標示、相同方式分享授權】 程式人雜誌，採用創作共用：姓名標示、相同方式分享授權，歡迎加入雜誌社團