人工智能之(搜索推理技術(shù)1-圖盲目搜索)

1、人人 工工 智智 能能Artificial Intelligence (AI)劉劉 靜靜理工學(xué)院理工學(xué)院2009年春季年春季 上一章中我們研究了知識(shí)表示方法，為人工上一章中我們研究了知識(shí)表示方法，為人工智能問(wèn)題的求解打下了基礎(chǔ)。從問(wèn)題表示到問(wèn)題智能問(wèn)題的求解打下了基礎(chǔ)。從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。接下來(lái)要研究的是的解決，有一個(gè)求解的過(guò)程。接下來(lái)要研究的是實(shí)現(xiàn)求解的過(guò)程，采用的基本方法包括搜索和推實(shí)現(xiàn)求解的過(guò)程，采用的基本方法包括搜索和推理。本章先介紹搜索技術(shù)，將要討論問(wèn)題求解的理。本章先介紹搜索技術(shù)，將要討論問(wèn)題求解的搜索原理，包括一些早期的搜索技術(shù)或用于解決搜索原理，包括一些早

2、期的搜索技術(shù)或用于解決比較簡(jiǎn)單問(wèn)題的搜索原理和一些比較新的能夠求比較簡(jiǎn)單問(wèn)題的搜索原理和一些比較新的能夠求解比較復(fù)雜問(wèn)題的搜索原理，包括解比較復(fù)雜問(wèn)題的搜索原理，包括AO*算法、遺算法、遺傳算法和模擬退火算法等。傳算法和模擬退火算法等。第第3章章 搜索推理原理搜索推理原理 3.1 圖的搜索策略圖的搜索策略3.2 盲目搜索盲目搜索3.3 啟發(fā)式搜索啟發(fā)式搜索3.4 與或樹(shù)搜索（與或樹(shù)搜索（補(bǔ)充補(bǔ)充）3.5 博弈樹(shù)搜索（博弈樹(shù)搜索（補(bǔ)充補(bǔ)充）3.6 消解原理消解原理解決實(shí)際問(wèn)題的兩個(gè)關(guān)鍵之處解決實(shí)際問(wèn)題的兩個(gè)關(guān)鍵之處：?jiǎn)栴}的表達(dá)問(wèn)題的表達(dá) 狀態(tài)空間法狀態(tài)空間法 問(wèn)題歸約法問(wèn)題歸約法 謂詞邏輯法謂詞

3、邏輯法問(wèn)題的求解問(wèn)題的求解 搜索技術(shù)搜索技術(shù) 推理技術(shù)推理技術(shù)盲目與啟發(fā)式搜索盲目與啟發(fā)式搜索：狀態(tài)空間法、圖的搜索技術(shù)：狀態(tài)空間法、圖的搜索技術(shù)與或樹(shù)搜索與或樹(shù)搜索：?jiǎn)栴}歸約法、與或圖的特例的搜索：?jiǎn)栴}歸約法、與或圖的特例的搜索技術(shù)技術(shù)博弈樹(shù)搜索博弈樹(shù)搜索：狀態(tài)空間法：狀態(tài)空間法問(wèn)題歸約法、雙人博問(wèn)題歸約法、雙人博弈的特殊搜索技術(shù)弈的特殊搜索技術(shù)消解原理消解原理：謂詞邏輯法、推理技術(shù)：謂詞邏輯法、推理技術(shù)在介紹圖搜索策略之前，讓我們來(lái)看一個(gè)例子。例子：從某王姓家族的四代中找王A的后代且其壽命為X的人。王A：壽命47，有兒子王B1、王B3、王B2王B1：壽命77，有兒子王C1、王C2王B3：壽

4、命52，有兒子王D1王B2：壽命65，有兒子王E1、王E2王F1：壽命32 王G1：壽命96王C2：壽命87，有兒子王F1王D1：壽命77，沒(méi)有兒子王E1：壽命57，有兒子王G1 王E2：壽命92，有兒子王H1 王C1：壽命27，沒(méi)有兒子王H1：壽命51若X=57，下面討論一種可通用的圖搜索策略求解此問(wèn)題。如果是一個(gè)N代的家族表中找其壽命為X的人，我們最可能用的手工方法是從家族表的開(kāi)始往下，例中還要求所找的人是某人的后代，就比較復(fù)雜了。如果用圖來(lái)表示，就很容易了。圖中把姓氏省去，每個(gè)成員的后代按例子中給出名字的先后順序。圖示為： 3.1 圖搜索策略圖搜索策略 狀態(tài)空間中狀態(tài)空間中： 狀態(tài)狀態(tài)初

