人工智能ch3 盲目搜索

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

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

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

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