第2章-基于狀態(tài)空間圖表示的搜索搜索技術(shù)(新)20121013_第1頁
第2章-基于狀態(tài)空間圖表示的搜索搜索技術(shù)(新)20121013_第2頁
第2章-基于狀態(tài)空間圖表示的搜索搜索技術(shù)(新)20121013_第3頁
第2章-基于狀態(tài)空間圖表示的搜索搜索技術(shù)(新)20121013_第4頁
第2章-基于狀態(tài)空間圖表示的搜索搜索技術(shù)(新)20121013_第5頁
已閱讀5頁,還剩144頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

第2章基于圖的知識(shí)表示與圖搜索技術(shù)2023/2/5人工智能2第2章基于圖的知識(shí)表示與圖搜索技術(shù)2.1概述2.2狀態(tài)空間圖表示2.3狀態(tài)空間圖的盲目搜索2.4狀態(tài)空間圖的啟發(fā)式搜索2.5與或圖表示及搜索技術(shù)2.6博弈樹及搜索技術(shù)2023/2/5人工智能32.1概述2.1.1知識(shí)與問題求解框架2.1.2知識(shí)表示2.1.3圖搜索技術(shù)2023/2/5人工智能42.1.1知識(shí)與問題求解框架(1)1.知識(shí)的定義心理學(xué):個(gè)體通過與環(huán)境相互作用后獲得的信息及其組織。費(fèi)根鮑姆:知識(shí)是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。博恩斯坦(Bernstein):知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過程組成的。概括地說,知識(shí)是高度組織起來的信息集團(tuán),是人們?cè)陂L期的生活和社會(huì)實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗(yàn)中積累起來的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)等。2.1.1知識(shí)與問題求解框架(2)2.知識(shí)的分類(1)從應(yīng)用領(lǐng)域來劃分常識(shí)性知識(shí)領(lǐng)域(專業(yè))性知識(shí)(2)從在問題求解中的作用來劃分?jǐn)⑹鲂灾R(shí)過程性知識(shí)控制性知識(shí)(3)從確定性來劃分確定性知識(shí)非確定性知識(shí)(4)從知識(shí)的表現(xiàn)形式來劃分,可分為文字、符號(hào)、聲音、圖形、圖像等。2023/2/5人工智能52.1.1知識(shí)與問題求解框架(3)3.問題求解框架問題:是指事件或事物的已知或當(dāng)前狀態(tài)與目標(biāo)狀態(tài)之間有差異。問題求解:是指在一定的控制策略下,通過一系列的操作或運(yùn)算來改變問題的狀態(tài),使之與目標(biāo)狀態(tài)接近或一致。例如,李明在北京,他要去西安(辦事)。又如,博弈問題。問題的求解框架(1)敘述性知識(shí):描述問題的狀態(tài)有關(guān)的各種知識(shí)。(2)過程性知識(shí):描述狀態(tài)之間的變換關(guān)系的各種知識(shí)。(3)控制性知識(shí):描述如何在當(dāng)前狀態(tài)下選擇合適操作的知識(shí)。2023/2/5人工智能62023/2/5人工智能72.1.2知識(shí)表示(1)知識(shí)表示:就是研究在計(jì)算機(jī)中如何用最合適的形式表示問題求解過程中所需要的各種知識(shí),包括構(gòu)成問題求解框架的全部知識(shí)。常用的知識(shí)表示形式狀態(tài)空間圖與或圖謂詞邏輯產(chǎn)生式框架語義網(wǎng)絡(luò)……2.1.2知識(shí)表示(2)2023/2/5人工智能8例2.1麥卡賽問題。在一個(gè)2n2n的方格棋盤中,去掉對(duì)角的兩個(gè)方格,如圖(a),問能否將它全部劃成若干12的小長方塊?目標(biāo)狀態(tài)初始狀態(tài)可達(dá)狀態(tài)同構(gòu)問題同態(tài)問題2023/2/5人工智能92.1.3圖搜索技術(shù)(1)1.搜索搜索,簡單地說就是“尋找”,目的是找到問題的解。在問題求解過程中,待求解的問題被抽象成一定空間上的圖,搜索過程就是從圖中初始節(jié)點(diǎn)出發(fā),沿著與之相連的邊試探著前進(jìn),尋找目標(biāo)節(jié)點(diǎn)或可解節(jié)點(diǎn)的過程。2.搜索樹搜索過程中經(jīng)過(考察過)的節(jié)點(diǎn)和邊,按原圖的連接關(guān)系,便會(huì)構(gòu)成一個(gè)樹型的有向圖,稱為搜索樹。搜索樹是一個(gè)搜索過程的搜索軌跡,或稱之為搜索空間。2.1.3圖搜索技術(shù)(2)2023/2/5人工智能10圖2-2搜索空間示意圖問題的狀態(tài)空間、搜索空間及解的示意圖:2.1.3圖搜索技術(shù)(3)3.搜索策略搜索策略將決定搜索過程按照什么樣的順序考察節(jié)點(diǎn)和經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。盲目搜索:無向?qū)У乃阉鳎卜Q窮舉搜索。啟發(fā)式搜索:利用“啟發(fā)性信息”作為導(dǎo)航的搜索過程。對(duì)于較大或無限狀態(tài)空間問題,盲目搜索效率太低,所以在實(shí)際當(dāng)中往往是不可行的。啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問題求解中,如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。2023/2/5人工智能112023/2/5人工智能122.2狀態(tài)空間圖表示2.2.1狀態(tài)空間圖2.2.2隱式狀態(tài)空間圖2023/2/5人工智能132.2.1狀態(tài)空間圖(1)1.狀態(tài)

狀態(tài)對(duì)應(yīng)敘述性知識(shí),描述一個(gè)問題在開始、結(jié)束或中間的某一時(shí)刻所處的狀況或狀態(tài)。通常引進(jìn)一組變量,表示與問題狀態(tài)相關(guān)的各種要素,并用這組變量所構(gòu)成的多元組來表示狀態(tài)。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。2023/2/5人工智能142.2.1狀態(tài)空間圖(2)2.操作

操作對(duì)應(yīng)過程性知識(shí),即狀態(tài)轉(zhuǎn)換規(guī)則,描述狀態(tài)之間的關(guān)系。描述一個(gè)操作要包含兩個(gè)部分條件:指明被作用的狀態(tài)要滿足的約束條件動(dòng)作:指明一個(gè)操作對(duì)狀態(tài)的分量所做的改變。操作的表示形式可以是一個(gè)機(jī)械性的步驟、過程、規(guī)則或算子。操作在狀態(tài)圖中表示為邊。在程序中,狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對(duì)、條件語句、規(guī)則、函數(shù)、過程等表示。如:如果室內(nèi)溫度低于26度,則關(guān)閉空調(diào)。2023/2/5人工智能152.2.1狀態(tài)空間圖(3)3.狀態(tài)空間圖問題的狀態(tài)空間圖是一個(gè)描述該問題全部可能的狀態(tài)及相互關(guān)系的圖,如考慮操作的代價(jià),狀態(tài)空間圖就是一個(gè)賦值有向圖。狀態(tài)空間常記為三元組:

