人工智能第一章課件講義

第1章、搜索問題有許多智力問題(如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等)許多實(shí)際問題（如最優(yōu)路徑規(guī)劃、人力排班、裝箱問題、機(jī)器人行動(dòng)規(guī)劃等）

都可以歸結(jié)為在某一狀態(tài)空間中搜索目標(biāo)或路徑的問題。1第1章、搜索問題有許多智力問題(如梵塔問題、旅行商問題、八皇22334455問題：如何解決這類問題？這類問題不能用簡(jiǎn)單的數(shù)學(xué)公式/數(shù)學(xué)方程來描述，屬于非結(jié)構(gòu)化問題。難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用屬于組合爆炸問題，稍大規(guī)模的問題就超出了人類的認(rèn)知負(fù)荷解決方法：利用計(jì)算機(jī)的超人計(jì)算能力，通過不斷試探搜索找到問題的（最優(yōu)）解。優(yōu)點(diǎn)建模簡(jiǎn)單6問題：如何解決這類問題？這類問題不能用簡(jiǎn)單的數(shù)學(xué)公式/數(shù)具體方法：狀態(tài)空間法狀態(tài)：是指問題狀態(tài)的的向量表示（x,y,z,….)。問題有初始狀態(tài)，有目標(biāo)狀態(tài)有些狀態(tài)可能是非法的，問題不可能發(fā)展到那種狀態(tài)問題表示為向量，向量就是在Euclidean空間，因此問題的初始狀態(tài)和目標(biāo)狀態(tài)都是此空間中的點(diǎn)。此類問題的特征是找出從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，方法是通過一個(gè)狀態(tài)向另一個(gè)狀態(tài)的轉(zhuǎn)換實(shí)現(xiàn)的。7具體方法：狀態(tài)空間法狀態(tài)：是指問題狀態(tài)的的向量表示（x,y問題狀態(tài)的表示方法（一）8問題狀態(tài)的表示方法（一）8問題狀態(tài)的表示方法（二）9問題狀態(tài)的表示方法（二）9問題狀態(tài)的變遷10問題狀態(tài)的變遷10問題狀態(tài)的表示方法11問題狀態(tài)的表示方法11問題狀態(tài)的變遷12問題狀態(tài)的變遷12搜索問題---主要內(nèi)容內(nèi)容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問題： 如何利用知識(shí)，盡可能有效地找到問題的解（最佳解），尋找過程就是搜索。13搜索問題---主要內(nèi)容內(nèi)容：13狀態(tài)空間法1.狀態(tài)空間表示方法狀態(tài)(State)：求解過程中每一步問題狀況的表示Sk=Sk0,Sk1…)當(dāng)對(duì)每一個(gè)分量都給以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。操作(Operator):也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。。操作可以是一個(gè)機(jī)械步驟，一個(gè)運(yùn)算，一條規(guī)則或一個(gè)過程。狀態(tài)空間(Statespace):用來描述一個(gè)問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用表示為(S,F,G)其中，S為問題的所有初始狀態(tài)的集合；F為操作的集合；G為目標(biāo)狀態(tài)的集合。狀態(tài)空間也可用一個(gè)賦值的有向圖來表示，稱為狀態(tài)空間圖,其中節(jié)點(diǎn)表示問題的狀態(tài)，有向邊表示操作。14狀態(tài)空間法1.狀態(tài)空間表示方法狀態(tài)(State)：求解過程狀態(tài)空間法求解問題的基本過程：首先為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止；此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個(gè)解。

狀態(tài)空間法2.狀態(tài)空間問題求解15狀態(tài)空間法求解問題的基本過程：狀態(tài)空間法15修道士(Missionaries)和野人(Cannibals)問題(簡(jiǎn)稱M-C問題)。設(shè)在河的一岸有三個(gè)野人、三個(gè)修道士和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束：修道士和野人都會(huì)劃船，但每次船上至多可載兩個(gè)人；在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會(huì)被野人吃掉。

如果野人會(huì)服從任何一次過河安排，請(qǐng)規(guī)劃一個(gè)確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計(jì)劃。

