1、第二章 圖搜索技術我們經常用八數碼難題或十五數碼難題來說明問題求解的概念。十五數碼難題是指由15個編有數碼1至15并放在4×4方格棋盤上的可走動的棋子組成，棋盤上總有一格是空的，以便讓周圍棋子走入空格，或者說是移動空格，如圖給出兩種棋局:119415-123413125678758691011121321014131415初始棋局 目標棋局 圖2.1 十五數碼難題即初始棋局與目標棋局。讓我們考慮如何把初始棋局變換為目標棋局。問題的解答就是某個合適的走步序列，如“左移棋子12，下移棋子15，右移棋子4”等等。在這類問題中，對初始情況和目標情況都是明確規定了的。還有一組把一種情況變換為另

2、一種情況的動作或走步。下面我們給出幾個基本概念，用于討論這一類問題的解答。 問題狀態與算符要討論上述問題解法，有必要引入下列幾個概念。狀態: 是表示問題解法中每一步問題狀況的數據結構。算符: 則是把問題從一種狀態變換為另一種狀態的手段。狀態空間: 是從初始狀態出發所能達到的狀態集合。下面四個相應的算符能夠最自然地說明十五數碼難題：空格左移、空格上移、空格右移及空格下移。在下棋問題中，這些算符對應于一定的走步。有時，某個算符（走步）不適用于某一狀態；例如不能把“空格右移”運用于上述例子中的目標狀態。用關于狀態和算符的語言來描述一個問題的解即是某個能夠把初始狀態變為目標狀態的算符序列。狀態圖: 把

3、初始狀態可達到的各狀態所組成的空間設想為一幅由各狀態對應節點組成的圖，這些節點與有關狀態相對應，這種圖稱為狀態圖。 任何問題的求解技術,包括狀態空間技術,都包括兩方面內容: 表示 先表示 ,后搜索搜索 表示的好壞不同 狀態空間大小相差很大 搜索效率 系統性能 關系我們首先研究狀態空間的表示，然后再對各種搜索策略及其算法進行討論。第一節 狀態空間的表示211狀態描述 在建立某個問題的狀態空間（或問題空間）表示的過程中，必須清楚什么是這個問題的狀態。在前例十五數碼難題中，把棋局作為問題的狀態是很自然的。但是，一個問題求解過程要找到一個解而實際上又不想移動棋子，就必須采用某些棋局的描述而不是棋局本身

4、。因此，任何狀態問題描述的一個重要部分就是為該問題狀態選擇一些具體的描述方式。狀態描述： 任何類型的數據結構都可以用來描述狀態其中包括：符號、字符串、向量、二維數組、樹和表格等對于十五數碼難題，一個4 ×4 陣列理應是一個自然的狀態描述方式。在選擇狀態描述方式時，我們還必須注意能夠易于用算符對它們進行運算，以便從一種狀態變換為另一種狀態。例如：讓我們考慮把代數式（AB+CD）/BC變換為較簡單的表達式A/C+D/B的問題。這里，問題的狀態顯然是代數表達式。不過，我們還必須決定狀態描述的方式。(1)一種常用的描述采用二元樹。這種描述樹的非終端節點代表 式中的算術運算符號（+ ，

5、5;和÷），而終端節點代表 式中的變量或常量符號（A，B，C和D）。這樣，式（AB+CD）/BC 的描述樹如圖(a)所示。圖中，節點÷的左分支代表分子，右分支代表分母。應用代數規則（狀態空間算符）把這一狀態描述變換為另一描述。對于所述的代數式子，可把它變換為如圖(b)所描述的狀態。 圖(a) 圖(b) (2)另一種常用的描述方式是線性字符串。式（AB+CD）/BC的一種可能的字符串描述為÷+×AB×CD×BC。其中，算術運算符號（÷+和×）叫做前綴，因為它們位于字符串中運算數的前面。因為我們知道每個運算符號只對兩個

6、運算數進行運算，所以字符串是不需要標點符號的。例如，字符串中符號×的運算數必定是兩個由合適的代數表達式描述的緊跟在此符號后面的子字符串，即×AB和×CD。應用字符串形式描述，我們可以把上述問題敘述為把字符串÷+×AB×CD×BC變換為字符串+÷AC÷DB的問題。2.1.2 算符與重寫規則 算符把一種狀態變換為另一種狀態。因此，可以把算符看做定義域為狀態集合的函數（實際上，算符只是部分函數，因為一個算符不可能適用于一切狀態）。 當狀態描述采用字符串形式時，我們有一個十分方便的方法來表示算符運算。這個方法應用

