圖搜索策略與深度優先搜索的實現

摘要： 本文通過實例分析，指出，將智能控制學科中的圖搜索策略與數據結構中深度優先搜索算法相結合，能夠得到計算機完成圖搜索過程的方法。

關鍵詞： 智能控制 圖搜索策略 深度優先搜索

智能控制是驅動智能機器自主地實現其目標的過程，或者說智能控制是一類無需人的干預就能夠獨立驅動智能機器實現其目標的自動控制。

每種以知識和符號作為基礎的智能系統，其問題求解方法都需要某種對解答的搜索。在這一過程中，采用適當的搜索技術，包括各種規則、過程和算法等推理技術，力求找到問題的解答方法。

一、圖搜索策略

要研究如何通過網絡尋找路徑，進而求解問題，首先介紹一下圖搜索的一般策略，它給出圖搜索過程的一般步驟，并可從中看出無信息搜索和啟發式搜索的區別。

可把圖搜索策略看成是一種在圖中尋找路徑的方法。初始節點和目標節點分別代表初始數據庫和滿足終止條件的數據庫。求得把一個數據庫變換為另一數據庫的規則序列問題就等價于求得圖中的一條路徑問題。

圖搜索（Graph Search）的一般過程如下：

1.建立一個只含有起始節點S的搜索圖G，把S放到一個叫做OPEN的未擴展節點表中。

2.建立一個叫做CLOSED的已擴展節點表，其初始為空表。

3.LOOP：若OPEN表是空表，則失敗退出。

4.選擇OPEN表上的第一個節點，把它從OPEN表移出并放進CLOSED表中。稱此節點為節點n。

5.若n為一目標節點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的。

6.擴展節點n，同時生成不是n的祖先的那些后繼節點的集合M。把M的這些成員作為n的后繼節點添入圖G中。

7.對那些未曾在G中出現過的（即未曾在OPEN表上或CLOSED表上出現過的）M成員設置一個通向n的指針。把M的這些成員加入OPEN表。對已經在OPEN或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節點的指針方向。

8.按某一任意方式或按某個探試值重排OPEN表。

9.GO LOOP。以上搜索過程可用如下程序流程圖來表示：

從圖搜索過程可以看出，是否重新安排OPEN表，即是否按照某個試探值重新對未擴展節點進行排序，將決定該圖搜索過程是無信息搜索或啟發式搜索。

二、盲目搜索之深度優先搜索

不需要重排OPEN表的搜索叫做盲目搜索，深度優先搜索就是其中之一，下面介紹一下深度優先搜索：

假設初始狀態是圖中所有節點未曾被訪問，則深度優先搜索可從圖中某頂點v出發，在訪問了v之后，依次從v的各個未曾訪問過的鄰接點進行深度優先遍歷，直至圖中所有和v有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的節點作為起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。

例如，使用深度優先搜索來遍歷圖2，若出發點為v1，所得深度優先搜索序列為：v1，v2，v4，v8，v5，v3，v6，v7。

深度優先遍歷的算法如下：

int visited［N］；

dfstraverse（list g，int ve）

{struct node*p；

visited［ve］=1；

printf（“%d”，ve）；

p=g［v］.next；

while（p）

{if（visited［p-＞vertex］==0）

dfstraverse（g，p-＞vertex）

p=p-＞next；

}

}

由此可見，深度優先搜索方法能夠保證我們在搜索樹中找到一條通向目標節點的最短路徑，從而為解決圖搜索問題提供了方法。

參考文獻：

［1］蔡自興.智能控制.電子工業出版社，2004.

［2］嚴蔚敏，吳偉民.數據結構.清華大學出版社，1997.

［3］秦玉平，馬靖善.數據結構.清華大學出版社，2005.