5、始狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)目標(biāo)狀態(tài)操作符操作符圖中有圖中有：節(jié)點(diǎn)節(jié)點(diǎn)初始節(jié)點(diǎn)初始節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)有向弧有向弧狀態(tài)空間法與圖的對(duì)應(yīng)關(guān)系狀態(tài)空間法與圖的對(duì)應(yīng)關(guān)系q 在狀態(tài)空間中，解是從在狀態(tài)空間中，解是從初始狀態(tài)初始狀態(tài)到到目標(biāo)狀態(tài)目標(biāo)狀態(tài)的的操作符序列操作符序列q 在圖中，解是從在圖中，解是從初始節(jié)點(diǎn)初始節(jié)點(diǎn)到到目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)的一條的一條路路徑徑解的含義解的含義：圖的搜索策略圖的搜索策略：圖搜索過(guò)程的一般步驟（圖搜索過(guò)程的一般步驟（基本基本思路、框架思路、框架），經(jīng)過(guò)細(xì)化后得到具體算法：），經(jīng)過(guò)細(xì)化后得到具體算法：盲目搜索技術(shù)（盲目搜索技術(shù)（深度深度、寬度寬度、代價(jià)代價(jià)優(yōu)先算法）優(yōu)先算法）啟發(fā)

6、式搜索技術(shù)（啟發(fā)式搜索技術(shù)（有序有序算法、算法、A*算法）算法）圖搜索中的圖搜索中的兩個(gè)重要記號(hào)兩個(gè)重要記號(hào)（符號(hào)）：（符號(hào)）：OPEN 表表： 存放待擴(kuò)展的節(jié)點(diǎn)存放待擴(kuò)展的節(jié)點(diǎn)CLOSED 表表：存放已擴(kuò)展的節(jié)點(diǎn)：存放已擴(kuò)展的節(jié)點(diǎn)注意注意：在與或樹(shù)搜索中也要用到這兩張表：在與或樹(shù)搜索中也要用到這兩張表數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)結(jié)構(gòu)中圖的遍及圖的遍及：從圖某一個(gè)節(jié)點(diǎn)出發(fā)，：從圖某一個(gè)節(jié)點(diǎn)出發(fā)，訪問(wèn)遍圖中其余節(jié)點(diǎn)，且每一個(gè)節(jié)點(diǎn)僅僅被訪問(wèn)訪問(wèn)遍圖中其余節(jié)點(diǎn)，且每一個(gè)節(jié)點(diǎn)僅僅被訪問(wèn)一次。一次。當(dāng)前圖的搜索技術(shù)中，有兩個(gè)當(dāng)前圖的搜索技術(shù)中，有兩個(gè)特殊之處特殊之處： 搜索前，圖并沒(méi)有生成好，需要邊搜索前，圖并沒(méi)有生

7、成好，需要邊生成生成圖邊圖邊搜索搜索 搜索從起始節(jié)點(diǎn)（初始狀態(tài)）開(kāi)始，到目標(biāo)節(jié)點(diǎn)搜索從起始節(jié)點(diǎn)（初始狀態(tài)）開(kāi)始，到目標(biāo)節(jié)點(diǎn)（目標(biāo)狀態(tài)）結(jié)束，不需要搜索（目標(biāo)狀態(tài)）結(jié)束，不需要搜索所有所有可能的節(jié)點(diǎn)可能的節(jié)點(diǎn)盲目搜索盲目搜索是指無(wú)問(wèn)題先驗(yàn)信息的搜索技術(shù)是指無(wú)問(wèn)題先驗(yàn)信息的搜索技術(shù)特點(diǎn)特點(diǎn)： OPEN表中節(jié)點(diǎn)的排列是人為規(guī)定的表中節(jié)點(diǎn)的排列是人為規(guī)定的 一般只適合于求解比較簡(jiǎn)單的一些問(wèn)題一般只適合于求解比較簡(jiǎn)單的一些問(wèn)題3.2 盲目搜索盲目搜索圖的盲目搜索技術(shù)分成圖的盲目搜索技術(shù)分成：寬度優(yōu)先搜索技術(shù)寬度優(yōu)先搜索技術(shù)深度優(yōu)先搜索技術(shù)深度優(yōu)先搜索技術(shù)等代價(jià)（代價(jià)優(yōu)先）搜索技術(shù)等代價(jià)（代價(jià)優(yōu)先）搜索技