S:初始狀態(tài)的集合

F:操作的集合

G:目標(biāo)狀態(tài)的集合。由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。2.2.1狀態(tài)空間圖(4)4.求解在狀態(tài)空間表示法中,問題求解過程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)Qs出發(fā)到達(dá)目標(biāo)狀態(tài)Qg的路徑問題,也就是尋找操作序列的問題。狀態(tài)空間的解為三元組<Qs,a,Qg>Qs:某個(gè)初始狀態(tài)Qg:某個(gè)目標(biāo)狀態(tài)a:把Qs變換成Qg的有限的操作序列狀態(tài)轉(zhuǎn)換圖S1S3S2…f1f2f3f4QsQgfn2023/2/5人工智能162023/2/5人工智能17例2.2翻轉(zhuǎn)錢幣問題(1)三枚錢幣處于反、正、反狀態(tài),每次只許翻動(dòng)一枚錢幣,問連續(xù)翻動(dòng)三次后,能否出現(xiàn)全正或全反狀態(tài)。初始狀態(tài)Qs目標(biāo)狀態(tài)集合{Q0,Q7}例2.2翻轉(zhuǎn)錢幣問題(2)引入一個(gè)三元組(q0,q1,q2)來描述總狀態(tài),錢幣正面為0,反面為1,全部可能的狀態(tài)為:

Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。翻動(dòng)錢幣的操作抽象為改變上述狀態(tài)的算子,即F={a,b,c}a:把錢幣q0翻轉(zhuǎn)一次

b:把錢幣q1翻轉(zhuǎn)一次

c:把錢幣q2翻轉(zhuǎn)一次問題的狀態(tài)空間為<{Q5},{a,b,c},{Q0Q7}>2023/2/5人工智能18例2.2翻轉(zhuǎn)錢幣問題(4)3.狀態(tài)空間圖問題的狀態(tài)空間為:2023/2/5人工智能19構(gòu)造狀態(tài)空間圖:

aabababaabbbbcccbcccb2023/2/5人工智能20例2.3修道士和野人問題(1)

在河的左岸有三個(gè)修道士、三個(gè)野人和一條船,修道士們想用這條船將所有的人都運(yùn)過河去,但受到以下條件的限制:(1)修道士和野人都會(huì)劃船,但船一次最多只能運(yùn)兩個(gè)人;(2)在任何岸邊野人數(shù)目都不得超過修道士,否則修道士就會(huì)被野人吃掉。假定野人會(huì)服從任何一種過河安排,試規(guī)劃出一種確保修道士安全過河方案。2023/2/5人工智能21例2.3修道士和野人問題(2)1、問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述:

S=(m,c,b)

m:左岸的修道士數(shù)c:左岸的野人數(shù)b:左岸的船數(shù)右岸的狀態(tài)不必標(biāo)出,因?yàn)椋?/p>

右岸的修道士數(shù)m’=3-m右岸的野人數(shù)c’=3-c右岸的船數(shù)b’=1-b2023/2/5人工智能22例2.3修道士和野人問題(3)狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28

030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S310002023/2/5人工智能23例2.3修道士和野人問題(4)2.操作集F={p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=1,m=m+1,c=c+1q10b=0,(m=0,c=1)或(m=2,c=2)b=1,m=m+1q01b=0,m=0或3,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=0,m=m-1,c=c-1p10b=1,(m=3,c=2)或(m=1,c=1)b=0,m=m-1p01b=1,m=0或3,c≥1b=0,c=c-1操作符條件動(dòng)作例2.3修道士和野人問題(5)3.狀態(tài)空間給出狀態(tài)和操作的描述之后,該問題的狀態(tài)空間是:{{S0},{P

01,P

10,P

11,P

02,P

20,Q01,Q

10,Q

11,Q

02,Q

20},{S31}}。2023/2/5人工智能25例2.3修道士和野人問題(6)S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S31(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0)p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.狀態(tài)空間圖:四條S0到S31長度相等的最短路徑,對(duì)應(yīng)的操作序列就是該問題的四個(gè)最優(yōu)解2023/2/5人工智能262.2.2隱式狀態(tài)空間圖顯式狀態(tài)空間圖:表示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系,這種表示方式稱為顯式狀態(tài)空間圖,或稱為狀態(tài)空間圖的顯示表示。隱式狀態(tài)空間圖:利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換(操作)的知識(shí)定義的狀態(tài)空間圖。在計(jì)算機(jī)中僅存儲(chǔ)描述問題狀態(tài)及操作的有關(guān)知識(shí),包括該問題的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài),以及全部操作的條件和動(dòng)作等。隱式狀態(tài)空間圖也稱為是狀態(tài)空間圖的隱式表示或隱式圖。重排九宮問題的隱式圖描述為:(1)有關(guān)狀態(tài)的知識(shí):狀態(tài)S的定義:S=(X0,X1,X2,X3,X4

,X5,X6

,X7,X8)其中,Xi{0,1,2,3,4,5,6,7,8},,且。初始狀態(tài):S0=(0,1,2,3,5,6,4,7,8)目標(biāo)狀態(tài):Sg=(0,1,2,3,4,5,6,7,8)重排九宮問題的狀態(tài)表示例2.4重排九宮問題(八數(shù)碼問題)

例2.4重排九宮問題(2)(2)有關(guān)操作的知識(shí)(規(guī)則):0組規(guī)則

R1(X0=0

)(X2=n

)X0=nX2=0;R2(X0=0

)(X4=n

)X0=nX4=0;R3(X0=0

)(X6=n

)X0=nX6=0;R4(X0=0

)(X8=n

)X0=nX8=0;1組規(guī)則

R5(X1=0

)(X2=n

)X1=nX2=0;R6(X1=0

)(X8=n

)X1=nX8=0;8組規(guī)則:

