資源描述:
《第3章圖搜索與問(wèn)題求解ppt課件.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第3章圖搜索與問(wèn)題求解9/4/20211人工智能推理與搜索圖搜索技術(shù)是人工智能的核心技術(shù)之一。任一搜索過(guò)程也都是一個(gè)推理過(guò)程。隱式圖的搜索過(guò)程是一種利用局部性知識(shí)構(gòu)造全局性答案的過(guò)程。在各種搜索過(guò)程中,人工智能最感興趣的是那些具有很強(qiáng)選擇性的啟發(fā)式方法,即那些利用很局部的狀態(tài)空間可以有效地找到問(wèn)題的解的方法。機(jī)器學(xué)習(xí)等很多過(guò)程都是在假設(shè)空間中搜索目標(biāo)的過(guò)程。9/4/20212人工智能第3章圖搜索與問(wèn)題求解3.1狀態(tài)圖知識(shí)表示(狀態(tài)圖搜索問(wèn)題求解)3.2狀態(tài)圖搜索3.3與或圖知識(shí)表示(與或圖搜索問(wèn)題求解)3.4與或圖搜索3.5博弈樹(shù)搜索9/4/20213人工智能3.1狀態(tài)圖知識(shí)表示3.1.
2、1狀態(tài)、操作和狀態(tài)空間3.1.2修道士和野人的狀態(tài)空間3.1.3梵塔問(wèn)題的狀態(tài)空間3.1.4問(wèn)題求解的基本框架3.1.5重排九宮問(wèn)題和隱式圖9/4/20214人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(1)例3.1走迷宮9/4/20215人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(2)例3.2八數(shù)碼問(wèn)題2831476512384765初始棋局目標(biāo)棋局以上兩個(gè)問(wèn)題抽象來(lái)看,都是某個(gè)有向圖中尋找目標(biāo)或路徑的問(wèn)題,在人工智能技術(shù)中,把這種描述問(wèn)題的有向圖稱(chēng)為狀態(tài)空間圖,簡(jiǎn)稱(chēng)狀態(tài)圖。9/4/20216人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(3)狀態(tài)(State)為了描述某一類(lèi)事物中各個(gè)不同事物之間的差異
3、而引入的最少的一組變量q的有序組合。表示成矢量形式:狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。9/4/20217人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(4)狀態(tài)轉(zhuǎn)換規(guī)則(操作operator)引起狀態(tài)中某些分量發(fā)生改變,從而使一個(gè)具體狀態(tài)變化到另一個(gè)具體狀態(tài)的作用。它可以是一個(gè)機(jī)械性的步驟、過(guò)程、規(guī)則或算子。操作描述了狀態(tài)之間的關(guān)系。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對(duì)、條件語(yǔ)句、規(guī)則、函數(shù)、過(guò)程等表示。9/4/20218人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(5)狀態(tài)空間(StateSpace)問(wèn)題的狀態(tài)空間是一個(gè)表示該問(wèn)題全部的可能狀態(tài)及相互關(guān)系的圖。一般用賦值有向圖表示,
4、包含S:?jiǎn)栴}的可能有的初始狀態(tài)的集合;F:操作的集合;G:目標(biāo)狀態(tài)的集合。狀態(tài)空間常記為三元序列9/4/20219人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(6)狀態(tài)空間中問(wèn)題求解在狀態(tài)空間表示法中,問(wèn)題求解過(guò)程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)Qs出發(fā)到達(dá)目標(biāo)狀態(tài)Qg的路徑問(wèn)題,也就是尋找操作序列的問(wèn)題。狀態(tài)空間的解為三元組Qs:某個(gè)初始狀態(tài)Qg:某個(gè)目標(biāo)狀態(tài)a:把變換成的有限的操作序列狀態(tài)轉(zhuǎn)換圖S1S3S2…O1O2O3O4QsQgOn9/4/202110人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(7)例3.7迷宮問(wèn)題的狀態(tài)圖表示。S:SoF:{(So,S4),(
5、S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)}G:Sg迷宮問(wèn)題規(guī)則集描述了圖中所有節(jié)點(diǎn)和邊。類(lèi)似于這樣羅列出全部節(jié)點(diǎn)和邊的狀態(tài)圖稱(chēng)為顯式狀態(tài)圖,或者說(shuō)狀態(tài)圖的顯式表示。9/4/202111人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(8)補(bǔ)充例1三枚錢(qián)幣,能否從下面狀態(tài)翻動(dòng)三次后出現(xiàn)全正或全反狀態(tài)。反正反正正正反反反初始狀態(tài)θs目標(biāo)狀態(tài)集合{θ0,θ7}9/
6、4/202112人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(9)引入一個(gè)三元組(q0,q1,q2)來(lái)描述總狀態(tài),錢(qián)幣正面為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)錢(qián)幣的操作抽象為改變上述狀態(tài)的算子,即F={a,b,c}a:把錢(qián)幣q0翻轉(zhuǎn)一次b:把錢(qián)幣q1翻轉(zhuǎn)一次c:把錢(qián)幣q2翻轉(zhuǎn)一次問(wèn)題的狀態(tài)空間為<{Q5},{Q0Q7},{a,b,c}>9/4/202113人工智能3.1.1狀態(tài)、操作和狀態(tài)空間(10)狀態(tài)空間圖(0,0,0
7、)(1,0,1)(0,0,1)(0,1,0)(1,1,0)(1,0,0)(0,1,0)(1,1,1)acabacabcbbc9/4/202114人工智能3.1.2修道士和野人問(wèn)題的狀態(tài)空間(1)補(bǔ)充例2修道士和野人問(wèn)題。在河的左岸有三個(gè)修道士、三個(gè)野人河一條船,修道士們想用這條船將所有的人都運(yùn)過(guò)河去,但受到以下條件的限制:(1)修道士和野人都會(huì)劃船,但船一次最多只能運(yùn)兩個(gè)人;(2)在任何岸邊野人數(shù)目都不得超過(guò)修道士,否則修道士就會(huì)被