8、術(shù)3.2.1 寬度優(yōu)先搜索寬度優(yōu)先搜索 寬度優(yōu)先搜索寬度優(yōu)先搜索：以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展：以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的搜索技術(shù)（即：離起始節(jié)點(diǎn)近的節(jié)點(diǎn)先被節(jié)點(diǎn)的搜索技術(shù)（即：離起始節(jié)點(diǎn)近的節(jié)點(diǎn)先被擴(kuò)展）擴(kuò)展）擴(kuò)展節(jié)點(diǎn)的原則擴(kuò)展節(jié)點(diǎn)的原則：先擴(kuò)展出來(lái)的節(jié)點(diǎn)隨后優(yōu)先被：先擴(kuò)展出來(lái)的節(jié)點(diǎn)隨后優(yōu)先被擴(kuò)展（擴(kuò)展（生成其所有的后繼節(jié)點(diǎn)生成其所有的后繼節(jié)點(diǎn)） 把起始節(jié)點(diǎn)放到把起始節(jié)點(diǎn)放到 OPEN 表中表中(如果該起始節(jié)點(diǎn)如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解為一目標(biāo)節(jié)點(diǎn)，則得到解) 如果如果 OPEN 是個(gè)空表，則無(wú)解，失敗退出；是個(gè)空表，則無(wú)解，失敗退出；否則繼續(xù)下一步否則繼續(xù)下一步寬度優(yōu)先搜

9、索算法寬度優(yōu)先搜索算法： 把第一個(gè)節(jié)點(diǎn)把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)記作節(jié)點(diǎn) n )從從 OPEN 表移出，表移出，并把它放入并把它放入 CLOSED 的已擴(kuò)展節(jié)點(diǎn)表中的已擴(kuò)展節(jié)點(diǎn)表中 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn) n 。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第步步 把把 n 的所有后繼節(jié)點(diǎn)放到的所有后繼節(jié)點(diǎn)放到OPEN表的表的，并提供從這些后繼節(jié)點(diǎn)回到并提供從這些后繼節(jié)點(diǎn)回到 n 的指針的指針 如果如果 n 的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解（找到一個(gè)解（反向追蹤得到從目標(biāo)節(jié)點(diǎn)到起始反向追蹤得到從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑節(jié)點(diǎn)的路徑），成功退出，否則轉(zhuǎn)向第步），

10、成功退出，否則轉(zhuǎn)向第步 OPEN 表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)，它是一個(gè)先進(jìn)先出的隊(duì)列上來(lái)說(shuō)，它是一個(gè)先進(jìn)先出的隊(duì)列 CLOSED 表是存放已被擴(kuò)展過(guò)的節(jié)點(diǎn)（包括表是存放已被擴(kuò)展過(guò)的節(jié)點(diǎn)（包括有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無(wú)后繼節(jié)點(diǎn)的端節(jié)有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無(wú)后繼節(jié)點(diǎn)的端節(jié)點(diǎn)）點(diǎn)）說(shuō)明說(shuō)明：流程圖流程圖 搜索過(guò)程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的搜索過(guò)程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的狀態(tài)空間樹(shù)的子樹(shù)，稱(chēng)之為狀態(tài)空間樹(shù)的子樹(shù)，稱(chēng)之為搜索樹(shù)搜索樹(shù)注意幾點(diǎn)注意幾點(diǎn)： 寬度優(yōu)先搜索方法能夠保證在搜索樹(shù)中找到寬度優(yōu)先搜索方法能夠保證在搜索樹(shù)中找到一條通向目標(biāo)節(jié)點(diǎn)的

11、一條通向目標(biāo)節(jié)點(diǎn)的最短途徑最短途徑（所用操作符（所用操作符最少）最少）例：例：八數(shù)碼問(wèn)題八數(shù)碼問(wèn)題初始狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)目標(biāo)狀態(tài)操作符：操作符：2831476512384765空空1243狀態(tài)狀態(tài)：長(zhǎng)度為：長(zhǎng)度為9的一維數(shù)組的一維數(shù)組 （q1 , q2 , , q9 ）其中，其中，qi 取取 0 , 1 , , 8 個(gè)數(shù)，個(gè)數(shù)，0 表示空格，且取值表示空格，且取值互不相同互不相同 如果記空格的位置為如果記空格的位置為P，這時(shí)空格的移動(dòng)規(guī)則是：，這時(shí)空格的移動(dòng)規(guī)則是：123456789123456789PP-3P+1P+3P-1數(shù)字表示位置數(shù)字表示位置 順序順序規(guī)則規(guī)則前提條件前提條件應(yīng)用結(jié)果

