人工智能第3章確定性推理課件

人工智能ArtificialIntelligence(AI)人工智能1第3章確定性推理

3.1圖的搜索策略3.2盲目搜索3.3啟發(fā)式搜索3.4與或樹搜索（補(bǔ)充）3.5博弈樹搜索（補(bǔ)充）3.6消解原理第3章確定性推理3.1圖的搜索策略2解決實(shí)際問題的兩個(gè)關(guān)鍵之處：①問題的表達(dá)狀態(tài)空間法問題歸約法謂詞邏輯法②問題的求解搜索技術(shù)推理技術(shù)解決實(shí)際問題的兩個(gè)關(guān)鍵之處：①問題的表達(dá)②問題的求解3盲目與啟發(fā)式搜索：狀態(tài)空間法、圖的搜索技術(shù)與或樹搜索：?jiǎn)栴}歸約法、與或圖的特例的搜索技術(shù)博弈樹搜索：狀態(tài)空間法＋問題歸約法、雙人博弈的特殊搜索技術(shù)消解原理：謂詞邏輯法、推理技術(shù)盲目與啟發(fā)式搜索：狀態(tài)空間法、圖的搜索技術(shù)43.1圖搜索策略

狀態(tài)空間中：狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)操作符圖中有：節(jié)點(diǎn)初始節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)有向弧狀態(tài)空間法與圖的對(duì)應(yīng)關(guān)系3.1圖搜索策略狀態(tài)空間中：圖中有：狀態(tài)空間法與圖的對(duì)應(yīng)5在狀態(tài)空間中，解是從初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列在圖中，解是從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑解的含義：在狀態(tài)空間中，解是從初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列解的含義：6狀態(tài)：(城市名)算子：常德→益陽 益陽→常德 益陽汨羅 益陽寧鄉(xiāng) 益陽婁底

…？？？？必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑狀態(tài)：(城市名)？？？？必須記住哪些點(diǎn)走過了必須記住下一步還7必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑OPEN表(記錄還沒有擴(kuò)展的點(diǎn))CLOSED表(記錄已經(jīng)擴(kuò)展的點(diǎn))每個(gè)表示狀態(tài)的節(jié)點(diǎn)結(jié)構(gòu)中必須有指向父節(jié)點(diǎn)的指針必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目8圖的搜索策略：圖搜索過程的一般步驟（基本思路、框架），經(jīng)過細(xì)化后得到具體算法：盲目搜索技術(shù)（深度、寬度、代價(jià)優(yōu)先算法）啟發(fā)式搜索技術(shù)（有序算法、A*算法）圖的搜索策略：圖搜索過程的一般步驟（基本思路、框架），經(jīng)過細(xì)9圖搜索中的兩個(gè)重要記號(hào)（符號(hào)）：OPEN表：存放待擴(kuò)展的節(jié)點(diǎn)CLOSED表：存放已擴(kuò)展的節(jié)點(diǎn)注意：在與或樹搜索中也要用到這兩張表圖搜索中的兩個(gè)重要記號(hào)（符號(hào)）：10數(shù)據(jù)結(jié)構(gòu)中圖的遍及：從圖某一個(gè)節(jié)點(diǎn)出發(fā)，訪問遍圖中其余節(jié)點(diǎn)，且每一個(gè)節(jié)點(diǎn)僅僅被訪問一次。當(dāng)前圖的搜索技術(shù)中，有兩個(gè)特殊之處：搜索前，圖并沒有生成好，需要邊生成圖邊搜索搜索從起始節(jié)點(diǎn)（初始狀態(tài)）開始，到目標(biāo)節(jié)點(diǎn)（目標(biāo)狀態(tài)）結(jié)束，不需要搜索所有可能的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)中圖的遍及：從圖某一個(gè)節(jié)點(diǎn)出發(fā)，訪問遍圖中其余節(jié)點(diǎn)，11盲目搜索是指無問題先驗(yàn)信息的搜索技術(shù)特點(diǎn)：OPEN表中節(jié)點(diǎn)的排列是人為規(guī)定的一般只適合于求解比較簡(jiǎn)單的一些問題3.2盲目搜索盲目搜索是指無問題先驗(yàn)信息的搜索技術(shù)3.2盲目搜索12圖的盲目搜索技術(shù)分成：寬度優(yōu)先搜索技術(shù)深度優(yōu)先搜索技術(shù)等代價(jià)（代價(jià)優(yōu)先）搜索技術(shù)圖的盲目搜索技術(shù)分成：133.2.1寬度優(yōu)先搜索

寬度優(yōu)先搜索：以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的搜索技術(shù)（即：離起始節(jié)點(diǎn)近的節(jié)點(diǎn)先被擴(kuò)展）擴(kuò)展節(jié)點(diǎn)的原則：先擴(kuò)展出來的節(jié)點(diǎn)隨后優(yōu)先被擴(kuò)展（生成其所有的后繼節(jié)點(diǎn)）3.2.1寬度優(yōu)先搜索寬度優(yōu)先搜索：以接近起始節(jié)點(diǎn)的程14人工智能第3章確定性推理課件15①

把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解)②

如果OPEN是個(gè)空表，則無解，失敗退出；否則繼續(xù)下一步寬度優(yōu)先搜索算法：①把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)16③

把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN

表移出，并把它放入

CLOSED的已擴(kuò)展節(jié)點(diǎn)表中④

擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第②步③把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN表移出，并17⑤

把n

的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n

的指針⑥

如果n

的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解（反向追蹤得到從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑），成功退出，否則轉(zhuǎn)向第②步⑤把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些18OPEN表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來說，它是一個(gè)先進(jìn)先出的隊(duì)列CLOSED表是存放已被擴(kuò)展過的節(jié)點(diǎn)（包括有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無后繼節(jié)點(diǎn)的端節(jié)點(diǎn)）說明：OPEN表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來說，它是一個(gè)先19流程圖

流程圖20①搜索過程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的狀態(tài)空間樹的子樹，稱之為搜索樹注意幾點(diǎn)：①搜索過程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的狀態(tài)空間樹的子樹21②

寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑（所用操作符最少）②寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的22例：八數(shù)碼問題初始狀態(tài)目標(biāo)狀態(tài)操作符：2831476512384765空1243例：八數(shù)碼問題初始狀態(tài)目標(biāo)狀態(tài)操作符：2831476512323狀態(tài)：長(zhǎng)度為9的一維數(shù)組（q1,q2,…,q9）其中，qi

取0,1,…,8個(gè)數(shù)，0表示空格，且取值互不相同狀態(tài)：長(zhǎng)度為9的一維數(shù)組24

如果記空格的位置為P，這時(shí)空格的移動(dòng)規(guī)則是：123456789123456789PP-3P+1P+3P-1數(shù)字表示位置如果記空格的位置為P，這時(shí)空格的移動(dòng)規(guī)則是：25

順序規(guī)則前提條件應(yīng)用結(jié)果1左移P≠1,4,7P位置與P-1

位置上的元素互換2上移P≠1,2,3

P-33下移P≠7,8,9

P+34右移P≠3,6,9

P+1空格移動(dòng)規(guī)則P-3PP+3P-1P+1123456789順序規(guī)則前提條件應(yīng)用結(jié)果1左移P≠1,4,726為了記錄后繼節(jié)點(diǎn)與父節(jié)點(diǎn)之間的指針，我們將長(zhǎng)度為9的數(shù)組擴(kuò)大到長(zhǎng)度為11的數(shù)組，其中一個(gè)元素記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志，另一個(gè)元素記錄操作符的序號(hào)操作符父節(jié)點(diǎn)狀態(tài)為了記錄后繼節(jié)點(diǎn)與父節(jié)點(diǎn)之間的指針，我們將長(zhǎng)度為9的數(shù)組27OPEN表的存儲(chǔ)形式：隊(duì)列插入端（隊(duì)尾）刪除端（隊(duì)頭）隊(duì)列：一種先進(jìn)先出的線性表，允許在表的一端進(jìn)行插入、另一端進(jìn)行刪除OPEN表的存儲(chǔ)形式：隊(duì)列插入端（隊(duì)尾）刪除端（隊(duì)頭）隊(duì)列：28CLOSED表的存儲(chǔ)形式：也可以用隊(duì)列父符插入端（隊(duì)尾）特殊的隊(duì)列：只進(jìn)不出的隊(duì)列，只允許在表的一端進(jìn)行插入CLOSED表的存儲(chǔ)形式：也可以用隊(duì)列父符插入端（隊(duì)尾）特殊29某一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志：記錄CLOSED表中的父節(jié)點(diǎn)的序號(hào)起始節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志和操作符：不作記錄或記錄為負(fù)某一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志：30搜索過程（按照程序運(yùn)行方式）①

起始節(jié)點(diǎn)放到OPEN表283104765②

OPEN不為空，繼續(xù)28314765搜索過程（按照程序運(yùn)行方式）①起始節(jié)點(diǎn)放到OPEN表231③

將第一個(gè)節(jié)點(diǎn)n

從OPEN

表中移出，并放到CLOSED表中00283104765OPEN表CLOSED表節(jié)點(diǎn)n1③將第一個(gè)節(jié)點(diǎn)n從OPEN表中移出，并放到CLO32④

擴(kuò)展節(jié)點(diǎn)n

283014765

203184765

283164705

28314076500283104765擴(kuò)展28314765④擴(kuò)展節(jié)點(diǎn)n28301476520318476533⑤將節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放到OPEN

表的末端，并提供這些后繼節(jié)點(diǎn)回到n

的指針11283014765122031847651328316470514283140765OPEN表符父00283104765CLOSED⑤將節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并34⑥

后繼節(jié)點(diǎn)中無目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)到②②

OPEN表不為空，繼續(xù)⑥后繼節(jié)點(diǎn)中無目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)到②②OPEN表不為空，繼35③

將第一個(gè)節(jié)點(diǎn)n

從OPEN

表中移出，并放到CLOSED表中OPEN表CLOSED表1220318476513283164705142831407650028310476511283014765節(jié)點(diǎn)n12③將第一個(gè)節(jié)點(diǎn)n從OPEN表中移出，并放到CLO36④

擴(kuò)展節(jié)點(diǎn)n

083214765

2837140651128301476528314765④擴(kuò)展節(jié)點(diǎn)n0832147652837140637⑤將節(jié)點(diǎn)n