狀態(tài)空間法3.狀態(tài)空間的例子16修道士(Missionaries)和野人(Cann

解：首先選取描述問題狀態(tài)的方法。在這個(gè)問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個(gè)三元組來表示狀態(tài)S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。右岸的狀態(tài)可由下式確定：右岸修道士數(shù)m'=3-m右岸野人數(shù)c'=3-c右岸船數(shù)b'=1-b在這種表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32種狀態(tài)。狀態(tài)空間法3.狀態(tài)空間的例子17解：首先選取描述問題狀態(tài)的方法。在這個(gè)問題中，需

這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了這些狀態(tài)，還需要考慮可進(jìn)行的操作。操作是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。每個(gè)操作都應(yīng)當(dāng)滿足如下條件：一是船至少有一個(gè)人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的m和c的增加數(shù)目；二是每次操作船上人數(shù)不得超過2個(gè)；三是操作應(yīng)保證不產(chǎn)生非法狀態(tài)。因此，操作應(yīng)由條件部分和動(dòng)作部分：條件：只有當(dāng)其條件具備時(shí)才能使用動(dòng)作：刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。

18這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士操作的表示：用符號(hào)Pij表示從左岸到右岸的運(yùn)人操作用符號(hào)Qij表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的野人數(shù)操作集本問題有10種操作可供選擇：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01為例來說明這些操作的條件和動(dòng)作。操作符號(hào)條件動(dòng)作P01b=1,m=0或m=3，c≥1b=0,c=c-1Q01b=0,m=0或m=3，c≤2b=1,c=c+1

19操作的表示：19搜索問題S0Sg20搜索問題S0Sg20如何實(shí)現(xiàn)搜索？討論的問題：有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。21如何實(shí)現(xiàn)搜索？討論的問題：211.1回溯策略例：皇后問題221.1回溯策略例：皇后問題22()23()23()Q((1,1))24()Q((1,1))24()QQ((1,1))((1,1)(2,3))25()QQ((1,1))((1,1)(2,3))25()Q((1,1))((1,1)(2,3))26()Q((1,1))((1,1)(2,3))26()QQ((1,1))((1,1)(2,3))((1,1)(2,4))27()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))28()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))29()QQ((1,1))((1,1)(2,3))((1,1()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))30()Q((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))31()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))32()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))33()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))34()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))35()((1,1))((1,1)(2,3))((1,1)遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g36遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g36一個(gè)遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12337一個(gè)遞歸的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。38回溯搜索算法 BACKTRACK（DATA）38回溯搜索算法遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);39回溯搜索算法遞歸過程BACKTRACK(DATA)39存在問題及解決辦法解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)問題：深度問題死循環(huán)問題40存在問題及解決辦法解決辦法：當(dāng)前狀態(tài)問題：40回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。41回溯搜索算法1BACKTRACK1（DATALIST）41回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);42回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);43回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULE一些深入的問題失敗原因分析、多步回溯QQ44一些深入的問題失敗原因分析、多步回溯QQ44一些深入問題（續(xù)）回溯搜索中知識(shí)的利用 基本思想(以皇后問題為例)： 盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ322345一些深入問題（續(xù)）回溯搜索中知識(shí)的利用QQQQ31.2圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

461.2圖搜索策略問題的引出46一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012347一些基本概念節(jié)點(diǎn)深度：012347一些基本概念（續(xù)1）路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。48一些基本概念（續(xù)1）路徑48一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。49一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn)49一般的圖搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);50一般的圖搜索算法1,G=G0(G0=s),OPEN:=一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針： ADD(mj,OPEN),并標(biāo)記mj到n的指針； 計(jì)算是否要修改mk、ml到n的指針； 計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8,對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GOLOOP；51一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針：51節(jié)點(diǎn)類型說明…...…...…...…...…...mjmkml52節(jié)點(diǎn)類型說明…...…...…...…...…...mjmk修改指針舉例123456s53修改指針舉例123456s53修改指針舉例（續(xù)1）123456s54修改指針舉例（續(xù)1）123456s54123456修改指針舉例（續(xù)2）s55123456修改指針舉例（續(xù)2）s55123456修改指針舉例（續(xù)3）s56123456修改指針舉例（續(xù)3）s561.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索571.3無信息圖搜索過程深度優(yōu)先搜索57深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標(biāo)記mj到n的指針;10,GOLOOP;58深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s1238476523184765591232359231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)6023232832深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉圖搜索是一個(gè)通用的與問題無關(guān)的方法61深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解61寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并標(biāo)記mj到n的指針;9,GOLOOP;62寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)82341876546323232832寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí)，一定能找到解當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法64寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí)，一定能找到解641.4啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解***651.4啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。***66希望：***66基本思想定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。***67基本思想定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一1，啟發(fā)式搜索算法A（A算法）評(píng)價(jià)函數(shù)的格式： f(n)=g(n)+h(n) f(n)：評(píng)價(jià)函數(shù) h(n)：?jiǎn)l(fā)函數(shù)***681，啟發(fā)式搜索算法A（A算法）評(píng)價(jià)函數(shù)的格式：***68符號(hào)的意義g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值***69符號(hào)的意義g*(n)：從s到n的最短路徑的耗散值***69A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},

