2023/1/191第3章搜索策略問(wèn)題求解系統(tǒng)劃分為兩大類知識(shí)貧乏系統(tǒng)

依靠搜索技術(shù)解決問(wèn)題知識(shí)貧乏、缺乏針對(duì)性效率低知識(shí)豐富系統(tǒng)

依靠推理技術(shù)解決問(wèn)題基于豐富知識(shí)的推理技術(shù)，直截了當(dāng)效率高2023/1/192第3章搜索策略兩大類搜索技術(shù):1、一般圖搜索、啟發(fā)式搜索2、基于問(wèn)題歸約的與或圖搜索兩種典型的推理技術(shù):1、基于歸結(jié)的演繹推理歸結(jié)反演2、基于規(guī)則的演繹推理正向演繹推理逆向演繹推理2023/1/1933.1引言

對(duì)于給定的問(wèn)題，智能系統(tǒng)的行為一般是找到能夠達(dá)到所希望目標(biāo)的動(dòng)作序列，并使其所付出的代價(jià)最小、性能最好。基于給定的問(wèn)題，問(wèn)題求解的第一步是目標(biāo)的表示。搜索就是找到智能系統(tǒng)的動(dòng)作序列的過(guò)程。2023/1/194搜索算法的輸入是給定的問(wèn)題，輸出是表示為動(dòng)作序列的方案。一旦有了方案，就可以執(zhí)行該方案所給出的動(dòng)作了。（執(zhí)行階段）因此，求解問(wèn)題包括：目標(biāo)表示搜索執(zhí)行2023/1/195（1）初始狀態(tài)集合：定義了初始的環(huán)境。（2）操作符集合：把一個(gè)問(wèn)題從一個(gè)狀態(tài)變換為另一個(gè)狀態(tài)的動(dòng)作集合。（3）目標(biāo)檢測(cè)函數(shù)：用來(lái)確定一個(gè)狀態(tài)是不是目標(biāo)。（4）路徑費(fèi)用函數(shù)：對(duì)每條路徑賦予一定費(fèi)用的函數(shù)。其中，初始狀態(tài)集合和操作符集合定義了問(wèn)題的搜索空間。一般給定問(wèn)題就是確定該問(wèn)題的一些基本信息，一個(gè)問(wèn)題由4部分組成:2023/1/196和通常的搜索空間不同，人工智能中大多數(shù)問(wèn)題的狀態(tài)空間在問(wèn)題求解之前不是全部知道的。

在人工智能中，搜索問(wèn)題一般包括兩個(gè)重要的問(wèn)題：搜索什么搜索什么通常指的就是目標(biāo)。在哪里搜索在哪里搜索就是“搜索空間”。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為狀態(tài)空間。2023/1/197所以，人工智能中的搜索可以分成兩個(gè)階段：狀態(tài)空間的生成階段在該狀態(tài)空間中對(duì)所求問(wèn)題狀態(tài)的搜索搜索可以根據(jù)是否使用啟發(fā)式信息分為盲目搜索啟發(fā)式搜索2023/1/198盲目搜索只是可以區(qū)分出哪個(gè)是目標(biāo)狀態(tài)。一般是按預(yù)定的搜索策略進(jìn)行搜索。沒(méi)有考慮到問(wèn)題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。

啟發(fā)式搜索是在搜索過(guò)程中加入了與問(wèn)題有關(guān)的啟發(fā)式信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解并找到最優(yōu)解。