的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供這些后繼節(jié)點(diǎn)回到n的指針122031847651328316470514283140765OPEN表2208321476523283714065⑤將節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并38….一直繼續(xù)下去，而且不產(chǎn)生已經(jīng)產(chǎn)生過的節(jié)點(diǎn)（狀態(tài)），防止死循環(huán)。在程序中每一個(gè)新產(chǎn)生的節(jié)點(diǎn)必須與OPEN和CLOSED表中狀態(tài)進(jìn)行比較，判斷是否已經(jīng)產(chǎn)生過，只保留從未產(chǎn)生過的節(jié)點(diǎn)….39最后的OPEN表：93234180765103283064175112283160754121208143765131283145706144830214765143813204765152283704615154283714650163123784065164123804765目標(biāo)節(jié)點(diǎn)12384765最后的OPEN表：93234180765103283064140最后的CLOSED表：2831047651128301476512203184765132831647051428314076522083214765232837140653102318476534230184765123456789最后的CLOSED表：2831047651128301476414128316407544283164750522801437505328314576064803214765742837146058312308476510111213141516164123804765目標(biāo)節(jié)點(diǎn)4128316407544283164750522801434283123084765164123804765目標(biāo)節(jié)點(diǎn)31023184765168122031847652831047653183123084765164123804765目標(biāo)節(jié)點(diǎn)310432831476528314765231847652831647528314765214383214765283714652318476523184765281437652831647528316475283145768321476528371465123847652341876528364175283167542814376528314576832147658132476512378465123847652837461528371465先生成的節(jié)點(diǎn)在左目標(biāo)節(jié)點(diǎn)28314765283147652318476528316444（先擴(kuò)展的節(jié)點(diǎn)畫在左邊）生成后繼節(jié)點(diǎn)的順序（先擴(kuò)展的節(jié)點(diǎn)畫在左邊）生成后繼節(jié)點(diǎn)的順序45OPEN與CLOSED表的存儲(chǔ)形式的簡(jiǎn)化CLOSEDOPEN加入擴(kuò)展節(jié)點(diǎn)OPEN與CLOSED表的存儲(chǔ)形式的簡(jiǎn)化CLOSEDOPEN46狀態(tài)：111狀態(tài)：212狀態(tài)：313狀態(tài)：414狀態(tài)：522狀態(tài)：623狀態(tài)：731狀態(tài)：834狀態(tài)：941狀態(tài)：1044狀態(tài)：1152狀態(tài)：1253狀態(tài)：1364狀態(tài)：1474狀態(tài)：1583狀態(tài)：1693狀態(tài)：17103狀態(tài)：18112狀態(tài)：19121狀態(tài)：20131狀態(tài)：21144狀態(tài)：22143狀態(tài)：23152狀態(tài)：24154狀態(tài)：25163狀態(tài)：26164狀態(tài)：27CO123456789101112131415161718192021222324252627CO狀態(tài)：111狀態(tài)：212狀態(tài)：313狀態(tài)：414狀態(tài)：547人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)(1,4)(3,4)WE(3,2)(3,1)ES(3,3)(4,4)ES目標(biāo)節(jié)點(diǎn)X例：迷宮問題人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,48例：四皇后問題QQQQQQQQQQQQQQQQQQQXQQQQQQQQQXQQQQX例：四皇后問題QQQQQQQQQQQQQQQQQQQXQQQ49練習(xí)：根據(jù)下列迷宮，用寬度優(yōu)先搜索算法尋找出從入口到出口的一條路徑狀態(tài)：用極坐標(biāo)表示的人的位置操作符：人向左方、前方、右方前進(jìn)提示：不要產(chǎn)生已有的狀態(tài)練習(xí)：根據(jù)下列迷宮，用寬度優(yōu)先搜索算法尋找出從入口到出口的一50存在的問題：走步方向不符合人走路的習(xí)慣沒有標(biāo)注走步的方向中間改變走步方向的順序多畫搜索樹，有解后還再往下擴(kuò)展存在的問題：51(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)(2,0)前右左(2,45)前(4,90)(0,0)前右(2,90)右(6,90)出口寬度優(yōu)先搜索算法（沒有生成已有的狀態(tài)）先在左XX(6,0)人向左向右向前2(4,0)前右(6,45)(4,452(6,0)向左1(4,0)前右(4,45)(2,0)前前(2,45)右(4,90)(0,0)前右(6,90)出口寬度優(yōu)先搜索算法先在左X人向右3向前2(6,0)向左(4,0)前右(4,45)(2,0)前前(2,533.2.2深度優(yōu)先搜索

深度優(yōu)先搜索策略是先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)

3.2.2深度優(yōu)先搜索深度優(yōu)先搜索策略是先擴(kuò)展最新產(chǎn)生54節(jié)點(diǎn)的深度；①、起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。②、任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1。

節(jié)點(diǎn)的深度；55深度優(yōu)先搜索的基本思路：先擴(kuò)展最深的節(jié)點(diǎn)。當(dāng)出現(xiàn)沒有后繼節(jié)點(diǎn)時(shí)，換到旁邊的次深節(jié)點(diǎn)后生成的節(jié)點(diǎn)畫在左邊深度優(yōu)先搜索的基本思路：后生成的節(jié)點(diǎn)畫在左邊56①

把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)的OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解②

如果OPEN

為一空表，則無解、失敗退出含有深度界限的深度優(yōu)先搜索算法：①把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)的OPEN表中。如果此57深度界限的設(shè)置：為了避免出現(xiàn)過深的路徑，搜索過程要設(shè)置一個(gè)深度界限對(duì)于等于深度界限的任何節(jié)點(diǎn)，當(dāng)作沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)來看待缺點(diǎn)：可能丟失解深度界限的設(shè)置：58③把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN

表移到CLOSED

表④

如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向②③把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN表移到CL59⑤

擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它們放入OPEN

表的前頭。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向②⑥