R22(X8=0

)(X1=n

)X8=nX1=0;R23(X8=0

)(X0=n

)X8=nX0=0;R24(X8=0

)(X7=n

)X8=nX7=0;……例2.4重排九宮問題(3)八數(shù)碼的狀態(tài)圖可表示為({S0},{r1,r2,…,r24},{Sg})八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn),其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖,或者說狀態(tài)圖的隱式表示。例2.4重排九宮問題(4)(3)隱式圖搜索初始狀態(tài)S=(0,1,2,3,5,6,4,7,8)滿足條件X0=0,故可以使用第0組的四條規(guī)則:如果選擇規(guī)則R1,則狀態(tài)轉(zhuǎn)換為:S1=(2,1,0,3,5,6,4,7,8)2023/2/5人工智能31例2.5旅行商問題(TSP)(1)設(shè)有n個(gè)互相可直達(dá)的城市,某推銷商準(zhǔn)備從其中的A城出發(fā),周游各城市一遍,最后又回到A城。要求為該推銷商規(guī)劃一條最短的旅行路線。(1)狀態(tài)描述:該問題的狀態(tài)為以A打頭城市序列:

=AA1…Ai…Aj…A’其中:A、Ai、Aj、A’為城市名,1i、jn-1,AjA,AiA;

1||n+1;當(dāng)i

j時(shí),AiAj;當(dāng)且僅當(dāng)||=n+1時(shí),A’=A。初始狀態(tài):=A,||=1終止?fàn)顟B(tài):=AA1A2…A,||=n+1例2.5旅行商問題(TSP)(2)(2)操作描述(狀態(tài)轉(zhuǎn)換規(guī)則):規(guī)則1:如果=AA1…Ai…Aj…,且||

n,但A’,則置=A。即沒遍歷完時(shí),在城市序列中添加一個(gè)沒有到過的城市。規(guī)則2:如果||=n,置=

A,即從當(dāng)前城市返回A城。

(3)隱式圖搜索對(duì)于有A、B、C、D四個(gè)城市所組成的連通城市網(wǎng),初始狀態(tài):=A,||=1,滿足規(guī)則1,則操作的結(jié)果為:=AB、或=AC、或=AD,繼續(xù)使用規(guī)則1,直到生成包含四個(gè)城市的序列出現(xiàn),再使用規(guī)則2。2023/2/5人工智能32補(bǔ)充例二階梵塔問題(1)

有三個(gè)桿,一號(hào)桿有A、B兩個(gè)金盤,A小于B。要求將A、B移至三號(hào)桿,每次只可移動(dòng)一個(gè)盤子,任何時(shí)刻B不能在A上。(1)有關(guān)狀態(tài)的知識(shí):用二元組(SA,SB)表示狀態(tài),SA表示A所在桿號(hào),SB表示B所在桿號(hào)。其中:SA

,SB{1,2,3}

,

則全部狀態(tài)如下:

(1,1),(1,2),(1,3)(2,1),(2,2),(2,3)(3,1),(3,2),(3,3)初始狀態(tài)為(1,1),終止?fàn)顟B(tài)為:(3,3)。2023/2/5人工智能33AB123S0:(1,1)123S1:(1,2)123S2:(1,3)AA123S5:(2,3)123S4:(2,2)123S3:(2,1)123S8:(3,3)123S7:(3,2)123S6:(3,1)AAAAABABBBBB補(bǔ)充例二階梵塔問題(2)2023/2/5人工智能34(2)有關(guān)操作的知識(shí)(規(guī)則):A(i,j)表示金盤A從第i號(hào)桿移到j(luò)號(hào)桿,B(i,j)表示金盤B從第i號(hào)桿移到j(luò)號(hào)桿,其中:i,j{1,2,3},但ij,全部操作為:

A(1,2),A(1,3),A(2,1)A(2,3),A(3,1),A(3,2)

B(1,2),B(1,3),B(2,1)B(2,3),B(3,1),B(3,2)分析每個(gè)操作的條件和動(dòng)作,得到下表:補(bǔ)充例二階梵塔問題(3)2023/2/5人工智能35補(bǔ)充例二階梵塔問題(4)操作符條件動(dòng)作A(1,2)SA=1SA=2A(1,3)SA=1SA=3A(2,1)SA=2SA=1A(2,3)SA=2SA=3A(3,1)SA=3SA=1A(3,2)SA=3SA=2B(1,2)SB=1,SA1,2或SA=3SB=2B(1,3)SB=1,SA1,3或SA=2SB=3B(2,1)SB=2,SA1,2或SA=3SB=1B(2,3)SB=2,SA2,3或SA=1SB=3B(3,1)SB=3,SA1,3或SA=2SB=1B(3,2)SB=3,SA2,3或SA=1SB=22023/2/5人工智能36補(bǔ)充例二階梵塔問題(5)(3)狀態(tài)空間圖1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2023/2/5人工智能372.3狀態(tài)空間圖的盲目搜索盲目搜索:搜索時(shí)不參考與具體待求解問題相關(guān)的任何信息,只是按預(yù)先設(shè)定的順序逐個(gè)考察節(jié)點(diǎn)。盲目搜索與問題無關(guān),具有通用性。算法中使用的數(shù)據(jù)結(jié)構(gòu):OPEN表:專門登記已經(jīng)生成但還沒有考察的節(jié)點(diǎn),即待考察節(jié)點(diǎn)。CLOSED表:用來記錄考察過的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系,如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)(返回指針)。CLOSED表中存放的就是一定搜索策略下的搜索樹。2023/2/5人工智能38節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)OPEN表CLOSED表2023/2/5人工智能392.3狀態(tài)空間圖的盲目搜索2.3.1廣度優(yōu)先搜索2.3.2深度優(yōu)先搜索2023/2/5人工智能402.3.1廣度優(yōu)先搜索(1)廣度優(yōu)先搜索(A?ed)基本思想:廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置一層一層向下的搜索過程。通過將OPEN表設(shè)計(jì)為一個(gè)隊(duì)列來實(shí)現(xiàn),將新生成的子節(jié)點(diǎn)放在OPEN表的后面,保證先生成的節(jié)點(diǎn)先考察。廣度優(yōu)先搜索算法:步1把初始節(jié)點(diǎn)S0放入OPEN表中;步2若OPEN表為空,則搜索失敗,退出;步3否則,取OPEN表中第一個(gè)節(jié)點(diǎn)N放在CLOSED表中;并冠以順序編號(hào)n;步4若節(jié)點(diǎn)N為目標(biāo)節(jié)點(diǎn),則搜索成功。利用CLOSED表中的返回指針找出S0到N的路徑即為所求解,退出;步5若N不可擴(kuò)展,轉(zhuǎn)步2;步6

