1、第五章狀態空間搜索策略搜索是人工智能的一個基本問題，是推理不可分割的一部分。搜索是求解問題的一種方法，是根據問題的實際情況，按照一定的策略或規則，從知識庫中尋找可利用的知識，從而構造出一條使問題獲得解決的推理路線的過程。搜索包含兩層含義：一層含義是要找到從初始事實到問題最終答案的一條推理路線；另一層含義是找到的這條路線是時間和空間復雜度最小的求解路線。搜索可分為盲目搜索和啟發式搜索兩種。11盲目搜索策略1狀態空間圖的搜索策略為了利用搜索的方法求解問題，首先必須將被求解的問題用某種形式表示出來。一般情況下，不同的知識表示對應著不同的求解方法。狀態空間表示法是一種用“狀態”和“算符”表示問題的方法

2、。狀態空間可由一個三元組表示（S，F，0S）。g利用搜索方法求解問題的基本思想是：首先將問題的初始狀態（即狀態空間圖中的初始節點）當作當前狀態，選擇一適當的算符作用于當前狀態，生成一組后繼狀態（或稱后繼節點），然后檢查這組后繼狀態中有沒有目標狀態。如果有，則說明搜索成功，從初始狀態到目標狀態的一系列算符即是問題的解；若沒有，則按照某種控制策略從已生成的狀態中再選一個狀態作為當前狀態，重復上述過程，直到目標狀態出現或不再有可供操作的狀態及算符時為止。算法51狀態空間圖的一般搜索算法建立一個只含有初始節點S的搜索圖G,把S放入OPEN表中。00表，且置為空表。CLOSED）建立判斷OPEN表是否為

3、空表，若為空，則問題無解，退出。選擇OPEN表中的第一個節點，把它從OPENS移出，并放入CLOSED!中，將此節點記為節點n。考察節點n是否為目標節點，若是，則問題有解，并成功退出。問題的解即可從圖G中沿著指針從n到S的這條路徑得到。擴展節點n生成一組不是n的祖先的后繼節點，并將它們記作集合M，將M中的這些節點作為n的后繼節點加入圖G中。對那些未曾在G中出現過的（即未曾在OPEN表上或CLOSED1上出現過的）M中的節點，設置一個指向父節點（即節點n）的指針，并把這些節點加入OPEN表中；對于已在G中出現過的M中的那些節點，確定是否需要修改指向父節點（n節點）的指針；對于那些先前已在G中出現

4、并且已在COLSEDI中的M中的節點，確定是否需要修改通向它們后繼節點的指針。按某一任意方式或按某種策略重排OPEN表中節點的順序。轉第步。2 寬度優先搜索策略寬度優先搜索是一種盲目搜索策略。其基本思想是，從初始節點開始，逐層對節點進行依次擴展，并考察它是否為目標節點，在對下層節點進行擴展（或搜索）之前，必須完成對當前層的所有節點的擴展（或搜索）。在搜索過程中，未擴展節點表OPEN中的節點排序準則是：先進入的節點排在前面，后進入的節點排在后面（即將擴展得到的后繼節點放于OPEN表的末端）。寬度優先搜索的盲目性較大，搜索效率低，這是它的缺點。但寬度優先搜索策略是完備的，即只要問題有解，用寬度優先

5、搜索總可以找到它的解。3 xx優先搜索首先擴展最新產生的其基本思想是：深度優先搜索也是一種盲目搜索策略，（即最深的）節點，即從初始節點S開始，在其后繼節點中選擇一個節點，對其進0行考察，若它不是目標節點，則對該節點進行擴展，并再從它的后繼節點中選擇一個節點進行考察。依此類推，一直搜索下去，當到達某個既非目標節點又無法繼續擴展的節點時，才選擇其兄弟節點進行考察。深度優先搜索與寬度優先搜索的區別就在于：在對節點n進行擴展時，其后繼節點在OPEN表中的存放位置。寬度優先搜索是將后繼節點放入OPEN表的末端，而深度優先搜索則是將后繼節點放入OPEN表的前端。4 有界xx優先搜索對于許多問題，其狀態空間

6、搜索樹的深度可能為無限深。為了避免搜索過程沿著無窮的路徑搜索下去，往往對一個節點擴展的最大深度進行限制。任何節點如果達到了深度界限，就把它作為沒有后繼節點進行處理，即對另一個分支進行搜索。在有界深度優先搜索算法中，深度界限的選擇很重要。選擇過大，可能會影響搜索的效率；選擇的過小，有可能求不到解。有界深度優先搜索策略是不完備的。5 代價樹的寬度優先搜索前面的搜索算法沒有考慮搜索的代價問題，即假設狀態空間圖中各節點之間的有向邊的代價是相同的。在實際問題求解中，往往是將一個狀態變換成另一個狀態時所付出的操作代價（或費用）是不一樣的，即狀態空間圖中各有向邊的代價是不一樣的。把有向邊上標有代價的搜索樹稱