如果后繼節(jié)點(diǎn)中有任一個(gè)節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解（反向追蹤從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑），成功退出；否則，轉(zhuǎn)向②⑤擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它們放入OPE60人工智能第3章確定性推理課件61人工智能第3章確定性推理課件62說明：現(xiàn)在的OPEN表是一個(gè)堆棧，后進(jìn)先出說明：63深度界限為4后生成的節(jié)點(diǎn)畫在左邊深度界限為4后生成的節(jié)點(diǎn)畫在左邊6428314765283147652318476528316475283147652143283164752831647528316754后生成的節(jié)點(diǎn)在左283167542816375428364175832641752836417528143765283145762831457628314576283157462814376528143765248137652318476523184765234187652341876523418576123847651238476512378465目標(biāo)節(jié)點(diǎn)28314765283147652318476528316465例：八數(shù)碼問題深度界限為5后生成的節(jié)點(diǎn)畫在左邊例：八數(shù)碼問題深度界限為5后生成的節(jié)點(diǎn)畫在左邊66說明：狀態(tài)旁邊的數(shù)字表示該節(jié)點(diǎn)生成后繼節(jié)點(diǎn)的順序，即CLOSED節(jié)點(diǎn)的存放順序，不是本身被生成的順序解是圖中的虛線擴(kuò)展過程中沒有生成已有的節(jié)點(diǎn)說明：67人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)E(3,2)(3,1)S例：迷宮問題(3,3)(3,4)(4,4)目標(biāo)節(jié)點(diǎn)ENE后生成的節(jié)點(diǎn)在左邊沒有已有節(jié)點(diǎn)人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,68寬度優(yōu)先（先在左）深度優(yōu)先（后在左）人4321寬度優(yōu)先（先在左）深度優(yōu)先人432169例：四皇后問題QQQQQQQQQQXQQQQQQXQQQQ后在左例：四皇后問題QQQQQQQQQQXQQQQQQXQQQQ后70練習(xí)：根據(jù)下列迷宮，用深度優(yōu)先搜索算法尋找出從入口到出口的一條路徑狀態(tài)：用極坐標(biāo)表示的人的位置操作符：人向左方、前方、右方前進(jìn)提示：不要產(chǎn)生已有的狀態(tài)練習(xí)：根據(jù)下列迷宮，用深度優(yōu)先搜索算法尋找出從入口到出口的一71深度優(yōu)先算法存在問題：先后順序有誤，規(guī)定的先后順序：左前右改變坐標(biāo)系，極坐標(biāo)直角坐標(biāo)對(duì)于一個(gè)節(jié)點(diǎn)，按照規(guī)定的操作符順序，使用所有可能的操作符，產(chǎn)生相應(yīng)的后繼節(jié)點(diǎn)深度優(yōu)先算法存在問題：72(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)前前(2,45)右(4,90)左(2,90)右(6,90)出口深度優(yōu)先搜索算法（沒有產(chǎn)生已有的節(jié)點(diǎn)）后在左(6,0)人向左向右向前2(4,0)前右(6,45)(4,473思考題：利用寬度優(yōu)先與深度優(yōu)先算法解決八數(shù)碼問題？思考題：743.2.3等代價(jià)搜索寬度優(yōu)先搜索技術(shù)找到了應(yīng)用算符數(shù)目最少或者深度最淺的解如果認(rèn)為每一個(gè)操作符的代價(jià)相等，則寬度優(yōu)先搜索技術(shù)就可以找到了代價(jià)最小的路徑或解3.2.3等代價(jià)搜索寬度優(yōu)先搜索技術(shù)找到了應(yīng)用算符數(shù)目最75所有操作符代價(jià)相等找到最短的路徑寬度優(yōu)先算法操作符的代價(jià)不相等找到代價(jià)最小的路徑等代價(jià)(代價(jià)優(yōu)先)搜索技術(shù)問題推廣推廣所有操作符代價(jià)相等操作符的代價(jià)不相等問題推廣推廣76寬度優(yōu)先搜索：按照先后順序取待擴(kuò)展節(jié)點(diǎn)等代價(jià)搜索：將初始節(jié)點(diǎn)到所有端節(jié)點(diǎn)（OPEN中的節(jié)點(diǎn)）的局部路徑中代價(jià)最小的端節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)

推廣的思路：寬度優(yōu)先搜索：按照先后順序取待擴(kuò)展節(jié)點(diǎn)推廣的思路：77寬度優(yōu)先搜索算法等代價(jià)搜索算法注：圓圈中的數(shù)字表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價(jià)寬度優(yōu)先搜索算法等代價(jià)搜索算法注：圓圈中的數(shù)字表示從起始節(jié)點(diǎn)78符號(hào)c(i,j)：從節(jié)點(diǎn)i

到它的直接后繼節(jié)點(diǎn)j

的連接弧線上的代價(jià)g(i)：從起始節(jié)點(diǎn)S

到某一節(jié)點(diǎn)i

的路徑的代價(jià)符號(hào)79選取待擴(kuò)展節(jié)點(diǎn)的原則：以g(i)

的遞增順序排列OPEN表以g(i)

最小的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)選取待擴(kuò)展節(jié)點(diǎn)的原則：80①

將起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)表OPEN中。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解。否則令g(S)＝0②如果OPEN是空表，則無解，失敗退出等代價(jià)搜索算法：①將起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)表OPEN中。如果此起始節(jié)點(diǎn)為81③

從OPEN表中選擇一個(gè)節(jié)點(diǎn)i

，使其g(i)

為最小。如果有幾個(gè)節(jié)點(diǎn)都合格，則分兩種情況，如果有目標(biāo)節(jié)點(diǎn)，則選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn)i

；否則，從中任選一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i

。把節(jié)點(diǎn)i

從OPEN表移至擴(kuò)展節(jié)點(diǎn)表CLOSED中③從OPEN表中選擇一個(gè)節(jié)點(diǎn)i，使其g(i)為最小82④

如果節(jié)點(diǎn)i為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則，繼續(xù)下一步⑤

擴(kuò)展節(jié)點(diǎn)i。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第②步④如果節(jié)點(diǎn)i為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解；否則，繼續(xù)下一步83⑥

對(duì)于節(jié)點(diǎn)i

的每個(gè)后繼節(jié)點(diǎn)j

，計(jì)算

g(j)＝g(i)+c(i，j)并把所有后繼節(jié)點(diǎn)j

放進(jìn)OPEN表。提供回到節(jié)點(diǎn)i的指針⑦

轉(zhuǎn)向第②步⑥對(duì)于節(jié)點(diǎn)i的每個(gè)后繼節(jié)點(diǎn)j，計(jì)算84人工智能第3章確定性推理課件85說明幾點(diǎn)：第一、上述算法實(shí)際是樹的搜索算法。如果是圖的搜索，則要檢查新產(chǎn)生的后繼節(jié)點(diǎn)是否已經(jīng)在OPEN表或CLOSED表，若是，比較新、舊代價(jià)并調(diào)整指針（保留代價(jià)小的路徑）說明幾點(diǎn)：86第二、OPEN表是一張線性表，其元素按代價(jià)的遞增順序排列。表的基本操作：刪除、定位與插入第二、OPEN表是一張線性表，其元素按代價(jià)的遞增順序排列。表87例：迷宮人4321代價(jià)：關(guān)鍵位置點(diǎn)之間的水平與垂直距離之和例：迷宮人4321代價(jià)：關(guān)鍵位置點(diǎn)之間的水平與垂直距離之和88人4S3E2N1W(1,1)N3(2,3)3(2,4)4N1S1(2,2)4(1,4)5(3,4)5W1E1(3,2)5(3,1)6E1S2(3,3)6(4,4)6E1S1XX可以擴(kuò)展(3,1)6(3,3)6人4S3E2N1W(1,1)N3(2,3)3(2,4)489例：最小路程問題。下圖是五個(gè)城市的交通路線圖，圖中的數(shù)字是公里數(shù)。問題是找到一條從A到E的最短路線。