2023/1/199根據(jù)問(wèn)題的表示方式分為狀態(tài)空間搜索與或圖搜索狀態(tài)空間搜索是用狀態(tài)空間法來(lái)求解問(wèn)題所進(jìn)行的搜索與/或圖搜索是指用問(wèn)題規(guī)約方法來(lái)求解問(wèn)題時(shí)所進(jìn)行的搜索。2023/1/1910考慮一個(gè)問(wèn)題的狀態(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)并且是無(wú)法擴(kuò)展的節(jié)點(diǎn)）的時(shí)候，才返回上一層選擇其他的節(jié)點(diǎn)搜索。2023/1/111無(wú)論是寬度度優(yōu)先搜索索還是深度度優(yōu)先搜索索，遍歷節(jié)節(jié)點(diǎn)的順序序一般都是是固定的，，即一旦搜搜索空間給給定，節(jié)點(diǎn)點(diǎn)遍歷的順順序就固定定了。這種種類型的遍遍歷稱為“確定性”的，也就是是盲目搜索。對(duì)于啟發(fā)式式搜索，在在計(jì)算每個(gè)個(gè)節(jié)點(diǎn)的參參數(shù)之前無(wú)法確定先先選擇哪個(gè)個(gè)節(jié)點(diǎn)擴(kuò)展展，這種搜索索一般也稱2023/1/112完備性：如果存在一個(gè)個(gè)解答，該策策略是否保證證能夠找到？時(shí)間復(fù)雜性：需要多長(zhǎng)時(shí)間可以找到解答？空間復(fù)雜性：執(zhí)行搜索需要多少存儲(chǔ)空間？最優(yōu)性：如果存在不同的幾個(gè)解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索策略評(píng)價(jià)價(jià)標(biāo)準(zhǔn):2023/1/113有許多智力力問(wèn)題(如梵塔問(wèn)題題、旅行商商問(wèn)題、八八皇后問(wèn)題題、農(nóng)夫過(guò)過(guò)河問(wèn)題等等)和實(shí)際問(wèn)題題（如路徑徑規(guī)劃、機(jī)機(jī)器人行動(dòng)動(dòng)規(guī)劃等））都可以歸歸結(jié)為狀態(tài)空間搜搜索。用狀態(tài)空間搜搜索來(lái)求解問(wèn)題題的系統(tǒng)均均定義一個(gè)個(gè)狀態(tài)空間，并通過(guò)適適當(dāng)?shù)乃阉魉惴ㄔ?.2基于狀態(tài)空空間圖的搜搜索技術(shù)2023/1/114狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(1)狀態(tài)空間的的表示狀態(tài)空間記記為SP，可表示為為二元組：：SP=(S,O)S——問(wèn)題求解（（即搜索））過(guò)程中所所有可能到達(dá)的合法狀態(tài)構(gòu)成的集合合；O——操作算子的集合，操作算子的的執(zhí)行會(huì)導(dǎo)導(dǎo)致問(wèn)題狀狀態(tài)的變遷遷；狀態(tài)——用于記載問(wèn)問(wèn)題求解（（即搜索））過(guò)程中某一時(shí)刻問(wèn)問(wèn)題現(xiàn)狀的的快照；抽象為矢量量形式Q=[q0,q1,…,qn]T每個(gè)元素qi稱為狀態(tài)分量給定每個(gè)個(gè)狀態(tài)分量量qi的值就得得到一個(gè)個(gè)具體的的狀態(tài)Qk=[q0k,q1k,…,qnk]T2023/1/115狀態(tài)表示狀態(tài)態(tài)的變遷遷操作算子子問(wèn)題的狀狀態(tài)空間間是一個(gè)表表示該問(wèn)問(wèn)題的全全部可能能狀態(tài)及及其變遷遷的有向圖。節(jié)點(diǎn)狀態(tài)有向弧狀態(tài)的變變遷弧上的標(biāo)標(biāo)簽導(dǎo)致狀態(tài)態(tài)變遷的的操作算子子用狀態(tài)空間間搜索來(lái)求解2023/1/116例1：走迷宮是人們熟悉悉的一種游游戲。狀態(tài)空間搜搜索2023/1/117格子、入口口和出口——節(jié)點(diǎn)——狀態(tài)通道——有向弧——操作算子迷宮可以由由一個(gè)有向圖表示2023/1/118例2:在一個(gè)3×3的方格棋盤盤上放置著著1,2,3,4,5,6,7,8八個(gè)數(shù)碼，，每個(gè)數(shù)碼碼占一格，，且有一個(gè)個(gè)空格。這這些數(shù)碼可可在棋盤上上移動(dòng)，其其移動(dòng)規(guī)則則是：與空空格相鄰的的數(shù)碼方可可移入空格格。現(xiàn)在的問(wèn)題是：對(duì)于指指定的56741382初始棋局56748321目標(biāo)棋局移動(dòng)數(shù)碼2023/1/119231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123847652023/1/1202023/1/121狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(2)狀態(tài)空間表示示的經(jīng)典例子子“傳教士和和野人問(wèn)題””問(wèn)題的描述：N個(gè)傳教士帶領(lǐng)領(lǐng)N個(gè)野人劃船過(guò)過(guò)河；3個(gè)安全約束條條件：1)船上人數(shù)不得得超過(guò)載重限限量，設(shè)為K個(gè)人；2)任何時(shí)刻（包包括兩岸、船船上）野人數(shù)數(shù)目不得超過(guò)過(guò)傳教士；3)允許在河的某某一岸或者在在船上只有野野人而沒(méi)有傳傳教士；22狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(2)狀態(tài)空間表表示的經(jīng)典典例子“傳傳教士和野野人問(wèn)題””特例：N=3，K=2狀態(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且0≤c≤≤N(左岸沒(méi)有傳傳道士，右右岸一定安安全);N-m=0且0≤N-c≤N(右岸沒(méi)有傳傳道士，左左岸一定安安全);2023/1/123設(shè)初始狀態(tài)下傳教士、、野人和船船都在左岸岸，目標(biāo)狀態(tài)下這三者均均在右岸，，問(wèn)題狀態(tài)以（m,c,b）表示。問(wèn)題的求解解任務(wù)可描描述為：(3,3,1)→(0,0,0)該簡(jiǎn)單問(wèn)題題可能到達(dá)的合法狀態(tài)：可能狀態(tài)總數(shù)：4×4×2=32根據(jù)條件得得出合法狀態(tài)：20m≧c且N-m≧≧N-c(左岸安全且且右岸安全全)m=1,c=1；m=2,c=2m=0且0≤c≤≤N(左岸沒(méi)有傳傳道士)m=0,c=0,1,2,3N-m=0且0≤N-c≤N(右岸沒(méi)有傳傳道士)m=3,c=0,1,2,3不可能到達(dá)達(dá)的合法狀狀態(tài)：(0,0,1),(0,3,0),(3,0,1),(3,3,0)可能到達(dá)的合法狀態(tài)共16個(gè)2023/1/124狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(2)狀態(tài)空間表示示的經(jīng)典例子子“傳教士和和野人問(wèn)題””定義2類操作算子：L(x,y)——指示從左岸到右岸的劃船操作R(x,y)——指示從右岸到左岸的劃船操作x+y≤≤K=2(船的載重限制制)；x和y取值的可能組組合只有5個(gè)10，20，11，01，02(允許在船上只只有野人而沒(méi)沒(méi)有傳教士)共有10個(gè)操作算子2023/1/125渡河問(wèn)題的狀狀態(tài)空間有向向圖2023/1/126狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示由此例可以以看出用狀態(tài)空間間方法表示示問(wèn)題時(shí)，，首先必須須定義狀態(tài)的的描述形式式，通過(guò)使用用這種描述述形式可把把問(wèn)題的一切狀態(tài)都都表示出來(lái)來(lái)。另外，還還要定義一組操操作，通過(guò)使用用這些操作作可把問(wèn)題題由一種狀態(tài)態(tài)轉(zhuǎn)變?yōu)榱砹硪环N狀態(tài)態(tài)。問(wèn)題的求解解過(guò)程是一一個(gè)不斷把操作作作用于狀狀態(tài)的過(guò)程程。如果在使使用某個(gè)操操作后得到到的新狀態(tài)態(tài)是目標(biāo)狀狀態(tài)，就得得到了問(wèn)題題的一個(gè)解解。這個(gè)解解是從初始狀態(tài)到到目標(biāo)狀態(tài)態(tài)所用操作作構(gòu)成的序序列。2023/1/127狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示由此例可以以看出要使問(wèn)題由由一種狀態(tài)態(tài)轉(zhuǎn)變到另另一種狀態(tài)態(tài)時(shí)，就必必須使用一一次操作。。這樣，在在從初始狀狀態(tài)轉(zhuǎn)變到到目標(biāo)狀態(tài)態(tài)時(shí)，就可可能存在多多個(gè)操作序序列(即得到多個(gè)解解)。那么，其中中使用操作最少少或較少的解解才為最優(yōu)解解(因?yàn)橹挥性谑故褂貌僮鲿r(shí)所所付出的代價(jià)價(jià)為最小的解解才是最優(yōu)解解)。對(duì)其中的某一一個(gè)狀態(tài)，可可能存在多個(gè)個(gè)操作．使該該狀態(tài)變到幾幾個(gè)不同的后后繼狀態(tài)．那那么到底用哪哪個(gè)操作進(jìn)行行搜索呢?這就有賴于搜索策略了．不同的搜索策策略有不同的的順序，這就是本章章后面要討論論的問(wèn)題。2023/1/128課堂練練習(xí)有一農(nóng)農(nóng)夫帶帶一只只狐貍貍、一一只小小羊和和一籃籃菜過(guò)過(guò)河（（從左左岸到到右岸岸）。。假設(shè)設(shè)船太太小，，農(nóng)夫夫每次次只能能帶一一樣?xùn)|東西過(guò)過(guò)河；；考慮慮到安安全，，無(wú)農(nóng)農(nóng)夫看看管時(shí)時(shí)，狐狐貍和和小羊羊不能能在一一起，，小羊羊和那那籃菜菜也不不能在在一起起。請(qǐng)請(qǐng)為該該問(wèn)題題的解解決設(shè)設(shè)計(jì)狀狀態(tài)空空間，，并畫畫出狀狀態(tài)空空間圖圖。2023/1/129解析以變量量m、f、s、v分別指指示農(nóng)農(nóng)夫、、狐貍貍、小小羊、、菜,且每個(gè)個(gè)變量量只可可取值值1(表示在在左岸岸)或0(表示在在右岸岸)。問(wèn)題題狀態(tài)態(tài)可以以四元元組(m、f、s、v)描述,設(shè)初始始狀態(tài)態(tài)下均均在左左岸,目標(biāo)狀狀態(tài)下下都到到達(dá)右右岸。。從而而,問(wèn)題求求解任任務(wù)可可描述述為(1,1,1,1)->(0,0,0,0)由于問(wèn)問(wèn)題簡(jiǎn)簡(jiǎn)單,狀態(tài)空空間中中可能能的狀狀態(tài)總總數(shù)為為2×2×2×2=16,由于要要遵從從安全全限制制,合法的的狀態(tài)態(tài)只有有(除初、、目狀狀態(tài)外外):1110，1101，1011，1010，0101，0001，0010，0100；不不合法法狀態(tài)態(tài)有:0111,1000,1100,0011,0110,1001設(shè)計(jì)二二類操操作算算子:Lx、Rx,x為m、f、s、v時(shí)分別別指示示農(nóng)夫夫獨(dú)自自,帶狐貍貍,帶小羊羊,帶菜過(guò)過(guò)河；；狀態(tài)態(tài)空間間圖如如下所所示.由于Lx和Rx是互逆逆操作作,故而解解答路路徑可可有無(wú)無(wú)數(shù)條條,但最近近的只只有二二條;都是7個(gè)操作作步.思考：：為什什么不不把船船的狀狀態(tài)放放到狀狀態(tài)空空間中中去？？2023/1/130解析:四元組組(m、f、s、v)2023/1/131狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(3)狀態(tài)空間的搜搜索狀態(tài)空間的搜搜索記為SE，可表示為五五元組：SE=(S,O,E,I,G)；E——搜索引擎；I——問(wèn)題的初始狀狀態(tài)，I∈S；G——問(wèn)題的目標(biāo)狀狀態(tài)集合，GS。搜索引擎E——可以設(shè)計(jì)為實(shí)現(xiàn)任何搜索索算法的控制系統(tǒng)。。基本思想——通過(guò)搜索引擎擎E尋找一個(gè)操作算子的調(diào)調(diào)用序列，使問(wèn)題從初初始狀態(tài)I變遷到目標(biāo)狀狀態(tài)G之一。解答路徑——初-目變遷過(guò)程中中的狀態(tài)序列或相應(yīng)的操作算子調(diào)用用序列。2023/1/132狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示或圖（一般般圖）一個(gè)狀態(tài)可以有多個(gè)可供供選擇的操作算子子；操作算子間間的選擇是是一種“或”的關(guān)系;這樣的有向向圖稱為或圖。2023/1/133狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(3)狀態(tài)空間的的搜索或圖（一般般圖）一個(gè)狀態(tài)可可以有多個(gè)個(gè)可供選擇擇的操作算算子；操作算子間間的選擇是是一種“或”的關(guān)關(guān)系系，，這樣樣的的有有向向圖圖稱稱為為或圖圖。。狀態(tài)態(tài)空空間間一般般都都表表示示為為或圖圖（（一一般般圖圖））搜索索圖圖———在搜索索解解答答路路徑徑的過(guò)過(guò)程程中中畫畫出出搜搜索索時(shí)時(shí)涉涉及及到到的的節(jié)節(jié)點(diǎn)點(diǎn)和和弧弧線線，，構(gòu)構(gòu)成成所所謂謂的的搜索索圖圖。狀態(tài)態(tài)空空間間搜搜索索一般般圖圖搜搜索索2023/1/134狀態(tài)空空間搜搜索——1.狀態(tài)空空間及及其搜搜索的的表示示(3)狀態(tài)空空間的的搜索索狀態(tài)空空間、搜索圖圖和解答路路徑之間的的關(guān)系系S0Sg2023/1/135狀態(tài)空間搜索索——1.狀態(tài)空間及其其搜索的表示示(4)一般圖搜索例例子——八數(shù)碼游戲求解的問(wèn)題：：給定初始布局局(即初始狀態(tài))和目標(biāo)布局(即目標(biāo)狀態(tài))，如何移動(dòng)數(shù)碼碼才能從初始始布局到達(dá)目目標(biāo)布局？解答就是一個(gè)合法法的棋牌走步序列列。初始布局目標(biāo)布局移動(dòng)數(shù)碼2023/1/136狀態(tài)態(tài)空空間間搜搜索索———1.狀態(tài)態(tài)空空間間及及其其搜搜索索的的表表示示(4)一般般圖圖搜搜索索例例子子———八數(shù)數(shù)碼碼游游戲戲用一一般般圖圖搜搜索索方方法法解解決決該該問(wèn)問(wèn)題題的的步步驟驟：：1、為為問(wèn)題題狀狀態(tài)態(tài)的表表示示建建立立數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)2、制制定定操作作算算子子集合合3、設(shè)設(shè)計(jì)計(jì)搜索索引引擎擎第一一步步：：為為問(wèn)問(wèn)題題狀狀態(tài)態(tài)的的表表示示建建立立數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)3××3的一一個(gè)個(gè)矩矩陣陣S矩陣陣元元素素Sij∈∈{0,1,2,3,4,5,6,7,8},其中1≤i,j≤3數(shù)字0表示空格數(shù)字1-8表示相應(yīng)的的棋牌八數(shù)碼問(wèn)題題就可表示示為：2023/1/137狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示初始布局目標(biāo)布局移動(dòng)數(shù)碼(4)一般圖搜索索例子——八數(shù)碼游戲戲2023/1/138狀態(tài)空間搜搜索——1.狀態(tài)空間及及其搜索的的表示(4)一般圖搜索索例子——八數(shù)碼游戲戲第二步：制制定操作算算子集直觀方法——為每個(gè)棋牌牌制定一套套可能的走走步：左、、上、右、、下四種移移動(dòng)。需要32個(gè)操作算子子簡(jiǎn)易方法——僅為空格制制定這4種走步。僅需4個(gè)操作算子子第三步：設(shè)設(shè)計(jì)搜索引引擎問(wèn)題狀態(tài)空空間的大小小與問(wèn)題題涉涉及及的的元元素素個(gè)數(shù)數(shù)是是程程指數(shù)數(shù)級(jí)級(jí)爆爆炸炸式式增增長(zhǎng)長(zhǎng)（即即，，組合合爆爆炸炸問(wèn)問(wèn)題題）如，，棋棋盤盤布布局局（（問(wèn)問(wèn)題題狀狀態(tài)態(tài)））總總共共有有9!=362880個(gè)研究究焦焦點(diǎn)點(diǎn)是解決決組組合合爆爆炸炸問(wèn)問(wèn)題題，通過(guò)過(guò)壓壓縮縮搜搜索索空空間間，提高高搜搜索索效效率率。2023/1/139狀態(tài)態(tài)空空間間搜搜索索———1.狀態(tài)態(tài)空空間間及及其其搜搜索索的的表表示示狀態(tài)態(tài)空空間間、搜索索圖圖和解答答路路徑徑之間間的的關(guān)關(guān)系系S0Sg2023/1/140狀態(tài)空間間搜索——2.一般圖搜搜索策略略（1）搜索術(shù)術(shù)語(yǔ)1、節(jié)點(diǎn)深深度根節(jié)點(diǎn)指示初始狀態(tài)態(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搜索圖2023/1/141狀態(tài)空間間搜索——2.一般圖搜搜索策略略（1）搜索術(shù)術(shù)語(yǔ)2、節(jié)點(diǎn)擴(kuò)擴(kuò)展應(yīng)用操作算子子將上一狀態(tài)態(tài)（節(jié)點(diǎn)ni）變遷到到下一狀態(tài)態(tài)（節(jié)點(diǎn)nj）節(jié)點(diǎn)ni稱為被擴(kuò)展節(jié)節(jié)點(diǎn)（父節(jié)點(diǎn)點(diǎn)）節(jié)點(diǎn)nj稱為ni的子節(jié)點(diǎn)節(jié)點(diǎn)ni節(jié)點(diǎn)nj2023/1/142（1）搜索術(shù)術(shù)語(yǔ)3、路徑節(jié)點(diǎn)ni到nj的路徑是是由相鄰鄰節(jié)點(diǎn)間間的弧線構(gòu)成成的折線線要求路徑徑是無(wú)環(huán)環(huán)的4、路徑代代價(jià)——相鄰節(jié)點(diǎn)點(diǎn)ni和ni+1間的路徑代價(jià)價(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)nj2023/1/143狀態(tài)態(tài)空空間間搜搜索索———2.一般般圖圖搜搜索索策策略略（1）搜搜索索術(shù)術(shù)語(yǔ)語(yǔ)4、路路徑徑代代價(jià)價(jià)目標(biāo)標(biāo)狀狀態(tài)態(tài)節(jié)節(jié)點(diǎn)點(diǎn)ng節(jié)點(diǎn)點(diǎn)ni節(jié)點(diǎn)點(diǎn)nkC(nk,ng)C(ni,nk)C(ni,ng)2023/1/144狀態(tài)空空間搜搜索——2.一般圖圖搜索索策略略（2）一般般圖搜搜索算算法符號(hào)說(shuō)說(shuō)明：：s-初始狀狀態(tài)節(jié)節(jié)點(diǎn)G-搜索圖圖OPEN-存放待擴(kuò)展展節(jié)點(diǎn)點(diǎn)的表CLOSE-存放已被擴(kuò)擴(kuò)展的的節(jié)點(diǎn)點(diǎn)的表MOVE-FIRST(OPEN)-取OPEN表首的的節(jié)點(diǎn)點(diǎn)作為當(dāng)前要要被擴(kuò)擴(kuò)展的的節(jié)點(diǎn)點(diǎn)n，同時(shí)時(shí)將節(jié)點(diǎn)點(diǎn)n移至CLOSE表一般圖圖搜索索算法法劃分分為二二個(gè)階階段：：1、初始始化2、搜索索循環(huán)環(huán)2023/1/145狀態(tài)空空間搜搜索——2.一般圖圖搜索索策略略（2）一般般圖搜搜索算算法算法劃劃分為為二個(gè)個(gè)階段段：1、初始始化建立只包含含初始始狀態(tài)態(tài)節(jié)點(diǎn)點(diǎn)s的搜索索圖G:={s}OPEN:={s}CLOSE:={}2、搜索索循環(huán)環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的的節(jié)點(diǎn)點(diǎn)n作為擴(kuò)擴(kuò)展的的節(jié)點(diǎn)點(diǎn)，同同時(shí)將將其移移到close表擴(kuò)展出出n的子節(jié)節(jié)點(diǎn),插入搜索圖圖G和OPEN表適當(dāng)?shù)牡臉?biāo)記記和修修改指指針排序OPEN表通過(guò)循循環(huán)地地執(zhí)行行該算算法，，搜索圖圖G會(huì)因不不斷有有新節(jié)節(jié)點(diǎn)加加入而而逐步步長(zhǎng)大大，直直到搜搜索到到目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)。2023/1/146以下面的八數(shù)數(shù)碼為例，看看一般圖的搜搜索算法初始布局目標(biāo)布局移動(dòng)數(shù)碼狀態(tài)空間搜索索——2.一般圖搜索策策略2023/1/1472023/1/1482023/1/1492023/1/1502023/1/1512023/1/1522023/1/1532023/1/1542023/1/1552023/1/1562023/1/1572023/1/1582023/1/1592023/1/1602023/1/1612023/1/1622023/1/1632023/1/1642023/1/1652023/1/166狀態(tài)態(tài)空空間間搜搜索索———2.一般般圖圖搜搜索索策策略略（2）一一般般圖圖搜搜索索算算法法———搜索索過(guò)過(guò)程程中中的的指指針針修修改改節(jié)點(diǎn)點(diǎn)n擴(kuò)展展后后的子子節(jié)節(jié)點(diǎn)點(diǎn)分分為為3類：(i)全新新節(jié)節(jié)點(diǎn)點(diǎn)(ii)已出出現(xiàn)現(xiàn)在在OPEN表中的的節(jié)節(jié)點(diǎn)點(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é)節(jié)點(diǎn)的路徑代價(jià)經(jīng)由新父節(jié)節(jié)點(diǎn)n的代價(jià)比較較小，則將將原子節(jié)點(diǎn)點(diǎn)指向老父父節(jié)點(diǎn)的指指針，修改改為指向新新父節(jié)點(diǎn)n(iii)類節(jié)點(diǎn)還得得從CLOSE表中移出，，重新加入入OPEN表。2023/1/167狀態(tài)空間搜搜索——2.一般圖搜索索策略Sn4ninjn1n2n3n31n32節(jié)點(diǎn)ni是當(dāng)前擴(kuò)展展的節(jié)點(diǎn)；；擴(kuò)展出4個(gè)后續(xù)節(jié)點(diǎn)點(diǎn)；n1、n2是新節(jié)點(diǎn)，只需建立指指向父節(jié)點(diǎn)點(diǎn)的指針，，并加入OPEN表；2023/1/168狀態(tài)空間搜索索——2.一般圖搜索策策略Sn4ninjn1n2n3n31n32n4已經(jīng)存在于OPEN表，并且已有有父節(jié)點(diǎn)njn4經(jīng)nj的路徑代價(jià)大大取消n4指向nj的指針改為建立n4指向新父節(jié)點(diǎn)點(diǎn)ni的指針n3已經(jīng)存在于CLOSE表，并且已有有父節(jié)點(diǎn)nj需要做和n4同樣的比較和和指針修改工工作。并且要要重新加入open表。2023/1/169狀態(tài)空空間搜搜索——2.一般圖圖搜索索策略略（2）一般般圖搜搜索算算法OPEN表中節(jié)節(jié)點(diǎn)簡(jiǎn)簡(jiǎn)單的的排序序方式式：深度優(yōu)優(yōu)先——擴(kuò)展當(dāng)當(dāng)前節(jié)節(jié)點(diǎn)后后生成成的子子節(jié)點(diǎn)點(diǎn)總是是置于OPEN表的前前端，即OPEN表作為棧，后進(jìn)先先出，使搜索優(yōu)優(yōu)先向向縱深深方向向發(fā)展展。2023/1/170深度優(yōu)先實(shí)例例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123468911131416181912384765目標(biāo)571012151720212023/1/171深度度優(yōu)優(yōu)先先搜搜索索在深深度度優(yōu)優(yōu)先先搜搜索索中中，，首首先先擴(kuò)擴(kuò)展展最最新新產(chǎn)產(chǎn)生生的的(最深深的的)節(jié)點(diǎn)點(diǎn)，，深深度度相相等等的的節(jié)節(jié)點(diǎn)點(diǎn)可可以以任任意意排排列列。。“最晚產(chǎn)產(chǎn)生的的節(jié)點(diǎn)點(diǎn)最先先擴(kuò)展展”起始節(jié)節(jié)點(diǎn)深深度為為0任何其其他節(jié)節(jié)點(diǎn)的的深度度等于于其父父輩節(jié)節(jié)點(diǎn)深深度加加上1:dn=dn-1+12023/1/172深度優(yōu)優(yōu)先搜搜索很明顯顯這樣樣做，，不一定定找到最最佳解解，而而且由由于深深度的的限制制，可可能找找不到到解，，然而而，若若不加加深度度限制制，可可能沿沿著一一條路路線無(wú)無(wú)限制制地?cái)U(kuò)擴(kuò)展下下去，，這當(dāng)當(dāng)然是是不允允許的的。為保證證找到到解，，應(yīng)選選擇適適當(dāng)?shù)牡纳疃冉缃缦蓿蛘哒卟扇∪〔粩鄶嗉哟蟠笊疃榷冉缦尴薜霓k辦法，，反復(fù)復(fù)搜索索，直直到找找到解解。這這種改改進(jìn)的的方法法叫做做迭代加加深搜搜索。2023/1/173ProcedureDepthFirstSearchBegin把初始始節(jié)點(diǎn)點(diǎn)壓入入棧，，并設(shè)設(shè)置棧棧頂指指針；；While棧不空空doBegin彈出棧棧頂元元素；；If棧頂元元素=goal，成功功返回回并結(jié)結(jié)束；；Else以任意意次序序把棧棧頂元元素的的子女女壓入入棧中中；EndWhileEnd基于棧棧實(shí)現(xiàn)現(xiàn)的深深度優(yōu)優(yōu)先搜搜索算算法：：2023/1/174初始節(jié)點(diǎn)點(diǎn)放到棧棧中，棧棧指針指指向棧的的最上邊邊的元素素。為了對(duì)該該節(jié)點(diǎn)進(jìn)進(jìn)行檢測(cè)測(cè)，需要要從棧中中彈出該該節(jié)點(diǎn)，，如果是是目標(biāo)，，該算法法結(jié)束，，否則把把其子節(jié)節(jié)點(diǎn)以任任何順序序壓入棧棧中。該該過(guò)程直直到棧變變成為空空。遍歷一棵樹的的過(guò)程（（下圖））。2023/1/175深度優(yōu)先搜索索的性質(zhì)一般不能保證證找到最優(yōu)解解當(dāng)深度限制不不合理時(shí)，可能找不到解解，可以將算法法改為可變深度限制制最壞情況時(shí)，，搜索空間等等同于窮舉是一個(gè)通用的的與問(wèn)題無(wú)關(guān)關(guān)的方法2023/1/176深度優(yōu)先搜搜索的優(yōu)點(diǎn)是比寬度優(yōu)優(yōu)先搜索算算法需要較較少的空間間，該算法法只需要保保存搜索樹樹的一部分分，它由當(dāng)當(dāng)前正在搜搜索的路徑徑和該路徑徑上還沒(méi)有有完全展開開的節(jié)點(diǎn)標(biāo)標(biāo)志所組成成。深度優(yōu)先搜搜索的存儲(chǔ)儲(chǔ)器要求是是深度約束束的線性函函數(shù)。深度優(yōu)先搜搜索的優(yōu)點(diǎn)點(diǎn)2023/1/177深度度優(yōu)優(yōu)先先搜搜索索的的缺缺點(diǎn)點(diǎn)既不不是是完完備備的的，，也也不不是是最最優(yōu)優(yōu)的的。。主要要問(wèn)問(wèn)題題是是可可能能搜搜索索到到了了錯(cuò)錯(cuò)誤誤的的路路徑徑上上。。很很多多問(wèn)問(wèn)題題可可能能具具有有很很深深甚甚至至是是無(wú)無(wú)限限的的搜搜索索樹樹，，如如果果不不幸幸選選擇擇了了一一個(gè)個(gè)錯(cuò)錯(cuò)誤誤的的路路徑徑，，則則深深度度優(yōu)優(yōu)先先搜搜索索會(huì)會(huì)一一直直搜搜索索下下去去，，而而不不會(huì)會(huì)回回到到正正確確的的路路徑徑上上。。這這樣樣一一來(lái)來(lái)對(duì)對(duì)于于這這些些問(wèn)問(wèn)題題，，深深度度優(yōu)優(yōu)先先搜搜索索要要么么陷陷入入無(wú)無(wú)限限的的循循環(huán)環(huán)而而不不能能給給出出一一個(gè)個(gè)答答案案，，要要么么最最后后找找到到一一個(gè)個(gè)答答案案，，但但路路徑徑很很長(zhǎng)長(zhǎng)而而且且不不是是最最優(yōu)優(yōu)的的答答案案。。2023/1/178狀態(tài)空間搜索索——2.一般圖搜索策策略（2）一般圖搜索索算法OPEN表中節(jié)點(diǎn)簡(jiǎn)單單的排序方式式：深度優(yōu)先——擴(kuò)展當(dāng)前節(jié)點(diǎn)點(diǎn)后生成的子子節(jié)點(diǎn)總是置于OPEN表的前端，即OPEN表作為棧，后進(jìn)先出，使搜索優(yōu)先向縱縱深方向發(fā)展展。寬度優(yōu)先——擴(kuò)展當(dāng)前節(jié)點(diǎn)點(diǎn)后生成的子子節(jié)點(diǎn)總是置于OPEN表的后端，即OPEN表作為隊(duì)列，先進(jìn)先出，使搜索優(yōu)先向橫橫向方向發(fā)展展。2023/1/179寬度優(yōu)先實(shí)例例23184765283147652318476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)8234187654910111213141516172023/1/180寬度優(yōu)優(yōu)先搜搜索如果搜搜索是是以接接近起起始節(jié)節(jié)點(diǎn)的的程度度依次次擴(kuò)展展節(jié)點(diǎn)點(diǎn)的，，那么么這種種搜索索就叫叫做寬度優(yōu)優(yōu)先搜搜索。。這種搜搜索是是逐層層進(jìn)行行的，，在對(duì)對(duì)下一一層的的任意意節(jié)點(diǎn)點(diǎn)進(jìn)行行搜索索之前前，必必須搜搜索完完本層層的所所有節(jié)節(jié)點(diǎn)。。“先產(chǎn)產(chǎn)生的的節(jié)點(diǎn)點(diǎn)先擴(kuò)擴(kuò)展””2023/1/181ProcedureBreadth-first-searchBegin把初始始節(jié)點(diǎn)點(diǎn)放入入隊(duì)列列；Repeat取得隊(duì)隊(duì)列最最前面面的元元素為為current;Ifcurrent=goal成功返返回并并結(jié)束束；ElsedoBegin如果current有子女女，則則current的子女女以任意意次序序添加加到隊(duì)隊(duì)列的的尾部部；EndUntil隊(duì)列為為空End采用隊(duì)隊(duì)列結(jié)結(jié)構(gòu)，，寬度度優(yōu)先先算法法可以以表示示如下下：2023/1/182寬度優(yōu)先搜搜索算法原原理：如果當(dāng)前的的節(jié)點(diǎn)不是是目標(biāo)節(jié)點(diǎn)點(diǎn)，則把當(dāng)當(dāng)點(diǎn)節(jié)點(diǎn)的的子孫以任任意順序增增加到隊(duì)列列的后面，，并把隊(duì)列列的前端元元素定義為為current。如果目標(biāo)發(fā)發(fā)現(xiàn)，則算算法終止。。2023/1/183寬度優(yōu)先搜搜索的性質(zhì)質(zhì)當(dāng)問(wèn)題有解解時(shí)，一定能找到解當(dāng)問(wèn)題為單單位代價(jià)時(shí)時(shí)，且問(wèn)題題有解時(shí)，，一定能找到到最優(yōu)解方法與問(wèn)題題無(wú)關(guān)，具具有通用性性效率較低屬于圖搜索索方法2023/1/184寬度優(yōu)先先搜索是一種盲盲目搜索索，時(shí)間間和空間間復(fù)雜度度都比較較高，當(dāng)當(dāng)目標(biāo)節(jié)節(jié)點(diǎn)距離離初始節(jié)節(jié)點(diǎn)較遠(yuǎn)遠(yuǎn)時(shí)會(huì)產(chǎn)產(chǎn)生許多多無(wú)用的的節(jié)點(diǎn)，，搜索效效率低。。寬度優(yōu)先先搜索中中，時(shí)間間需求是是一個(gè)很很大的問(wèn)問(wèn)題，特特別是當(dāng)當(dāng)搜索的的深度比比較大時(shí)時(shí)，尤為為嚴(yán)重，，但是空空間需求求是比執(zhí)執(zhí)行時(shí)間間更嚴(yán)重重的問(wèn)題題。寬度優(yōu)先先搜索優(yōu)優(yōu)點(diǎn)：目標(biāo)節(jié)點(diǎn)點(diǎn)如果存存在，用用寬度優(yōu)優(yōu)先搜索索算法總總可以找找到該目目標(biāo)節(jié)點(diǎn)點(diǎn)，而且且是最小小（即最最短路徑徑）的節(jié)節(jié)點(diǎn)。寬度優(yōu)先先搜索的的優(yōu)點(diǎn)和和缺點(diǎn)2023/1/185總結(jié)適用場(chǎng)場(chǎng)合深度優(yōu)優(yōu)先——當(dāng)一個(gè)個(gè)問(wèn)題題有多多個(gè)解解答或或多條條解答答路徑徑，且且只須須找到到其中中一個(gè)個(gè)時(shí)；；往往往應(yīng)對(duì)對(duì)搜索索深度度加以以限制制。寬度優(yōu)優(yōu)先——確保搜搜索到到最短短的解解答路路徑。。共同優(yōu)優(yōu)缺點(diǎn)點(diǎn)：可直接接應(yīng)用用一般般圖搜搜索算算法實(shí)實(shí)現(xiàn)，，不需需要設(shè)設(shè)計(jì)特特別的的節(jié)點(diǎn)點(diǎn)排序序方法法，從從而簡(jiǎn)簡(jiǎn)單易易行，，適合合于許許多復(fù)復(fù)雜度度不高高的問(wèn)問(wèn)題求求解任任務(wù)。。節(jié)點(diǎn)排排序的的盲目目性，，由于于不采采用領(lǐng)領(lǐng)域?qū)ｉT知知識(shí)去去指導(dǎo)導(dǎo)排序序，往往往會(huì)會(huì)在白白白搜搜索了了大量量無(wú)關(guān)關(guān)的狀狀態(tài)節(jié)節(jié)點(diǎn)后后才碰碰到解解答，，所以以也稱稱為盲目搜搜索。2023/1/186有界深度搜搜索和迭代代加深搜索索有界深度優(yōu)優(yōu)先搜索過(guò)程總體上上按深度優(yōu)優(yōu)先算法方方法進(jìn)行，，但對(duì)搜索索深度需要要給出一個(gè)個(gè)深度限制制dm，當(dāng)深度達(dá)達(dá)到了dm的時(shí)候，如如果還沒(méi)有有找到解答答，就停止止對(duì)該分支支的搜索，，換到另外外一個(gè)分支支進(jìn)行搜索索。2023/1/187策略說(shuō)明:（1）深度限制dm很重要。當(dāng)問(wèn)題有解，，且解的路徑徑長(zhǎng)度小于或或等于dm時(shí)，則搜索過(guò)過(guò)程一定能夠夠找到解，但但是和深度優(yōu)優(yōu)先搜索一樣樣這并不能保保證最先找到到的是最優(yōu)解解。但是當(dāng)dm取得太小，解解的路徑長(zhǎng)度度大于dm時(shí)，則搜索過(guò)過(guò)程中就找不不到解，即這這時(shí)搜索過(guò)程程甚至是不完完備的。2023/1/188（2）深度限限制dm不能太太大。當(dāng)dm太大時(shí)時(shí)，搜搜索過(guò)過(guò)程會(huì)會(huì)產(chǎn)生生過(guò)多多的無(wú)無(wú)用節(jié)節(jié)點(diǎn)，，既浪浪費(fèi)了了計(jì)算算機(jī)資資源，，又降降低了了搜索索效率率。（3）有界界深度度搜索索的主主要問(wèn)問(wèn)題是是深度限限制值值dm的選取取。2023/1/189改進(jìn)方法法：（迭迭代加深深搜索））先任意給給定一個(gè)個(gè)較小的的數(shù)作為為dm，然后按按有界深深度算法法搜索，，若在此此深度限限制內(nèi)找找到了解解，則算算法結(jié)束束；如在在此限制制內(nèi)沒(méi)有有找到問(wèn)問(wèn)題的解解，則增增大深度度限制dm，繼續(xù)搜搜索。2023/1/190迭代加深搜索索，試圖嘗試所所有可能的深深度限制：首先深度為0，然后深度為1，然后為2，等等。如果初始深度度為0，則該算法只只生成根節(jié)點(diǎn)點(diǎn)，并檢測(cè)它它。如果根節(jié)點(diǎn)不不是目標(biāo)，則則深度加1，通過(guò)典型的的深度優(yōu)先算算法，生成深深度為1的樹。當(dāng)深度限制為為m時(shí)，樹的深度度為m。2023/1/191迭代加深搜索索看起來(lái)會(huì)很很浪費(fèi)，因?yàn)闉楹芏喙?jié)點(diǎn)都都可能擴(kuò)展多多次。然而對(duì)于很多多問(wèn)題，這種種多次的擴(kuò)展展負(fù)擔(dān)實(shí)際上上很小，直覺(jué)覺(jué)上可以想象象，如果一棵棵樹的分支系系數(shù)很大，幾幾乎所有的節(jié)節(jié)點(diǎn)都在最底底層上，則對(duì)對(duì)于上面各層層節(jié)點(diǎn)擴(kuò)展多多次對(duì)整個(gè)系系統(tǒng)來(lái)說(shuō)影響響不是很大。。2023/1/192搜索最優(yōu)策略略的比較表注：b是分支系數(shù)，，d是解答的深度度，m是搜索樹的最最大深度，l是深度限制。。2023/1/193寬度優(yōu)先搜索索、深度優(yōu)先先搜索和迭代代加深搜索都都可以用于生生成和測(cè)試算算法。寬度度優(yōu)優(yōu)先先搜搜索索需要要指指數(shù)數(shù)數(shù)數(shù)量量的的空空間間，，深深度度優(yōu)優(yōu)先先搜搜索索的的空空間間復(fù)復(fù)雜雜度度和和最最大大搜搜索索深深度度呈呈線線性性關(guān)關(guān)系系。。2023/1/194迭代加深深搜索對(duì)一棵深深度受控控的樹采采用深度度優(yōu)先的的搜索。。它結(jié)合合了寬度度優(yōu)先和和深度優(yōu)優(yōu)先搜索索的優(yōu)點(diǎn)點(diǎn)。和寬度優(yōu)優(yōu)先搜索索一樣，，它是最最優(yōu)的，，也是完完備的。。但對(duì)空空間要求求和深度度優(yōu)先搜搜索一樣樣是適中中的。2023/1/195一般圖搜搜索算法法常用的簡(jiǎn)簡(jiǎn)單方式式：深度優(yōu)先先寬度優(yōu)先先【缺點(diǎn)：節(jié)節(jié)點(diǎn)排序序的盲目目性】在白白搜索了大大量無(wú)關(guān)關(guān)的狀態(tài)態(tài)節(jié)點(diǎn)后才碰到到解答，，效率低提高一般圖搜搜索效率的關(guān)鍵優(yōu)化OPEN表中節(jié)點(diǎn)點(diǎn)的排序序方式盲目搜索索3.4啟發(fā)式搜搜索★2023/1/196125634最理想情情況：每次排序序后OPEN表表首元素素n總在解答答路徑上上2023/1/197啟發(fā)式搜索索啟發(fā)式知識(shí)識(shí)指導(dǎo)OPEN表排序的一般圖搜索索：全局排序——對(duì)OPEN表中的所有節(jié)點(diǎn)排排序，使最有希望的節(jié)點(diǎn)排在在表首。A算法，A*算法（掌握握！）局部排序——僅對(duì)新擴(kuò)展出來(lái)的的子節(jié)點(diǎn)排排序，使這些新節(jié)點(diǎn)中最有希望者能優(yōu)先取取出考察和和擴(kuò)展；爬山法（了了解，對(duì)深度優(yōu)先法法的改進(jìn)）；2023/1/198啟發(fā)式搜索索——1.A算法（掌握）【基本思想】設(shè)計(jì)體現(xiàn)啟啟發(fā)式知識(shí)識(shí)的評(píng)價(jià)函數(shù)f(n)；指導(dǎo)一般圖搜索索中OPEN表待擴(kuò)展節(jié)節(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)點(diǎn)n到達(dá)目標(biāo)節(jié)節(jié)點(diǎn)ng，估計(jì)的最小路徑代代價(jià)；g(n)-G中從s到n，目前實(shí)際的路徑代價(jià)價(jià)；h(n)-從n到ng，估計(jì)的最小路徑徑代價(jià)；2023/1/199啟發(fā)式搜索索——1.A算法（掌握）Snng目標(biāo)狀態(tài)節(jié)節(jié)點(diǎn)ng初始狀態(tài)節(jié)節(jié)點(diǎn)S節(jié)點(diǎn)n搜索圖Gh(n):n-ng的估計(jì)最小小路徑代價(jià)價(jià)g(n):s-n的實(shí)際路徑徑代價(jià)f(n):s-n-ng的估計(jì)最小路徑代代價(jià)2023/1/1100啟發(fā)發(fā)式式搜搜索索———1.A算法法（（掌握握）【評(píng)價(jià)價(jià)函函數(shù)數(shù)f(n)=g(n)+h(n)（掌掌握握））】n-搜索索圖圖G中的節(jié)節(jié)點(diǎn)點(diǎn)；f(n)-G中從從s經(jīng)n到ng，估計(jì)計(jì)的最小小路路徑徑代代價(jià)價(jià)；g(n)-G中從從s到n，目前實(shí)實(shí)際的路徑徑代價(jià)價(jià)；h(n)-從n到ng，估計(jì)的最小路路徑代代價(jià)；h(n)值-依賴于于啟發(fā)式式知識(shí)識(shí)加以計(jì)計(jì)算；；h(n)稱為啟發(fā)式式函數(shù)數(shù)（掌握意意義！！）。如何用用評(píng)價(jià)價(jià)函數(shù)數(shù)來(lái)實(shí)實(shí)現(xiàn)A算法?（掌握！！）2023/1/1101啟發(fā)式式搜索索——1.A算法（（掌握）A算法的設(shè)計(jì)計(jì)與一般圖圖搜索索相同，，劃分分為二二個(gè)階階段：：1、初始始化建立只只包含含初始始狀態(tài)態(tài)節(jié)點(diǎn)點(diǎn)s的搜索索圖G:={s}OPEN:={s}CLOSE:={}2、搜索索循環(huán)環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點(diǎn)點(diǎn)n⑥擴(kuò)展出出n的子節(jié)節(jié)點(diǎn),插入搜搜索圖圖G和OPEN表⑦適當(dāng)?shù)牡臉?biāo)記記和修修改指指針（（子節(jié)點(diǎn)點(diǎn)父節(jié)節(jié)點(diǎn)）⑧排序OPEN表（評(píng)價(jià)函函數(shù)f(n)的值排排序））通過(guò)循循環(huán)地地執(zhí)行行該算算法，，搜索索圖會(huì)會(huì)因不不斷有有新節(jié)節(jié)點(diǎn)加加入而而逐步步長(zhǎng)大大，直直到搜搜索到到目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)。2023/1/1102啟發(fā)式搜搜索——1.A算法（掌握）算法A的設(shè)計(jì)與與一般圖圖搜索類類似，劃劃分為二二個(gè)階段段：1、初始化化2、搜索循循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)節(jié)點(diǎn)n⑥擴(kuò)展出n的子節(jié)點(diǎn)點(diǎn),插入搜索索圖G和OPEN表對(duì)每個(gè)子子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni)⑦適當(dāng)?shù)臉?biāo)標(biāo)記和修修改指針針（子節(jié)點(diǎn)父節(jié)點(diǎn)點(diǎn)）⑧排序OPEN表（評(píng)價(jià)函函數(shù)f(n)的值排序序）2023/1/1103啟發(fā)式搜搜索——1.A算法（掌握）⑥擴(kuò)展出n的子節(jié)點(diǎn)點(diǎn),插入搜索索圖G和OPEN表對(duì)每個(gè)子子節(jié)點(diǎn)ni,計(jì)算f(n,ni)=g(n,ni)+h(ni)⑦適當(dāng)?shù)臉?biāo)標(biāo)記和修修改指針針（子節(jié)點(diǎn)父節(jié)點(diǎn)點(diǎn)）(i)全新節(jié)點(diǎn)點(diǎn)：f(ni)=f(n,ni)(ii)已出現(xiàn)在在OPEN表中的節(jié)點(diǎn)點(diǎn)(iii)已出現(xiàn)的的CLOSE表中的節(jié)點(diǎn)點(diǎn)IFf(ni)>f(n,ni)THEN修改指針針指向新父結(jié)點(diǎn)nf(ni)=f(n,ni)⑧排序OPEN表（f(n)值從小到到大排序序）2023/1/11042.若OPEN表是空表表，則失失敗退出出；算法A3.選擇擇OPEN表上上的的第第一一個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn)，，把把它它從從OPEN表移移出出并并放放進(jìn)進(jìn)CLOSE表中中，，稱稱此此節(jié)節(jié)點(diǎn)點(diǎn)為為節(jié)節(jié)點(diǎn)點(diǎn)n；1.建立立一一個(gè)個(gè)只包包含含起起始始節(jié)節(jié)點(diǎn)點(diǎn)S的搜搜索索圖圖G,把S放到到一一個(gè)個(gè)叫叫OPEN的未未擴(kuò)擴(kuò)展展節(jié)節(jié)點(diǎn)點(diǎn)表表中中；；建建立立一一個(gè)個(gè)叫叫做做CLOSE的已已擴(kuò)擴(kuò)展展節(jié)節(jié)點(diǎn)點(diǎn)表表，，其其初初始始為為空空表表；；5.擴(kuò)展展節(jié)節(jié)點(diǎn)點(diǎn)n，同同時(shí)時(shí)生生成成不不是是n的祖祖先先的的那那些些子子節(jié)節(jié)點(diǎn)點(diǎn)的的集集合合M,把M的這這些些成成員員作作為為n的后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)添添入入圖圖G中；；對(duì)于于M中每每個(gè)個(gè)子子節(jié)節(jié)點(diǎn)點(diǎn)ni,計(jì)算算f(n,ni)=g(n,ni)+h(ni);4.若n為一一目目標(biāo)標(biāo)節(jié)節(jié)點(diǎn)點(diǎn)，，則則有有解解成成功功退退出出，，此此解解是是追追蹤蹤圖圖G中沿沿著著指指針針從從n到S這條條路路徑徑而而得得到到的的；；2023/1/11056.對(duì)那那些些未未曾曾在在G中出出現(xiàn)現(xiàn)過(guò)過(guò)的的M成員員（（全全新新節(jié)節(jié)點(diǎn)點(diǎn)））設(shè)設(shè)置置一一個(gè)個(gè)通通向向n的指指針針。。把把M的這這些些成成員員加加進(jìn)進(jìn)OPEN表。。對(duì)對(duì)已已經(jīng)經(jīng)在在OPEN表上上的的每每一一個(gè)個(gè)M成員員，，比較較子子節(jié)節(jié)點(diǎn)點(diǎn)ni經(jīng)由由新新、、老老父父節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)價(jià)價(jià)函函數(shù)數(shù)值值f(n,ni)、f(ni);若f(n,ni)<f(ni)點(diǎn),則令f(ni)=f(n,ni),并移動(dòng)動(dòng)子節(jié)節(jié)點(diǎn)指指向老老父節(jié)節(jié)點(diǎn)的的指針針，改改為指指向新新父節(jié)節(jié)點(diǎn)。。對(duì)已已在在CLOSE表上上的的每每個(gè)個(gè)M成員員，，作作與與第第2類同同樣樣的的處處理理，，并并把把這這些些子子結(jié)結(jié)點(diǎn)點(diǎn)從從CLOSE表移出，，重新加加入OPEN表。7.按f(n)排序OPEN表中的節(jié)節(jié)點(diǎn)，f(n)值最小者者排在首首位，重排OPEN表；8.轉(zhuǎn)2。此過(guò)程生生成一個(gè)個(gè)明確的的圖G(搜索圖））和一個(gè)個(gè)G的子集T(搜索樹））。2023/1/1106啟發(fā)式搜搜索——1.A算法（掌握）A算法實(shí)例例——八數(shù)碼游游戲1)設(shè)計(jì)評(píng)價(jià)價(jià)函數(shù)f(n)f(n)=d(n)+w(n),其中d(n)-節(jié)點(diǎn)n在搜索圖圖中的節(jié)點(diǎn)深度度，對(duì)g(n)的度量；w(n)-代表啟發(fā)發(fā)式函數(shù)數(shù)h(n),其值是節(jié)節(jié)點(diǎn)n與目標(biāo)狀狀態(tài)節(jié)點(diǎn)點(diǎn)ng相比較，，不考慮慮空格，，錯(cuò)位的棋棋牌個(gè)數(shù)數(shù)；初始布局目標(biāo)布局移動(dòng)數(shù)碼2023/1/1107啟發(fā)式搜搜索——1.A算法（掌握）啟發(fā)式算算法A實(shí)例——八數(shù)碼游游戲1)設(shè)計(jì)評(píng)價(jià)價(jià)函數(shù)f(n)f(n)計(jì)算實(shí)例例初始布局局s目標(biāo)布局局ngw(s):錯(cuò)位的棋棋牌個(gè)數(shù)數(shù)d(s):當(dāng)前節(jié)點(diǎn)點(diǎn)深度f(wàn)(s)h(n):n-ng的最小路路徑代價(jià)價(jià)g(n):s-n的最小路路徑代價(jià)價(jià)f(n):s-n-ng的最小路路徑代價(jià)價(jià)注：W(S)不考慮空空格2023/1/1108狀態(tài)空間搜索索——2.一般圖搜索策策略（1）搜索術(shù)語(yǔ)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搜索圖G2023/1/1109啟發(fā)式搜索——1.A算法（掌握）啟發(fā)式算法A實(shí)例——八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)數(shù)f(n)f(n)計(jì)算實(shí)例初始布局s目標(biāo)布局ngw(s):錯(cuò)位的棋牌個(gè)個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度度f(wàn)(s)h(n):n-ng的最小路徑代代價(jià)g(n):s-n的最小路徑代代價(jià)f(n):s-n-ng的最最小小路路徑徑代代價(jià)價(jià)044注：：W(S)不考考慮慮空空格格2023/1/1110初始始化化OPEN:={s4}CLOSE:={}2023/1/1111循環(huán)1CLOSE:={s4}OPEN:={abc}OPEN:={a6b4c6}OPEN:={b4a6c6}2023/1/1112循環(huán)2CLOSE:={s4b4}OPEN:={a6c6dei}OPEN:={a6c6d5e5i6}OPEN:={d5e5a6c6i6}2023/1/1113循環(huán)3CLOSE:={s4b4d5}OPEN:={e5a6c6i6jk}OPEN:={e5a6c6i6j7k6}OPEN:={e5a6c6i6k6j7}2023/1/1114循環(huán)4CLOSE:={s4,b4,d5,e5}OPEN:={a6c6i6k6j7lm}OPEN:={a6c6i6k6j7l5m7}OPEN:={l5a6c6i6k6j7m7}2023/1/1115CLOSE:={s4,b4,d5,e5,l5}循環(huán)5OPEN:={a6c6i6k6j7m7n}OPEN:={a6c6i6k6j7m7n5}OPEN:={n5a6c6i6k6j7m7}2023/1/1116循環(huán)6CLOSE:={s4,b4,d5,e5,l5,n5}OPEN:={a6c6i6k6j7m7og}OPEN:={a6c6i6k6j7m7o7g5}OPEN:={g5a6c6i6k6j7m7o7}2023/1/1117循環(huán)7成功結(jié)結(jié)束2023/1/1118最理想想搜索索圖G2023/1/1119判斷失失誤2023/1/1120例2給定4L和3L的水壺壺各一一個(gè)，，水壺壺上沒(méi)沒(méi)有刻刻度，，可以以向水水壺中中加水水。如何在在4L的壺中中準(zhǔn)確確地得得到2L水？（x,y）——4L壺里的的水有有xL，3L壺里的的水有有yL，n表示搜搜索空空間中中的任任一節(jié)節(jié)點(diǎn)。。則給出出下面面的啟啟發(fā)式式函數(shù)數(shù)：2023/1/1121h(n)=2如果果0<x<4并且且0<y<3=4如果果0<x<4或者者0<y<3=8如果果x=0并且且y=3或者者x=4并且且y=0=10如果果x=0并且且y=0或者者x=4并且且y=3假定定g(n)表示示搜搜索索樹樹中中搜搜索索的的深深度度，，則則根根據(jù)據(jù)圖圖搜搜索索策策略略得得下下圖圖的的搜搜索索空空間間。。2023/1/1122水壺壺問(wèn)問(wèn)題題的的狀狀態(tài)態(tài)空空間間擴(kuò)擴(kuò)展展圖圖在第第0步，，由由節(jié)節(jié)點(diǎn)點(diǎn)O可以以得得到到g+h=10。在第第1步，，得得到到兩兩個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn)M和N，其其估估價(jià)價(jià)函函數(shù)數(shù)值值都都為為1+8=9，因因此此可可以以任任選選一一個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn)擴(kuò)擴(kuò)展展。。2023/1/1123水壺壺問(wèn)問(wèn)題題的的狀狀態(tài)態(tài)空空間間擴(kuò)擴(kuò)展展圖圖假定定選選擇擇了了節(jié)節(jié)點(diǎn)點(diǎn)M，在在第第2步擴(kuò)擴(kuò)展展M得到到了了兩兩個(gè)個(gè)后后繼繼點(diǎn)點(diǎn)P和R，對(duì)對(duì)于于P有2+4=6，對(duì)對(duì)于于R有2+10=12。現(xiàn)現(xiàn)在在，，在在節(jié)節(jié)點(diǎn)點(diǎn)P、R、N中，節(jié)節(jié)點(diǎn)P具有最最小的的估價(jià)價(jià)函數(shù)數(shù)值，，所以以選擇擇節(jié)點(diǎn)點(diǎn)P擴(kuò)展。。在第3步，可可以得得到節(jié)節(jié)點(diǎn)S，其中中3+4=7。現(xiàn)在在，在在節(jié)點(diǎn)點(diǎn)S、R、N中，節(jié)節(jié)點(diǎn)S的估價(jià)價(jià)函數(shù)數(shù)值最最小，，所以以下一一步就就會(huì)選選擇S節(jié)點(diǎn)擴(kuò)擴(kuò)展。。該過(guò)過(guò)程一一直進(jìn)進(jìn)行下下去，，直到到到達(dá)達(dá)目標(biāo)標(biāo)節(jié)點(diǎn)點(diǎn)。2023/1/1124啟發(fā)式式搜索索——2.實(shí)現(xiàn)啟啟發(fā)式式搜索索的關(guān)關(guān)鍵因因素（（理解解）實(shí)現(xiàn)啟啟發(fā)式式搜索索應(yīng)考考慮的的關(guān)鍵鍵因素素：（1）搜索索算法法的可采納納性(Admissibility);（2）啟發(fā)式式函數(shù)數(shù)h(n)的強(qiáng)弱弱及其影影響；；2023/1/1125啟發(fā)式式搜索索——2.實(shí)現(xiàn)啟啟發(fā)式式搜索索的關(guān)關(guān)鍵因因素（1）搜索索算法法的可可采納納性(Admissibility)1)定義在存在從初始狀狀態(tài)節(jié)點(diǎn)到到目標(biāo)狀狀態(tài)節(jié)點(diǎn)解答路路徑的情況況下，，若一一個(gè)搜搜索法法總能找找到最最短（（代價(jià)價(jià)最小小）的的解答答路徑徑，則稱稱該狀態(tài)空空間中的搜索算算法具有可可采納納性，，也叫叫最優(yōu)優(yōu)性。如，寬度優(yōu)優(yōu)先的搜索索算法法是可采納納的，只是是搜索索效率不不高。2)A算法的的可采采納性性——定義f*(n)=g*(n)+h*(n)n-搜索圖圖G中最短解解答路路徑的節(jié)點(diǎn)點(diǎn)；f*(n)-s經(jīng)節(jié)點(diǎn)點(diǎn)n到ng的最短解解答路路徑的路徑徑代價(jià)價(jià)；g*(n)-該路徑徑前段（從s到n）的路路徑代代價(jià)；；h*(n)-該路徑徑后段（從n到ng）的路路徑代代價(jià)；；2023/1/1126啟發(fā)式式搜索索——2.實(shí)現(xiàn)啟啟發(fā)式式搜索索的關(guān)關(guān)鍵因因素（1）搜索索算法法的可可采納納性(Admissibility)3)評(píng)價(jià)函函數(shù)f與f*的比較較f(n)、g(n)、h(n)分別是是f*(n)、g*(n)、h*(n)的近似值值（估估計(jì)值值）理想情情況下下：若g(n)=g*(n)、h(n)=h*(n)，則搜索索過(guò)程程中，，每次都都正確確選擇擇，不擴(kuò)展展任何何無(wú)關(guān)關(guān)的節(jié)節(jié)點(diǎn)。實(shí)際情情況：：設(shè)計(jì)接接近f*的f是很困困難的的在算法執(zhí)執(zhí)行過(guò)程程中，g(n)容易從已已經(jīng)生成成的搜索索樹中計(jì)計(jì)算出來(lái)來(lái)Sn搜索圖Gng2023/1/1127啟發(fā)式搜搜索——2.實(shí)現(xiàn)啟發(fā)發(fā)式搜索索的關(guān)鍵鍵因素（1）搜索算算法的可可采納性性(Admissibility)3)評(píng)價(jià)函數(shù)數(shù)f與f*的比價(jià)理想情況況下：若g(n)=g*(n)、h(n)=h*(n)，不擴(kuò)展無(wú)無(wú)關(guān)的節(jié)節(jié)點(diǎn)實(shí)際情況況：設(shè)計(jì)接近近f*的f是很困難難的在算法執(zhí)執(zhí)行過(guò)程程中，g(n)容易從已已經(jīng)生成成的搜索索樹中計(jì)計(jì)算出來(lái)來(lái)，比如如就以節(jié)節(jié)點(diǎn)深度度d(n)當(dāng)做g(n),且有g(shù)(n)>=g*(n)h(n