計(jì)算f(n,mi):=g(n,mi)+h(mi);

70A算法1,OPEN:=(s),f(s):=g(s)+h(A算法（續(xù)） ADD(mj,OPEN),標(biāo)記mj到n的指針； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

標(biāo)記mk到n的指針； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 標(biāo)記ml到n的指針, ADD(ml,OPEN);7,OPEN中的節(jié)點(diǎn)按f值從小到大排序；8,GOLOOP；71A算法（續(xù)） ADD(mj,OPEN),標(biāo)記mj到n的指…...…...…...…...…...mjmkmlnab72…...…...…...…...…...mjmkmlnab7Closed表Open表73Closed表Open表73一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值 h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)

2831647512384765***74一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)：2831h計(jì)算舉例 h(n)=42

831

64751234576

8***75h計(jì)算舉例 h(n)=428312831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456762832832832爬山法（局部搜索算法）f(n)=h(n)77爬山法（局部搜索算法）f(n)=h(n)77分支界限法 如果對(duì)于任何n，f(n)=g(n),h(n)=078分支界限法78動(dòng)態(tài)規(guī)劃算法 如果對(duì)于任何n，當(dāng)h(n)=0時(shí)，求s->t的最短路徑,對(duì)某一中間結(jié)點(diǎn)I,只要考慮s到I的最短路徑分支,其余路徑不考慮,A算法就成為了動(dòng)態(tài)規(guī)劃算法。79動(dòng)態(tài)規(guī)劃算法792，最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。***802，最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：2***81A*條件舉例8數(shù)碼問題28312A*算法的性質(zhì)A*算法的假設(shè)

設(shè)ni、nj是任意兩個(gè)節(jié)點(diǎn)，有：C(ni,nj)>其中為大于0的常數(shù)幾個(gè)等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節(jié)點(diǎn)，t是目標(biāo)節(jié)點(diǎn)，n是s到t的最佳路徑上的節(jié)點(diǎn)。***82A*算法的性質(zhì)A*算法的假設(shè)幾個(gè)等式***82A*算法的性質(zhì)（續(xù)1）定理1.1： 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。***83A*算法的性質(zhì)（續(xù)1）定理1.1：***83A*算法的性質(zhì)（續(xù)2）引理1.1： 對(duì)無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。***84A*算法的性質(zhì)（續(xù)2）引理1.1：***84A*算法的性質(zhì)（續(xù)3）引理1.2： A*結(jié)束前，OPEN表中必存在f(n)≤f*(s)。存在一個(gè)節(jié)點(diǎn)n，n在最佳路徑上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)***85A*算法的性質(zhì)（續(xù)3）引理1.2：存在一個(gè)節(jié)點(diǎn)n，n在***A*算法的性質(zhì)（續(xù)3）定理1.2： 對(duì)無限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。引理1.1：A*如果不結(jié)束，則OPEN中所有的n有f(n)>f*(s)引理1.2：在A*結(jié)束前，必存在節(jié)點(diǎn)n，使得f(n)≤f*(s)所以，如果A*不結(jié)束，將導(dǎo)致矛盾。***86A*算法的性質(zhì)（續(xù)3）定理1.2：引理1.1：A*如果不結(jié)束A*算法的性質(zhì)（續(xù)4）推論1.1： OPEN表上任一具有f(n)<f*(s)的節(jié)點(diǎn)n，最終都將被A*選作擴(kuò)展的節(jié)點(diǎn)。由定理1.2，知A*一定結(jié)束，由A*的結(jié)束條件，OPEN表中f(t)最小時(shí)才結(jié)束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被擴(kuò)展。得證。***87A*算法的性質(zhì)（續(xù)4）推論1.1：由定理1.2，知A*A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。***88A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)：***8可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結(jié)束設(shè)找到的路徑s→t不是最佳的（t為目標(biāo)）則：f(t)=g(t)>f*(s)由引理1.2知結(jié)束前OPEN中存在f(n)≤f*(s)的節(jié)點(diǎn)n，所以f(n)≤f*(s)<f(t)因此A*應(yīng)選擇n擴(kuò)展，而不是t。與假設(shè)A*選擇t結(jié)束矛盾。得證。***89可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結(jié)束A*算法的性質(zhì)（續(xù)6）推論1.2： A*選作擴(kuò)展的任一節(jié)點(diǎn)n，有f(n)≤f*(s)。由引理2.2知在A*結(jié)束前，OPEN中存在節(jié)點(diǎn)n’，f(n’)≤f*(s)設(shè)此時(shí)A*選擇n擴(kuò)展。如果n＝n’，則f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴(kuò)展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。***90A*算法的性質(zhì)（續(xù)6）推論1.2：由引理2.2知在A*結(jié)束前A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對(duì)同一個(gè)問題定義了兩個(gè)A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，由A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和A2一樣多。簡(jiǎn)寫：如果h2(n)>h1(n)(目標(biāo)節(jié)點(diǎn)除外)，則A1擴(kuò)展的節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)***91A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對(duì)同一個(gè)問題定義了兩個(gè)AA*算法的性質(zhì)（續(xù)7）注意：