操作符:從一個(gè)城市走向另一個(gè)城市（方向大體上從A指向E）例：最小路程問題。下圖是五個(gè)城市的交通路線圖，圖中的數(shù)字是公90人工智能第3章確定性推理課件91人工智能第3章確定性推理課件92A(0)B(2)C(3)D(7)C(5)D(6)D(7)E(13)E(11)237344105CLOSEDA(0)B(2)C(3)D(7)C(5)D(6)D(7)E(93思考題對(duì)于下列迷宮，用等代價(jià)搜索算法尋找出從入口到出口的一條路徑代價(jià)：關(guān)鍵位置之間的路程，其中π=3.0思考題對(duì)于下列迷宮，用等代價(jià)搜索算法尋找出從入口到出口的一條94等代價(jià)算法存在的問題：如果當(dāng)前擴(kuò)展出來的節(jié)點(diǎn)，已經(jīng)存在，需要比較新舊代價(jià)，一般先畫出節(jié)點(diǎn)，再刪除代價(jià)大的節(jié)點(diǎn)。也可以不畫代價(jià)大的節(jié)點(diǎn)。但是不能有的地方畫，有點(diǎn)的地方不畫。等代價(jià)算法存在的問題：95(6,0)0人向左1向右3向前2(4,0)2前2右4.5(6,45)4.5(4,45)5(2,0)4前2右3左2(2,45)7前3(4,90)8(0,0)

9前2右1.5(2,90)8.5右2(6,90)10出口等代價(jià)搜索算法XX24.531.5前2(4,45)6.5左2(2,90)10XX(4,90)10.5前2X右2(6,45)7X(6,0)0人向左向右向前2(4,0)2前2右4.5(696說明：當(dāng)擴(kuò)展某一個(gè)節(jié)點(diǎn)生成全部后繼節(jié)點(diǎn)時(shí)出現(xiàn)搜索圖中已經(jīng)有的節(jié)點(diǎn)（在Open或者Closed表的節(jié)點(diǎn)），在等代價(jià)搜索中有兩種處理策略：只保留新產(chǎn)生的節(jié)點(diǎn)，已有的節(jié)點(diǎn)都不保留借助于有序算法中的處理策略（上述例子中的方法）說明：當(dāng)擴(kuò)展某一個(gè)節(jié)點(diǎn)生成全部后繼節(jié)點(diǎn)時(shí)出現(xiàn)搜索圖中已經(jīng)有的97三種盲目搜索技術(shù)的比較主要差別：在于挑選要擴(kuò)展節(jié)點(diǎn)的規(guī)則不同寬度優(yōu)先搜索技術(shù)：先擴(kuò)展出來的節(jié)點(diǎn)隨后先擴(kuò)展，OPEN表是隊(duì)列深度優(yōu)先搜索技術(shù)：后擴(kuò)展出來的節(jié)點(diǎn)隨后先擴(kuò)展，OPEN表是堆棧等代價(jià)搜索技術(shù)：選取OPEN表中代價(jià)最小的節(jié)點(diǎn)先擴(kuò)展，OPEN表是線性表（以局部代價(jià)的遞增順序排列）三種盲目搜索技術(shù)的比較98寬度優(yōu)先深度優(yōu)先代價(jià)優(yōu)先三種算法的比較（流程圖）寬度優(yōu)先深度優(yōu)先代價(jià)優(yōu)先三種算法的比較（流程圖）99人工智能ArtificialIntelligence(AI)人工智能100第3章確定性推理

3.1圖的搜索策略3.2盲目搜索3.3啟發(fā)式搜索3.4與或樹搜索（補(bǔ)充）3.5博弈樹搜索（補(bǔ)充）3.6消解原理第3章確定性推理3.1圖的搜索策略101解決實(shí)際問題的兩個(gè)關(guān)鍵之處：①問題的表達(dá)狀態(tài)空間法問題歸約法謂詞邏輯法②問題的求解搜索技術(shù)推理技術(shù)解決實(shí)際問題的兩個(gè)關(guān)鍵之處：①問題的表達(dá)②問題的求解102盲目與啟發(fā)式搜索：狀態(tài)空間法、圖的搜索技術(shù)與或樹搜索：?jiǎn)栴}歸約法、與或圖的特例的搜索技術(shù)博弈樹搜索：狀態(tài)空間法＋問題歸約法、雙人博弈的特殊搜索技術(shù)消解原理：謂詞邏輯法、推理技術(shù)盲目與啟發(fā)式搜索：狀態(tài)空間法、圖的搜索技術(shù)1033.1圖搜索策略

狀態(tài)空間中：狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)操作符圖中有：節(jié)點(diǎn)初始節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)有向弧狀態(tài)空間法與圖的對(duì)應(yīng)關(guān)系3.1圖搜索策略狀態(tài)空間中：圖中有：狀態(tài)空間法與圖的對(duì)應(yīng)104在狀態(tài)空間中，解是從初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列在圖中，解是從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑解的含義：在狀態(tài)空間中，解是從初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列解的含義：105狀態(tài)：(城市名)算子：常德→益陽 益陽→常德 益陽汨羅 益陽寧鄉(xiāng) 益陽婁底