否則,擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的返回指針放入OPEN表的尾部,轉(zhuǎn)步2。2.3.1廣度優(yōu)先搜索(2)2023/2/5人工智能42例2.6使用廣度優(yōu)先搜索算法求解重排九宮問題1238574611238567481382574610123845767123845766138257461112384576212385746312384576412378546122318574613123847651412345876151285374617135827461881325746191237854620231857462112843765221238574651238476523八數(shù)碼廣度優(yōu)先搜索12853746916123856742023/2/5人工智能432.3.1廣度優(yōu)先搜索廣度優(yōu)先搜索的特點(diǎn):廣度優(yōu)先中OPEN表是一個(gè)隊(duì)列,CLOSED表是一個(gè)順序表,表中各節(jié)點(diǎn)按順序編號(hào),正被考察的節(jié)點(diǎn)在表中編號(hào)最大。廣度優(yōu)先搜索又稱為寬度優(yōu)先或橫向搜索。廣度優(yōu)先策略是完備的,即如果問題的解存在,則它一定可以找到解,并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān),具有通用性。缺點(diǎn)搜索效率低。2023/2/5人工智能442.3.2深度優(yōu)先搜索(1)深度優(yōu)先搜索的基本思想:

深度優(yōu)先搜索是一種一直向下的搜索過程,它優(yōu)先在自己的子節(jié)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn),不斷向縱深方向前進(jìn),直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時(shí),才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。深度優(yōu)先搜索算法:

與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是OPEN表被設(shè)計(jì)成后進(jìn)先出的棧,新生成的子節(jié)點(diǎn)放在OPEN表的前面,后生成的節(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索算法只需將寬度優(yōu)先搜索算法步6修改為:步6否則,擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的指針放入OPEN表的首部,轉(zhuǎn)步2。

例2.7使用深度優(yōu)先搜索算法求解重排九宮問題

12385746112384576312384576

123845761238574612384576123847654128437651238574621238476552023/2/5人工智能462.3.2深度優(yōu)先搜索深度優(yōu)先搜索的特點(diǎn):OPEN表為一個(gè)堆棧。深度優(yōu)先又稱縱向搜索。一般不能保證找到最優(yōu)解。如下圖所示:圖2-13深度優(yōu)先搜索不具有完備性示意圖2023/2/5人工智能471.有界深度優(yōu)先搜索(Acd)為克服深度優(yōu)先搜索的不足,可以對(duì)其深度進(jìn)行限制深度界限的選擇很重要

dm若太小,則達(dá)不到解的深度,得不到解;若太大,既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間,又降低了搜索效率。由于解的路徑長度事先難以預(yù)料,所以要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解,它也不一定是最優(yōu)解。2.可變界深度優(yōu)先搜索算法(1)當(dāng)在dm界限之內(nèi)找不到解時(shí),可以將深度界限dm不斷擴(kuò)大,每次增加一個(gè)深度增量d,直到找到解,或者搜索完整棵樹。這樣算法的完備性得到了保證,稱為可變界深度優(yōu)先搜索算法(或迭代加深搜索)。當(dāng)⊿d

=1時(shí),算法開始蛻變?yōu)閺V度優(yōu)先搜索算法。

2.可變界深度優(yōu)先搜索算法(2)迭代加深搜索過程:步1把初始節(jié)點(diǎn)S0放入OPEN表中,置S0的深度d(S0)=0,dm為任意初值。步2若OPEN表為空,則考查CLOSED表是否有待擴(kuò)展節(jié)點(diǎn):

①若無,則問題無解,退出。②若有,則取出CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表中,令dm=dm+⊿d。

2.可變界深度優(yōu)先搜索算法(3)

步3取OPEN表中第一個(gè)節(jié)點(diǎn)N放在CLOSED表中;并冠以編號(hào)n;步4若節(jié)點(diǎn)N為目標(biāo)節(jié)點(diǎn),成功退出。步5若N的深度d(N)>dm(深度限制值),則標(biāo)N為待擴(kuò)展節(jié)點(diǎn),則轉(zhuǎn)步2;

步6N無子節(jié)點(diǎn),則轉(zhuǎn)步2;步7擴(kuò)展N,將其所有子節(jié)點(diǎn)Ni配上指向N的指針放入OPEN首部,置d(Ni)=d(N)+1,轉(zhuǎn)步2。3.可采納的有界深度優(yōu)先搜索算法(1)問題:當(dāng)⊿d

>1時(shí),是否能保證找到最優(yōu)解?2023/2/5人工智能533.可采納的有界深度優(yōu)先搜索算法(2)步1把初始節(jié)點(diǎn)S0放入OPEN表中,置d(S0)=0,dm=dm0,G=NULL。步2若OPEN表為空,則考察CLOSED表是否有待擴(kuò)展節(jié)點(diǎn):(1)若無待擴(kuò)展節(jié)點(diǎn),則判斷G表是否為空:若為空,搜索失敗,退出;否則,取出G表最后面的節(jié)點(diǎn)Sg,Sg即為所求最優(yōu)解,搜索成功,退出;(2)若有待擴(kuò)展節(jié)點(diǎn),則取出CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表中,令dm=dm+⊿d,轉(zhuǎn)步2;3.可采納的有界深度優(yōu)先搜索算法(3)步3取OPEN表中首部的節(jié)點(diǎn)N放在CLOSED表中;并冠以順序編號(hào)n;步4若d(N)>dm,則標(biāo)N為待擴(kuò)展節(jié)點(diǎn),轉(zhuǎn)步2;步5若N是目標(biāo)節(jié)點(diǎn)Sg,則令dm=d(Sg

)-1,把Sg放到G表的尾部,轉(zhuǎn)步2。步6若N不可擴(kuò)展,則轉(zhuǎn)步2;步7否則,擴(kuò)展N,將其所有子節(jié)點(diǎn)Ni配上指向N的返回指針放入OPEN表首部,置d(Ni)=d(N)+1,轉(zhuǎn)步2。

2023/2/5人工智能542.4狀態(tài)空間圖的啟發(fā)式搜索(1)1.啟發(fā)性知識(shí)與啟發(fā)函數(shù)啟發(fā)性知識(shí)就是與被求解問題自身特性相關(guān)的知識(shí),包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗(yàn)、技巧等,對(duì)應(yīng)于問題求解框架中的控制性知識(shí)。啟發(fā)函數(shù)要實(shí)現(xiàn)啟發(fā)式搜索,需要把啟發(fā)性知識(shí)形式化,即用一定的函數(shù)表示出來,通過函數(shù)計(jì)算來評(píng)價(jià)每種選擇的價(jià)值大小,用以指導(dǎo)搜索過程,這樣的函數(shù)稱為啟發(fā)函數(shù)。2023/2/5人工智能552023/2/5人工智能562.4狀態(tài)空間圖的啟發(fā)式搜索(2)2.啟發(fā)函數(shù)的設(shè)計(jì)在實(shí)際設(shè)計(jì)過程中,啟發(fā)函數(shù)是用來估計(jì)搜索樹節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù),通常記為h(x)。啟發(fā)函數(shù)可以是:(1)一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度;(2)一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率;(3)根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。2023/2/5人工智能572.4狀態(tài)空間圖的啟發(fā)式搜索(3)2.4.1啟發(fā)式搜索算法2.4.2啟發(fā)式搜索的A算法和A*算法2.4.3

