人工智能ch3 盲目搜索

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

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

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

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