…？？？？必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑狀態(tài)：(城市名)？？？？必須記住哪些點(diǎn)走過了必須記住下一步還106必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目標(biāo)返回的路徑OPEN表(記錄還沒有擴(kuò)展的點(diǎn))CLOSED表(記錄已經(jīng)擴(kuò)展的點(diǎn))每個(gè)表示狀態(tài)的節(jié)點(diǎn)結(jié)構(gòu)中必須有指向父節(jié)點(diǎn)的指針必須記住哪些點(diǎn)走過了必須記住下一步還可以走哪些點(diǎn)必須記住從目107圖的搜索策略：圖搜索過程的一般步驟（基本思路、框架），經(jīng)過細(xì)化后得到具體算法：盲目搜索技術(shù)（深度、寬度、代價(jià)優(yōu)先算法）啟發(fā)式搜索技術(shù)（有序算法、A*算法）圖的搜索策略：圖搜索過程的一般步驟（基本思路、框架），經(jīng)過細(xì)108圖搜索中的兩個(gè)重要記號(hào)（符號(hào)）：OPEN表：存放待擴(kuò)展的節(jié)點(diǎn)CLOSED表：存放已擴(kuò)展的節(jié)點(diǎn)注意：在與或樹搜索中也要用到這兩張表圖搜索中的兩個(gè)重要記號(hào)（符號(hào)）：109數(shù)據(jù)結(jié)構(gòu)中圖的遍及：從圖某一個(gè)節(jié)點(diǎn)出發(fā)，訪問遍圖中其余節(jié)點(diǎn)，且每一個(gè)節(jié)點(diǎn)僅僅被訪問一次。當(dāng)前圖的搜索技術(shù)中，有兩個(gè)特殊之處：搜索前，圖并沒有生成好，需要邊生成圖邊搜索搜索從起始節(jié)點(diǎn)（初始狀態(tài)）開始，到目標(biāo)節(jié)點(diǎn)（目標(biāo)狀態(tài)）結(jié)束，不需要搜索所有可能的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)中圖的遍及：從圖某一個(gè)節(jié)點(diǎn)出發(fā)，訪問遍圖中其余節(jié)點(diǎn)，110盲目搜索是指無問題先驗(yàn)信息的搜索技術(shù)特點(diǎn)：OPEN表中節(jié)點(diǎn)的排列是人為規(guī)定的一般只適合于求解比較簡(jiǎn)單的一些問題3.2盲目搜索盲目搜索是指無問題先驗(yàn)信息的搜索技術(shù)3.2盲目搜索111圖的盲目搜索技術(shù)分成：寬度優(yōu)先搜索技術(shù)深度優(yōu)先搜索技術(shù)等代價(jià)（代價(jià)優(yōu)先）搜索技術(shù)圖的盲目搜索技術(shù)分成：1123.2.1寬度優(yōu)先搜索

寬度優(yōu)先搜索：以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的搜索技術(shù)（即：離起始節(jié)點(diǎn)近的節(jié)點(diǎn)先被擴(kuò)展）擴(kuò)展節(jié)點(diǎn)的原則：先擴(kuò)展出來的節(jié)點(diǎn)隨后優(yōu)先被擴(kuò)展（生成其所有的后繼節(jié)點(diǎn)）3.2.1寬度優(yōu)先搜索寬度優(yōu)先搜索：以接近起始節(jié)點(diǎn)的程113人工智能第3章確定性推理課件114①

把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解)②

如果OPEN是個(gè)空表，則無解，失敗退出；否則繼續(xù)下一步寬度優(yōu)先搜索算法：①把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)115③

把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN

表移出，并把它放入

CLOSED的已擴(kuò)展節(jié)點(diǎn)表中④

擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第②步③把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN表移出，并116⑤

把n

的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n

的指針⑥

如果n

的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解（反向追蹤得到從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑），成功退出，否則轉(zhuǎn)向第②步⑤把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些117OPEN表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來說，它是一個(gè)先進(jìn)先出的隊(duì)列CLOSED表是存放已被擴(kuò)展過的節(jié)點(diǎn)（包括有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無后繼節(jié)點(diǎn)的端節(jié)點(diǎn)）說明：OPEN表是存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來說，它是一個(gè)先118流程圖

流程圖119①搜索過程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的狀態(tài)空間樹的子樹，稱之為搜索樹注意幾點(diǎn)：①搜索過程產(chǎn)生的節(jié)點(diǎn)和指針構(gòu)成一棵隱式定義的狀態(tài)空間樹的子樹120②

寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑（所用操作符最少）②寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的121例：八數(shù)碼問題初始狀態(tài)目標(biāo)狀態(tài)操作符：2831476512384765空1243例：八數(shù)碼問題初始狀態(tài)目標(biāo)狀態(tài)操作符：28314765123122狀態(tài)：長(zhǎng)度為9的一維數(shù)組（q1,q2,…,q9）其中，qi

取0,1,…,8個(gè)數(shù)，0表示空格，且取值互不相同狀態(tài)：長(zhǎng)度為9的一維數(shù)組123

如果記空格的位置為P，這時(shí)空格的移動(dòng)規(guī)則是：123456789123456789PP-3P+1P+3P-1數(shù)字表示位置如果記空格的位置為P，這時(shí)空格的移動(dòng)規(guī)則是：124

順序規(guī)則前提條件應(yīng)用結(jié)果1左移P≠1,4,7P位置與P-1

位置上的元素互換2上移P≠1,2,3

P-33下移P≠7,8,9

P+34右移P≠3,6,9

P+1空格移動(dòng)規(guī)則P-3PP+3P-1P+1123456789順序規(guī)則前提條件應(yīng)用結(jié)果1左移P≠1,4,7125為了記錄后繼節(jié)點(diǎn)與父節(jié)點(diǎn)之間的指針，我們將長(zhǎng)度為9的數(shù)組擴(kuò)大到長(zhǎng)度為11的數(shù)組，其中一個(gè)元素記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志，另一個(gè)元素記錄操作符的序號(hào)操作符父節(jié)點(diǎn)狀態(tài)為了記錄后繼節(jié)點(diǎn)與父節(jié)點(diǎn)之間的指針，我們將長(zhǎng)度為9的數(shù)組126OPEN表的存儲(chǔ)形式：隊(duì)列插入端（隊(duì)尾）刪除端（隊(duì)頭）隊(duì)列：一種先進(jìn)先出的線性表，允許在表的一端進(jìn)行插入、另一端進(jìn)行刪除OPEN表的存儲(chǔ)形式：隊(duì)列插入端（隊(duì)尾）刪除端（隊(duì)頭）隊(duì)列：127CLOSED表的存儲(chǔ)形式：也可以用隊(duì)列父符插入端（隊(duì)尾）特殊的隊(duì)列：只進(jìn)不出的隊(duì)列，只允許在表的一端進(jìn)行插入CLOSED表的存儲(chǔ)形式：也可以用隊(duì)列父符插入端（隊(duì)尾）特殊128某一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志：記錄CLOSED表中的父節(jié)點(diǎn)的序號(hào)起始節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志和操作符：不作記錄或記錄為負(fù)某一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)志：129搜索過程（按照程序運(yùn)行方式）①

