第3章盲目搜索3.1一般搜索過程3.2回溯策略3.3寬度(廣度)優先搜索3.4代價樹的寬度優先搜索3.5深度優先搜索1參考教材M.TimJones著,黃厚寬等譯.人工智能,電子工業出版社,2010年7月.第3章盲目搜索搜索、推理與人工智能 搜索是人工智能中的一個基本問題，是推理不可分割的一部分，它直接關系到智能系統的性能與運行效率，尼爾遜把它列為人工智能研究中的核心問題之一。搜索的基本問題：是否一定能找到一個解；是否能終止運行或陷入一個死循環；找到的是否是最佳解；時間與空間復雜性如何。第3章盲目搜索已提出的搜索策略求任一解路的搜索策略爬山法、深度優先法、限定范圍搜索法、回溯法、最好優先法……求最佳解路的搜索策略寬度優先法、分枝界限法、動態規劃法、最佳圖搜索法（A*）……求與或關系解圖的搜索法一般與或圖搜索法、極大極小法、-剪枝法、啟發式剪枝法……第3章盲目搜索搜索策略選取操作算子的方式盲目搜索對特定問題不具有任何有關信息，按預定步驟（依次或隨機）進行搜索，搜索過程中獲得的中間信息不用來改進控制策略。特點：能快速調用操作算子。啟發式搜索考慮特定問題領域可應用的啟發性信息，動態確定調用操作算子的步驟，指導搜索朝最有希望的方向前進。特點：優先選取合適的操作算子，減少不必要搜索，提高效率啟發式一般優于盲目搜索，但不能過于追求更多甚至更完整的啟發信息。應綜合考慮，盡量使搜索系統的總開銷較小。第3章盲目搜索3.1一般搜索過程一、數據結構OPEN：未擴展節點表擴展：用合適算符對一個節點進行操作，生成一組子節點。存放剛生成的節點。不同搜索策略，節點在OPEN表中的排列順序不同。CLOSED：已擴展節點表存放將擴展或已擴展節點。OPEN表狀態節點父節點COLSE表編號狀態節點父節點3.1一般搜索過程3.1.3一般搜索過程3.1一般搜索過程二、算法流程建立只含有初始節點S的搜索圖G，把S放到OPEN表中；建立CLOSED表，其初始值為空表；若OPEN表是空表，則失敗退出；選擇OPEN表中第一個節點，把它從OPEN表移出并放進CLOSED表中，稱此節點為節點n；若n為目標節點，則有解并成功退出，解是追蹤圖G中沿指針從n到S這條路徑得到（指針在第⑦步中設置）；擴展n，生成不是n的祖先的那些后繼節點的集合M，把M的這些成員作為n的后繼節點添入圖G中；3.1一般搜索過程二、算法流程對M中子節點進行如下處理：對沒在G中出現過的（即沒在OPEN或CLOSED表中出現過的）M成員設置一個指向n的指針，把M的這些成員加進OPEN表；已在OPEN或CLOSED表中的每個M成員，確定是否需要更改指向n的指針方向；已在CLOSED表中的每個M成員，確定是否需要更改圖G中它的每個后裔節點指向父節點的指針。按某種方式或按某個試探值，重排OPEN表；轉第③步。3.1一般搜索過程三、幾點說明搜索過程具有通用性此后討論的各種搜索策略都可以看成是它的特例。各種搜索策略的主要區別在于：步驟⑧對OPEN表上的節點進行排序的準則，以便選出一個“最好”的節點作為步驟④擴展使用。排序是任意的，即肓目的——盲目搜索。排序用啟發信息為依據——啟發式搜索。3.1一般搜索過程三、幾點說明搜索圖和搜索樹圖搜索的一般過程中生成的明確圖，被稱為搜索圖G

。由圖G中所有節點及反向指針（在第⑦步形成的指向父節點的指針）構成的集合T，是一棵樹，稱為搜索樹。擴展某節點時圖G已保存了從初始節點到該節點的搜索樹。G中每個節點（S除外）有且僅有一個指向G中一個父節點的指針。OPEN表中節點都是搜索圖上未被擴展的端節點。CLOSED表中節點，是已被擴展但沒有生成后繼節點的端節點，或是搜索樹的非端節點。3.1一般搜索過程三、幾點說明搜索過程終止條件有解：在第⑤步，當被選作擴展的節點是目標節點時，搜索過程成功結束，得到了一個解。從目標節點按指向父節點的指針（第⑦步形成）不斷回溯，能重現從初始節點到目標節點的成功路徑。解是由從初始節點到該目標節點路徑上的算符構成。無解：當搜索樹不再有末被擴展的端節點時，即OPEN表為空，搜索過程失敗，從初始節點達不到目標節點。3.1一般搜索過程三、幾點說明步驟⑥的說明一個節點經一個算符操作通常指生成一個子節點。由于適用于一個節點的算符可能有多個，此時就會生成一組子節點。判斷子節點是否是當前擴展節點的父節點、祖父節點等，若是，則刪除。余下的子節點記做集合M，加入圖G中。