A*算法在游戲中的應(yīng)用2023/2/5人工智能582.4.1啟發(fā)式搜索算法(1)啟發(fā)式搜索用啟發(fā)函數(shù)來導(dǎo)航,其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計(jì)算與傳播過程,并且由啟發(fā)函數(shù)值來確定節(jié)點(diǎn)的擴(kuò)展順序。按選擇范圍不同,啟發(fā)式搜索分為:全局擇優(yōu)搜索局部擇優(yōu)搜索2023/2/5人工智能592.4.1啟發(fā)式搜索算法(2)1.全局擇優(yōu)搜索基本思想:在OPEN表中保留所有已生成而未考察的節(jié)點(diǎn),并用啟發(fā)函數(shù)h(x)對(duì)它們?nèi)窟M(jìn)行估價(jià),從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展,而不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹的什么地方。2.4.1啟發(fā)式搜索算法(3)全局擇優(yōu)搜索算法:步1把初始節(jié)點(diǎn)S0放入OPEN表中,計(jì)算h(S0);步2若OPEN表為空,則搜索失敗,退出;步3否則,移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以序號(hào)n;步4若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,利用CLOSED表中的返回指針找出S0到N的路徑即為所求解,退出;步5若N不可擴(kuò)展,則轉(zhuǎn)步2;步6否則,擴(kuò)展N,計(jì)算N的每個(gè)子節(jié)點(diǎn)x的函數(shù)值,并將N所有子節(jié)點(diǎn)x配以指向N的返回指針后放入OPEN表中,依據(jù)啟發(fā)函數(shù)對(duì)節(jié)點(diǎn)的計(jì)算,再對(duì)OPEN表中所有節(jié)點(diǎn)按其啟發(fā)函數(shù)值的大小以升序排列,轉(zhuǎn)步2。2023/2/5人工智能602.4.1啟發(fā)式搜索算法(4)2.局部擇優(yōu)搜索基本思想:局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)先搜索,在OPEN表中保留所有已生成而未考察的節(jié)點(diǎn),對(duì)其中新生成的每個(gè)子節(jié)點(diǎn)x計(jì)算啟發(fā)函數(shù),從全部子節(jié)點(diǎn)中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展,其選擇下一個(gè)要考察節(jié)點(diǎn)的范圍是剛剛生成的全部子節(jié)點(diǎn),局部擇優(yōu)搜索算法:與全局擇優(yōu)搜索算法的區(qū)別僅在步6:步6否則,擴(kuò)展N,計(jì)算N的每個(gè)子節(jié)點(diǎn)x的函數(shù)值,并將N的所有子節(jié)點(diǎn)x配以指向節(jié)點(diǎn)N的指針后,將全部子節(jié)點(diǎn)按啟發(fā)函數(shù)值升序排列后放入OPEN表的首部,轉(zhuǎn)步2。2023/2/5人工智能612.4.2啟發(fā)式搜索的A算法和A*算法(1)啟發(fā)函數(shù)是對(duì)當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)未來可能要付出的代價(jià)的估計(jì)。在全局擇優(yōu)和局部擇優(yōu)搜索算法中,都沒有考慮從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)已經(jīng)付出的實(shí)際代價(jià)。在很多實(shí)際問題中,已經(jīng)付出的實(shí)際代價(jià)是必須考慮的,如TSP問題等。將兩者同時(shí)考慮,用于指導(dǎo)搜索的算法稱為A算法和A*算法。2023/2/5人工智能632.4.2啟發(fā)式搜索的A算法和A*算法(2)1.A算法估價(jià)函數(shù)f(x):為了防止在單獨(dú)利用啟發(fā)函數(shù)的時(shí)候誤入歧途,將啟發(fā)函數(shù)h(x)與代價(jià)函數(shù)g(x)相結(jié)合,即初始節(jié)點(diǎn)S0到達(dá)節(jié)點(diǎn)x處已付出的代價(jià)與節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計(jì)值總和。

f(x)=g(x)+h(x)

g(x)代價(jià)函數(shù):初始節(jié)點(diǎn)S0到達(dá)節(jié)點(diǎn)x處已付出的代價(jià),有利于搜索縱向發(fā)展,提高搜索效率,但影響完備性。

h(x)啟發(fā)函數(shù):節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計(jì)值有利于搜索橫向發(fā)展,提高搜索的完備性,但影響搜索效率。2.4.2啟發(fā)式搜索的A算法和A*算法(3)代價(jià)g(x)的計(jì)算

g(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià):

g(S0)=0

g(xj)=g(xi)+c(xi,xj)其中,c(xi,xj)表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的代價(jià)ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32023/2/5人工智能642.4.2啟發(fā)式搜索的A算法和A*算法(4)對(duì)估價(jià)函數(shù)

f(x)=g(x)+h(x)