在定理1.4中，評(píng)價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說，同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次，都只計(jì)算一次。***92A*算法的性質(zhì)（續(xù)7）注意：***92定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納（1）當(dāng)d(n)＝0時(shí)，即只有一個(gè)節(jié)點(diǎn)，顯然定理成立。（2）設(shè)d(n)≤k時(shí)定理成立。（歸納假設(shè)）（3）當(dāng)d(n)=k+1時(shí)，用反證法。設(shè)存在一個(gè)深度為k＋1的節(jié)點(diǎn)n，被A2擴(kuò)展，但沒有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n的父節(jié)點(diǎn)，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時(shí)，n將被保留在OPEN中。93定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納93定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2擴(kuò)展了n，有f2(n)≤f*(s)(引理1.2)即：h2(n)≤f*(s)–g2(n)(A)由于d(n)=k時(shí)，A2擴(kuò)展的節(jié)點(diǎn)A1一定擴(kuò)展，有g(shù)1(n)≤g2(n)(因?yàn)锳2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比較A、B兩式，有h1(n)≥h2(n)，與定理?xiàng)l件矛盾。故定理得證。94定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)對(duì)h的評(píng)價(jià)方法平均分叉樹 設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜索了N個(gè)節(jié)點(diǎn)，則:

其中，b*稱為平均分叉樹。b*越小，說明h效果越好。實(shí)驗(yàn)表明，b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。95對(duì)h的評(píng)價(jià)方法平均分叉樹95對(duì)h的評(píng)價(jià)舉例例：8數(shù)碼問題，隨機(jī)產(chǎn)生若干初始狀態(tài)。使用h1： d=14,N=539, b*=1.44;d=20,N=7276， b*=1.47；使用h2： d=14,N=113, b*=1.23; d=20,N=676, b*=1.2796對(duì)h的評(píng)價(jià)舉例例：8數(shù)碼問題，隨機(jī)產(chǎn)生若干初始狀態(tài)。96A*的復(fù)雜性一般來說，A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時(shí)： abs(h(n)-h*(n))≤O(log(h*(n))) A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下，h與h*的差別至少是和離目標(biāo)的距離成正比的。***97A*的復(fù)雜性一般來說，A*的算法復(fù)雜性是指數(shù)型的，可以證明，3，A*算法的改進(jìn)問題的提出： 因A算法第6步對(duì)ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。***983，A*算法的改進(jìn)問題的提出：***98s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)***99s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G目標(biāo)631118***100出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到解決的途徑對(duì)h加以限制能否對(duì)h增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。對(duì)算法加以改進(jìn)能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。***101解決的途徑對(duì)h加以限制***101改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性***102改進(jìn)的條件可采納性不變***102對(duì)h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(jié)點(diǎn)ni和nj，其中nj是ni的子節(jié)點(diǎn)，滿足 h(ni)-h(nj)≤c(ni,nj) h(t)=0 或h(ni)≤c(ni,nj)+h(nj) h(t)=0則稱h是單調(diào)的。h(ni)ninjh(nj)c(ni,nj)***103對(duì)h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(jié)點(diǎn)ni和nj，h單調(diào)的性質(zhì)定理1.5： 若h(n)是單調(diào)的，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑。 即：當(dāng)A*選n擴(kuò)展時(shí)，有g(shù)(n)=g*(n)。***104h單調(diào)的性質(zhì)定理1.5：***104定理1.5的證明設(shè)n是A*擴(kuò)展的任一節(jié)點(diǎn)。當(dāng)n＝s時(shí)，定理顯然成立。下面考察n≠s的情況。設(shè)P＝(n0=s,n1,n2,…,nk=n)是s到n的最佳路徑P中一定有節(jié)點(diǎn)在CLOSED中，設(shè)P中最后一個(gè)出現(xiàn)在CLOSED中的節(jié)點(diǎn)為nj，則nj+1在OPEN中。105定理1.5的證明設(shè)n是A*擴(kuò)展的任一節(jié)點(diǎn)。當(dāng)n＝s時(shí)，定理顯定理1.5的證明（續(xù)1）由單調(diào)限制條件，對(duì)P中任意節(jié)點(diǎn)ni有：h(ni)≤C(ni,ni+1)+h(ni+1)

