1、第3章 搜索策略問題求解系統(tǒng)劃分為兩大類知識(shí)貧乏系統(tǒng) 依靠搜索技術(shù)知識(shí)貧乏、缺乏針對(duì)性效率低 知識(shí)豐富系統(tǒng) 依靠推理技術(shù)基于豐富知識(shí)的推理技術(shù)，直截了當(dāng) 效率高 2022/7/101第3章 搜索策略兩大類搜索技術(shù):1、一般圖搜索、啟發(fā)式搜索2、基于問題歸約的與或圖搜索 兩種典型的推理技術(shù):1、基于歸結(jié)的演繹推理歸結(jié)反演2、基于規(guī)則的演繹推理正向演繹推理逆向演繹推理 2022/7/1023.1 引言 對(duì)于給定的問題，智能系統(tǒng)的行為一般是找到能夠到達(dá)所希望目標(biāo)的動(dòng)作序列，并使其所付出的代價(jià)最小、性能最好?；诮o定的問題，問題求解的第一步是目標(biāo)的表示。搜索就是找到智能系統(tǒng)的動(dòng)作序列的過程。 2022

2、/7/103搜索算法的輸入是給定的問題，輸出是表示為動(dòng)作序列的方案。一旦有了方案，就可以執(zhí)行該方案所給出的動(dòng)作了。（執(zhí)行階段）因此，求解問題包括：目標(biāo)表示搜索執(zhí)行2022/7/104（1）初始狀態(tài)集合：定義了初始的環(huán)境。（2）操作符集合：把一個(gè)問題從一個(gè)狀態(tài)變換為另一個(gè)狀態(tài)的動(dòng)作集合。（3）目標(biāo)檢測(cè)函數(shù)：用來確定一個(gè)狀態(tài)是不是目標(biāo)。（4）路徑費(fèi)用函數(shù)：對(duì)每條路徑賦予一定費(fèi)用的函數(shù)。其中，初始狀態(tài)集合和操作符集合定義了問題的搜索空間。一般給定問題就是確定該問題的一些根本信息，一個(gè)問題由4局部組成:2022/7/105和通常的搜索空間不同，人工智能中大多數(shù)問題的狀態(tài)空間在問題求解之前不是全部知道的

3、。 在人工智能中，搜索問題一般包括兩個(gè)重要的問題：搜索什么搜索什么通常指的就是目標(biāo)。在哪里搜索在哪里搜索就是“搜索空間。搜索空間通常是指一系列狀態(tài)的聚集，因此稱為狀態(tài)空間。2022/7/106所以，人工智能中的搜索可以分成兩個(gè)階段：狀態(tài)空間的生成階段在該狀態(tài)空間中對(duì)所求問題狀態(tài)的搜索搜索可以根據(jù)是否使用啟發(fā)式信息分為盲目搜索啟發(fā)式搜索 2022/7/107盲目搜索 只是可以區(qū)分出哪個(gè)是目標(biāo)狀態(tài)。 一般是按預(yù)定的搜索策略進(jìn)行搜索。 沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問題的求解。 啟發(fā)式搜索是在搜索過程中參加了與問題有關(guān)的啟發(fā)式信息，用于指導(dǎo)搜索朝著最有希望的

4、方向前進(jìn)，加速問題的求解并找到最優(yōu)解。 2022/7/108根據(jù)問題的表示方式分為狀態(tài)空間搜索與或圖搜索狀態(tài)空間搜索是用狀態(tài)空間法來求解問題所進(jìn)行的搜索與/或圖搜索是指用問題規(guī)約方法來求解問題時(shí)所進(jìn)行的搜索。2022/7/109考慮一個(gè)問題的狀態(tài)空間為一棵樹的形式。寬度優(yōu)先搜索深度優(yōu)先搜索如果根節(jié)點(diǎn)首先擴(kuò)展，然后是擴(kuò)展根節(jié)點(diǎn)生成的所有節(jié)點(diǎn)，然后是這些節(jié)點(diǎn)的后繼，如此反復(fù)下去。在樹的最深一層的節(jié)點(diǎn)中擴(kuò)展一個(gè)節(jié)點(diǎn)。只有當(dāng)搜索遇到一個(gè)死亡節(jié)點(diǎn)（非目標(biāo)節(jié)點(diǎn)并且是無法擴(kuò)展的節(jié)點(diǎn)）的時(shí)候，才返回上一層選擇其他的節(jié)點(diǎn)搜索。2022/7/1010無論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點(diǎn)的順序一般都是固定的

5、，即一旦搜索空間給定，節(jié)點(diǎn)遍歷的順序就固定了。這種類型的遍歷稱為“確定性的，也就是盲目搜索。對(duì)于啟發(fā)式搜索，在計(jì)算每個(gè)節(jié)點(diǎn)的參數(shù)之前無法確定先選擇哪個(gè)節(jié)點(diǎn)擴(kuò)展，這種搜索一般也稱為非確定的。 2022/7/1011完備性：如果存在一個(gè)解答，該策略是否保證能夠找到？時(shí)間復(fù)雜性：需要多長(zhǎng)時(shí)間可以找到解答？空間復(fù)雜性：執(zhí)行搜索需要多少存儲(chǔ)空間？最優(yōu)性：如果存在不同的幾個(gè)解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索策略評(píng)價(jià)標(biāo)準(zhǔn):2022/7/1012有許多智力問題(如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等)和實(shí)際問題（如路徑規(guī)劃、機(jī)器人行動(dòng)規(guī)劃等）都可以歸結(jié)為狀態(tài)空間搜索。用狀態(tài)空間搜索來求解

6、問題的系統(tǒng)均定義一個(gè)狀態(tài)空間，并通過適當(dāng)?shù)乃阉魉惴ㄔ跔顟B(tài)空間中搜索解答路徑。3.2 基于狀態(tài)空間圖的搜索技術(shù)2022/7/1013狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(1)狀態(tài)空間的表示狀態(tài)空間記為SP，可表示為二元組：SP=(S,O)S問題求解（即搜索）過程中所有可能到達(dá)的合法狀態(tài)構(gòu)成的集合；O操作算子的集合，操作算子的執(zhí)行會(huì)導(dǎo)致問題狀態(tài)的變遷 ；狀態(tài)用于記載問題求解（即搜索）過程中某一時(shí)刻問題現(xiàn)狀的快照；抽象為矢量形式 Q=q0,q1,qnT每個(gè)元素qi稱為狀態(tài)分量 給定每個(gè)狀態(tài)分量qi的值就得到一個(gè)具體的狀態(tài) Qk=q0k,q1k,qnkT2022/7/1014狀態(tài)表示狀態(tài)的變遷操作算

