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

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

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

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

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

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

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

8、j,ni,祖先,后裔,2021/2/10,當用有向圖來表示狀態空間法時，對應關系： 圖中的一個節點對應于某一個狀態 圖中的一個有向弧對應于某一個算符,注：有向弧的旁邊可以標以具體算符,2021/2/10,狀態,節點,操作符,有向弧,2021/2/10,問題：尋找從初始狀態到目標狀態的某個操作符序列,問題：尋找圖中初始節點（對應初始狀態）到目標節點（對應于目標狀態）的一條路徑,轉化為,2021/2/10,c (ni , nj) 表示從節點 ni 指向節點 nj （相鄰）的那一段弧的代價,n j,n i,在某些情況下，每個操作符作用、成本是不一樣的，需要引入代價的概念,2021/2/10,不相鄰的

9、）兩個節點間路徑的代價等于連接該路徑的各個節點的所有弧線的代價之和,nk,n0,C(n0,n1,C(nk-1,nk,2021/2/10,引入代價的概念后，我們的問題可能是： 尋找初始節點到目標節點之間的代價最小的路徑 對應的原始問題：尋找從初始狀態到目標狀態的操作符代價之和最小的操作符序列,2021/2/10,利用圖論的技術，我們要解決兩個問題： 第一、找出初始節點到目標節點的一條路徑。對應于尋找初始狀態到目標狀態的操作符序列 第二、找出初始節點到目標節點的一條代價最小的路徑。對應于尋找將初始狀態變換到目標狀態所用操作符代價之和最小的操作符序列,2021/2/10,2.1.3 例子,例1：八數

10、碼問題 八數碼的任何一種擺法是一個狀態，狀態總數為9！。用一個長度為9的一維數組來描述狀態：（q1, q2, ,q9） 其中，qi 取0, 1, , 8個數，0表示空格，且取值互不相同。 算符是空格的上、下、左、右移動,2021/2/10,如果記空格的位置為P，這時空格的移動規則是,P,P-3,P+1,P+3,P-1,表示位置,1 2 3 4 5 6 7 8 9,P,2021/2/10,空格移動規則,表示位置,2021/2/10,初始狀態：(2，0，3，1，8，4，5，6，7,目標狀態:（1，2，3，8，0，4，7，6，5,部分狀態空間圖,2021/2/10,注意： 事先規定操作符的前后順序，

11、便于編程 不要生成已有的狀態（節點），防止進入死循環,2021/2/10,例2：迷宮問題,2021/2/10,給圖上加一個坐標系，定義每一個分叉路口為一個狀態,2021/2/10,操作符為人的上、下、左、右走動,初始狀態為（1，1,目標狀態為（4，4,2021/2/10,部分狀態空間圖,2021/2/10,例3：梵塔問題（三個盤） 對于 n 個盤的問題，我們用 n 維向量 （a1 a2an） 表示問題的一個狀態 其中ai = 1, 2, 3 表示第i個盤位于第一、二、三個柱子上，a1 an中盤的大小從大到小,2021/2/10,初始狀態為（11），目標狀態為（33） 操作符m(i, j)：表示

12、一個盤從 i 根柱子搬到第 j 根柱子。 T(k)：表示第 k 根柱子上（最上面）的盤的大小。 操作符集合為： O=m( i , j ) | T( i )T( j,2021/2/10,部分狀態空間圖,2021/2/10,例4：猴子與香蕉問題,a c b,2021/2/10,用一個四元組（W，x, Y, z）來表示問題的狀態 W：猴子的水平位置 x： 當猴子爬到箱子頂上取1，否則取0 Y： 箱子的水平位置 z： 當猴子摘到香蕉時取1，否則取0 初始狀態是（a, 0, b, 0），目標狀態是（c, 1, c, 1,2021/2/10,操作符： 猴子當前位置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/10,操作符： 猴子爬到箱子上：climbbox： （W, 0, W, z） (W，1, W, z) 猴子