7、了重寫規則（有時叫做產生式）的概念。 一套重寫規則規定了由一個字符串變換為另一個字符串的方法。重寫規則全部具有SiSj的形式，即字符串Si可變換為字符串Sj。例如，字符串 A$B$意味著出現在第一個字符串中的符號A 可被符號B 所取代。其中，$代表一任意的子字符串（包括空字符串）。在這條重寫規則中，符號$用來指明當以B取代A時，A后面的字符串是不變的，則有字符串AEFDBEFD。在重寫規則中可用幾個$符號來指出幾個不同的字符串。于是我們又可能有下列重寫規則的例子：1. A$AA 以A 開始和結束的字符串可用單一出現的A 來取代2. $1BAB$2$1BB$2 出現在兩個B之間的字符串可被刪去3

8、. $1$2$3$1$2$2$3 任何子字符串均可被重復4. $1$2$2$3$1$2$3 任何相鄰重復的子字符串可被刪去例如，應用最后兩個規則，我們可以把字符串ABCBABC變為字符串ABC：ABCBABCABABCBABCABABCABC一個重寫規則常可以不同的方法用于某字符串。在上例中，規則4 完全不能用于字符串ABCBABC，而規則3卻可以多種方法加以應用。顯然，應用某個具體的重寫規則是與某個算符相對應的。由于可以用單條重寫規則來表示大量的不同算符，所以在問題求解方法中經常使用重寫規則。用重寫規則表示算符并不要求只限于由字符串描述的狀態。例如，可以把類似的概念用于十五數碼難題，其中，自

9、然狀態描述是一個4×4的陣列。讓我們用八數碼難題（十五數碼難題的一種簡化形式）來說明重寫規則的一般概念。在八數碼難題中，八個編碼棋子擺在一個3×3陣列中。一種表示八數碼難題中棋子正當走步的方法是一套對陣列的重寫規則。這些規則規定了把一種3×3陣列變換為另一種3×3陣列的方法。八數碼難題的一套重寫規則表示如下:X1X2X3<-àX1X2X3X4X5X4X5X6X7X8X6X7X8 雙向，兩條規則2.1.3 目標狀態尋找狀態空間的全部過程包括從舊的狀態描述產生新的狀態描述，以及然后檢驗這些新的狀態描述，看其是否描述了該目標狀態。這種檢驗往往只

10、是查看某個狀態是否與給定的目標狀態描述相匹配。綜上所述我們可以看到，要完成某個問題的狀態描述，我們必須確定三件事：l 該狀態描述的方式，特別是初始狀態描述；l 算符集合及其對狀態描述的作用；l 目標狀態描述的特性。前已述及，把狀態空間表達為有向圖是有益的。圖表示法對于討論各種狀態空間搜索方法是特別有效的。2.1.4 圖示法下面介紹圖論中的幾個術語和一些有關圖的正式表示法。一個圖由節點的集合構成（不一定是有限的節點）。一對節點用弧線連接起來，這些弧線從對子的一個節點指向該對子的另一節點。這種圖叫做有向圖。 ni nj如果某條弧線從節點ni指向節點nj ，那么節點nj 就叫做節點ni的后繼節點或后

11、裔，而節點ni叫做節點nj 的父輩節點或祖先。在我們感興趣的各種圖中，一個節點只有有限個后繼節點，因為產生式系統只有有限個適用規則。一對節點可能互為后裔，這時，該對有向弧線有時就用一條棱線代替。 ni nj當用一個圖來表示某個狀態空間時，圖中各節點標上相應的狀態描述，而有向弧線旁邊標有算符。某個節點序列（ni1，ni2，nik）當j=2，3，k時，如果對于每一個nij-1都有一個后繼節點nij存在，那么就把這個節點序列叫做從節點ni1至節點nik的長度為K 的路徑。如果從節點ni至節點nj存在有一條路徑，那么就稱節點nj從節點ni可達到的節點，或者稱節點nj為節點ni的后裔，而且稱節點ni為節