12、應(yīng)用結(jié)果1左移左移P1,4,7P 位置與位置與 P-1 位置上的元素互換位置上的元素互換2上移上移P1,2,3 P-33下移下移P7,8,9 P+34右移右移P3,6,9 P+1空格移動(dòng)規(guī)則空格移動(dòng)規(guī)則P-3P+3P-1P+1123456789為了記錄后繼節(jié)點(diǎn)與父節(jié)點(diǎn)之間的指針，我們將為了記錄后繼節(jié)點(diǎn)與父節(jié)點(diǎn)之間的指針，我們將長(zhǎng)度為長(zhǎng)度為 9 的數(shù)組擴(kuò)大到長(zhǎng)度為的數(shù)組擴(kuò)大到長(zhǎng)度為 11 的數(shù)組，其中的數(shù)組，其中一個(gè)元素記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志，另一個(gè)元素一個(gè)元素記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志，另一個(gè)元素記錄操作符的序號(hào)記錄操作符的序號(hào)操作符操作符父節(jié)點(diǎn)父節(jié)點(diǎn)狀態(tài)狀態(tài)OPEN表的存儲(chǔ)形式表的存儲(chǔ)形式：隊(duì)列

13、：隊(duì)列插入端（隊(duì)尾）插入端（隊(duì)尾）刪除端（隊(duì)頭）刪除端（隊(duì)頭）隊(duì)列隊(duì)列：一種先進(jìn)先出的線性表，允許在表的一：一種先進(jìn)先出的線性表，允許在表的一端進(jìn)行插入、另一端進(jìn)行刪除端進(jìn)行插入、另一端進(jìn)行刪除CLOSED表的存儲(chǔ)形式表的存儲(chǔ)形式：也可以用隊(duì)列：也可以用隊(duì)列父父 符符插入端（隊(duì)尾）插入端（隊(duì)尾）特殊的隊(duì)列特殊的隊(duì)列：只進(jìn)不出的隊(duì)列，只允許在表的：只進(jìn)不出的隊(duì)列，只允許在表的一端進(jìn)行插入一端進(jìn)行插入某一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志某一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志： 記錄記錄CLOSED表中的父節(jié)點(diǎn)的序號(hào)表中的父節(jié)點(diǎn)的序號(hào)起始節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志和操作符起始節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志和操作符： 不作記錄或記錄為負(fù)不作記錄或記錄為負(fù)

14、搜索過(guò)程搜索過(guò)程（按照程序運(yùn)行方式）（按照程序運(yùn)行方式） 起始節(jié)點(diǎn)放到起始節(jié)點(diǎn)放到OPEN表表283104765 OPEN不為空，繼續(xù)不為空，繼續(xù)28314765 將第一個(gè)節(jié)點(diǎn)將第一個(gè)節(jié)點(diǎn) n 從從 OPEN 表中移出，并放到表中移出，并放到CLOSED表中表中00283104765OPEN表表CLOSED表表節(jié)點(diǎn)節(jié)點(diǎn)n1 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n 283014765 203184765 283164705 28314076500283104765擴(kuò)展擴(kuò)展28314765 將節(jié)點(diǎn)將節(jié)點(diǎn) n 的所有后繼節(jié)點(diǎn)放到的所有后繼節(jié)點(diǎn)放到 OPEN 表的末表的末端，并提供這些后繼節(jié)點(diǎn)回到端，并提供這些后繼節(jié)點(diǎn)回

15、到 n 的指針的指針11283014765122031847651328316470514283140765OPEN表表符符父父00283104765CLOSED 后繼節(jié)點(diǎn)中無(wú)目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)到后繼節(jié)點(diǎn)中無(wú)目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)到 OPEN表不為空，繼續(xù)表不為空，繼續(xù) 將第一個(gè)節(jié)點(diǎn)將第一個(gè)節(jié)點(diǎn) n 從從 OPEN 表中移出，并放到表中移出，并放到CLOSED 表中表中OPEN表表CLOSED表表1220318476513283164705142831407650028310476511283014765節(jié)節(jié)點(diǎn)點(diǎn)n12 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn) n 083214765 283714065112830147652831