g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路徑上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)帶入上式有：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)從i=j到i=k-1應(yīng)用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)

注意：(nj在CLOSED中，nj+1在OPEN中)106定理1.5的證明（續(xù)1）由單調(diào)限制條件，對(duì)P中任意節(jié)點(diǎn)ni有定理1.5的證明（續(xù)2）重寫上式：f(nj+1)≤g*(n)+h(n)另一方面，A*選n擴(kuò)展，必有：f(n)=g(n)+h(n)≤f(nj+1)比較兩式，有：g(n)≤g*(n)但已知g*(n)是最佳路徑的耗散值，所以只有：g(n)=g*(n)。得證。107定理1.5的證明（續(xù)2）重寫上式：f(nj+1)≤g*(h單調(diào)的性質(zhì)（續(xù)）定理1.6： 若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。即f(ni)≤f(nj)。

***108h單調(diào)的性質(zhì)（續(xù)）定理1.6：***108定理1.6的證明由單調(diào)限制條件，有：h(ni)–h(nj)≤C(ni,nj)=f(ni)-g(ni)=f(nj)-g(nj)

f(ni)-g(ni)-f(nj)+g(nj)≤C(ni,nj)=g(ni)+C(ni,nj)

f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)≤C(ni,nj)f(ni)-f(nj)≤0，得證。***109定理1.6的證明由單調(diào)限制條件，有：=f(ni)-g(nih單調(diào)的例子8數(shù)碼問題：h為“不在位”的將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni的后繼節(jié)點(diǎn))-1 h(t)=0 c(ni,nj)=1滿足單調(diào)的條件。 ***110h單調(diào)的例子8數(shù)碼問題：***110對(duì)算法加以改進(jìn)一些結(jié)論：OPEN表上任以具有f(n)<f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)≤f*(s)。***111對(duì)算法加以改進(jìn)一些結(jié)論：***111改進(jìn)的出發(fā)點(diǎn)OPEN=(…………)f*(s)f值小于f*(s)的節(jié)點(diǎn)f值大于等于f*(s)的節(jié)點(diǎn)fm：到目前為止已擴(kuò)展節(jié)點(diǎn)的最大f值，用fm代替f*(s)h(n)==0fornodesinNEST***112改進(jìn)的出發(fā)點(diǎn)OPEN=(…………)f*(修正過程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=()THENEXIT(FAIL);3,NEST:={ni|f(ni)<fm} IFNEST≠()THENn:=NEST中g(shù)最小的節(jié)點(diǎn) ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同過程A。***113修正過程A1,OPEN:=(s),f(s)=g(s)+hs(10)A(1)B(5)C(8)G目標(biāo)631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)***114s(10)A(1)B(5)C(8)G目標(biāo)631118前面的h的單調(diào)化方法如果令： f(n)=max(f(n的父節(jié)點(diǎn)),g(n)+h(n)) 則容易證明，這樣處理后的h是單調(diào)的。***115h的單調(diào)化方法如果令：***115搜索算法的討論1.弱方法盲目搜索算法產(chǎn)生組合爆炸啟發(fā)搜索算法屬于弱方法,不能保證找到解2.算法分析數(shù)學(xué)分析統(tǒng)計(jì)分析程序分析分析指標(biāo):時(shí)間和空間***116搜索算法的討論1.弱方法***116作業(yè)1.28數(shù)碼問題.Figure1.17h1(n)=“不在位”的將牌數(shù)DrawoutthesearchingtreeusingA***117作業(yè)1.28數(shù)碼問題.Figure1.17***117第1章、搜索問題有許多智力問題(如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等)許多實(shí)際問題（如最優(yōu)路徑規(guī)劃、人力排班、裝箱問題、機(jī)器人行動(dòng)規(guī)劃等）