令其中的h(x)=0時(shí),這時(shí)得到的是代價(jià)樹的非啟發(fā)式搜索算法。按對(duì)節(jié)點(diǎn)的考察范圍不同,可分為兩種搜索策略:分支界限法將全局擇優(yōu)搜索算法中的h(x)替換為g(x),即可得到分支界限搜索算法。瞎子爬山法將局部擇優(yōu)搜索算法中的h(x)替換為g(x),即可得到瞎子爬山搜索算法。2023/2/5人工智能652023/2/5人工智能662.4.2啟發(fā)式搜索的A算法和A*算法(5)步1把附有f(S0

)的初始節(jié)點(diǎn)S0放入OPEN表中;步2若OPEN表為空,則搜索失敗,退出;步3否則,移出OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號(hào)n;步4若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,利用CLOSED表中的返回指針找出S0到N的路徑即為所求解,退出。步5若N不可擴(kuò)展,則轉(zhuǎn)步2;2.4.2啟發(fā)式搜索的A算法和A*算法(6)步6否則,擴(kuò)展N,生成一組子節(jié)點(diǎn)xi,計(jì)算f(xi

),并對(duì)這組節(jié)點(diǎn)xi作如下處理:1)若xi是N的先輩節(jié)點(diǎn),則刪除之。2)若xi存在于OPEN或CLOSED表中,也刪除之,但表明此時(shí)存在兩條初始節(jié)點(diǎn)S0到xi的路徑;如果新路徑較短,則修改xi節(jié)點(diǎn)的返回指針(指向N),并修改xi及其后裔節(jié)點(diǎn)和f值;同時(shí)若xi存在于CLOSED表中,則將其移出放入OPEN表重新考察。3)對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針放入OPEN表。步7對(duì)OPEN表中所有節(jié)點(diǎn)按f值以升序排列,轉(zhuǎn)步2。2023/2/5人工智能672023/2/5人工智能682.4.2啟發(fā)式搜索的A算法和A*算法(7)對(duì)步6的1)的說明:2.4.2啟發(fā)式搜索的A算法和A*算法(8)對(duì)步6的2)的說明:2023/2/5人工智能692.4.2啟發(fā)式搜索的A算法和A*算法(9)樹式搜索例對(duì)于已存在于OPEN表中的節(jié)點(diǎn)(如果有的話)也刪除之;刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑,如果新路徑短,則修改這些節(jié)點(diǎn)在OPEN表中的原返回指針,使其沿原路徑返回。Path1Path2S0mnP先擴(kuò)展后擴(kuò)展P在n之前已是某一節(jié)點(diǎn)m的后繼如圖所示:說明從S0→P至少有兩條路,這時(shí)有兩種情況:f(Path2)<f(Path1),當(dāng)前路徑較好,要修改P的指針,使其指向n,即搜索之后的最佳路徑。否則,原路徑好。2023/2/5人工智能702.4.2啟發(fā)式搜索的A算法和A*算法(10)對(duì)已存在于CLOSED表的節(jié)點(diǎn),作與(2)同樣的處理,并將其移出CLOSED表,放入OPEN表中重新擴(kuò)展。S0過去生成P的路徑現(xiàn)在生成P的路徑過去對(duì)Ps的最優(yōu)路徑PsPmnka.P在n之前已是某一節(jié)點(diǎn)m的后繼,所以需要做如同(2)同樣的處理,如圖右部所示。b.P在Closed表中,說明P的后繼也在n之前已經(jīng)生成,稱為Ps。對(duì)Ps而言同樣可能由于n→P這一路徑的加入,又必須比較多條路徑之后而取代價(jià)小的一條,如圖左部所示。2023/2/5人工智能712.4.2啟發(fā)式搜索的A算法和A*算法(11)f(x)=g(x)+h(x)探討九宮重排問題的估價(jià)函數(shù)的設(shè)計(jì)過程。g(x):對(duì)某一確定的節(jié)點(diǎn),是確定的值。h(x):不同的問題啟發(fā)函數(shù)的定義不同,相同的問題也可以定義出不同的啟發(fā)函數(shù)。衡量h(x)優(yōu)劣的標(biāo)準(zhǔn)是看其是否能夠準(zhǔn)確反映出節(jié)點(diǎn)x到達(dá)目標(biāo)的難易程度(距離)。估價(jià)函數(shù)定義探討2023/2/5人工智能722.4.2啟發(fā)式搜索的A算法和A*算法(12)2023/2/5人工智能7314832765S012384765Sg

估價(jià)函數(shù)f(x)=g(x)+h(x)因素1格局中將牌是否在家g(x)用節(jié)點(diǎn)深度d(x)來衡量如何定義?h(x)用x的格局與目標(biāo)節(jié)點(diǎn)格局相比,不在家的將牌數(shù)目w(x)來衡量。例2.8

A算法在重排九宮問題中的應(yīng)用。1

42837653238533414

28

37651

4

283

5761142

8376512384576212384765012384765Sg1擴(kuò)展順序f(x)值134827653

148

3

2765148327653441428637541428

37651284

376534128

43765128

4

37654261238476571

428376532556714

28

37651

4

283

576142

8376512384765Sg1擴(kuò)展順序f2(x)值134827654

148

3

27651483

276545134

8

27651

3482765513486

27566361

382476551

3482576798

143

27657

341

8

27651347

8

26513486

275713486

27578847810138247655111284376514

28

6

37514

2

8

3765788123847655128

138247652.4.2啟發(fā)式搜索的A算法和A*算法(15)81263754a12384765Sg28146375b問題:是否對(duì)于所有的節(jié)點(diǎn)w(x)都能反映出從x節(jié)點(diǎn)變化到目標(biāo)節(jié)點(diǎn)的難易程度(到目標(biāo)的距離)?

w(a)=7

w(b)=6,從w(x)值看a格局離目標(biāo)格局更遠(yuǎn)。

a格局真的比b格局距離目標(biāo)更遠(yuǎn)嗎?812637

5412384765Sga812637

54

128637

54128637

54128637

54123867

541238647

51238647512384765Sgw(a)=7實(shí)際距離為8123456782023/2/5人工智能772814376528143765

812437658124376581243765281463758132476581324765

13824765138247651238476512384765Sg81324765w(b)=6實(shí)際距離為1112345678910112023/2/5人工智能782.4.2啟發(fā)式搜索的A算法和A*算法(18)

81263754a12384765Sg28146375b考慮因素2,定義h(x)=p(x)p(x)是x格局中每個(gè)將牌離家(Sg中的位置)的最短距離(不論路上是否放有其他將牌)的總和。02111111

p(a)=802122101

p(b)=9反映出a比b更容易到達(dá)目標(biāo)格局實(shí)際距離為8實(shí)際距離為112023/2/5人工智能791

483

2765512384765Sg1擴(kuò)展順序f3(x)值134827655

148

3

27651483276577134

8

27651

3482765513486

27577231

382476551

348257674138247655512384765568

138247652023/2/5人工智能802.4.2啟發(fā)式搜索的A算法和A*算法(20)

因素3格局中將牌回家的順序812637

5412384765Sg2

8

146375ba

因素4中心位置是否有將牌沿著周圍非中心方格上依順時(shí)針檢查x格局中的每一個(gè)將牌,如果其后緊跟著的將牌正好是目標(biāo)格局中該將牌的后續(xù)者,該將牌得0分,否則得2分。在正中方格上有將牌得1分,否則得0分。

綜合因素3和因素4的值,記為s(x)2023/2/5人工智能811

48

3

276520238522253014

28

37651

4

283

57610142

83765123845761812384765712384765Sg1擴(kuò)展順序f4(x)值1348276523

148

3

2765148327652228414286375301428

37651284

37651630128

43765128

4

