人工智能ch3 盲目搜索

第3章盲目搜索3.1一般搜索過(guò)程3.2回溯策略3.3寬度(廣度)優(yōu)先搜索3.4代價(jià)樹(shù)的寬度優(yōu)先搜索3.5深度優(yōu)先搜索1參考教材M.TimJones著,黃厚寬等譯.人工智能,電子工業(yè)出版社,2010年7月.第3章盲目搜索搜索、推理與人工智能 搜索是人工智能中的一個(gè)基本問(wèn)題，是推理不可分割的一部分，它直接關(guān)系到智能系統(tǒng)的性能與運(yùn)行效率，尼爾遜把它列為人工智能研究中的核心問(wèn)題之一。搜索的基本問(wè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ì)特定問(wèn)題不具有任何有關(guān)信息，按預(yù)定步驟（依次或隨機(jī)）進(jìn)行搜索，搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。特點(diǎn)：能快速調(diào)用操作算子。啟發(fā)式搜索考慮特定問(wèn)題領(lǐng)域可應(yīng)用的啟發(fā)性信息，動(dòng)態(tài)確定調(diào)用操作算子的步驟，指導(dǎo)搜索朝最有希望的方向前進(jìn)。特點(diǎn)：優(yōu)先選取合適的操作算子，減少不必要搜索，提高效率啟發(fā)式一般優(yōu)于盲目搜索，但不能過(guò)于追求更多甚至更完整的啟發(fā)信息。應(yīng)綜合考慮，盡量使搜索系統(tǒng)的總開(kāi)銷(xiāo)較小。第3章盲目搜索3.1一般搜索過(guò)程一、數(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一般搜索過(guò)程3.1.3一般搜索過(guò)程3.1一般搜索過(guò)程二、算法流程建立只含有初始節(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一般搜索過(guò)程二、算法流程對(duì)M中子節(jié)點(diǎn)進(jìn)行如下處理：對(duì)沒(méi)在G中出現(xiàn)過(guò)的（即沒(méi)在OPEN或CLOSED表中出現(xiàn)過(guò)的）M成員設(shè)置一個(gè)指向n的指針，把M的這些成員加進(jìn)OPEN表；已在OPEN或CLOSED表中的每個(gè)M成員，確定是否需要更改指向n的指針?lè)较?；已在CLOSED表中的每個(gè)M成員，確定是否需要更改圖G中它的每個(gè)后裔節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。按某種方式或按某個(gè)試探值，重排OPEN表；轉(zhuǎn)第③步。3.1一般搜索過(guò)程三、幾點(diǎn)說(shuō)明搜索過(guò)程具有通用性此后討論的各種搜索策略都可以看成是它的特例。各種搜索策略的主要區(qū)別在于：步驟⑧對(duì)OPEN表上的節(jié)點(diǎn)進(jìn)行排序的準(zhǔn)則，以便選出一個(gè)“最好”的節(jié)點(diǎn)作為步驟④擴(kuò)展使用。排序是任意的，即肓目的——盲目搜索。排序用啟發(fā)信息為依據(jù)——啟發(fā)式搜索。3.1一般搜索過(guò)程三、幾點(diǎn)說(shuō)明搜索圖和搜索樹(shù)圖搜索的一般過(guò)程中生成的明確圖，被稱為搜索圖G

。由圖G中所有節(jié)點(diǎn)及反向指針（在第⑦步形成的指向父節(jié)點(diǎn)的指針）構(gòu)成的集合T，是一棵樹(shù)，稱為搜索樹(shù)。擴(kuò)展某節(jié)點(diǎn)時(shí)圖G已保存了從初始節(jié)點(diǎn)到該節(jié)點(diǎn)的搜索樹(shù)。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ò)展但沒(méi)有生成后繼節(jié)點(diǎn)的端節(jié)點(diǎn)，或是搜索樹(shù)的非端節(jié)點(diǎn)。3.1一般搜索過(guò)程三、幾點(diǎn)說(shuō)明搜索過(guò)程終止條件有解：在第⑤步，當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)，搜索過(guò)程成功結(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)成。無(wú)解：當(dāng)搜索樹(shù)不再有末被擴(kuò)展的端節(jié)點(diǎn)時(shí)，即OPEN表為空，搜索過(guò)程失敗，從初始節(jié)點(diǎn)達(dá)不到目標(biāo)節(jié)點(diǎn)。3.1一般搜索過(guò)程三、幾點(diǎn)說(shuō)明步驟⑥的說(shuō)明一個(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一般搜索過(guò)程三、幾點(diǎn)說(shuō)明步驟⑦的說(shuō)明問(wèn)題：一個(gè)新生成的節(jié)點(diǎn)，若已作為其他節(jié)點(diǎn)的后繼節(jié)點(diǎn)被生成過(guò)，該新節(jié)點(diǎn)應(yīng)作為哪個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)？解決方法：一般由初始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來(lái)決定，那條路經(jīng)付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為父節(jié)點(diǎn)。3.1一般搜索過(guò)程實(shí)心圓圈代表已擴(kuò)展節(jié)點(diǎn)，它們位于CLOSED表中；空心圓圈代表未擴(kuò)展節(jié)點(diǎn)，它們位于OPEN表中；有向邊旁的箭頭是指向父節(jié)點(diǎn)的指針。設(shè)有向弧兩端節(jié)點(diǎn)間的代價(jià)都為144524353.1一般搜索過(guò)程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可避免算法重新搜索無(wú)解的路徑?！狾pen表Close表3.2回溯策略回溯策略示例CSPSNPSNSS0AAA1BBABEFA2CCBACDBEFA3DDBADBEFAC4EEAEFABDC5FFAFAEBDC6GGFAGHIFAEBDC7HHFAHIFAGEDBC1A2B5E6F7G8H9I3C4D3.2回溯策略回溯策略的偽代碼procedurebreadth_first_searchbeginPS:=[Start]；NPS:=[Start]；NSS:=[]；CS:=Start；*初始化whileNPS[]dobeginifCS=目標(biāo)節(jié)點(diǎn)thenreturn(PS)ifCS沒(méi)有子節(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)說(shuō)明各種合適的推理規(guī)則或其他問(wèn)題求解操作都可以應(yīng)用于PS，得到一些新的子節(jié)點(diǎn)有序集；為避免死循環(huán)，若有序集中的子節(jié)點(diǎn)已在3張表的任一表中，說(shuō)明它已被搜索過(guò)，不需要再考慮；有序集中的第一個(gè)子節(jié)點(diǎn)作為CS（當(dāng)前正在被檢測(cè)的節(jié)點(diǎn)），并加入到PS中；有序集中其余子節(jié)點(diǎn)按順序放入NPS，用于以后搜索；如應(yīng)用后，CS無(wú)子節(jié)點(diǎn)，從PS、NPS中刪除它，并將它加入到NSS中，之后回溯查找NPS中表首位置的節(jié)點(diǎn)。3.2回溯策略3.3寬度優(yōu)先搜索基本思想：從初始節(jié)點(diǎn)開(kāi)始，逐層對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展，并考察它是否為目標(biāo)節(jié)點(diǎn)。在第n層節(jié)點(diǎn)沒(méi)有全部擴(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ò)展過(guò)的節(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是空表，則沒(méi)有解，失敗退出；否則繼續(xù)。把第一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)n）從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。擴(kuò)展n。如果沒(méi)有后繼節(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)說(shuō)明刪除OPEN或CLOSED表中出現(xiàn)過(guò)的子狀態(tài)，避免循環(huán)搜索。只要問(wèn)題有解，總能找到最短解題路徑。如果問(wèn)題無(wú)解，對(duì)有限圖，算法會(huì)失敗退出；對(duì)無(wú)限圖，則永遠(yuǎn)不會(huì)終止。3.3寬度優(yōu)先搜索五、算法的缺陷盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)，會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低。因此，當(dāng)圖中分枝數(shù)太多，實(shí)用意義不大。圖中各邊代價(jià)都相同，都為一個(gè)單位量，從而可用路徑的長(zhǎng)度代替路徑的代價(jià)。然而，對(duì)許多問(wèn)題這種假設(shè)是不現(xiàn)實(shí)的，即狀態(tài)空間中各邊的代價(jià)不可能完全相同。代價(jià)樹(shù)的寬度優(yōu)先搜索算法啟發(fā)式搜索算法3.3寬度優(yōu)先搜索3.4代價(jià)樹(shù)的寬度優(yōu)先搜索算法例：城市交通問(wèn)題。設(shè)有5個(gè)城市,它們之間的交通路線如圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用，即代價(jià)。求從A市出發(fā)到E市，費(fèi)用最小的交通路線。結(jié)論：在搜索樹(shù)中給每條邊都標(biāo)上代價(jià)。3.4代價(jià)樹(shù)的寬度優(yōu)先搜索一、代價(jià)樹(shù)生成方法從初始節(jié)點(diǎn)A開(kāi)始，把與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à)樹(shù)中多次出現(xiàn)。為便于區(qū)分，用下標(biāo)1,2,……標(biāo)出。3.4代價(jià)樹(shù)的寬度優(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à)樹(shù)的寬度優(yōu)先搜索三、算法流程把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)表OPEN中。如果S為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則令g(S)=0。如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出。把OPEN表中第一個(gè)節(jié)點(diǎn)n取出，放入CLOSED表。如果n是目標(biāo)節(jié)點(diǎn)，則求得問(wè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à)樹(shù)的寬度優(yōu)先搜索四、示例最優(yōu)解為：AB1E1代價(jià)為：9OPEN表狀態(tài)節(jié)點(diǎn)AC1B1B1D1D2E1D1E1D1E3C2COLSED表狀態(tài)節(jié)點(diǎn)AC1AB1C1AD2B1C1AE1D2B1C1A3.4代價(jià)樹(shù)的寬度優(yōu)先搜索3.5深度優(yōu)先搜索從初始節(jié)點(diǎn)開(kāi)始，在其子節(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è)無(wú)窮分支，則不可能得到解。因此，深度優(yōu)先搜索是不完備的。解決方法：為防止搜索沿一條路徑無(wú)限擴(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。深度界限為避免考慮太長(zhǎng)路徑，防止搜索沿著無(wú)益路徑擴(kuò)展，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度，稱為深度界限。若達(dá)到深度界限，對(duì)任何節(jié)點(diǎn)都認(rèn)為它們沒(méi)有后繼節(jié)點(diǎn)。采用深度界限后，解答路徑也不一定是最短路徑。3.5深度優(yōu)先搜索三、有界深度優(yōu)先搜索算法流程：把起始節(jié)點(diǎn)S放到OPEN表中。如果此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解