12、點nj祖先。這樣，(尋求一種狀態è另一種狀態的某個算符序列問題)ó尋求圖的某一路徑問題。費用: 給各弧線指定費用以表示加在相應算符上的費用。用C(ni，nj)來表示從節點ni指向節點nj 的那段弧線的費用。兩節點間路徑的費用 = 連接該路徑上各節點的所有弧線費用之和。 初始狀態 -à目標狀態 解 某指定節點 -à 另一節點 路徑 -最小費用 第二節 狀態空間表示舉例對各種問題都可以用狀態空間法表示，并用狀態空間搜索法來求解。下面舉例之前，簡單介紹產生式系統的描述搜索過程的方法。一個產生式系統由下列三個部分組成： (1)一個總數據庫，它含有與具體任務有關的

13、信息。隨著應用情況的不同，這些數據庫可能小得像數字矩陣那樣簡單，或許大得如檢索文件結構那么復雜。(2)一套對數據庫進行操作運算的規則，每條規則由左右兩部分組成，左邊部分鑒別規則的適用性或先決條件，右邊部分描述規則應用時所完成的動作。應用規則來改變數據庫，就像應用算符來改變狀態一樣。(3)一個控制策略，它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。控制策略由控制系統選擇和確定。下面讓我們來介紹幾個狀態空間表示的例子。例1 推銷員旅行問題推銷員旅行問題是個古典的綜合問題。一個推銷員計劃做一次旅行，他必須訪問如圖所示的每個城市。每兩個城市間的路徑旁標有距離。問題的提法如下：

14、從城市A 出發，訪問每個城市一次，且最多一次，并返回到城市A ，要求尋找一條距離最短的路線。為了確定這個問題，我們規定如下：(1)總數據庫是到目前為止所訪問過的城市表。初始數據庫被描述為表（A）。我們不允許表中任一城市的出現多于一次，只有A 城市例外，但也只有當所有其他城市均已出現之后，才能再次出現A。(2)規則對應于決策：（a）下一步走向城市A：（b）下一步走向城市B；，（e）下一步走向城市E。一條規則除非能夠把某個數據庫變換為一合法的數據庫，否則就不適用于這個數據庫。因此應用“下一步走向城市A”這條規則就不適用于尚未出現所有城市的任一數據庫。(3)任一以A為起點和終點，并出現所有其他城市的

15、總數據庫，都滿足終止條件。我們可以使用下圖的距離圖表來計算任一旅程的總距離。提出作為解答的任一旅程，必須是具有最短矩離的旅程。1007 C 推銷員旅行問題地圖下面給出求解該問題時可能生成的部分搜索樹。樹枝旁邊的數字是應用相應規則時加到旅程上的距離增量。67 （A） (AB) (AC) (AD) (AE)例2 猴子和香蕉問題 狀態描述模式: 用來描述一個狀態集合的含有變量的表達式下面，我們舉例來說明。 在人工智能文獻中，“猴子和香蕉”問題常常被用來說明自動求解系統的操作。在一個房間內有一只猴子（可以認為這是一個機器人），一個箱子和一束掛在天花板上的香蕉。但猴子的高度不足以碰到香蕉，那么這只猴子怎

16、樣才能摘到香蕉？現在我們用含有變量的狀態來描述這個問題。 我們用一個四元表列（W ，x ，Y ，z ）來表示猴子和香蕉問題的狀態，其中： W: 猴子的水平位置x: 當猴子在箱子頂上時取x = 1 ；否則取x = 0 Y: 箱子的水平位置z: 當猴子摘到香蕉時取z = 1 ；否則z = 0 這個問題中的操作（算符）如下：(1)goto（U）猴子走到水平位置U ，或者用產生式規則表示為：（W ，0 ，Y ，z ）goto(U)（U ，0 ，Y ，z ） 即應用操作goto（U），能把狀態（W ，0 ，Y ，z ）變換為狀態（U ，0 ，Y ，z ）。 (2)pushbox（V）猴子把箱子推到水平位