3765171661238476572023/2/5人工智能822023/2/5人工智能832.4.2啟發(fā)式搜索的A算法和A*算法(22)對(duì)A算法再限制其估價(jià)函數(shù)中的啟發(fā)函數(shù)h(x)滿足:對(duì)所有的節(jié)點(diǎn)x均有:h(x)h*(x)其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià),這就稱為A*算法。A*算法也稱為最佳圖搜索算法,利用A*算法,如果問題存在最優(yōu)解,就保證能找到最優(yōu)解。2.4.2啟發(fā)式搜索的A算法和A*算法(23)例2.9修道士和野人問題。在河的左岸有五個(gè)修道士、五個(gè)野人和一條船,修道士們想用這條船將所有的人都運(yùn)過河去,但受到以下條件的限制:(1)修道士和野人都會(huì)劃船,但船一次最多只能運(yùn)三個(gè)人;(2)在任何岸邊及船上野人數(shù)目都不得超過修道士,否則修道士就會(huì)被野人吃掉。假定野人會(huì)服從任何一種過河安排,試規(guī)劃出一種確保修道士安全過河方案。請(qǐng)定義啟發(fā)函數(shù),并給出相應(yīng)的搜索樹。2023/2/5人工智能842.4.2啟發(fā)式搜索的A算法和A*算法(24)解:先建立問題的狀態(tài)空間。問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述:

S=(m,c,b)

m:左岸的修道士數(shù)c:左岸的野人數(shù)b:左岸的船數(shù)初始狀態(tài)為:(5,5,1)

終止?fàn)顟B(tài)為:(0,0,0)

合法的操作只有使?fàn)顟B(tài)如下轉(zhuǎn)換:從平衡狀態(tài)(m=c)轉(zhuǎn)換為修道士扎堆(m=0或m=5)從平衡狀態(tài)(m=c)轉(zhuǎn)換為平衡狀態(tài)(m=c)從扎堆狀態(tài)(m=0或m=5)轉(zhuǎn)換為平衡狀態(tài)(m=c)2023/2/5人工智能852.4.2啟發(fā)式搜索的A算法和A*算法(25)

定義啟發(fā)函數(shù),若滿足h(n)≤h*(n),即滿足A*條件的。啟發(fā)函數(shù)1:h(n)=0;啟發(fā)函數(shù)2:h(n)=M+C;對(duì)狀態(tài)(1,1,1),啟發(fā)函數(shù)2不滿足h(n)≤h*(n)

提示:不考慮限制條件的運(yùn)送次數(shù)一定小于有限制條件的運(yùn)送次數(shù)。2023/2/5人工智能862.4.2啟發(fā)式搜索的A算法和A*算法(26)先考慮船在左岸的情況:如果不考慮限制條件,至少需要[(m+c-3)/2]*2+1化簡后為:[(m+c-3)/2]*2+1大于等于m+n-2再考慮船在右岸的情況:同樣不考慮限制條件。船在右岸,需要一個(gè)人將船運(yùn)往左岸,因此,對(duì)于狀態(tài)(m,c,0),需要的擺渡數(shù),相當(dāng)于船在左岸的(m+1,c,1)或(m,c+1,1),所以需要的最少擺渡數(shù)為:m+c+1-2+1=m+c綜合條件,需要的最少擺渡數(shù)為m+c-2b。2023/2/5人工智能87(5,5,1)1h=8f=8(5,3,0)11h=8f=9(5,4,0)20h=9f=10(5,2,0)2h=7f=8(4,4,0)12h=8f=9(5,4,2)10h=7f=9(5,3,1)3h=6f=8(3,3,0)8h=6f=9(5,1,0)9h=6f=9(5,0,0)4h=5f=8(4,4,1)19h=6f=10(5,2,1)6h=5f=9(5,1,1)5h=4f=8(2,2,0)7h=4f=9(3,3,1)13h=4f=10(0,3,0)14h=3f=10擴(kuò)展順序h(x)及f(x)值2023/2/5人工智能88(0,3,0)14h=3f=10(0,4,1)15h=2f=10(0,5,1)h=3f=11(1,1,1)17h=0f=10(0,2,1)18h=0f=10(0,3,1)h=1f=11(0,0,0)21h=0f=11(0,1,0)16h=1f=10(0,2,0)h=2f=112023/2/5人工智能892023/2/5人工智能902.4.3

A*算法在游戲中的應(yīng)用(1)啟發(fā)式算法逐漸發(fā)展成為路徑搜索算法的核心,除了A*算法以外,國內(nèi)外研究者還在此基礎(chǔ)上逐漸發(fā)展了許多其它智能算法,包括IDA*算法、D*算法等,它們的基本原理都借鑒了A*算法中的估價(jià)函數(shù)思想。目前,游戲業(yè)界的標(biāo)準(zhǔn)是使用A*算法或IDA*算法,A*算法一般要快一些,而IDA*算法則比A*算法要使用更少的內(nèi)存。2.4.3

A*算法在游戲中的應(yīng)用(2)如果游戲僅僅要求出從點(diǎn)A到達(dá)點(diǎn)B的一條最短路徑的話,那么使用A*算法,將h(x)設(shè)計(jì)為對(duì)A點(diǎn)到B點(diǎn)的最短路徑的估計(jì)就可以完成此任務(wù);然而,真實(shí)游戲中往往還要考慮路上的障礙物、或者在從點(diǎn)A到點(diǎn)B的途中避免被看到或被射擊到、以及敵方的位置和火力線等。在游戲設(shè)計(jì)中,使用A*算法尋找路徑時(shí),啟發(fā)函數(shù)h(x)的設(shè)計(jì)還需要考慮更多的因素,如路徑的距離、途中的障礙物、地形允許的行走速度、是否敵人視線與火力之下的位置、敵我雙方暴露的時(shí)間和次數(shù)、敵方的威脅是否動(dòng)態(tài)的、有掩護(hù)物和隱身處的路徑等因素。2.4.3

