第3章圖搜索與問題求解

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

1、第3章圖搜索與問題求解推理與搜索圖搜索技術(shù)是人工智能的核心技術(shù)之一。任一搜索過程也都是一個推理過程。隱式圖的搜索過程是一種利用局部性知識構(gòu)造全局性答案的過程。在各種搜索過程中，人工智能最感興趣的是那些具有很強選擇性的啟發(fā)式方法，即那些利用很局部的狀態(tài)空間可以有效地找到問題的解的方法。機器學(xué)習(xí)等很多過程都是在假設(shè)空間中搜索目標(biāo)的過程。9/10/20212人工智能第3章圖搜索與問題求解3.1狀態(tài)圖知識表示（狀態(tài)圖搜索問題求解）3.2狀態(tài)圖搜索3.3與或圖知識表示（與或圖搜索問題求解）3.4與或圖搜索3.5博弈樹搜索9/10/20213人

2、工智能3.1狀態(tài)圖知識表示3.1.1狀態(tài)、操作和狀態(tài)空間3.1.2修道士和野人的狀態(tài)空間3.1.3梵塔問題的狀態(tài)空間3.1.4重排九宮問題和隱式圖3.1.5問題求解的基本框架9/10/20214人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（1）例3.1走迷宮走迷宮問題就是從該有向圖的初始節(jié)點出發(fā)，尋找目標(biāo)節(jié)點的問題，或者是尋找通向目標(biāo)節(jié)點的路徑問題。9/10/20215人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（2）例3.2八數(shù)碼難題(重排九宮問題)2831476512384765初始棋局目標(biāo)棋局以上兩個問題抽象來看，都是某個有向圖中尋找目標(biāo)

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

4、使一個具體狀態(tài)變化到另一個具體狀態(tài)的作用。它可以是一個機械性的步驟、過程、規(guī)則或算子。操作描述了狀態(tài)之間的關(guān)系。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。9/10/20218人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（5）狀態(tài)空間（StateSpace）問題的狀態(tài)空間是一個表示該問題全部的可能狀態(tài)及相互關(guān)系的圖。狀態(tài)空間一般用賦值有向圖表示，記為：（S，F(xiàn)，G）S：問題的可能有的初始狀態(tài)的集合；F：操作的集合；G：目標(biāo)狀態(tài)的集合。9/10/20219人工智能3.1.1狀態(tài)、操作和狀

5、態(tài)空間（6）狀態(tài)空間中問題求解在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)Qs出發(fā)到達(dá)目標(biāo)狀態(tài)Qg的路徑問題，也就是尋找操作序列的問題。狀態(tài)空間的解為三元組Qs：某個初始狀態(tài)Qg：某個目標(biāo)狀態(tài)a：把Qs變換成Qg的有限的操作序列狀態(tài)轉(zhuǎn)換圖S1S3S2…O1O2O3O4QsQgOn9/10/202110人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（7）例3.7迷宮問題的狀態(tài)圖表示。S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),

6、(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迷宮問題規(guī)則集描述了圖中所有節(jié)點和邊。類似于這樣羅列出全部節(jié)點和邊的狀態(tài)圖稱為顯式狀態(tài)圖，或者說狀態(tài)圖的顯式表示。9/10/202111人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（8）補充例1三枚錢幣，能否從下面狀態(tài)翻動三次后出現(xiàn)全正或全反狀態(tài)。反正反正正正反反反初始狀態(tài)θs目標(biāo)狀態(tài)集合{θ0,θ7}9/10/202112人工智能3.1.1

7、狀態(tài)、操作和狀態(tài)空間（9）引入一個三元組(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)。翻動錢幣的操作抽象為改變上述狀態(tài)的算子，即F＝{a,b,c}a:把錢幣q0翻轉(zhuǎn)一次b:把錢幣q1翻轉(zhuǎn)一次c:把錢幣q2翻轉(zhuǎn)一次問題的狀態(tài)空間為<{Q5},{Q0Q7},{a,b,c}>9/10/202113人工智能3.1.1狀態(tài)、操作和狀態(tài)空間（10

8、）狀態(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/10/202114人工智能3.1.2修道士和野人問題的狀態(tài)空間（1）補充例2修道士