圖搜索與問(wèn)題求解.ppt

《圖搜索與問(wèn)題求解.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第3章圖搜索與問(wèn)題求解推理與搜索圖搜索技術(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/6/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/6/20213

2、人工智能3.1狀態(tài)圖知識(shí)表示3.1.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/6/20214人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（1）例3.1走迷宮走迷宮問(wèn)題就是從該有向圖的初始節(jié)點(diǎn)出發(fā)，尋找目標(biāo)節(jié)點(diǎn)的問(wèn)題，或者是尋找通向目標(biāo)節(jié)點(diǎn)的路徑問(wèn)題。9/6/20215人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（2）例3.2八數(shù)碼難題(重排九宮問(wèn)題)2831476512384765初始棋局目標(biāo)棋局以上兩個(gè)問(wèn)題抽象來(lái)看，都是某個(gè)有向圖中尋找

3、目標(biāo)或路徑的問(wèn)題，在人工智能技術(shù)中，把這種描述問(wèn)題的有向圖稱為狀態(tài)空間圖，簡(jiǎn)稱狀態(tài)圖。棋局作為節(jié)點(diǎn)，相鄰節(jié)點(diǎn)通過(guò)移動(dòng)數(shù)碼一個(gè)一個(gè)產(chǎn)生出來(lái)，所有節(jié)點(diǎn)由它們的相鄰關(guān)系連成一個(gè)有向圖。9/6/20216人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（3）狀態(tài)（State）p62為了描述某一類事物中各個(gè)不同事物之間的差異而引入的最少的一組變量q的有序組合，表征了問(wèn)題的特征和結(jié)構(gòu)。表示成矢量形式：狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。9/6/20217人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（4）狀態(tài)轉(zhuǎn)換規(guī)則（操作operator）引起狀態(tài)中某些分量發(fā)生改變

4、，從而使一個(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/6/20218人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（5）狀態(tài)空間（StateSpace）問(wèn)題的狀態(tài)空間是一個(gè)表示該問(wèn)題全部的可能狀態(tài)及相互關(guān)系的圖。狀態(tài)空間一般用賦值有向圖表示，記為：（S，F(xiàn)，G）S：?jiǎn)栴}的可能有的初始狀態(tài)的集合；F：操作的集合；G：目標(biāo)狀態(tài)的集合。9/6/20219人工智能3.1.1狀態(tài)、

5、操作和狀態(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：把Qs變換成Qg的有限的操作序列狀態(tài)轉(zhuǎn)換圖S1S3S2…O1O2O3O4QsQgOn9/6/202110人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（7）例3.7迷宮問(wèn)題的狀態(tài)圖表示。S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S

6、2,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)和邊。類似于這樣羅列出全部節(jié)點(diǎn)和邊的狀態(tài)圖稱為顯式狀態(tài)圖，或者說(shuō)狀態(tài)圖的顯式表示。9/6/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/202112人工

7、智能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/6/202113人工智能3.1.1狀態(tài)、操

8、作和狀態(tài)空間（10）狀態(tài)空間圖（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc9/6/202114人工智能3.1.2修道士和野人問(wèn)題的狀態(tài)空間（1）補(bǔ)充例2修道士和野人問(wèn)題。在河的左岸有三