7、子問題的狀態(tài)空間是一個(gè)表示該問題的全部可能狀態(tài)及其變遷的有向圖。 節(jié)點(diǎn)狀態(tài)有向弧狀態(tài)的變遷 弧上的標(biāo)簽導(dǎo)致狀態(tài)變遷的操作算子 用狀態(tài)空間搜索來求解問題的系統(tǒng)均定義一個(gè)狀態(tài)空間，并通過適當(dāng)?shù)乃阉魉惴ㄔ跔顟B(tài)空間中搜索解答路徑。2022/7/1015例1：走迷宮是人們熟悉的一種游戲。狀態(tài)空間搜索2022/7/1016格子、入口和出口節(jié)點(diǎn)狀態(tài)通道有向弧操作算子迷宮可以由一個(gè)有向圖表示2022/7/1017 例2:在一個(gè)33的方格棋盤上放置著1,2,3,4,5,6,7,8八個(gè)數(shù)碼，每個(gè)數(shù)碼占一格，且有一個(gè)空格。這些數(shù)碼可在棋盤上移動(dòng)，其移動(dòng)規(guī)則是：與空格相鄰的數(shù)碼方可移入空格?，F(xiàn)在的問題是：對(duì)于指定的初

8、始棋局和目標(biāo)棋局，給出數(shù)碼的移動(dòng)序列。該問題稱為八數(shù)碼問題。 56741382初始棋局56748321目標(biāo)棋局移動(dòng)數(shù)碼2022/7/10182 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48

9、 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52022/7/10192022/7/1020狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題問題的描述：N個(gè)傳教士帶著N個(gè)野人劃船過河；3個(gè)平安約束條件：1)船上人數(shù)不得超過載重限量，設(shè)為K個(gè)人； 2)任何時(shí)刻（包括兩岸、船上）野人數(shù)目不得超過傳教士； 3)允許在河的某一岸或者在船上只有野人而沒有傳教士；2022/7/1021狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題 特例：N=3，K=2

10、 狀態(tài)分量m傳教士在左岸的實(shí)際人數(shù)狀態(tài)分量c野人在左岸的實(shí)際人數(shù)狀態(tài)分量b指示船是否在左岸(1、0)3個(gè)平安約束條件m c (左岸平安)且 N-m N-c(右岸平安);m=0且0c N (左岸沒有傳道士，右岸一定平安);N-m=0且0N-cN (右岸沒有傳道士，左岸一定平安);2022/7/1022設(shè)初始狀態(tài)下傳教士、野人和船都在左岸，目標(biāo)狀態(tài)下這三者均在右岸，問題狀態(tài)以（m,c,b）表示。問題的求解任務(wù)可描述為：(3,3,1) (0,0,0)該簡(jiǎn)單問題可能到達(dá)的合法狀態(tài)：可能狀態(tài)總數(shù)：442=32根據(jù)條件得出合法狀態(tài)：20m c 且 N-m N-c (左岸平安且右岸平安)m=1,c=1；m=

11、2,c=2 m=0且0c N(左岸沒有傳道士)m=0,c=0,1,2,3 N-m=0且0N-cN(右岸沒有傳道士)m=3,c=0,1,2,3不可能到達(dá)的合法狀態(tài)：(0,0,1),(0,3,0),(3,0,1),(3,3,0)可能到達(dá)的合法狀態(tài)共16個(gè)2022/7/1023狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題定義2類操作算子：L(x,y)指示從左岸到右岸的劃船操作 R(x,y)指示從右岸到左岸的劃船操作x + y K=2(船的載重限制)；x和y取值的可能組合只有5個(gè)10，20，11，01，02 ( 允許在船上只有野人而沒有傳教士 )共有10個(gè)操作算

12、子2022/7/1024渡河問題的狀態(tài)空間有向圖2022/7/1025狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示由此例可以看出用狀態(tài)空間方法表示問題時(shí)，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。另外，還要定義一組操作，通過使用這些操作可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。 問題的求解過程是一個(gè)不斷把操作作用于狀態(tài)的過程。如果在使用某個(gè)操作后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到了問題的一個(gè)解。這個(gè)解是從初始狀態(tài)到目標(biāo)狀態(tài)所用操作構(gòu)成的序列。 2022/7/1026狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示由此例可以看出要使問題由一種狀態(tài)轉(zhuǎn)變到另一種狀態(tài)時(shí)，就必須使用一次操作。

13、這樣，在從初始狀態(tài)轉(zhuǎn)變到目標(biāo)狀態(tài)時(shí)，就可能存在多個(gè)操作序列(即得到多個(gè)解)。那么，其中使用操作最少或較少的解才為最優(yōu)解(因?yàn)橹挥性谑褂貌僮鲿r(shí)所付出的代價(jià)為最小的解才是最優(yōu)解)。 對(duì)其中的某一個(gè)狀態(tài)，可能存在多個(gè)操作使該狀態(tài)變到幾個(gè)不同的后繼狀態(tài)那么到底用哪個(gè)操作進(jìn)行搜索呢?這就有賴于搜索策略了不同的搜索策略有不同的順序，這就是本章后面要討論的問題。 2022/7/1027課堂練習(xí)有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。假設(shè)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；考慮到平安，無農(nóng)夫看管時(shí)，狐貍和小羊不能在一起，小羊和那籃菜也不能在一起。請(qǐng)為該問題的解決設(shè)計(jì)狀態(tài)空間，并畫出狀態(tài)空間圖

14、。2022/7/1028解析以變量m、f、s、v分別指示農(nóng)夫、狐貍、小羊、菜,且每個(gè)變量只可取值1(表示在左岸)或0(表示在右岸)。問題狀態(tài)可以四元組(m、f、s、v)描述,設(shè)初始狀態(tài)下均在左岸,目標(biāo)狀態(tài)下都到達(dá)右岸。從而,問題求解任務(wù)可描述為 (1, 1, 1, 1) -(0, 0, 0, 0)由于問題簡(jiǎn)單,狀態(tài)空間中可能的狀態(tài)總數(shù)為2222 = 16,由于要遵從平安限制,合法的狀態(tài)只有(除初、目狀態(tài)外): 1110，1101，1011，1010，0101，0001，0010，0100；不合法狀態(tài)有: 0111,1000,1100,0011,0110,1001設(shè)計(jì)二類操作算子:Lx、Rx,x

15、為m、f、s、v時(shí)分別指示農(nóng)夫單獨(dú),帶狐貍,帶小羊,帶菜過河；狀態(tài)空間圖如下所示.由于Lx和Rx是互逆操作,故而解答路徑可有無數(shù)條,但最近的只有二條;都是7個(gè)操作步. 思考：為什么不把船的狀態(tài)放到狀態(tài)空間中去？2022/7/1029解析:四元組(m、f、s、v)2022/7/1030狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(3)狀態(tài)空間的搜索狀態(tài)空間的搜索記為SE，可表示為五元組：SE=(S,O,E,I,G)；E搜索引擎；I問題的初始狀態(tài)，I S；G問題的目標(biāo)狀態(tài)集合，G S。搜索引擎E可以設(shè)計(jì)為實(shí)現(xiàn)任何搜索算法的控制系統(tǒng)。根本思想通過搜索引擎E尋找一個(gè)操作算子的調(diào)用序列，使問題從初始狀態(tài)I變遷