17、置V，即有：（W ，0 ，W ，z ）pushbox(V)（V ，0 ，V ，z ）應當注意的是:要調用算符pushbox（V），就要求產生式規則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。這種強加于操作的適用性條件，叫做產生式規則的先決條件。(3)climbbox猴子爬上箱頂，即有：（W ，0 ，W ，z ）climbbox（W ，1 ，W ，z ）在應用算符climbbox時也必須注意到，猴子和箱子應當在同一位置上，而且猴子不在箱頂上。 (4)grasp猴子摘到香蕉，即有： （C ，1 ，C ，0 ） grasp（C ，1 ，C ，1 ）其中，C 是香蕉正下方的地板位置。

18、在應用算符grasp時，要求猴子和箱子都在位置C 上，并且猴子已在箱子頂上。 應當說明的是，在這種情況下，算符（操作）的適用性及作用均由產生式規則表示。令初始狀態為（a ，0 ，b ，0 ）。這時goto(U)是唯一適用的操作，并導致下一狀態（U ，0 ，b ，0 ）。現在有三個適用的操作，即goto(U)，pushbox(V)，和climbbox（若U=b）。把所有適用的操作繼續應用于每個狀態，我們就能夠得到狀態空間圖如下。從圖中不難看出，把該初始狀態變換為目標狀態的操作序列為：goto（b），pushbox（c），climbbox，grasp 第三節 搜索過程要點用圖 來說明 狀態空間。求

19、解一個能滿足目標條件的問題可以表達為搜索一個圖以找到一個滿足目標狀態描述的節點問題。討論的所有狀態空間搜索方法可以由下列圖論方法來模擬：1.起始節點: 對應于初始狀態描述。2.后繼節點（又稱子節點） 把適用于某個節點狀態描述的一些算符用來推算該節點而得到的新節點，稱為該節點的后繼節點。令為推算所有后繼節點的特別算符。我們把應用于某節點的過程叫做 擴展一個節點。3.指針: 從每個后繼節點返回指向其父輩節點。當最終找到目標節點時，這些指針能夠指出一條回到起始節點的路徑。4.目標匹配: 檢查各后繼節點看其是否為目標節點。如果還沒有找到目標節點，則繼續進行擴展節點和設置指針的過程。當找到一個目標節點時

20、，沿著有關各指針可以從目標節點回溯到起始節點，產生一條解答路徑。于是，對應于這條路徑上各連線的有關狀態描述算符，就構成一個解答序列。 對一個搜索過程的完全說明必須敘述被擴展節點的次序。寬（廣）度優先搜索: 如果搜索是以接近起始節點的程度(由節點間連接弧線的數目來衡量)依次擴展節點的，就叫做寬度優先搜索，這種搜索是逐層進行的。深度優先搜索: 如果搜索時首先擴展最新產生的節點, 則稱為深度優先搜索。上述兩種搜索方法都屬于盲目( 或稱無信息)搜索過程, 其節點的擴展次序不受目標節點位置的影響。 5.搜索過程的主要控制問題是選出一個適用于待擴展節點的算符( 有時也稱為規則) , 以產生后繼節點; 或者

21、是在選擇一個后繼節點之后, 再選擇一個合適的算符以產生一個新的后繼節點。其他控制任務包括檢驗算符的適用條件, 測試終止條件以及記住用過的算符等。因此, 我們可以把控制系統( 即選擇和確定控制策略的系統) 進行算符( 規則) 選擇的過程看做一個搜索過程。 對于許多任務來說, 有可能指出經驗法則或原則來簡化搜索。任何這種用來加速搜索的技術取決于由圖表示問題的特別信息。我們稱這種信息為啟發信息。利用這些信息, 我們往往能夠首先擴展最有希望的節點, 從而把搜索較快地推向目標. 。 S if then if then 控制策略費用規則應用費用.G 系 統 總 費 用 控制策略費用規則應用費用計 算 費

22、用(為選優而增加的費用)搜索空間大小費用00 啟發信息量傳統的計算費用分為兩類：規則應用費用和控制費用。一個完全無信息的控制系統只需要很少的控制費用，因為只是任意選取規則而不需要花費多少控制計算費用。但是，這種策略的規則應用費用卻很高，因為一般說來，要找到一個解需要應用大量的規則。第四節 狀態空間搜索策略2.4.1 圖搜索策略顯示圖: 各節點及其具有費用的弧線由一張表明確給出;表: 每一節點 后繼節點及連接弧線費用對 大型圖 不切實際 對無限節點圖不可能隱式圖: 起始節點已知,后繼節點算符已知 擴展節點 顯示圖可將使用隱式圖的狀態空間中的各節點劃分為以下三類: 未生成節點-暫不放入計算機存儲