A*算法在游戲中的應(yīng)用(3)比如:對(duì)那些暴露在敵方火力偵查或是覆蓋之下的位置增加其代價(jià)值,使得A*算法生成一條盡量避免敵人偵查或射擊的路徑;如果敵方的飛機(jī)處于被我方地對(duì)空導(dǎo)彈防御的區(qū)域,那么,同樣暴露20秒,是一次暴露20秒,還是分四次暴露,一次暴露5秒,顯然對(duì)我方來說代價(jià)是不一樣的;另外,敵方的威脅是靜態(tài)的或動(dòng)態(tài)的,估價(jià)函數(shù)值計(jì)算出來也應(yīng)該不同。當(dāng)然,考慮更多的因素一定會(huì)增加代價(jià)計(jì)算量,所以,在實(shí)際當(dāng)中,使用A*算法進(jìn)行游戲設(shè)計(jì)時(shí),還需要在獲得戰(zhàn)術(shù)能力和所付出的計(jì)算量之間做出權(quán)衡。2023/2/5人工智能932.5與或圖表示及搜索技術(shù)2.5.1與或圖表示2.5.2與或樹的盲目搜索2.5.3與或樹的啟發(fā)式搜索問題分解:在問題求解過程中,常常將一個(gè)復(fù)雜的問題P分解為一組子問題,當(dāng)這些子問題全部可解時(shí),原問題P可解;任何一個(gè)子問題無解時(shí),都將導(dǎo)致原問題P無解。即一個(gè)問題與一組子問題的“與”等價(jià)。如:保送研究生的條件是每門課程成績都在85分以上。問題變換:有時(shí)將一個(gè)復(fù)雜的問題P變換為與之等價(jià)的一組子問題,其中任何一個(gè)子問題可解時(shí),原問題P可解;全部子問題無解時(shí),原問題P無解。即一個(gè)問題與一組子問題的“或”等價(jià)。如:保送研究生的條件中,要求英語成績是通過六級(jí)考試,或者通過GRE考試。與或圖:將問題對(duì)應(yīng)節(jié)點(diǎn),分解或變換關(guān)系對(duì)應(yīng)邊,這樣,就可以將一個(gè)問題求解過程中的分解和變換過程表示為一棵與或圖。與狀態(tài)空間圖的意義不同,這里的與或圖對(duì)應(yīng)的是問題空間圖。2023/2/5人工智能942.5.1與或圖表示(1)與或圖的概念來源于問題求解中的分解和變換一個(gè)復(fù)雜的問題P常常可以分解為與之等價(jià)的一組子問題P1,P2,

Pn,當(dāng)這些問題全部可解時(shí),問題可解;任何一個(gè)子問題無解時(shí),都將導(dǎo)致原問題P無解。即一個(gè)問題與一組子問題的與等價(jià)。一個(gè)復(fù)雜的問題P常??梢苑謩e變換為與之等價(jià)的一組子問題P1,P2,

Pn,其中任何一個(gè)子問題可解時(shí),問題可解;全部子問題無解時(shí),原問題P無解。即一個(gè)問題與一組子問題的或等價(jià)。2.5.1與或圖表示(2)例2.10猴子摘香蕉問題房間內(nèi)有一只猴子位于A處,有一只箱子位于B處,還有一架梯子位于C處,A到B的距離與A到C是距離相同,梯子和箱子的重量相同。屋頂上D處掛著一串香蕉,猴子爬到梯子上或箱子上都能摘到香蕉。2023/2/5人工智能962.5.1與或圖表示(3)2023/2/5人工智能97定義五個(gè)動(dòng)作:f1(x,y):表示猴子從x處走到y(tǒng)處;f2(x,y):表示猴子推箱子從x處走到y(tǒng)處;f3(x,y):表示猴子搬梯子從x處走到y(tǒng)處;f4()

:表示登上箱子;f5():表示登上梯子;f6()

:表示摘到香蕉;則猴子摘香蕉問題的分解變換過程可用如下與或圖表示:2023/2/5人工智能982.5.1與或圖表示(4)例2.11證明四邊形全等。分析:連接BD,B′D′,原來問題可以分解為兩個(gè)子問題:Q1:證明ΔABC≌ΔA′B′C′Q2:證明ΔBCD≌ΔB′C′D′原來問題可以分為兩個(gè)子問題解決。ABDCA′B′D′C′2.5.1與或圖表示(5)問題Q1還可以再被分解為:

Q11

:證明AB=A′B′Q12

:證明AD=A′D′Q13

:證明∠A=∠A′或

Q11′:證明AB=A′B′Q12′:證明AD=A′D′Q13′:證明BD=B′D′問題Q2還可以再被分解為:

Q21

:證明BC=B′C′Q22

:證明CD=C′D′Q23

:證明∠C=∠C′或

Q21′:證明BC=B′C′Q22′:證明CD=C′D′Q23′:證明BD=B′D′′2023/2/5人工智能1002.5.1與或圖表示(5)將原問題用圖的形式表示如下:QQ1Q2Q11Q12Q13Q11'Q12'Q13'Q21Q22Q23Q21'Q22'Q23'弧線表示所連邊為“與”的關(guān)系不帶弧線的邊為或關(guān)系2.5.1與或圖表示(6)例2.12梵塔問題。

有1、2、3號(hào)桿,1號(hào)桿自上而下串著從小到大的n個(gè)金盤,要把1號(hào)桿上的n個(gè)金盤移到3號(hào)桿上。移動(dòng)金盤的規(guī)則是:一次只能移一個(gè)金盤;移動(dòng)的過程中不允許大盤壓在小盤上。2023/2/5人工智能1013123122.5.1與或圖表示(6)(1,1,1)=>(3,3,3)(1,1,1)=>(1,1,3)(1,2,3)=>(1,2,2)(3,2,2)=>(3,2,1)(3,3,1)=>(3,3,3)(1,1,3)=>(1,2,3)(3,2,1)=>(3,3,1)(1,1,1)=>(1,2,2)(1,2,2)=>(3,2,2)(3,2,2)=>(3,3,3)三階梵塔問題的與或樹2023/2/5人工智能1032.5.1與或圖表示(7)與或圖的幾個(gè)概念:直接可解的問題稱為本原問題。本原問題對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)。無子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)。子節(jié)點(diǎn)為與關(guān)系,則該節(jié)點(diǎn)為與節(jié)點(diǎn)。子節(jié)點(diǎn)為或關(guān)系,則該節(jié)點(diǎn)為或節(jié)點(diǎn)。與或圖一般表示問題的變換過程,就是從原問題出發(fā),運(yùn)用某些規(guī)則不斷的進(jìn)行問題的分解(得到與分支)和變換(得到或分支),而得到一個(gè)與或圖,與或圖的節(jié)點(diǎn)一般代表問題,整個(gè)圖就表示問題空間。2023/2/5人工智能1042.5.1與或圖表示(8)與或圖也可以用三元組表示:(Q0,F,Qn)Q0表示初始問題F表示問題變換規(guī)則集Qn表示本原問題集2.5.1與或圖表示(9)節(jié)點(diǎn)的可解性判別:(1)終止節(jié)點(diǎn)是可解節(jié)點(diǎn);(2)一個(gè)與節(jié)點(diǎn)可解,當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)可解;(3)一個(gè)或節(jié)點(diǎn)可解,只要其子節(jié)點(diǎn)至少有一個(gè)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論