16、4765 將節(jié)點(diǎn)將節(jié)點(diǎn) n 的所有后繼節(jié)點(diǎn)放到的所有后繼節(jié)點(diǎn)放到 OPEN 表的末表的末端，并提供這些后繼節(jié)點(diǎn)回到端，并提供這些后繼節(jié)點(diǎn)回到 n 的指針的指針122031847651328316470514283140765OPEN表表 2 2083214765 2 3283714065.一直繼續(xù)下去，而且不產(chǎn)生已經(jīng)產(chǎn)生過(guò)的節(jié)點(diǎn)一直繼續(xù)下去，而且不產(chǎn)生已經(jīng)產(chǎn)生過(guò)的節(jié)點(diǎn)（狀態(tài)），防止死循環(huán)。在程序中每一個(gè)新產(chǎn)（狀態(tài)），防止死循環(huán)。在程序中每一個(gè)新產(chǎn)生的節(jié)點(diǎn)必須與生的節(jié)點(diǎn)必須與 OPEN 和和 CLOSED 表中狀態(tài)表中狀態(tài)進(jìn)行比較，判斷是否已經(jīng)產(chǎn)生過(guò)，只保留從未進(jìn)行比較，判斷是否已經(jīng)產(chǎn)生過(guò)，只保

17、留從未產(chǎn)生過(guò)的節(jié)點(diǎn)產(chǎn)生過(guò)的節(jié)點(diǎn)最后的最后的OPEN表：表：93234180765103283064175112283160754121208143765131283145706144830214765143813204765152283704615154283714650163123784065164123804765目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)12384765最后的最后的CLOSED表：表：283104765112830147651220318476513283164705142831407652208321476523283714065310231847653423018476512345678941

18、28316407544283164750522801437505328314576064803214765742837146058312308476510111213141516164123804765目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)83123084765164123804765目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)3102318476516812203184765283104765312831476528314765231847652831647528314765214383214765283714652318476523184765281437652831647528316475283145768321476528371465

19、123847652341876528364175283167542814376528314576832147658132476512378465123847652837461528371465先生成的先生成的節(jié)點(diǎn)在左節(jié)點(diǎn)在左目標(biāo)目標(biāo)節(jié)點(diǎn)節(jié)點(diǎn)（先擴(kuò)展的節(jié)點(diǎn)畫(huà)在左邊）（先擴(kuò)展的節(jié)點(diǎn)畫(huà)在左邊）生成后繼節(jié)生成后繼節(jié)點(diǎn)的順序點(diǎn)的順序OPEN與與CLOSED表的存儲(chǔ)形式的簡(jiǎn)化表的存儲(chǔ)形式的簡(jiǎn)化CLOSEDOPEN加入擴(kuò)展節(jié)點(diǎn)加入擴(kuò)展節(jié)點(diǎn)狀態(tài)：狀態(tài)：11 1狀態(tài)：狀態(tài)：21 2狀態(tài)：狀態(tài)：31 3狀態(tài)：狀態(tài)： 41 4狀態(tài)：狀態(tài)： 52 2狀態(tài)：狀態(tài)： 62 3狀態(tài)：狀態(tài)： 73 1狀態(tài)：狀態(tài)： 83 4狀

20、態(tài)：狀態(tài)： 94 1狀態(tài)：狀態(tài)：104 4狀態(tài)：狀態(tài)： 115 2狀態(tài)：狀態(tài)： 125 3狀態(tài)：狀態(tài)： 136 4狀態(tài)：狀態(tài)： 1474狀態(tài)：狀態(tài)：1583狀態(tài)：狀態(tài)：1693狀態(tài)：狀態(tài)：1710 3狀態(tài)：狀態(tài)：1811 2狀態(tài)：狀態(tài)：1912 1狀態(tài)：狀態(tài)：2013 1狀態(tài)：狀態(tài)：2114 4狀態(tài)：狀態(tài)：2214 3狀態(tài)：狀態(tài)：2315 2狀態(tài)：狀態(tài)：2415 4狀態(tài)：狀態(tài)：2516 3狀態(tài)：狀態(tài)：2616 4狀態(tài)：狀態(tài)：27C123456789101112131415161718192021222324252627C4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)(1,4)(

21、3,4)WE(3,2)(3,1)ES(3,3)(4,4)ES目標(biāo)目標(biāo)節(jié)點(diǎn)節(jié)點(diǎn)X例：例：迷宮問(wèn)題迷宮問(wèn)題例：四皇后問(wèn)題例：四皇后問(wèn)題QQQQQQQQQQQQQQQQQQQXQQQQQQQQQXQQQQX深度廣度時(shí)間內(nèi)存需求211000.11秒1M字節(jié)4111，10011秒106M字節(jié)610719分鐘10G字節(jié) 810931小時(shí)1T字節(jié)101011129天101T字節(jié)12101535年10P字節(jié)假設(shè)，每個(gè)節(jié)點(diǎn)的分支數(shù)為假設(shè)，每個(gè)節(jié)點(diǎn)的分支數(shù)為1010；1000010000節(jié)點(diǎn)節(jié)點(diǎn)/ /秒；秒；10001000字節(jié)字節(jié)/ /節(jié)點(diǎn)節(jié)點(diǎn)大家聽(tīng)懂了大家聽(tīng)懂了“寬度優(yōu)先算法寬度優(yōu)先算法” ？基本聽(tīng)懂（基本聽(tīng)