23、已生成但尚未擴展節點-實現時放入一個OPEN表中 已擴展節點-實現時放入一個CLOSED表中 OPEN表格式 CLOSED表格式狀態結構返回指針狀態結構編號返回指針 一般的圖搜索過程如下：GRAPHSEARCH過程 將始點S放到OPEN表中。 OPEN表為空 ? (Y) 失敗退出 (N) 將OPEN表中的第一個節點n 取出，放入CLOSED表 n為目標點否 ? (Y) 輸出解并成功退出 (N) 擴展節點n，即生成非n之祖先的后繼節點集合M 注1 將M中那些既未在OPEN表,也沒在CLOSED表中出現過的節點加入OPEN表,并逐一設置指向n的指針 對M中每一個出現于OPEN中的節點K來說,則要確

24、定一下它們是否應該”投奔新父點”n (當求最小費用路徑時,必須進行這一判斷) 注2 對M中每一個出現于CLOSED表中的節點K來說,則要:1確定一下 K是否應該”投奔新父點”n 2由于K 已擴展有子代,此時還需確認K 的子孫后代節點的指針方向是否也要修改 注3 按某一方式或按某個試探組，重排OPEN表 說明如下:2.4.2 啟發式搜索策略在狀態空間的盲目搜索中搜索到一個解，所需要擴展的節點數目可能是很大的。因為這些節點的擴展次序完全是隨意的，而且沒有應用已解決問題的任何特性。因此，除了那些最簡單的問題之外，一般都要占用很多時間或空間（或者兩者均有）。這種結果是組合爆炸的一種表現形式。 有關具體

25、問題領域的信息常常可以用來簡化搜索。我們假設，初始狀態、算符和目標狀態的定義都是完全確定的，然后決定一個搜索空間，因此，問題就是如何有效地搜索這個給定空間。進行這種搜索的技術一般需要某些有關具體問題領域的特性的信息。我們已把此種信息叫做啟發信息，并把利用啟發信息的搜索方法叫做啟發性搜索方法。啟發信息: 具有某些有關具體問題領域的特性的知識 啟發信息分三種:用于決定下一個要擴展的節點 擴展節點時,用于決定要生成哪些后繼節點,而非全部 用于決定某些應該從搜索樹中拋棄或修剪的節點 第七節中，我們將提出一個只利用上述第一種啟發信息的狀態空間搜索算法，即決定哪一個是下一步要擴展的節點。一般，這種搜索總是

26、選擇“最有希望”的節點作為下一個被擴展的節點。執行這種思想的搜索，叫做有序搜索或最佳優先搜索。“最有希望”之節點:標準1 以此節點距離目標節點的估計距離進行估算,近者為優 (注重 ”未來”)標準2 估算從起點S到此點,以及從此點到目標節點的”綜合費用”,小者為優 (注重 ”歷史”+ ”未來”) 第五節 寬度優先搜索2.5.1 定義在圖搜索過程中，如果在有關問題的領域內沒有任何啟發信息可以用于排列OPEN表上的節點，這樣得到的過程，叫做無信息搜索過程，又叫盲目搜索過程。在人工智能中，實際上我們對無信息搜索過程并不感興趣，但是為了便于進行比較和加深對其他搜索過程或問題的理解，我們還是需要討論兩種類

27、型的無信息搜索，即寬度優先搜索和深度優先搜索。 寬度優先搜索: 按層次搜索 缺點: 時間長,如有解在有限層,必可找到 2.5.2 算法寬度優先搜索的搜索算法如下： 將始點S放到OPEN表中。 OPEN表為空 ? (Y) 失敗退出 (N) 從OPEN表首取走一個節點n，將其放入CLOSED表之尾部(并在編號欄給出一個順序號) 擴展節點n，將其子代節點依次放入OPEN表的 表尾 ,并逐一提供指向n的指針 是否有后繼節點為目標節點 ? (Y) 輸出解并成功退出 寬度優先搜索算法程序框圖注: 2.5.3 例題例: 給出把寬度優先搜索應用于八數碼難題時所生成的搜索樹。搜索樹上的所有節點都標記它們所對應的