擴展節點時，生成該節點的所有后繼節點。3.1一般搜索過程三、幾點說明步驟⑦的說明問題：一個新生成的節點，若已作為其他節點的后繼節點被生成過，該新節點應作為哪個節點的后繼節點？解決方法：一般由初始節點到該節點路徑上所付出的代價來決定，那條路經付出的代價小，相應的節點就作為父節點。3.1一般搜索過程實心圓圈代表已擴展節點，它們位于CLOSED表中；空心圓圈代表未擴展節點，它們位于OPEN表中；有向邊旁的箭頭是指向父節點的指針。設有向弧兩端節點間的代價都為144524353.1一般搜索過程3.2回溯策略基本思想：從初始節點出發，不停地、試探性地尋找路徑直到到達目標節點或“不可解節點”為止。當遇到不可解節點時，就回溯到路徑中最近的父節點上，查看該節點是否還有其他的子節點未被擴展。如有，則沿這些子節點繼續搜索。如找到目標，就成功地退出搜索，返回解題路徑。3.2回溯策略回溯策略示例1A2B5F6G7H8I9J3C4D3.2回溯策略回溯策略的數據結構PS（PathStates）表——保存當前搜索路徑上的節點若找到目標節點，PS就是解題路徑上的節點有序集。NPS（NewPathStates）表——新路徑表包含待搜索節點，其后裔節點還未被搜索，即未被擴展。NPS可使算法回溯到其中任一節點；NSS（NoSolvableStates）表——不可解節點表列出找不到解題路徑的節點。如果在搜索中，擴展出的節點包含在NSS中，則立即將它排除，不需要沿著該節點繼續搜索。NSS可避免算法重新搜索無解的路徑。——Open表Close表3.2回溯策略回溯策略示例CSPSNPSNSS0AAA1BBABEFA2CCBACDBEFA3DDBADBEFAC4EEAEFABDC5FFAFAEBDC6GGFAGHIFAEBDC7HHFAHIFAGEDBC1A2B5E6F7G8H9I3C4D3.2回溯策略回溯策略的偽代碼procedurebreadth_first_searchbeginPS:=[Start]；NPS:=[Start]；NSS:=[]；CS:=Start；*初始化whileNPS[]dobeginifCS=目標節點thenreturn(PS)ifCS沒有子節點(不包括PS，NPS，NSS中已有節點)thenbeginwhile((PS非空)and(CS=PS中第一個元素))dobegin將CS加入到NSS*標明此*節點不可解從CS中刪除第一個元素CS*回溯從NPS中刪去第一個元素CSCS:=NPS中第一個元素；end將CS加入PS；endendelsebegin將CS子節點(不包括PS、NPS和NSS中已有的)加入到NPS；CS:=NPS中第一個元素；將CS加入到PS；endruturnFAIL；endendend3.2回溯策略回溯策略的幾點說明各種合適的推理規則或其他問題求解操作都可以應用于PS，得到一些新的子節點有序集；為避免死循環，若有序集中的子節點已在3張表的任一表中，說明它已被搜索過，不需要再考慮；有序集中的第一個子節點作為CS（當前正在被檢測的節點），并加入到PS中；有序集中其余子節點按順序放入NPS，用于以后搜索；如應用后，CS無子節點，從PS、NPS中刪除它，并將它加入到NSS中，之后回溯查找NPS中表首位置的節點。3.2回溯策略3.3寬度優先搜索基本思想：從初始節點開始，逐層對節點進行擴展，并考察它是否為目標節點。在第n層節點沒有全部擴展并考察之前，不對第n+1層的節點進行擴展。3.3寬度優先搜索一、數據結構OPEN表包含已生成但子節點未被搜索的節點。表中節點的排列次序就是搜索的次序。OPEN表采用先進先出的隊列結構。CLOSED表記錄已被生成擴展過的節點。相當于回溯算法中PS表和NSS表的合并。3.3寬度優先搜索二、算法流程把起始節點放到OPEN表中，如果該起始節點為一目標節點，則求得一個解答。若OPEN是空表，則沒有解，失敗退出；否則繼續。把第一個節點（節點n）從OPEN表移出，并把它放入CLOSED的擴展節點表中。擴展n。如果沒有后繼節點，則轉向步驟②。把n的所有后繼節點放到OPEN表的末端，并提供從這些后繼節點回到n的指針。如果n的任一個后繼節點是個目標節點，則找到一個解答，成功退出；否則轉向步驟②；3.3寬度優先搜索四、幾點說明刪除OPEN或CLOSED表中出現過的子狀態，避免循環搜索。只要問題有解，總能找到最短解題路徑。如果問題無解，對有限圖，算法會失敗退出；對無限圖，則永遠不會終止。3.3寬度優先搜索五、算法的缺陷盲目性較大，當目標節點距初始節點較遠，會產生許多無用節點，搜索效率低。因此，當圖中分枝數太多，實用意義不大。圖中各邊代價都相同，都為一個單位量，從而可用路徑的長度代替路徑的代價。然而，對許多問題這種假設是不現實的，即狀態空間中各邊的代價不可能完全相同。代價樹的寬度優先搜索算法啟發式搜索算法3.3寬度優先搜索3.4代價樹的寬度優先搜索算法例：城市交通問題。設有5個城市,它們之間的交通路線如圖所示，圖中的數字表示兩個城市之間的交通費用，即代價。求從A市出發到E市，費用最小的交通路線。結論：在搜索樹中給每條邊都標上代價。3.4代價樹的寬度優先搜索一、代價樹生成方法從初始節點A開始，把與A直接相鄰的節點作為子節點。對其他節點作相同處理。若一個節點已是某節點的直系先輩節點，就不能再作為該節點的子節點。除A外，其它節點可能在代價樹中多次出現。為便于區分，用下標1,2,……標出。3.4代價樹的寬度優先搜索二、代價的定義若節點j是i的子女，