16、到目標(biāo)狀態(tài)G之一。解答路徑初-目變遷過程中的狀態(tài)序列或相應(yīng)的操作算子調(diào)用序列。2022/7/1031狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示或圖（一般圖）一個(gè)狀態(tài)可以有多個(gè)可供選擇的操作算子；操作算子間的選擇是一種“或的關(guān)系;這樣的有向圖稱為或圖。2022/7/1032狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(3)狀態(tài)空間的搜索或圖（一般圖）一個(gè)狀態(tài)可以有多個(gè)可供選擇的操作算子；操作算子間的選擇是一種“或的關(guān)系，這樣的有向圖稱為或圖。狀態(tài)空間一般都表示為或圖（一般圖）搜索圖在搜索解答路徑的過程中畫出搜索時(shí)涉及到的節(jié)點(diǎn)和弧線，構(gòu)成所謂的搜索圖。狀態(tài)空間搜索一般圖搜索2022/7/1033狀態(tài)空間搜索

17、1.狀態(tài)空間及其搜索的表示(3)狀態(tài)空間的搜索狀態(tài)空間、搜索圖和解答路徑之間的關(guān)系S0Sg2022/7/1034狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(4)一般圖搜索例子八數(shù)碼游戲 求解的問題：給定初始布局(即初始狀態(tài))和目標(biāo)布局(即目標(biāo)狀態(tài))，如何移動(dòng)數(shù)碼才能從初始布局到達(dá)目標(biāo)布局？解答就是一個(gè)合法的棋牌走步序列。初始布局目標(biāo)布局移動(dòng)數(shù)碼2022/7/1035狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(4)一般圖搜索例子八數(shù)碼游戲 用一般圖搜索方法解決該問題的步驟：1、為問題狀態(tài)的表示建立數(shù)據(jù)結(jié)構(gòu)2、制定操作算子集合3、設(shè)計(jì)搜索引擎 第一步：為問題狀態(tài)的表示建立數(shù)據(jù)結(jié)構(gòu)33的一個(gè)矩陣S矩陣元素S

18、ij0,1,2,3,4,5,6,7,8,其中1i,j3 數(shù)字0表示空格 數(shù)字1-8表示相應(yīng)的棋牌八數(shù)碼問題就可表示為：2022/7/1036狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示初始布局目標(biāo)布局移動(dòng)數(shù)碼(4)一般圖搜索例子八數(shù)碼游戲 2022/7/1037狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示(4)一般圖搜索例子八數(shù)碼游戲 第二步：制定操作算子集直觀方法為每個(gè)棋牌制定一套可能的走步：左、上、右、下四種移動(dòng)。需要32個(gè)操作算子簡(jiǎn)易方法僅為空格制定這4種走步。僅需4個(gè)操作算子第三步：設(shè)計(jì)搜索引擎 問題狀態(tài)空間的大小與問題涉及的元素個(gè)數(shù)是程指數(shù)級(jí)爆炸式增長(zhǎng)（即，組合爆炸問題）如，棋盤布局（問題狀態(tài)）

19、總共有9!=362880個(gè) 研究焦點(diǎn)是解決組合爆炸問題，通過壓縮搜索空間，提高搜索效率。 2022/7/1038狀態(tài)空間搜索1.狀態(tài)空間及其搜索的表示狀態(tài)空間、搜索圖和解答路徑之間的關(guān)系S0Sg2022/7/1039狀態(tài)空間搜索2.一般圖搜索策略 （1）搜索術(shù)語1、節(jié)點(diǎn)深度根節(jié)點(diǎn)指示初始狀態(tài)，令其深度為0；搜索圖中的其他節(jié)點(diǎn)的深度dn就可以遞歸地定義為其父節(jié)點(diǎn)深度dn-1加1：dn= dn-1+1。 根節(jié)點(diǎn)深度=0第n-1層節(jié)點(diǎn)dn-1第n層節(jié)點(diǎn)dn= dn-1+1搜索圖2022/7/1040狀態(tài)空間搜索2.一般圖搜索策略 （1）搜索術(shù)語2、節(jié)點(diǎn)擴(kuò)展應(yīng)用操作算子將上一狀態(tài)（節(jié)點(diǎn)ni）變遷到下一

20、狀態(tài)（節(jié)點(diǎn)nj）節(jié)點(diǎn)ni稱為被擴(kuò)展節(jié)點(diǎn)（父節(jié)點(diǎn)）節(jié)點(diǎn)nj稱為ni的子節(jié)點(diǎn)節(jié)點(diǎn)ni節(jié)點(diǎn)nj2022/7/1041（1）搜索術(shù)語3、路徑 節(jié)點(diǎn)ni到nj的路徑是由相鄰節(jié)點(diǎn)間的弧線構(gòu)成的折線要求路徑是無環(huán)的4、路徑代價(jià)相鄰節(jié)點(diǎn)ni和ni+1間的路徑代價(jià)記為C(ni, ni+1) 通常令任意相鄰節(jié)點(diǎn)間的路徑代價(jià)相同，并以路徑長(zhǎng)度1指示。即C(ni, ni+1)=1 。狀態(tài)空間搜索2.一般圖搜索策略節(jié)點(diǎn)ni節(jié)點(diǎn)ni+1節(jié)點(diǎn)nj2022/7/1042狀態(tài)空間搜索2.一般圖搜索策略 （1）搜索術(shù)語4、路徑代價(jià)目標(biāo)狀態(tài)節(jié)點(diǎn)ng節(jié)點(diǎn)ni節(jié)點(diǎn)nkC(nk,ng) C(ni,nk) C(ni,ng) 2022/7/

21、1043狀態(tài)空間搜索2.一般圖搜索策略（2）一般圖搜索算法符號(hào)說明：s-初始狀態(tài)節(jié)點(diǎn)G-搜索圖OPEN-存放待擴(kuò)展節(jié)點(diǎn)的表CLOSE-存放已被擴(kuò)展的節(jié)點(diǎn)的表MOVE-FIRST(OPEN)-取OPEN表首的節(jié)點(diǎn)作為當(dāng)前要被擴(kuò)展的節(jié)點(diǎn)n，同時(shí)將節(jié)點(diǎn)n移至CLOSE表一般圖搜索算法劃分為二個(gè)階段：1、初始化 2、搜索循環(huán) 2022/7/1044狀態(tài)空間搜索2.一般圖搜索策略（2）一般圖搜索算法算法劃分為二個(gè)階段：1、初始化 建立只包含初始狀態(tài)節(jié)點(diǎn)s的搜索圖G:=sOPEN:=sCLOSE:= 2、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)n作為擴(kuò)展的節(jié)點(diǎn)，同時(shí)將其移到clos