28、狀態描述，每個節點旁邊的數字表示節點擴展的順序，我們預先規定產生后繼節點的順序如下：首先空格左移，接著上移，右移，最后向下移。如圖示:例: 考慮一個由一張桌子和三個積木玩具組成的世界。這一世界的初始狀態是這樣的：積木塊B 和C 放在桌面上，而積木塊A 堆放在積木塊B 上，如圖所示。我們希望達到一個目標狀態，三個積木這樣堆疊在一起：積木A 在頂部，B 在中間，而C 在底部。ABACBC 初始態 目標態這個問題中的唯一算符為MOVE（X，Y ），即把物體X 移到物體Y 上面。這個算符應用的先決條件是：(1)被移動物體的頂部必須是空的；(2)如果Y 是積木（即不是桌子），則Y 的頂部也必須是空的；(

29、3)應用算符去操作同一狀態不得多于一次（最后這一條件可從擴展節點表和非擴展節點表加以檢查）；(4) 移動時按A、B、C順序進行，即A 能移動時先移A。如圖示：樹上的節點為狀態S0至S10十一個節點；例如，節點S1對應于由“移動積木A 到桌子上”，即MOVE（A，Table）而得到的S0的后繼狀態。各節點以它們的給定數字次序產生和擴展，即S0，S1，S2，S10。當此運算終止時，我們找到S10這一目標狀態。被擴展節點表包括S0至S5，而OPEN表還包括有S6至S10各節點。2.5.4 等費用搜索及其算法(代價推進或代價驅動搜索)( 總朝著當前代價最小的節點方位向前推進 )例: 令c(i,j)表示

30、從節點i 到節點j 的連接弧線費用，g(i)為從起始節點S 到任一節點i 的路徑費用。其算法如下： 將始點S放到OPEN表中。 S為目標節點 ? (Y) 退出 (N) 令 g(s) = 0 OPEN表為空? (Y) 失敗退出 (N) 在整個OPEN表中選具有最小g(i)的節點i，將其放入CLOSED表 i為目標節點? (Y) 成功退出 (N) 擴展節點i，算出各后繼j的g(j)值g(j)=g(i)+c(i,j)將各后繼節點及其代價g值放入OPEN表 注 注: OPEN表格式 CLOSED表格式狀態字符串代價g(i)代價g(i)狀態字符串第六節 深度優先搜索 OPEN表及CLOSED表可設計為:

31、有界深度優先搜索算法 將始點s放到OPEN表中,置d(s)= 0 S為目標節點 ? (Y) 退出 (N) OPEN表為空 ? (Y) 失敗退出 (N) 取出OPEN表中最前面(棧頂)的節點n，放入CLOSED表尾,編上順序號 節點n的深度d(n)是否已到深度界限 ? (Y) (N) 擴展節點n，將其子節點n依次放入OPEN表前面(棧頂),并配上指向n的指針,置d(n)=d(n)+1 是否有任何后繼節點為目標節點 (Y) 成功 (N) 首先擴展最深的節點的結果使得搜索沿著狀態空間某條單一的路徑從起始節點向下進行下去；只有當搜索到達一個沒有后裔的狀態時，它才考慮另一條替代的路徑。為了避免考慮太長的

32、路徑（防止搜索過程沿著無益的路徑擴展下去），往往給出一個節點擴展的最大深度深度界限。任何節點如果達到了深度界限，那么都將把它們作為沒有后繼節點處理。值得說明的是，即使應用了深度界限的規定，所求得的解答路徑并不一定就是最短的路徑。例: 深度優先搜索所產生的八數碼難題搜索樹其中，我們設置深度界限為5 。第七節 啟發式搜索無論是寬度優先搜索或深度優先搜索，這些盲目搜索方法要尋找一個通向目標節點的路徑，都是耗費十分大的,所以我們必須尋找比盲目搜索更有效的其他搜索方法。 對于許多任務來說我們能夠利用與任務有關的信息來簡化搜索過程，稱此類信息為啟發信息，而稱這種利用啟發信息的搜索過程為啟發式搜索方法。2.