起始節(jié)點(diǎn)放到OPEN表283104765②

OPEN不為空，繼續(xù)28314765搜索過程（按照程序運(yùn)行方式）①起始節(jié)點(diǎn)放到OPEN表2130③

將第一個(gè)節(jié)點(diǎn)n

從OPEN

表中移出，并放到CLOSED表中00283104765OPEN表CLOSED表節(jié)點(diǎn)n1③將第一個(gè)節(jié)點(diǎn)n從OPEN表中移出，并放到CLO131④

擴(kuò)展節(jié)點(diǎn)n

283014765

203184765

283164705

28314076500283104765擴(kuò)展28314765④擴(kuò)展節(jié)點(diǎn)n283014765203184765132⑤將節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放到OPEN

表的末端，并提供這些后繼節(jié)點(diǎn)回到n

的指針11283014765122031847651328316470514283140765OPEN表符父00283104765CLOSED⑤將節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并133⑥

后繼節(jié)點(diǎn)中無目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)到②②

OPEN表不為空，繼續(xù)⑥后繼節(jié)點(diǎn)中無目標(biāo)節(jié)點(diǎn)，轉(zhuǎn)到②②OPEN表不為空，繼134③

將第一個(gè)節(jié)點(diǎn)n

從OPEN

表中移出，并放到CLOSED表中OPEN表CLOSED表1220318476513283164705142831407650028310476511283014765節(jié)點(diǎn)n12③將第一個(gè)節(jié)點(diǎn)n從OPEN表中移出，并放到CLO135④

擴(kuò)展節(jié)點(diǎn)n

083214765

2837140651128301476528314765④擴(kuò)展節(jié)點(diǎn)n08321476528371406136⑤將節(jié)點(diǎn)n

的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供這些后繼節(jié)點(diǎn)回到n的指針122031847651328316470514283140765OPEN表2208321476523283714065⑤將節(jié)點(diǎn)n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并137….一直繼續(xù)下去，而且不產(chǎn)生已經(jīng)產(chǎn)生過的節(jié)點(diǎn)（狀態(tài)），防止死循環(huán)。在程序中每一個(gè)新產(chǎn)生的節(jié)點(diǎn)必須與OPEN和CLOSED表中狀態(tài)進(jìn)行比較，判斷是否已經(jīng)產(chǎn)生過，只保留從未產(chǎn)生過的節(jié)點(diǎn)….138最后的OPEN表：93234180765103283064175112283160754121208143765131283145706144830214765143813204765152283704615154283714650163123784065164123804765目標(biāo)節(jié)點(diǎn)12384765最后的OPEN表：932341807651032830641139最后的CLOSED表：2831047651128301476512203184765132831647051428314076522083214765232837140653102318476534230184765123456789最后的CLOSED表：28310476511283014761404128316407544283164750522801437505328314576064803214765742837146058312308476510111213141516164123804765目標(biāo)節(jié)點(diǎn)41283164075442831647505228014314183123084765164123804765目標(biāo)節(jié)點(diǎn)31023184765168122031847652831047653183123084765164123804765目標(biāo)節(jié)點(diǎn)3101422831476528314765231847652831647528314765214383214765283714652318476523184765281437652831647528316475283145768321476528371465123847652341876528364175283167542814376528314576832147658132476512378465123847652837461528371465先生成的節(jié)點(diǎn)在左目標(biāo)節(jié)點(diǎn)283147652831476523184765283164143（先擴(kuò)展的節(jié)點(diǎn)畫在左邊）生成后繼節(jié)點(diǎn)的順序（先擴(kuò)展的節(jié)點(diǎn)畫在左邊）生成后繼節(jié)點(diǎn)的順序144OPEN與CLOSED表的存儲(chǔ)形式的簡(jiǎn)化CLOSEDOPEN加入擴(kuò)展節(jié)點(diǎn)OPEN與CLOSED表的存儲(chǔ)形式的簡(jiǎn)化CLOSEDOPEN145狀態(tài)：111狀態(tài)：212狀態(tài)：313狀態(tài)：414狀態(tài)：522狀態(tài)：623狀態(tài)：731狀態(tài)：834狀態(tài)：941狀態(tài)：1044狀態(tài)：1152狀態(tài)：1253狀態(tài)：1364狀態(tài)：1474狀態(tài)：1583狀態(tài)：1693狀態(tài)：17103狀態(tài)：18112狀態(tài)：19121狀態(tài)：20131狀態(tài)：21144狀態(tài)：22143狀態(tài)：23152狀態(tài)：24154狀態(tài)：25163狀態(tài)：26164狀態(tài)：27CO123456789101112131415161718192021222324252627CO狀態(tài)：111狀態(tài)：212狀態(tài)：313狀態(tài)：414狀態(tài)：5146人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)(1,4)(3,4)WE(3,2)(3,1)ES(3,3)(4,4)ES目標(biāo)節(jié)點(diǎn)X例：迷宮問題人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,147例：四皇后問題QQQQQQQQQQQQQQQQQQQXQQQQQQQQQXQQQQX例：四皇后問題QQQQQQQQQQQQQQQQQQQXQQQ148練習(xí)：根據(jù)下列迷宮，用寬度優(yōu)先搜索算法尋找出從入口到出口的一條路徑狀態(tài)：用極坐標(biāo)表示的人的位置操作符：人向左方、前方、右方前進(jìn)提示：不要產(chǎn)生已有的狀態(tài)練習(xí)：根據(jù)下列迷宮，用寬度優(yōu)先搜索算法尋找出從入口到出口的一149存在的問題：走步方向不符合人走路的習(xí)慣沒有標(biāo)注走步的方向中間改變走步方向的順序多畫搜索樹，有解后還再往下擴(kuò)展存在的問題：150(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)(2,0)前右左(2,45)前(4,90)(0,0)前右(2,90)右(6,90)出口寬度優(yōu)先搜索算法（沒有生成已有的狀態(tài)）先在左XX(6,0)人向左向右向前2(4,0)前右(6,45)(4,4151(6,0)向左1(4,0)前右(4,45)(2,0)前前(2,45)右(4,90)(0,0)前右(6,90)出口寬度優(yōu)先搜索算法先在左X人向右3向前2(6,0)向左(4,0)前右(4,45)(2,0)前前(2,1523.2.2深度優(yōu)先搜索

深度優(yōu)先搜索策略是先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)

3.2.2深度優(yōu)先搜索深度優(yōu)先搜索策略是先擴(kuò)展最新產(chǎn)生153節(jié)點(diǎn)的深度；①、起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。②、任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1。

節(jié)點(diǎn)的深度；154深度優(yōu)先搜索的基本思路：先擴(kuò)展最深的節(jié)點(diǎn)。當(dāng)出現(xiàn)沒有后繼節(jié)點(diǎn)時(shí)，換到旁邊的次深節(jié)點(diǎn)后生成的節(jié)點(diǎn)畫在左邊深度優(yōu)先搜索的基本思路：后生成的節(jié)點(diǎn)畫在左邊155①

把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)的OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解②