22、e表 擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表 適當(dāng)?shù)臉?biāo)記和修改指針排序OPEN表通過循環(huán)地執(zhí)行該算法，搜索圖G會(huì)因不斷有新節(jié)點(diǎn)參加而逐步長(zhǎng)大，直到搜索到目標(biāo)節(jié)點(diǎn)。 2022/7/1045以下面的八數(shù)碼為例，看一般圖的搜索算法初始布局目標(biāo)布局移動(dòng)數(shù)碼狀態(tài)空間搜索2.一般圖搜索策略2022/7/10462022/7/10472022/7/10482022/7/10492022/7/10502022/7/10512022/7/10522022/7/10532022/7/10542022/7/10552022/7/10562022/7/10572022/7/10582022/7/10592022/

23、7/10602022/7/10612022/7/10622022/7/10632022/7/10642022/7/1065狀態(tài)空間搜索2.一般圖搜索策略（2）一般圖搜索算法搜索過程中的指針修改節(jié)點(diǎn)n擴(kuò)展后的子節(jié)點(diǎn)分為3類：(i)全新節(jié)點(diǎn)(ii)已出現(xiàn)在OPEN表中的節(jié)點(diǎn)(iii)已出現(xiàn)的CLOSE表中的節(jié)點(diǎn)指針標(biāo)記和修改的方法：(i)類節(jié)點(diǎn)：參加OPEN表，建立從子節(jié)點(diǎn)到父節(jié)點(diǎn)n的指針(ii)類節(jié)點(diǎn)、 (iii)類節(jié)點(diǎn)比較經(jīng)由老父節(jié)點(diǎn)、新父節(jié)點(diǎn)n到達(dá)初始狀態(tài)節(jié)點(diǎn)的路徑代價(jià) 經(jīng)由新父節(jié)點(diǎn)n的代價(jià)比較小，則將原子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，修改為指向新父節(jié)點(diǎn)n (iii)類節(jié)點(diǎn)還得從CLOSE表中移出

24、，重新參加OPEN表。2022/7/1066狀態(tài)空間搜索2.一般圖搜索策略Sn4ninjn1n2n3n31n32節(jié)點(diǎn)ni是當(dāng)前擴(kuò)展的節(jié)點(diǎn)；擴(kuò)展出4個(gè)后續(xù)節(jié)點(diǎn)；n1、n2是新節(jié)點(diǎn)，只需建立指向父節(jié)點(diǎn)的指針，并參加OPEN表；2022/7/1067狀態(tài)空間搜索2.一般圖搜索策略Sn4ninjn1n2n3n31n32n4已經(jīng)存在于OPEN表，并且已有父節(jié)點(diǎn)njn4經(jīng)nj的路徑代價(jià)大取消n4指向nj的指針改為建立n4指向新父節(jié)點(diǎn)ni的指針n3已經(jīng)存在于CLOSE表，并且已有父節(jié)點(diǎn)nj需要做和n4同樣的比較和指針修改工作。并且要重新參加open表。2022/7/1068狀態(tài)空間搜索2.一般圖搜索策略（2

25、）一般圖搜索算法OPEN表中節(jié)點(diǎn)簡(jiǎn)單的排序方式：深度優(yōu)先擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的前端，即OPEN表作為棧，后進(jìn)先出，使搜索優(yōu)先向縱深方向開展。2022/7/1069深度優(yōu)先實(shí)例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6

26、52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 612346891113141618191 2 3 8 47 6 5目標(biāo)571012151720212022/7/1070深度優(yōu)先搜索在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(最深的)節(jié)點(diǎn)，深度 相等的節(jié)點(diǎn)可以任意排列。“最晚產(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展起始節(jié)點(diǎn)深度為0 任何其他節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1 :dn=dn-1+12022/7/1071深度優(yōu)先搜索很明顯這樣做，不一定找到最正確解，而且由于深度的限制，可能找不到解，然而，若不加深度限

27、制，可能沿著一條路線無限制地?cái)U(kuò)展下去，這當(dāng)然是不允許的。為保證找到解，應(yīng)選擇適當(dāng)?shù)纳疃冉缦蓿蛘卟扇〔粩嗉哟笊疃冉缦薜姆椒ǎ磸?fù)搜索，直到找到解。這種改進(jìn)的方法叫做迭代加深搜索。2022/7/1072Procedure Depth First SearchBegin把初始節(jié)點(diǎn)壓入棧，并設(shè)置棧頂指針；While 棧不空 do Begin彈出棧頂元素； If 棧頂元素=goal，成功返回并結(jié)束； Else 以任意次序把棧頂元素的子女壓入棧中；End WhileEnd基于棧實(shí)現(xiàn)的深度優(yōu)先搜索算法： 2022/7/1073初始節(jié)點(diǎn)放到棧中，棧指針指向棧的最上邊的元素。為了對(duì)該節(jié)點(diǎn)進(jìn)行檢測(cè)，需要從棧中彈

28、出該節(jié)點(diǎn)，如果是目標(biāo)，該算法結(jié)束，否則把其子節(jié)點(diǎn)以任何順序壓入棧中。該過程直到棧變成為空。遍歷一棵樹的過程（以下圖）。 2022/7/1074深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉是一個(gè)通用的與問題無關(guān)的方法2022/7/1075深度優(yōu)先搜索的優(yōu)點(diǎn)是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜索樹的一局部，它由當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點(diǎn)標(biāo)志所組成。深度優(yōu)先搜索的存儲(chǔ)器要求是深度約束的線性函數(shù)。 深度優(yōu)先搜索的優(yōu)點(diǎn)2022/7/1076深度優(yōu)先搜索的缺點(diǎn) 既不是完備的，也不是

29、最優(yōu)的。 主要問題是可能搜索到了錯(cuò)誤的路徑上。很多問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個(gè)錯(cuò)誤的路徑，則深度優(yōu)先搜索會(huì)一直搜索下去，而不會(huì)回到正確的路徑上。這樣一來對(duì)于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個(gè)答案，要么最后找到一個(gè)答案，但路徑很長(zhǎng)而且不是最優(yōu)的答案。2022/7/1077狀態(tài)空間搜索2.一般圖搜索策略（2）一般圖搜索算法OPEN表中節(jié)點(diǎn)簡(jiǎn)單的排序方式：深度優(yōu)先擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的前端，即OPEN表作為棧，后進(jìn)先出，使搜索優(yōu)先向縱深方向開展。寬度優(yōu)先擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于OPEN表的后端，即OPEN表作為隊(duì)列，先進(jìn)

30、先出，使搜索優(yōu)先向橫向方向開展。2022/7/1078寬度優(yōu)先實(shí)例2 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 54910111213141516172022/7/107