33、7.1 估價函數的應用啟發式搜索: 生成子代時,“甩去”無希望者 總擴展最有希望的節點利用某些信息,應用某些規則重排OPEN表 有序搜索 沿著某個被認為是最有希望的邊緣區段向外擴展。要應用這種排序過程，我們需要某些估算節點“希望”的量度。我們把這種估算節點“希望”的量度叫做估價函數。 我們用符號f 來標記估價函數，用f(n)表示節點n 的估價函數值。暫時令f 為任意函數，以后我們將會提出f 是從起始節點約束地通過節點n 而到達目標節點的最小費用路徑上的一個估算費用。應用某個算法（例如等費用算法）選擇OPEN表上具有最小f 值的節點作為下一個要擴展的節點，這種搜索方法叫做有序搜索或最佳優先搜索，

34、而其算法就叫做有序搜索算法或最佳優先算法。2.7.2 有序狀態空間搜索算法( Best - First Search )尼爾遜（Nilsson） 1971年提出了一個有序狀態空間的基本算法。估價函數f 是這樣確定的：一個節點的希望程度越大，其f 值就越小。選為擴展的節點是估價函數最小的節點。假設狀態空間為一個一般的圖。 有序狀態空間搜索算法如下：1.把起始節點S 放到OPEN 表中，計算f(S)并把其值與節點S 聯系起來。2.如果OPEN是個空表，則失敗退出，無解。3.從OPEN表中選擇一個f 值最小的節點i 。4.將i 從OPEN表中移出，并把它放入CLOSED表中,并給出順序編號。5.若i

35、 為目標節點，則成功退出，求得一個解。6.擴展節點i ，生成其全部后繼節點 ，對于i 的每個后繼節點j ： a）計算f(j)； b） 如果j 既不在OPEN表中，又不在CLOSED表中，則靠f 把它添入OPEN表，并設置j 指向其父輩節點i 的指針；注1 c） 如果j 已在OPEN表或CLOSED表中時 ，則拿新算出f 值和原OPEN表（或CLOSED表中）的原f 值進行比較 ，如果新的f 值較小，則： i) 以新f值取代原f值； ii) 從j 指向i ，而不再指向它（j）的“原父”點； iii) 若節點j 在CLOSED表中，則將其移回OPEN表。注27.轉向2，即GO TO 2.。注釋：1

36、) 在算法6中(b)處，每次往OPEN表中插入一新節點時，總按其f值將其插入到一個“合適”的位置（使節點有序）為好，這樣做可免去： 算法第3步從OPEN表選最小f值的元素時，要找遍OPEN表； 算法第4步從OPEN表移走一個元素時，會出現“空洞”的麻煩；2) 算法6中(c) 之iii)處的處理方法，可省去一段程序，該段程序對 j的子孫后代進行是否需要修改返回指針及f值的判斷與具體操作（參考Graph Search算法第7步）。運行該算法時，當再一次將j 從OPEN表移入CLOSED表中進行擴展時，仍會進行對其子代的相同檢查與修改操作，這樣逐層次進行下去（可能是間斷地進行），最終也達到了檢查j的

37、所有后代的指針方向與f值的相同效果。3) 有序搜索算法的特例設 f(n) = d(n) - 寬度優先搜索設 f(n) = - d(n)- 深度優先搜索 設 f(n) = 從起點S至節點n的路徑費用 -等費用搜索4) 在Nilsson算法中，并沒給出具體的f ：“估計過嚴”-有可能找不到解 或 最優解 “估計過寬”-可找到最優解 ，但搜索效率下降 5) 問題類型與f的選擇類型(a) 問題有多個解，現要找最優解： f 應較“寬”；類型(b) 求解該類問題所需時間、空間費用太高，只要求找到一個較好的解，這時f應稍嚴；類型(c) 找到任一解，f應盡可能地“嚴”，使搜索范圍盡可能小； 例： 解八數碼難題時，對f的幾種選法：(1) f(n)= w(n) 對應節點n的數據庫中（距目標點的數據庫來說）尚有多少沒有到位的棋子數 f28=?316475 12384765 目標 “嚴” (2) f(n)= p(n) 設對應節點n的數據庫中，每個數碼i（ 1<=i<=8 ）移到目標位置所需的最短距離為li(注：可朝上、下、左、右四方向移動，而不用管該方位是否有子)，則定義 P(n)= li 8 lii=1 f28=?146375 “嚴”(3) f(n)= d(n)+w(n) d(n): 從n“走”到目標，還需付