22、懂（85以上）以上）大概聽(tīng)懂（大概聽(tīng)懂（70以上）以上）似懂非懂（似懂非懂（50左右）左右）沒(méi)有聽(tīng)懂（沒(méi)有聽(tīng)懂（25以下）以下）課堂作業(yè)課堂作業(yè)（寫(xiě)上學(xué)號(hào)與姓名）寫(xiě)上學(xué)號(hào)與姓名）根據(jù)下列迷宮，用根據(jù)下列迷宮，用寬度優(yōu)先搜索算法寬度優(yōu)先搜索算法尋找出從入尋找出從入口到出口的一條路徑口到出口的一條路徑狀態(tài)狀態(tài)：用極坐標(biāo)表示的人的：用極坐標(biāo)表示的人的位置位置操作符操作符：人向左方、前方、：人向左方、前方、右方前進(jìn)右方前進(jìn)提示提示：不要產(chǎn)生已有的狀態(tài)：不要產(chǎn)生已有的狀態(tài)3.2.2 深度優(yōu)先搜索深度優(yōu)先搜索 深度優(yōu)先搜索策略深度優(yōu)先搜索策略是先擴(kuò)展最新產(chǎn)生的是先擴(kuò)展最新產(chǎn)生的(即最深的即最深的)節(jié)點(diǎn)節(jié)點(diǎn)

23、 節(jié)點(diǎn)的深度；節(jié)點(diǎn)的深度；、起始節(jié)點(diǎn)起始節(jié)點(diǎn)(即根即根節(jié)點(diǎn)節(jié)點(diǎn))的深度為的深度為0。、任何其它節(jié)點(diǎn)的、任何其它節(jié)點(diǎn)的深度等于其父輩深度等于其父輩節(jié)點(diǎn)深度加上節(jié)點(diǎn)深度加上1。 深度優(yōu)先搜索的基本深度優(yōu)先搜索的基本思路思路：先擴(kuò)展最深的節(jié)點(diǎn)。先擴(kuò)展最深的節(jié)點(diǎn)。當(dāng)出現(xiàn)沒(méi)有后繼節(jié)點(diǎn)當(dāng)出現(xiàn)沒(méi)有后繼節(jié)點(diǎn)時(shí)，換到旁邊的次深時(shí)，換到旁邊的次深節(jié)點(diǎn)節(jié)點(diǎn)后生成的節(jié)點(diǎn)畫(huà)在左邊后生成的節(jié)點(diǎn)畫(huà)在左邊深度界限的設(shè)置：深度界限的設(shè)置：q 為了避免出現(xiàn)過(guò)深的路徑，搜索過(guò)程要設(shè)為了避免出現(xiàn)過(guò)深的路徑，搜索過(guò)程要設(shè)置一個(gè)深度界限置一個(gè)深度界限q 對(duì)于等于深度界限的任何節(jié)點(diǎn)，當(dāng)作沒(méi)有對(duì)于等于深度界限的任何節(jié)點(diǎn)，當(dāng)作沒(méi)有后繼節(jié)點(diǎn)的節(jié)

24、點(diǎn)來(lái)看待后繼節(jié)點(diǎn)的節(jié)點(diǎn)來(lái)看待缺點(diǎn)缺點(diǎn)：可能丟失解：可能丟失解 把起始節(jié)點(diǎn)把起始節(jié)點(diǎn) S 放到未擴(kuò)展節(jié)點(diǎn)的放到未擴(kuò)展節(jié)點(diǎn)的 OPEN 表中。表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解 如果如果 OPEN 為一空表，則無(wú)解、失敗退出為一空表，則無(wú)解、失敗退出含有深度界限的深度優(yōu)先搜索算法含有深度界限的深度優(yōu)先搜索算法： 把第一個(gè)節(jié)點(diǎn)把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)記作節(jié)點(diǎn) n )從從 OPEN 表移到表移到 CLOSED 表表 如果節(jié)點(diǎn)如果節(jié)點(diǎn) n 的深度等于最大深度，則轉(zhuǎn)向的深度等于最大深度，則轉(zhuǎn)向 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn) n ，產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它們