31、9寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索是逐層進(jìn)行的，在對(duì)下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)?！跋犬a(chǎn)生的節(jié)點(diǎn)先擴(kuò)展2022/7/1080Procedure Breadth-first-searchBegin把初始節(jié)點(diǎn)放入隊(duì)列； Repeat取得隊(duì)列最前面的元素為current; If current=goal 成功返回并結(jié)束； Else do Begin 如果current有子女，則current的子女 以任意次序添加到隊(duì)列的尾部； End Until 隊(duì)列為空 End采用隊(duì)列結(jié)構(gòu)，寬度優(yōu)先算法可以表示如下：20

32、22/7/1081寬度優(yōu)先搜索算法原理：如果當(dāng)前的節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，則把當(dāng)點(diǎn)節(jié)點(diǎn)的子孫以任意順序增加到隊(duì)列的后面，并把隊(duì)列的前端元素定義為current。如果目標(biāo)發(fā)現(xiàn)，則算法終止。 2022/7/1082寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí)，一定能找到解當(dāng)問題為單位代價(jià)時(shí)，且問題有解時(shí)，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法2022/7/1083寬度優(yōu)先搜索是一種盲目搜索，時(shí)間和空間復(fù)雜度都比較高，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)會(huì)產(chǎn)生許多無用的節(jié)點(diǎn)，搜索效率低。寬度優(yōu)先搜索中，時(shí)間需求是一個(gè)很大的問題，特別是當(dāng)搜索的深度比較大時(shí)，尤為嚴(yán)重，但是空間需求是比執(zhí)行時(shí)間更嚴(yán)重的問題

33、。 寬度優(yōu)先搜索優(yōu)點(diǎn)：目標(biāo)節(jié)點(diǎn)如果存在，用寬度優(yōu)先搜索算法總可以找到該目標(biāo)節(jié)點(diǎn)，而且是最?。醋疃搪窂剑┑墓?jié)點(diǎn)。寬度優(yōu)先搜索的優(yōu)點(diǎn)和缺點(diǎn)2022/7/1084總結(jié) 適用場(chǎng)合 深度優(yōu)先當(dāng)一個(gè)問題有多個(gè)解答或多條解答路徑，且只須找到其中一個(gè)時(shí)；往往應(yīng)對(duì)搜索深度加以限制。 寬度優(yōu)先確保搜索到最短的解答路徑。共同優(yōu)缺點(diǎn)： 可直接應(yīng)用一般圖搜索算法實(shí)現(xiàn)，不需要設(shè)計(jì)特別的節(jié)點(diǎn)排序方法，從而簡(jiǎn)單易行，適合于許多復(fù)雜度不高的問題求解任務(wù)。 節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識(shí)去指導(dǎo)排序，往往會(huì)在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解答，所以也稱為盲目搜索。 2022/7/1085有界深度搜索和迭代加深搜索

34、 有界深度優(yōu)先搜索過程總體上按深度優(yōu)先算法方法進(jìn)行，但對(duì)搜索深度需要給出一個(gè)深度限制dm，當(dāng)深度到達(dá)了dm的時(shí)候，如果還沒有找到解答，就停止對(duì)該分支的搜索，換到另外一個(gè)分支進(jìn)行搜索。2022/7/1086策略說明: （1）深度限制dm很重要。當(dāng)問題有解，且解的路徑長(zhǎng)度小于或等于dm時(shí)，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。但是當(dāng)dm取得太小，解的路徑長(zhǎng)度大于dm時(shí)，則搜索過程中就找不到解，即這時(shí)搜索過程甚至是不完備的。2022/7/1087（2）深度限制dm不能太大。當(dāng)dm太大時(shí)，搜索過程會(huì)產(chǎn)生過多的無用節(jié)點(diǎn)，既浪費(fèi)了計(jì)算機(jī)資源，又降低了搜索效率。（3

35、）有界深度搜索的主要問題是深度限制值dm的選取。 2022/7/1088改進(jìn)方法： （迭代加深搜索） 先任意給定一個(gè)較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限制內(nèi)沒有找到問題的解，則增大深度限制dm，繼續(xù)搜索。2022/7/1089迭代加深搜索，試圖嘗試所有可能的深度限制：首先深度為0，然后深度為1，然后為2，等等。如果初始深度為0，則該算法只生成根節(jié)點(diǎn)，并檢測(cè)它。如果根節(jié)點(diǎn)不是目標(biāo)，則深度加1，通過典型的深度優(yōu)先算法，生成深度為1的樹。當(dāng)深度限制為m時(shí)，樹的深度為m。 2022/7/1090迭代加深搜索看起來會(huì)很浪費(fèi)，因?yàn)楹芏喙?jié)點(diǎn)都可能擴(kuò)展屢次。

36、然而對(duì)于很多問題，這種屢次的擴(kuò)展負(fù)擔(dān)實(shí)際上很小，直覺上可以想象，如果一棵樹的分支系數(shù)很大，幾乎所有的節(jié)點(diǎn)都在最底層上，則對(duì)于上面各層節(jié)點(diǎn)擴(kuò)展屢次對(duì)整個(gè)系統(tǒng)來說影響不是很大。 2022/7/1091搜索最優(yōu)策略的比較 表注：b是分支系數(shù)，d是解答的深度，m是搜索樹的最大深度，l是深度限制。2022/7/1092寬度優(yōu)先搜索、深度優(yōu)先搜索和迭代加深搜索都可以用于生成和測(cè)試算法。寬度優(yōu)先搜索需要指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線性關(guān)系。 2022/7/1093迭代加深搜索對(duì)一棵深度受控的樹采用深度優(yōu)先的搜索。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點(diǎn)。和寬度優(yōu)先搜索一樣，它是最優(yōu)的

37、，也是完備的。但對(duì)空間要求和深度優(yōu)先搜索一樣是適中的。 2022/7/1094一般圖搜索算法常用的簡(jiǎn)單方式：深度優(yōu)先寬度優(yōu)先【缺點(diǎn)：節(jié)點(diǎn)排序的盲目性】在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解答，效率低提高一般圖搜索效率的關(guān)鍵優(yōu)化OPEN表中節(jié)點(diǎn)的排序方式盲目搜索3.4 啟發(fā)式搜索2022/7/1095125634最理想情況：每次排序后OPEN表表首元素n總在解答路徑上2022/7/1096啟發(fā)式搜索啟發(fā)式知識(shí)指導(dǎo)OPEN表排序的一般圖搜索：全局排序?qū)PEN表中的所有節(jié)點(diǎn)排序，使最有希望的節(jié)點(diǎn)排在表首。A算法， A*算法（掌握?。┚植颗判騼H對(duì)新擴(kuò)展出來的子節(jié)點(diǎn)排序，使這些新節(jié)點(diǎn)中最有希望者能優(yōu)