如果OPEN

為一空表，則無解、失敗退出含有深度界限的深度優(yōu)先搜索算法：①把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)的OPEN表中。如果此156深度界限的設(shè)置：為了避免出現(xiàn)過深的路徑，搜索過程要設(shè)置一個(gè)深度界限對(duì)于等于深度界限的任何節(jié)點(diǎn)，當(dāng)作沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)來看待缺點(diǎn)：可能丟失解深度界限的設(shè)置：157③把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN

表移到CLOSED

表④

如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向②③把第一個(gè)節(jié)點(diǎn)(記作節(jié)點(diǎn)n)從OPEN表移到CL158⑤

擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它們放入OPEN

表的前頭。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向②⑥

如果后繼節(jié)點(diǎn)中有任一個(gè)節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解（反向追蹤從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑），成功退出；否則，轉(zhuǎn)向②⑤擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它們放入OPE159人工智能第3章確定性推理課件160人工智能第3章確定性推理課件161說明：現(xiàn)在的OPEN表是一個(gè)堆棧，后進(jìn)先出說明：162深度界限為4后生成的節(jié)點(diǎn)畫在左邊深度界限為4后生成的節(jié)點(diǎn)畫在左邊16328314765283147652318476528316475283147652143283164752831647528316754后生成的節(jié)點(diǎn)在左283167542816375428364175832641752836417528143765283145762831457628314576283157462814376528143765248137652318476523184765234187652341876523418576123847651238476512378465目標(biāo)節(jié)點(diǎn)283147652831476523184765283164164例：八數(shù)碼問題深度界限為5后生成的節(jié)點(diǎn)畫在左邊例：八數(shù)碼問題深度界限為5后生成的節(jié)點(diǎn)畫在左邊165說明：狀態(tài)旁邊的數(shù)字表示該節(jié)點(diǎn)生成后繼節(jié)點(diǎn)的順序，即CLOSED節(jié)點(diǎn)的存放順序，不是本身被生成的順序解是圖中的虛線擴(kuò)展過程中沒有生成已有的節(jié)點(diǎn)說明：166人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,2)E(3,2)(3,1)S例：迷宮問題(3,3)(3,4)(4,4)目標(biāo)節(jié)點(diǎn)ENE后生成的節(jié)點(diǎn)在左邊沒有已有節(jié)點(diǎn)人4S3E2N1W(1,1)N(2,3)(2,4)NS(2,167寬度優(yōu)先（先在左）深度優(yōu)先（后在左）人4321寬度優(yōu)先（先在左）深度優(yōu)先人4321168例：四皇后問題QQQQQQQQQQXQQQQQQXQQQQ后在左例：四皇后問題QQQQQQQQQQXQQQQQQXQQQQ后169練習(xí)：根據(jù)下列迷宮，用深度優(yōu)先搜索算法尋找出從入口到出口的一條路徑狀態(tài)：用極坐標(biāo)表示的人的位置操作符：人向左方、前方、右方前進(jìn)提示：不要產(chǎn)生已有的狀態(tài)練習(xí)：根據(jù)下列迷宮，用深度優(yōu)先搜索算法尋找出從入口到出口的一170深度優(yōu)先算法存在問題：先后順序有誤，規(guī)定的先后順序：左前右改變坐標(biāo)系，極坐標(biāo)直角坐標(biāo)對(duì)于一個(gè)節(jié)點(diǎn)，按照規(guī)定的操作符順序，使用所有可能的操作符，產(chǎn)生相應(yīng)的后繼節(jié)點(diǎn)深度優(yōu)先算法存在問題：171(6,0)人向左1向右3向前2(4,0)前右(6,45)(4,45)前前(2,45)右(4,90)左(2,90)右(6,90)出口深度優(yōu)先搜索算法（沒有產(chǎn)生已有的節(jié)點(diǎn)）后在左(6,0)人向左向右向前2(4,0)前右(6,45)(4,4172思考題：利用寬度優(yōu)先與深度優(yōu)先算法解決八數(shù)碼問題？思考題：1733.2.3等代價(jià)搜索寬度優(yōu)先搜索技術(shù)找到了應(yīng)用算符數(shù)目最少或者深度最淺的解如果認(rèn)為每一個(gè)操作符的代價(jià)相等，則寬度優(yōu)先搜索技術(shù)就可以找到了代價(jià)最小的路徑或解3.2.3等代價(jià)搜索寬度優(yōu)先搜索技術(shù)找到了應(yīng)用算符數(shù)目最174所有操作符代價(jià)相等找到最短的路徑寬度優(yōu)先算法操作符的代價(jià)不相等找到代價(jià)最小的路徑等代價(jià)(代價(jià)優(yōu)先)搜索技術(shù)問題推廣推廣所有操作符代價(jià)相等操作符的代價(jià)不相等問題推廣推廣175寬度優(yōu)先搜索：按照先后順序取待擴(kuò)展節(jié)點(diǎn)等代價(jià)搜索：將初始節(jié)點(diǎn)到所有端節(jié)點(diǎn)（OPEN中的節(jié)點(diǎn)）的局部路徑中代價(jià)最小的端節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)

推廣