c(i,j)：從i到j的連接弧線代價。g(i)：從起始節點S到i的路徑代價，即從S到i的最少代價路徑上的代價。g(j)=g(i)+c(i,j)3.4代價樹的寬度優先搜索三、算法流程把起始節點S放到未擴展節點表OPEN中。如果S為一目標節點，則求得一個解；否則令g(S)=0。如果OPEN是個空表，則沒有解，失敗退出。把OPEN表中第一個節點n取出，放入CLOSED表。如果n是目標節點，則求得問題的解，退出。若n不可擴展，則轉第(2)步。擴展n，將其子節點放入OPEN表，并配置指向父節點的指針；計算各子節點的代價，按代價對OPEN表中全部節點從小到大進行排序，然后轉第②步。3.4代價樹的寬度優先搜索四、示例最優解為：AB1E1代價為：9OPEN表狀態節點AC1B1B1D1D2E1D1E1D1E3C2COLSED表狀態節點AC1AB1C1AD2B1C1AE1D2B1C1A3.4代價樹的寬度優先搜索3.5深度優先搜索從初始節點開始，在其子節點中選擇一個進行考察，記為子節點n。若n不是目標節點，搜索n所有子節點以及子節點的后裔節點。當到達某個子節點，該子節點既不是目標節點又不能繼續擴展，才選擇n的兄弟節點進行考察。3.5深度優先搜索一、兩種算法比較深度與寬度優先搜索的不同寬度深度OPEN表先進先出的隊列結構先進后出的堆棧結構最優解總能找到最短解題路徑不一定能找到最優解3.5深度優先搜索二、算法缺陷和解決方法缺陷：搜索一旦進入某個分支，就沿著該分支一直向下搜索。如果目標節點不在此分支上，且該分支又是一個無窮分支，則不可能得到解。因此，深度優先搜索是不完備的。解決方法：為防止搜索沿一條路徑無限擴展，深度優先搜索常設定深度限制值，即有界深度優先搜索。3.5深度優先搜索三、有界深度優先搜索節點深度定義起始節點的深度為0。其他節點的深度等于其父節點的深度加1。深度界限為避免考慮太長路徑，防止搜索沿著無益路徑擴展，往往給出一個節點擴展的最大深度，稱為深度界限。若達到深度界限，對任何節點都認為它們沒有后繼節點。采用深度界限后，解答路徑也不一定是最短路徑。3.5深度優先搜索三、有界深度優先搜索算法流程：把起始節點S放到OPEN表中。如果此節點為目標節點，則得到一個解