38、先取出考察和擴(kuò)展；爬山法（了解，對(duì)深度優(yōu)先法的改進(jìn)）；2022/7/1097啟發(fā)式搜索1.A算法（掌握）【根本思想】設(shè)計(jì)表達(dá)啟發(fā)式知識(shí)的評(píng)價(jià)函數(shù)f(n)；指導(dǎo)一般圖搜索中OPEN表待擴(kuò)展節(jié)點(diǎn)的排序：【評(píng)價(jià)函數(shù)f(n)=g(n)+h(n) （掌握） 】n-搜索圖G中的節(jié)點(diǎn)；f(n)- G中從初始狀態(tài)節(jié)點(diǎn)s，經(jīng)由節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)ng，估計(jì)的最小路徑代價(jià)；g(n)- G中從s到n，目前實(shí)際的路徑代價(jià)；h(n)-從n到ng，估計(jì)的最小路徑代價(jià)；2022/7/1098啟發(fā)式搜索1.A算法（掌握）Snng目標(biāo)狀態(tài)節(jié)點(diǎn)ng初始狀態(tài)節(jié)點(diǎn)S節(jié)點(diǎn)n搜索圖Gh(n): n-ng的估計(jì)最小路徑代價(jià) g(n):s-n

39、的實(shí)際路徑代價(jià) f(n):s-n-ng的估計(jì)最小路徑代價(jià) 2022/7/1099啟發(fā)式搜索1.A算法（掌握）【評(píng)價(jià)函數(shù)f(n)=g(n)+h(n) （掌握） 】n-搜索圖G中的節(jié)點(diǎn)；f(n)- G中從s經(jīng)n到ng，估計(jì)的最小路徑代價(jià)；g(n)- G中從s到n，目前實(shí)際的路徑代價(jià)；h(n)-從n到ng，估計(jì)的最小路徑代價(jià)； h(n)值-依賴于啟發(fā)式知識(shí)加以計(jì)算；h(n)稱為啟發(fā)式函數(shù)（掌握意義！）。如何用評(píng)價(jià)函數(shù)來實(shí)現(xiàn)A算法? （ 掌握?。?2022/7/10100啟發(fā)式搜索1.A算法（掌握）A算法的設(shè)計(jì)與一般圖搜索相同，劃分為二個(gè)階段：1、初始化 建立只包含初始狀態(tài)節(jié)點(diǎn)s的搜索圖G:=sOPE

40、N:=sCLOSE:= 2、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)n 擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表 適當(dāng)?shù)臉?biāo)記和修改指針（子節(jié)點(diǎn)父節(jié)點(diǎn)）排序OPEN表（評(píng)價(jià)函數(shù)f(n)的值排序）通過循環(huán)地執(zhí)行該算法，搜索圖會(huì)因不斷有新節(jié)點(diǎn)參加而逐步長(zhǎng)大，直到搜索到目標(biāo)節(jié)點(diǎn)。2022/7/10101啟發(fā)式搜索1.A算法（掌握）算法A的設(shè)計(jì)與一般圖搜索類似，劃分為二個(gè)階段：1、初始化 2、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)n 擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表 對(duì)每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni)適當(dāng)?shù)臉?biāo)記和

41、修改指針（子節(jié)點(diǎn)父節(jié)點(diǎn)）排序OPEN表（評(píng)價(jià)函數(shù)f(n)的值排序）2022/7/10102啟發(fā)式搜索1.A算法（掌握）擴(kuò)展出n的子節(jié)點(diǎn),插入搜索圖G和OPEN表 對(duì)每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni)適當(dāng)?shù)臉?biāo)記和修改指針（子節(jié)點(diǎn)父節(jié)點(diǎn)）(i)全新節(jié)點(diǎn)：f(ni)=f(n,ni)(ii)已出現(xiàn)在OPEN表中的節(jié)點(diǎn)(iii)已出現(xiàn)的CLOSE表中的節(jié)點(diǎn)IF f(ni)f(n,ni) THEN 修改指針指向新父結(jié)點(diǎn)n f(ni)=f(n,ni)排序OPEN表（f(n)值從小到大排序）2022/7/101032.若OPEN表是空表，則失敗退出；算法A3.選擇OPEN表上的第一

42、個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSE表中，稱此節(jié)點(diǎn)為節(jié)點(diǎn)n； 1.建立一個(gè)只包含起始節(jié)點(diǎn)S的搜索圖G,把S放到一個(gè)叫OPEN的未擴(kuò)展節(jié)點(diǎn)表中；建立一個(gè)叫做CLOSE的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表；5.擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些子節(jié)點(diǎn)的集合M,把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中；對(duì)于M中每個(gè)子節(jié)點(diǎn)ni,計(jì)算f(n,ni) = g(n,ni) + h(ni);4.若n為一目標(biāo)節(jié)點(diǎn)，則有解成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的；2022/7/101046.對(duì)那些未曾在G中出現(xiàn)過的M成員（全新節(jié)點(diǎn)）設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)已經(jīng)在

43、OPEN表上的每一個(gè)M成員，比較子節(jié)點(diǎn)ni經(jīng)由新、老父節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f(n,ni)、f(ni);若f(n,ni) f(ni)點(diǎn),則令f(ni) = f(n,ni),并移動(dòng)子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，改為指向新父節(jié)點(diǎn)。對(duì)已在CLOSE表上的每個(gè)M成員，作與第2類同樣的處理，并把這些子結(jié)點(diǎn)從CLOSE表移出，重新參加OPEN表。7.按f(n)排序OPEN表中的節(jié)點(diǎn)，f(n)值最小者排在首位，重排OPEN表；8.轉(zhuǎn)2。此過程生成一個(gè)明確的圖G(搜索圖）和一個(gè)G的子集T(搜索樹）。2022/7/10105啟發(fā)式搜索1.A算法（掌握）A算法實(shí)例八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)=d(n)+w(n

44、),其中d(n)-節(jié)點(diǎn)n在搜索圖中的節(jié)點(diǎn)深度，對(duì)g(n)的度量；w(n)-代表啟發(fā)式函數(shù)h(n),其值是節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)ng相比較，不考慮空格，錯(cuò)位的棋牌個(gè)數(shù)；初始布局目標(biāo)布局移動(dòng)數(shù)碼2022/7/10106啟發(fā)式搜索1.A算法（掌握）啟發(fā)式算法A實(shí)例八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)計(jì)算實(shí)例初始布局s目標(biāo)布局ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)h(n): n-ng的最小路徑代價(jià) g(n):s-n的最小路徑代價(jià) f(n):s-n-ng的最小路徑代價(jià) 注：W(S)不考慮空格2022/7/10107狀態(tài)空間搜索2.一般圖搜索策略 （1）搜索術(shù)語1、節(jié)點(diǎn)深度根節(jié)點(diǎn)