25、放入們放入 OPEN 表的表的前頭前頭。如果沒(méi)有后繼節(jié)。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向點(diǎn)，則轉(zhuǎn)向 如果后繼節(jié)點(diǎn)中有任一個(gè)節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，如果后繼節(jié)點(diǎn)中有任一個(gè)節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解（則求得一個(gè)解（反向追蹤從目標(biāo)節(jié)點(diǎn)到起始反向追蹤從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑節(jié)點(diǎn)的路徑），成功退出；否則，轉(zhuǎn)向），成功退出；否則，轉(zhuǎn)向說(shuō)明說(shuō)明：現(xiàn)在的現(xiàn)在的OPEN表是一個(gè)堆棧，后進(jìn)先出表是一個(gè)堆棧，后進(jìn)先出例：例：八數(shù)碼問(wèn)題八數(shù)碼問(wèn)題深度界限為深度界限為5后生成的節(jié)點(diǎn)畫(huà)在左邊后生成的節(jié)點(diǎn)畫(huà)在左邊深度界限為深度界限為4后生成的節(jié)點(diǎn)畫(huà)在左邊后生成的節(jié)點(diǎn)畫(huà)在左邊說(shuō)明說(shuō)明： 狀態(tài)旁邊的數(shù)字表示該節(jié)點(diǎn)生成后繼節(jié)點(diǎn)的狀態(tài)旁邊的數(shù)

26、字表示該節(jié)點(diǎn)生成后繼節(jié)點(diǎn)的順序，即順序，即CLOSED節(jié)點(diǎn)的存放順序，不是本節(jié)點(diǎn)的存放順序，不是本身被生成的順序身被生成的順序 解是圖中的虛線解是圖中的虛線 擴(kuò)展過(guò)程中沒(méi)有生成已有的節(jié)點(diǎn)擴(kuò)展過(guò)程中沒(méi)有生成已有的節(jié)點(diǎn)4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)E(3,2)(3,1)S例：例：迷宮問(wèn)題迷宮問(wèn)題(3,3)(3,4)(4,4)目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)ENE 后生成的節(jié)點(diǎn)后生成的節(jié)點(diǎn)在左邊在左邊 沒(méi)有已有節(jié)點(diǎn)沒(méi)有已有節(jié)點(diǎn)寬度優(yōu)先（先在左）寬度優(yōu)先（先在左）深度優(yōu)先深度優(yōu)先（后在左）（后在左）4321例：四皇后問(wèn)題例：四皇后問(wèn)題QQQQQQQQQQXQQQQQQXQQQQ后在左后

27、在左課堂作業(yè)課堂作業(yè)根據(jù)下列迷宮，用根據(jù)下列迷宮，用深度優(yōu)先搜索算法深度優(yōu)先搜索算法尋找出從入尋找出從入口到出口的一條路徑口到出口的一條路徑狀態(tài)狀態(tài)：用極坐標(biāo)表示的人的：用極坐標(biāo)表示的人的位置位置操作符操作符：人向左方、前方、：人向左方、前方、右方前進(jìn)右方前進(jìn)提示提示：不要產(chǎn)生已有的狀態(tài)：不要產(chǎn)生已有的狀態(tài)思考題思考題：（兩人一組來(lái)完成）：（兩人一組來(lái)完成）利用寬度優(yōu)先和深度優(yōu)先算法解決八數(shù)碼問(wèn)題？利用寬度優(yōu)先和深度優(yōu)先算法解決八數(shù)碼問(wèn)題？（要求用（要求用C/C+語(yǔ)言編寫(xiě)出核心代碼，考核的指語(yǔ)言編寫(xiě)出核心代碼，考核的指標(biāo)分成零、一、二、五、多步）標(biāo)分成零、一、二、五、多步）3.2.3 等代價(jià)搜