7、為代價搜索樹，簡稱代價樹。代價樹寬度優先搜索的基本思想是：每次從OPEN表中選擇一個代價最小的節點，移入COLSED!。因此，每當對一節點擴展之后，就要計算它的所有后繼節點的代價，并將它們與OPEN表中已有的待擴展的節點按代價的大小從小到大依次排序。而從OPEN®選擇被擴展節點時即選擇排在最前面的節點（代價最小）。代價樹的寬度優先搜索算法是一個完備算法。6 代價樹的xx優先搜索代價樹的深度優先搜索和寬度優先搜索的區別是：寬度優先搜索法每次從OPEN®中的全體節點中選擇彳t價最小的節點移入CLOSED1,并對這一節點進行擴展或判斷（是否為目標節點），而深度優先搜索法則是從剛剛

8、擴展的節點之后3/ 6繼節點中選擇一個代價最小的節點移入CLOSED1,并進行擴展或判斷。代價樹的深度優先搜索算法是不完備的算法，所求得的解不一定是最優解，甚至有可能進入無窮分支路徑而搜索不到問題的解。12啟發式搜索策略利用問題自身特性信息，以提高搜索效率的搜索策略，稱為啟發式搜索或有信息搜索。1啟發信息與估價函數在搜索過程中，如果在確定要被考察的節點時，能夠利用被求解問題的有關特性信息，估計出各節點的重要性，就可選擇重要性較高的節點進行擴展，以便提高求解的效率。通常可以構造一個函數來表示節點的“希望”程度，稱這種函數為估價函數。估價函數f(x)可定義為從初始節點經過節點z到達目標節點的最小代

9、價路徑的代價估計值。它的一般形式為f(x)=g(x)+h(x)其中g(x)為初始節點S到節點z已實際付出的代價；h(x)是從節點x到目標節0點S的最優路徑的估計代價，搜索的啟發信息主要由h(x)來體現，故把h(x)稱g作啟發函數。估價函數是針對具體問題構造的，是與問題特性密切相關的。不同的問題，其估價函數可能不同。在構造估價函數時，依賴于問題特性的啟發函數h(x)的構造尤為重要。.在構造啟發函數時，還要考慮到兩個方面因素的影響：一個是搜索工作量，一個是搜索代價。有些啟發信息雖然能夠大大減少搜索的工作量，但卻不能保證求得最小代價的路徑。而我們感興趣的是，使問題求解的路徑代價與為求此路徑所花費的搜

10、索代價的綜合指標為最小。最佳優先搜索又稱為有序搜索或擇優搜索，它總是選擇最有希望的節點作為下一個要擴展的節點，而這種最有希望的節點是按估價函數f(x)的值來挑選的，一般估價函數的值越小，它的希望程度越大。最佳優先搜索又分局部最佳優先搜索和全局最佳優先搜索。(1)局部最佳優先搜索局部最佳優先搜索的思想類似于深度優先搜索法，但由于使用了與問題特性相關的估價函數來確定下一個待擴展的節點，所以它是一種啟發式搜索方法。其思想是：當對某一個節點擴展之后，對它的每一個后繼節點計算估價函數f(x)的值，并在這些后繼節點的范圍內，選擇一個f(x)的值最小的節點，作為下一個要考察的節點。由于它每次只在后繼節點的范

11、圍內選擇下一個要考察的節點，范圍比較小，所以稱為局部最佳優先搜索或局部擇優搜索。局部最佳優先搜索與深度優先搜索及代價樹的深度優先搜索的區別，就在于在選擇下一個節點時所用的標準不一樣。局部最佳優先搜索是以估價函數值作為標準；深度優先搜索則是以后繼節點的深度作為選擇標準，后生成的節點先考察；而代價樹深度優先則是以各后繼節點到其前驅節點之間的代價作為選擇標準。如果把層深函數d(x)就當作估價函數f(x),或把代價函數g(x)當作估價函數f(x),那么就可以把深度優先搜索和代價樹深度優先搜索看作局部最佳優先搜索的兩個特例。(2)全局最佳優先搜索它的思想類似于寬度優先全局最佳優先搜索也是一個有信息的啟發

12、式搜索，搜索，所不同的是，在確定下一個擴展節點時，以與問題特性密切相關的估價函數f(x)作為標準，不過這種方法是在OPEN表中的全部節點中選擇一個估價函數值f(x)最小的節點，作為下一個被考察的節點。正因為選擇的范圍是OPEN®中的全部節點，所以它稱為全局最佳優先搜索或全局擇優搜索。全局最佳優先搜索實際是對寬度優先搜索和代價樹的寬度優先搜索的擴展，而寬度優先搜索和代價樹的寬度優先搜索則是它的兩個特例(這時可分別令f(x)等于d(x)或g(x),d(x)表示節點x的深度，而g(x)則表示初始節點S到節點x在啟發式搜索中，估價函數的定義是非常重要的，如果定義得不好，則上述的搜索算法不一定能找到問題的解，即便找到解，也不一定是最優解。所以，有必要討論如何對估價函數進行限制或定義。A*啟發式搜索算法就使用了一種特殊定義的估價函數。A*算法具有下列一些性質：可采納性。所謂可采納性是指對于可求解的狀態空間圖(即從狀態空間圖的初始節點到目標節點有路徑存在)來說，如果一個搜索算法能在有限步內終止，并且能找到最優解，則稱該算法是可采納的。單調性。所謂單調性是指在A*算法中，如果對其估價函數中的h(x)部分即啟發性函數，加以適當的單調性限制條件，就可以使它對所擴展的