45、指示初始狀態(tài)，令其深度為0；搜索圖中的其他節(jié)點(diǎn)的深度dn就可以遞歸地定義為其父節(jié)點(diǎn)深度dn-1加1：dn= dn-1+1。 根節(jié)點(diǎn)深度=0第n-1層節(jié)點(diǎn)dn-1第n層節(jié)點(diǎn)dn= dn-1+1搜索圖G2022/7/10108啟發(fā)式搜索1.A算法（掌握）啟發(fā)式算法A實(shí)例八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)計(jì)算實(shí)例初始布局s目標(biāo)布局ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)h(n): n-ng的最小路徑代價(jià) g(n):s-n的最小路徑代價(jià) f(n):s-n-ng的最小路徑代價(jià) 0 4 4 注：W(S)不考慮空格2022/7/10109初始化OPEN:=s4 CLOSE:= 2

46、022/7/10110循環(huán)1CLOSE:=s4 OPEN:=a b c OPEN:=a6 b4 c6 OPEN:=b4 a6 c6 2022/7/10111循環(huán)2CLOSE:=s4 b4 OPEN:=a6 c6 d e i OPEN:=a6 c6 d5 e5 i6 OPEN:=d5 e5 a6 c6 i6 2022/7/10112循環(huán)3CLOSE:=s4 b4 d5 OPEN:=e5 a6 c6 i6 j k OPEN:=e5 a6 c6 i6 j7 k6 OPEN:=e5 a6 c6 i6 k6 j7 2022/7/10113循環(huán)4CLOSE:=s4,b4,d5,e5 OPEN:=a6 c6

47、 i6 k6 j7 l m OPEN:=a6 c6 i6 k6 j7 l5 m7 OPEN:=l5 a6 c6 i6 k6 j7 m7 2022/7/10114CLOSE:=s4,b4,d5,e5,l5 循環(huán)5OPEN:=a6 c6 i6 k6 j7 m7 n OPEN:=a6 c6 i6 k6 j7 m7 n5 OPEN:=n5 a6 c6 i6 k6 j7 m7 2022/7/10115循環(huán)6CLOSE:=s4,b4,d5,e5,l5,n5 OPEN:=a6 c6 i6 k6 j7 m7 o g OPEN:=a6 c6 i6 k6 j7 m7 o7 g5 OPEN:=g5 a6 c6 i6

48、 k6 j7 m7 o7 2022/7/10116循環(huán)7成功結(jié)束2022/7/10117最理想搜索圖G2022/7/10118判斷失誤2022/7/10119 例 2 給定4L和3L的水壺各一個(gè)，水壺上沒有刻度，可以向水壺中加水。如何在4L的壺中準(zhǔn)確地得到2L水？ （x,y）4L壺里的水有xL，3L壺里的水有yL，n表示搜索空間中的任一節(jié)點(diǎn)。則給出下面的啟發(fā)式函數(shù)： 2022/7/10120 h(n) = 2 如果0 x 4并且0 y 3 = 4 如果0 x 4或者0 y =g*(n)h(n)盡可能靠近h*(n) A算法的關(guān)鍵。2022/7/10127啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1

49、）搜索算法的可采納性(Admissibility)4)改進(jìn)啟發(fā)式函數(shù)八數(shù)碼游戲f(n)=d(n)+w(n),其中w(n)-表示錯(cuò)位的棋牌個(gè)數(shù)，不夠貼切，錯(cuò)誤的擴(kuò)展了節(jié)點(diǎn)d；p(n)-節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)比較，錯(cuò)位棋牌在不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和；p(n)比w(n)更接近于h*(n)-p(n)不僅考慮了棋牌的錯(cuò)位因素，還考慮了錯(cuò)位的距離（移動(dòng)距離）2022/7/10128啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素4)改進(jìn)啟發(fā)式函數(shù)八數(shù)碼游戲f(s)計(jì)算實(shí)例初始布局s目標(biāo)布局ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)0 4 4 p(s):錯(cuò)位棋

50、牌移動(dòng)距離d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)0 5 5 1 1 1 2 2022/7/10129初始化OPEN:=s5 CLOSE:= 2022/7/10130循環(huán)1CLOSE:=s5 OPEN:=a b c OPEN:=a7 b5 c7 OPEN:=b5 a7 c7 2022/7/10131循環(huán)2CLOSE:=s5 b5 OPEN:=a7 c7 d e i OPEN:=a7 c7 d7 e5 i7 OPEN:=e5 a7 c7 d7 i7 2022/7/10132循環(huán)3CLOSE:=s5 b5 e5 OPEN:=a7 c7 d7 i7 l m OPEN:=a7 c7 d7 i7 l5 m7 O

51、PEN:=l5 a7 c7 d7 i7 m7 2022/7/10133CLOSE:=s5,b5,e5,l5 循環(huán)4OPEN:=a7 c7 d7 i7 m7 n OPEN:=a7 c7 d7 i7 m7 n5 OPEN:=n5 a7 c7 d7 i7 m7 2022/7/10134CLOSE:=s5,b5,e5,l5,n5 循環(huán)5OPEN:=a7 c7 d7 i7 m7 o g OPEN:=a7 c7 d7 i7 m7 o7 g5 OPEN:=g5 a7 c7 d7 i7 m7 o7 2022/7/10135循環(huán)6成功結(jié)束最理想搜索圖G2022/7/10136防止了錯(cuò)誤選擇2022/7/1013

52、7啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1）搜索算法的可采納性(Admissibility)5) A*算法定義：1、在A算法中，規(guī)定h(n)h*(n);2、經(jīng)如此限制以后的A算法就是A*算法。A*算法是可采納的，即總能搜索到最短解答路徑【回憶：八數(shù)碼游戲的h(n)】w(n)-錯(cuò)位的棋牌個(gè)數(shù)p(n)-錯(cuò)位棋牌在不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和；2022/7/10138啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1）搜索算法的可采納性(Admissibility)5) A*算法定義：1、在A算法中，規(guī)定h(n)h*(n);2、經(jīng)如此限制以后的A算法就是A*算法。A*

53、算法是可采納的，即總能搜索到最短解答路徑證明：【人工智能 上冊(cè)陸汝鈐P248】1）如果存在一條從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑，則一定存在一條最短解答通路；2）設(shè)狀態(tài)n是最短解答路徑上的一個(gè)狀態(tài)，那么經(jīng)過有限步后，n必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；3）因?yàn)樽疃探獯鹇窂街挥杏邢迋€(gè)節(jié)點(diǎn)n，所以有限步后算法必然因到達(dá)目標(biāo)狀態(tài)ng。這就是最優(yōu)解。證明完畢。2022/7/10139啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1）搜索算法的可采納性(Admissibility)5)滿足可采納性條件的算法A*算法證明：2）設(shè)狀態(tài)n是最短解答路徑上的一個(gè)狀態(tài)，那么經(jīng)過有限步后，n必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；