都可以歸結(jié)為在某一狀態(tài)空間中搜索目標(biāo)或路徑的問題。118第1章、搜索問題有許多智力問題(如梵塔問題、旅行商問題、八皇1192120312141225問題：如何解決這類問題？這類問題不能用簡(jiǎn)單的數(shù)學(xué)公式/數(shù)學(xué)方程來描述，屬于非結(jié)構(gòu)化問題。難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用屬于組合爆炸問題，稍大規(guī)模的問題就超出了人類的認(rèn)知負(fù)荷解決方法：利用計(jì)算機(jī)的超人計(jì)算能力，通過不斷試探搜索找到問題的（最優(yōu)）解。優(yōu)點(diǎn)建模簡(jiǎn)單123問題：如何解決這類問題？這類問題不能用簡(jiǎn)單的數(shù)學(xué)公式/數(shù)具體方法：狀態(tài)空間法狀態(tài)：是指問題狀態(tài)的的向量表示（x,y,z,….)。問題有初始狀態(tài)，有目標(biāo)狀態(tài)有些狀態(tài)可能是非法的，問題不可能發(fā)展到那種狀態(tài)問題表示為向量，向量就是在Euclidean空間，因此問題的初始狀態(tài)和目標(biāo)狀態(tài)都是此空間中的點(diǎn)。此類問題的特征是找出從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，方法是通過一個(gè)狀態(tài)向另一個(gè)狀態(tài)的轉(zhuǎn)換實(shí)現(xiàn)的。124具體方法：狀態(tài)空間法狀態(tài)：是指問題狀態(tài)的的向量表示（x,y問題狀態(tài)的表示方法（一）125問題狀態(tài)的表示方法（一）8問題狀態(tài)的表示方法（二）126問題狀態(tài)的表示方法（二）9問題狀態(tài)的變遷127問題狀態(tài)的變遷10問題狀態(tài)的表示方法128問題狀態(tài)的表示方法11問題狀態(tài)的變遷129問題狀態(tài)的變遷12搜索問題---主要內(nèi)容內(nèi)容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問題： 如何利用知識(shí)，盡可能有效地找到問題的解（最佳解），尋找過程就是搜索。130搜索問題---主要內(nèi)容內(nèi)容：13狀態(tài)空間法1.狀態(tài)空間表示方法狀態(tài)(State)：求解過程中每一步問題狀況的表示Sk=Sk0,Sk1…)當(dāng)對(duì)每一個(gè)分量都給以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。操作(Operator):也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。。操作可以是一個(gè)機(jī)械步驟，一個(gè)運(yùn)算，一條規(guī)則或一個(gè)過程。狀態(tài)空間(Statespace):用來描述一個(gè)問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用表示為(S,F,G)其中，S為問題的所有初始狀態(tài)的集合；F為操作的集合；G為目標(biāo)狀態(tài)的集合。狀態(tài)空間也可用一個(gè)賦值的有向圖來表示，稱為狀態(tài)空間圖,其中節(jié)點(diǎn)表示問題的狀態(tài)，有向邊表示操作。131狀態(tài)空間法1.狀態(tài)空間表示方法狀態(tài)(State)：求解過程狀態(tài)空間法求解問題的基本過程：首先為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止；此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個(gè)解。

狀態(tài)空間法2.狀態(tài)空間問題求解132狀態(tài)空間法求解問題的基本過程：狀態(tài)空間法15修道士(Missionaries)和野人(Cannibals)問題(簡(jiǎn)稱M-C問題)。設(shè)在河的一岸有三個(gè)野人、三個(gè)修道士和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束：修道士和野人都會(huì)劃船，但每次船上至多可載兩個(gè)人；在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會(huì)被野人吃掉。

如果野人會(huì)服從任何一次過河安排，請(qǐng)規(guī)劃一個(gè)確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計(jì)劃。

