人工智能第2章(知識表示方法1-狀態(tài)空間法)ppt課件

1、2021/2/1,人 工 智 能 Artificial Intelligence (AI,許建華 南京師范大學計算機科學與技術(shù)學院 2011年秋季,2021/2/1,第2章 知識表示方法,2.1 狀態(tài)空間法 2.2 問題歸約法 2.3 謂詞邏輯法,2021/2/1,用計算機技術(shù)解決實際問題的一般思路,實際 問題,問題表達 知識表達 數(shù)學建模,求解的方法 或者算法,結(jié)果的解釋,2021/2/1,例：求側(cè)面積為150平方米的體積最大的長方體,設(shè)長、寬、高分別為 x, y, z 側(cè)面積為：2(xy + yz + xz) 體積為：xyz 數(shù)學模型 max xyz s.t. 2(xy + yz + xz

2、)=150,x,y,z,2021/2/1,利用最優(yōu)化技術(shù)中的算法，可以得到結(jié)果： x = y = z = 5.0 解釋：長、寬、高都等于5米時，體積最大,說明：在計算數(shù)學的課程中，主要關(guān)心求解的具體算法,2021/2/1,在人工智能中，重點關(guān)注兩個方面的內(nèi)容： 問題的表示（知識的表示）：即要找到問題的一種合適的表示方法 在人工智能中，我們要涉及到： 狀態(tài)空間法 問題歸約法 謂詞邏輯法 樣本向量法,2021/2/1,問題的求解：從問題表示方法出發(fā)，找到一個合理的辦法來求解 在人工智能中，常有的方法有： 搜索法 推理法 計算方法,2021/2/1,2.1 狀態(tài)空間法,在日常的一些智力游戲（八數(shù)碼、

3、走八卦陣、走迷宮等）中，我們采用的策略：試著向前走，如果走不通，則往后退，不停地試、試、試，直到成功,2021/2/1,類似地，在人工智能中，一種最基本的求解方法就是試探搜索法，即，通過在某個可能的解空間（例如，所有可能的走法）中尋找一個解,這種基于解空間的問題表示和求解方法就是狀態(tài)空間法，其基礎(chǔ)是狀態(tài)和算符（算子,2021/2/1,2.1.1 問題狀態(tài)描述,狀態(tài)： 描述某一類不同事物間的差別而引入的一組最少變量q0 ,q1 , qn的有序集合,2021/2/1,例：描述在坐的同學 變量可以有 年級 班級 姓名 性別 學號,根據(jù)要解決的問題、從中選擇最少的一組變量,例： 區(qū)分哪一個班：年級、班

4、級 區(qū)分哪一位同學：姓名、性別、學號,2021/2/1,矢量形式： Q= q0, q1, , qn T,其中，元素 qi ( i=0, 1, n)為集合的分量，稱為狀態(tài)變量,具體狀態(tài)：給每一個狀態(tài)變量一個具體的值（符號、數(shù)值等,2021/2/1,矩陣形式,2021/2/1,例：八數(shù)碼問題,矢量形式的狀態(tài)表示,矩陣形式的狀態(tài)表示,2021/2/1,算符（操作符）：使問題從一個狀態(tài)變換到另一狀態(tài)的手段。 例如：走步、規(guī)則、數(shù)學算子、運算符號等等,2021/2/1,例：描述在坐的同學（續(xù)） 狀態(tài)變量可以有 年級 班級 姓名 性別 學號,操作符 入學 正常升級 畢業(yè),2021/2/1,例：八數(shù)碼問題,

5、算符： 1、數(shù)字的上、下、左、右移動 2、空格的上、下、左、右移動,2021/2/1,問題的狀態(tài)空間：一個表示問題全部可能狀態(tài)及其關(guān)系的圖，它包含了三個集合： 所有可能的問題初始狀態(tài)集合S 操作符集合F 目標狀態(tài)集合G 狀態(tài)空間記作三元狀態(tài)（S, F, G,2021/2/1,例：十五數(shù)碼問題,初始狀態(tài)：左圖 目標狀態(tài)：右圖 操作符集合F空格的左移、上移、右移、下移,2021/2/1,可能的求解過程,注：在程序和圖示求解過程中，需要規(guī)定好操作符的使用順序,2021/2/1,要完成某一個具體問題的狀態(tài)描述，必須完成三項工作： 如何描述狀態(tài)，特別是初始狀態(tài) 操作符集合及其對狀態(tài)描述的作用 如何描述目

6、標狀態(tài) 即定義好三元狀態(tài)（S, F, G）中的三個成分,2021/2/1,狀態(tài)空間法： 從某一個初始狀態(tài)開始，每次施加一個操作符，遞增地建立操作符序列，直到達到目標狀態(tài)為止,2021/2/1,狀態(tài)空間法的問題： 尋找從初始狀態(tài)到目標狀態(tài)的某一個操作符序列 狀態(tài)空間法的解： 從初始狀態(tài)變換到目標狀態(tài)的操作符序列,左、下、上,2021/2/1,2.1.2 狀態(tài)圖示法,圖是由節(jié)點（不一定是有限個的節(jié)點）的集合構(gòu)成的 注意：在圖論中，圖的定義中還包括邊的集合,狀態(tài)空間法（求解過程）的表示方法：用圖來表示（借助于圖論中某些技術(shù),2021/2/1,有向圖和無向圖,2021/2/1,無向圖：一對節(jié)點可能互為

7、后裔，邊用線段來表示,2021/2/1,有向圖：一對節(jié)點用弧線連接起來，并且從一個節(jié)點指向另一個節(jié)點,父輩節(jié)點或祖先n i,后繼節(jié)點或后裔nj,2021/2/1,對于某一個節(jié)點序列 （ni0, ni2, nij, , nik） 如果每一個節(jié)點 nij-1 都有一個后繼節(jié)點 nij 存在，則將這一序列稱為從節(jié)點 ni0 到 nik 的長度為 k 的路徑,nik,ni0,2021/2/1,如果從節(jié)點 ni 到 nj 存在一條路徑，則稱節(jié)點 nj 是從節(jié)點 ni 可到達的節(jié)點，或者稱 nj 是 ni 的后裔節(jié)點、稱 ni 是 nj 的祖先,nj,ni,祖先,后裔,2021/2/1,當用有向圖來表示狀

8、態(tài)空間法時，對應(yīng)關(guān)系： 圖中的一個節(jié)點對應(yīng)于某一個狀態(tài) 圖中的一個有向弧對應(yīng)于某一個算符,注：有向弧的旁邊可以標以具體算符,2021/2/1,狀態(tài),節(jié)點,操作符,有向弧,2021/2/1,問題：尋找從初始狀態(tài)到目標狀態(tài)的某個操作符序列,問題：尋找圖中初始節(jié)點（對應(yīng)初始狀態(tài)）到目標節(jié)點（對應(yīng)于目標狀態(tài)）的一條路徑,轉(zhuǎn)化為,2021/2/1,c (ni , nj) 表示從節(jié)點 ni 指向節(jié)點 nj （相鄰）的那一段弧的代價,n j,n i,在某些情況下，每個操作符作用、成本是不一樣的，需要引入代價的概念,2021/2/1,不相鄰的）兩個節(jié)點間路徑的代價等于連接該路徑的各個節(jié)點的所有弧線的代價之和,

9、nk,n0,C(n0,n1,C(nk-1,nk,2021/2/1,引入代價的概念后，我們的問題可能是： 尋找初始節(jié)點到目標節(jié)點之間的代價最小的路徑 對應(yīng)的原始問題：尋找從初始狀態(tài)到目標狀態(tài)的操作符代價之和最小的操作符序列,2021/2/1,利用圖論的技術(shù)，我們要解決兩個問題： 第一、找出初始節(jié)點到目標節(jié)點的一條路徑。對應(yīng)于尋找初始狀態(tài)到目標狀態(tài)的操作符序列 第二、找出初始節(jié)點到目標節(jié)點的一條代價最小的路徑。對應(yīng)于尋找將初始狀態(tài)變換到目標狀態(tài)所用操作符代價之和最小的操作符序列,2021/2/1,2.1.3 例子,例1：八數(shù)碼問題 八數(shù)碼的任何一種擺法是一個狀態(tài)，狀態(tài)總數(shù)為9！。用一個長度為9的一

10、維數(shù)組來描述狀態(tài)：（q1, q2, ,q9） 其中，qi 取0, 1, , 8個數(shù)，0表示空格，且取值互不相同。 算符是空格的上、下、左、右移動,2021/2/1,如果記空格的位置為P，這時空格的移動規(guī)則是,P,P-3,P+1,P+3,P-1,表示位置,1 2 3 4 5 6 7 8 9,P,2021/2/1,空格移動規(guī)則,表示位置,2021/2/1,初始狀態(tài)：(2，0，3，1，8，4，5，6，7,目標狀態(tài):（1，2，3，8，0，4，7，6，5,部分狀態(tài)空間圖,2021/2/1,注意： 事先規(guī)定操作符的前后順序，便于編程 不要生成已有的狀態(tài)（節(jié)點），防止進入死循環(huán),2021/2/1,例2：迷宮

11、問題,2021/2/1,給圖上加一個坐標系，定義每一個分叉路口為一個狀態(tài),2021/2/1,操作符為人的上、下、左、右走動,初始狀態(tài)為（1，1,目標狀態(tài)為（4，4,2021/2/1,部分狀態(tài)空間圖,2021/2/1,例3：梵塔問題（三個盤） 對于 n 個盤的問題，我們用 n 維向量 （a1 a2an） 表示問題的一個狀態(tài) 其中ai = 1, 2, 3 表示第i個盤位于第一、二、三個柱子上，a1 an中盤的大小從大到小,2021/2/1,初始狀態(tài)為（11），目標狀態(tài)為（33） 操作符m(i, j)：表示一個盤從 i 根柱子搬到第 j 根柱子。 T(k)：表示第 k 根柱子上（最上面）的盤的大小。

12、 操作符集合為： O=m( i , j ) | T( i )T( j,2021/2/1,部分狀態(tài)空間圖,2021/2/1,例4：猴子與香蕉問題,a c b,2021/2/1,用一個四元組（W，x, Y, z）來表示問題的狀態(tài) W：猴子的水平位置 x： 當猴子爬到箱子頂上取1，否則取0 Y： 箱子的水平位置 z： 當猴子摘到香蕉時取1，否則取0 初始狀態(tài)是（a, 0, b, 0），目標狀態(tài)是（c, 1, c, 1,2021/2/1,操作符： 猴子當前位置W走到水平位置U：goto(U)： （W, 0 , Y, z）(U, 0 , Y, z) 注：猴子必須不在箱子上 猴子將箱子從W位置推到水平位置V：pushbox(V)： （W, 0, W, z） (V, 0, V, z) 注：猴子與箱子必須在同一位置,2021/2/1,操作符： 猴子爬到箱子上：climbbox： （W, 0, W, z） (W，1, W, z) 猴子