54、f(n)=g(n)+h(n)根據(jù)假設(shè)，n在最短解答路徑上 經(jīng)過有限步驟后，g(n)= g*(n)f(n)=g*(n)+h(n) h(n)h*(n)f(n)=g*(n)+h(n) g*(n)+h*(n)=f*(n) f*(n)= f*(ng) f(n) f*(ng)2022/7/10140啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（1）搜索算法的可采納性(Admissibility)5)滿足可采納性條件的算法A*算法證明：2）設(shè)狀態(tài)n是最短解答路徑上的一個(gè)狀態(tài)，那么經(jīng)過有限步后，n必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；設(shè)OPEN表中n之前的節(jié)點(diǎn)只有有限個(gè)，設(shè)為N個(gè)，其中估計(jì)值最小者為a1，并稱之為第一代

55、節(jié)點(diǎn)；由第一代節(jié)點(diǎn)生成的節(jié)點(diǎn)稱為第二代節(jié)點(diǎn)，其中估計(jì)值最小者為a2；a2a1+e(其中，e0，表示每擴(kuò)展一次起碼的代價(jià))擴(kuò)展j代后， aj a1+(j-1)e當(dāng)j足夠大時(shí)一定有aj f*(ng)f(n) f*(ng)且OPEN表中n之前的節(jié)點(diǎn)經(jīng)過j次擴(kuò)展后的最小估計(jì)值aj f*(ng) f(n) 經(jīng)過有限步后，n必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)2022/7/10141啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（2）啟發(fā)式函數(shù)的強(qiáng)弱及其影響h(n)接近h*(n)的程度衡量啟發(fā)式函數(shù)的強(qiáng)弱h(n)h*(n)，h(n)過強(qiáng)，A算法失去可采納性，不能確保找到最短解答路徑；h(n)=h*(n)是最理想的，

56、OPEN表中節(jié)點(diǎn)排序沒有誤差，可以確保產(chǎn)生最小的搜索圖，搜索到最短解答路徑；無法設(shè)計(jì)A*算法搜索問題解答的關(guān)鍵h(n)在滿足h(n) h*(n)的條件下，越大越好！2022/7/10142啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（2）啟發(fā)式函數(shù)的強(qiáng)弱及其影響定理：解決同一問題的兩個(gè)A*算法A1和A2，若h1(n) h2(n) h*(n)且g1(n)=g2(n)則t(A1) t(A2)其中，h1、h2分別是算法A1、A2的啟發(fā)式函數(shù)，t指示相應(yīng)算法到達(dá)目標(biāo)狀態(tài)時(shí)搜索圖含的節(jié)點(diǎn)總數(shù)。【證明： 人工智能 上冊(cè)陸汝鈐 P250）】八數(shù)碼游戲：w(n)p(n) h*(n)p(n)擴(kuò)展出的節(jié)點(diǎn)總數(shù)t(w(n

57、)2022/7/10143啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（3）設(shè)計(jì)h(n)的實(shí)用考慮和寬度優(yōu)先和深度優(yōu)先的關(guān)系若h(n)0, 則意味著先進(jìn)入OPEN表的節(jié)點(diǎn)會(huì)優(yōu)先被考察和擴(kuò)展，因?yàn)榧词共灰詃(n)作為g(n), 通常先進(jìn)入OPEN表的節(jié)點(diǎn)n也具有較小的g(n)值若g(n)0,則導(dǎo)致后進(jìn)入OPEN表的節(jié)點(diǎn)會(huì)優(yōu)先被考察和擴(kuò)展，因?yàn)楹筮M(jìn)入OPEN表的節(jié)點(diǎn)n往往更接近于目標(biāo)狀態(tài)，即h(n)值較小，從而使搜索過程接近于深度優(yōu)先的搜索策略 2022/7/10144啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（3）設(shè)計(jì)h(n)的實(shí)用考慮為更有效地搜索解答 ，可使用評(píng)價(jià)函數(shù)f(n) = g(n) + wh(

58、n)，w用作加權(quán) 在搜索圖的淺層（上部），可讓w取較大值，以使g(n)所占比例很小，從而突出啟發(fā)式函數(shù)的作用，加速向縱深方向搜索 一旦搜索到較深的層次，又讓w取較小值，以使g(n)所占比例很大，并確保wh(n)h* (n),從而引導(dǎo)搜索向橫廣方向開展，尋找到較短的解答路徑。 2022/7/101453. 迭代加深A(yù)*算法 由于A*算法把所有生成的節(jié)點(diǎn)保存在內(nèi)存中，所以A*算法在耗盡計(jì)算時(shí)間之前一般早已經(jīng)把空間耗盡了。目前開發(fā)了一些新的算法，它們的目的是為了克服空間問題。但一般不滿足最優(yōu)性或完備性，如迭代加深A(yù)*算法IDA*、簡(jiǎn)化內(nèi)存受限A*算法SMA*等。下面簡(jiǎn)單介紹IDA*算法。 2022/

59、7/10146迭代加深搜索算法，它以深度優(yōu)先的方式在有限制的深度內(nèi)搜索目標(biāo)節(jié)點(diǎn)。在每個(gè)深度上，該算法在每個(gè)深度上檢查目標(biāo)節(jié)點(diǎn)是否出現(xiàn)，如果出現(xiàn)則停止，否則深度加1繼續(xù)搜索。而A*算法是選擇具有最小估價(jià)函數(shù)值的節(jié)點(diǎn)擴(kuò)展。2022/7/10147迭代加深A(yù)* 搜索算法IDA*是上述兩種算法的結(jié)合。這里啟發(fā)式函數(shù)用做深度的限制，而不是選擇擴(kuò)展節(jié)點(diǎn)的排序。2022/7/10148迭代加深A(yù)*算法Procedure IDA*算法Begin (1) 初始化當(dāng)前的深度限制c=1 (2) 把初始節(jié)點(diǎn)壓入棧; 并假定 (3) While 棧不空橋do Begin 彈出棧頂元素n If n=goal, Then

60、結(jié)束, 返回n以及從初始節(jié)點(diǎn)到n的路徑 Else do Begin For n 的每個(gè)子節(jié)點(diǎn) If , Then 把 壓入棧 Else End for End End While (4) If 棧為空并且 , Then 停止并退出 (5) If 棧為空并且 , Then , 并返回2 End 2022/7/10149IDA*算法和A*算法相比，主要優(yōu)點(diǎn)是對(duì)于內(nèi)存的需求。A*算法需要指數(shù)級(jí)數(shù)量的存儲(chǔ)空間，因?yàn)闆]有深度方面的限制。而IDA*算法只有當(dāng)節(jié)點(diǎn)n的所有子節(jié)點(diǎn) 的 小于限制值c時(shí)才擴(kuò)展它,這樣就可以節(jié)省大量的內(nèi)存。另一問題是當(dāng)啟發(fā)式函數(shù)是最優(yōu)的時(shí)候，IDA*算法和A*算法擴(kuò)展相同的節(jié)點(diǎn)，并