狀態(tài)空間法3.狀態(tài)空間的例子133修道士(Missionaries)和野人(Cann

解：首先選取描述問題狀態(tài)的方法。在這個(gè)問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個(gè)三元組來表示狀態(tài)S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。右岸的狀態(tài)可由下式確定：右岸修道士數(shù)m'=3-m右岸野人數(shù)c'=3-c右岸船數(shù)b'=1-b在這種表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32種狀態(tài)。狀態(tài)空間法3.狀態(tài)空間的例子134解：首先選取描述問題狀態(tài)的方法。在這個(gè)問題中，需

這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了這些狀態(tài)，還需要考慮可進(jìn)行的操作。操作是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。每個(gè)操作都應(yīng)當(dāng)滿足如下條件：一是船至少有一個(gè)人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的m和c的增加數(shù)目；二是每次操作船上人數(shù)不得超過2個(gè)；三是操作應(yīng)保證不產(chǎn)生非法狀態(tài)。因此，操作應(yīng)由條件部分和動(dòng)作部分：條件：只有當(dāng)其條件具備時(shí)才能使用動(dòng)作：刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。

135這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士操作的表示：用符號(hào)Pij表示從左岸到右岸的運(yùn)人操作用符號(hào)Qij表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的野人數(shù)操作集本問題有10種操作可供選擇：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01為例來說明這些操作的條件和動(dòng)作。操作符號(hào)條件動(dòng)作P01b=1,m=0或m=3，c≥1b=0,c=c-1Q01b=0,m=0或m=3，c≤2b=1,c=c+1

136操作的表示：19搜索問題S0Sg137搜索問題S0Sg20如何實(shí)現(xiàn)搜索？討論的問題：有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。138如何實(shí)現(xiàn)搜索？討論的問題：211.1回溯策略例：皇后問題1391.1回溯策略例：皇后問題22()140()23()Q((1,1))141()Q((1,1))24()QQ((1,1))((1,1)(2,3))142()QQ((1,1))((1,1)(2,3))25()Q((1,1))((1,1)(2,3))143()Q((1,1))((1,1)(2,3))26()QQ((1,1))((1,1)(2,3))((1,1)(2,4))144()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))145()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))146()QQ((1,1))((1,1)(2,3))((1,1()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))147()Q((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))148()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))149()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))150()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))151()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))152()((1,1))((1,1)(2,3))((1,1)遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g153遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g36一個(gè)遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST123154一個(gè)遞歸的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。155回溯搜索算法 BACKTRACK（DATA）38回溯搜索算法遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);156回溯搜索算法遞歸過程BACKTRACK(DATA)39存在問題及解決辦法解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)問題：深度問題死循環(huán)問題157存在問題及解決辦法解決辦法：當(dāng)前狀態(tài)問題：40回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。158回溯搜索算法1BACKTRACK1（DATALIST）41回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);159回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);160回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULE一些深入的問題失敗原因分析、多步回溯QQ161一些深入的問題失敗原因分析、多步回溯QQ44一些深入問題（續(xù)）回溯搜索中知識(shí)的利用 基本思想(以皇后問題為例)： 盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ3223162一些深入問題（續(xù)）回溯搜索中知識(shí)的利用QQQQ31.2圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

1631.2圖搜索策略問題的引出46一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+10123164一些基本概念節(jié)點(diǎn)深度：012347一些基本概念（續(xù)1）路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。165一些基本概念（續(xù)1）路徑48一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。166一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn)49一般的圖搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);167一般的圖搜索算法1,G=G0(G0=s),OPEN:=一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針： ADD(mj,OPEN),并標(biāo)記mj到n的指針； 計(jì)算是否要修改mk、ml到n的指針； 計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8,對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GOLOOP；168一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針：51節(jié)點(diǎn)類型說明…...…...…...…...…...mjmkml169節(jié)點(diǎn)類型說明…...…...…...…...…...mjmk修改指針舉例123456s170修改指針舉例123456s53修改指針舉例（續(xù)1）123456s171修改指針舉例（續(xù)1）123456s54123456修改指針舉例（續(xù)2）s172123456修改指針舉例（續(xù)2）s55123456修改指針舉例（續(xù)3）s173123456修改指針舉例（續(xù)3）s561.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索1741.3無信息圖搜索過程深度優(yōu)先搜索57深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標(biāo)記mj到n的指針;10,GOLOOP;175深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s12384765231847651761232359231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉圖搜索是一個(gè)通用的與問題無關(guān)的方法178深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解61寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()