28、索等代價(jià)搜索 寬度優(yōu)先搜索技術(shù)找到了應(yīng)用算符數(shù)目最少寬度優(yōu)先搜索技術(shù)找到了應(yīng)用算符數(shù)目最少或者深度最淺的解或者深度最淺的解 如果認(rèn)為每一個(gè)操作符的代價(jià)相等，則寬度如果認(rèn)為每一個(gè)操作符的代價(jià)相等，則寬度優(yōu)先搜索技術(shù)就可以找到了代價(jià)最小的路徑優(yōu)先搜索技術(shù)就可以找到了代價(jià)最小的路徑或解或解所有操作符代所有操作符代價(jià)相等價(jià)相等找到最短的路找到最短的路徑徑寬度優(yōu)先算法寬度優(yōu)先算法操作符的代操作符的代價(jià)不相等價(jià)不相等找到代價(jià)最找到代價(jià)最小的路徑小的路徑等代價(jià)等代價(jià)( (代價(jià)代價(jià)優(yōu)先優(yōu)先) )搜索技搜索技術(shù)術(shù)問(wèn)題問(wèn)題推廣推廣寬度優(yōu)先搜索寬度優(yōu)先搜索：按照先后順序取待擴(kuò)展節(jié)點(diǎn)：按照先后順序取待擴(kuò)展節(jié)點(diǎn)等代價(jià)搜

29、索等代價(jià)搜索：將初始節(jié)點(diǎn)到所有端節(jié)點(diǎn)（：將初始節(jié)點(diǎn)到所有端節(jié)點(diǎn)（OPEN中的節(jié)點(diǎn)中的節(jié)點(diǎn)）的局部路徑中代價(jià)最小的端節(jié)點(diǎn)作）的局部路徑中代價(jià)最小的端節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)為下一個(gè)要擴(kuò)展的節(jié)點(diǎn) 推廣的思路推廣的思路：寬度優(yōu)先寬度優(yōu)先搜索算法搜索算法等代價(jià)等代價(jià)搜索算法搜索算法注注：圓圈中的數(shù)字表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)：圓圈中的數(shù)字表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)點(diǎn)的代價(jià)符號(hào)符號(hào)c(i, j)：從節(jié)點(diǎn)從節(jié)點(diǎn) i 到它的直接后繼節(jié)點(diǎn)到它的直接后繼節(jié)點(diǎn) j 的連接弧的連接弧線上的代價(jià)線上的代價(jià)g(i) ：從起始節(jié)點(diǎn)從起始節(jié)點(diǎn) S 到某一節(jié)點(diǎn)到某一節(jié)點(diǎn) i 的路徑的代價(jià)的路徑的代價(jià)選取待擴(kuò)展節(jié)點(diǎn)的原則選取

30、待擴(kuò)展節(jié)點(diǎn)的原則： 以以 g(i) 的遞增順序排列的遞增順序排列OPEN表表 以以 g(i) 最小的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的最小的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)節(jié)點(diǎn) 將起始節(jié)點(diǎn)將起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)表放到未擴(kuò)展節(jié)點(diǎn)表OPEN中。如中。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解。果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解。否則令否則令g(S)0 如果如果OPEN是空表，則無(wú)解，失敗退出是空表，則無(wú)解，失敗退出等代價(jià)搜索算法等代價(jià)搜索算法： 從從OPEN表中選擇一個(gè)節(jié)點(diǎn)表中選擇一個(gè)節(jié)點(diǎn) i ，使其使其 g(i) 為最為最小。如果有幾個(gè)節(jié)點(diǎn)都小。如果有幾個(gè)節(jié)點(diǎn)都合格合格，則分兩種情況，則分兩種情況，如果有目

31、標(biāo)節(jié)點(diǎn)，則選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)如果有目標(biāo)節(jié)點(diǎn)，則選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn)點(diǎn) i ；否則，從中任選一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)否則，從中任選一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn) i 。把節(jié)點(diǎn)把節(jié)點(diǎn) i 從從OPEN表移至擴(kuò)展節(jié)點(diǎn)表表移至擴(kuò)展節(jié)點(diǎn)表CLOSED中中 如果節(jié)點(diǎn)如果節(jié)點(diǎn) i 為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則，為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則，繼續(xù)下一步繼續(xù)下一步 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn) i 。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第步步 對(duì)于節(jié)點(diǎn)對(duì)于節(jié)點(diǎn) i 的每個(gè)后繼節(jié)點(diǎn)的每個(gè)后繼節(jié)點(diǎn) j ，計(jì)算計(jì)算 g( j )g( i )+c( i ，j )并把所有后繼節(jié)點(diǎn)并把所有后繼節(jié)點(diǎn) j 放進(jìn)放進(jìn)OPEN表。提供回到節(jié)點(diǎn)表。提供