知識(shí)表示方法狀態(tài)空間法

1、知識(shí)表示方法 狀態(tài)空間法用計(jì)算機(jī)技術(shù)解決實(shí)際問(wèn)題的一般思路:實(shí)際問(wèn)題問(wèn)題表達(dá)知識(shí)表達(dá)數(shù)學(xué)建模求解的方法或者算法結(jié)果的解釋例：求側(cè)面積為150平方米的體積最大的長(zhǎng)方體？設(shè)長(zhǎng)、寬、高分別為 x, y, z側(cè)面積為：2(xy + yz + xz)體積為：xyz數(shù)學(xué)模型 max xyz s.t. 2(xy + yz + xz)=150 xyz利用最優(yōu)化技術(shù)中的算法，可以得到結(jié)果：x = y = z 解釋：長(zhǎng)、寬、高都等于5米時(shí)，體積最大說(shuō)明：在計(jì)算數(shù)學(xué)的課程中，主要關(guān)心求解的具體算法在人工智能中，重點(diǎn)關(guān)注兩個(gè)方面的內(nèi)容：?jiǎn)栴}的表示（知識(shí)的表示）：即要找到問(wèn)題的一種合適的表示方法在人工智能中，我們要涉及

2、到：狀態(tài)空間法問(wèn)題歸約法謂詞邏輯法樣本向量法問(wèn)題的求解：從問(wèn)題表示方法出發(fā)，找到一個(gè)合理的辦法來(lái)求解在人工智能中，常有的方法有：搜索法推理法計(jì)算方法 狀態(tài)空間法 在日常的一些智力游戲（八數(shù)碼、走八卦陣、走迷宮等）中，我們采用的策略：試著向前走，如果走不通，則往后退，不停地試、試、試，直到成功1245783612345678類似地，在人工智能中，一種最基本的求解方法就是試探搜索法，即，通過(guò)在某個(gè)可能的解空間（例如，所有可能的走法）中尋找一個(gè)解這種基于解空間的問(wèn)題表示和求解方法就是狀態(tài)空間法，其基礎(chǔ)是狀態(tài)和算符（算子）1. 問(wèn)題狀態(tài)描述狀態(tài)：描述某一類不同事物間的差別而引入的一組最少變量q0 ,q

3、1 , qn的有序集合例：描述在坐的同學(xué)變量可以有:年級(jí)班級(jí)姓名性別學(xué)號(hào)根據(jù)要解決的問(wèn)題、從中選擇最少的一組變量例：區(qū)分哪一個(gè)班：年級(jí)、班級(jí)區(qū)分哪一位同學(xué)：姓名、性別、學(xué)號(hào)矢量形式： Q= q0, q1, , qn T 其中，元素 qi ( i=0, 1, n)為集合的分量，稱為狀態(tài)變量。具體狀態(tài)：給每一個(gè)狀態(tài)變量一個(gè)具體的值（符號(hào)、數(shù)值等）。矩陣形式例：八數(shù)碼問(wèn)題矢量形式的狀態(tài)表示：12347865矩陣形式的狀態(tài)表示：算符（操作符）：使問(wèn)題從一個(gè)狀態(tài)變換到另一狀態(tài)的手段。例如：走步、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)等等。例：描述在坐的同學(xué)（續(xù)）狀態(tài)變量可以有：年級(jí)班級(jí)姓名性別學(xué)號(hào)操作符：入學(xué)正常升級(jí)

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

5、其對(duì)狀態(tài)描述的作用如何描述目標(biāo)狀態(tài)即定義好三元狀態(tài)（S, F, G）中的三個(gè)成分 狀態(tài)空間法：從某一個(gè)初始狀態(tài)開(kāi)始，每次施加一個(gè)操作符，遞增地建立操作符序列，直到達(dá)到目標(biāo)狀態(tài)為止?fàn)顟B(tài)空間法的問(wèn)題：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某一個(gè)操作符序列狀態(tài)空間法的解：從初始狀態(tài)變換到目標(biāo)狀態(tài)的操作符序列1194151312758613210141234567891011121314152. 狀態(tài)圖示法 圖是由節(jié)點(diǎn)（不一定是有限個(gè)的節(jié)點(diǎn)）的集合構(gòu)成的注意：在圖論中，圖的定義中還包括邊的集合狀態(tài)空間法（求解過(guò)程）的表示方法：用圖來(lái)表示（借助于圖論中某些技術(shù)）有向圖和無(wú)向圖：無(wú)向圖：一對(duì)節(jié)點(diǎn)可能互為后裔，邊用線段

6、來(lái)表示有向圖：一對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，并且從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn) 父輩節(jié)點(diǎn)或祖先n i后繼節(jié)點(diǎn)或后裔nj 對(duì)于某一個(gè)節(jié)點(diǎn)序列（ni0 , ni2 , nij , , nik） 如果每一個(gè)節(jié)點(diǎn) nij-1 都有一個(gè)后繼節(jié)點(diǎn) nij 存在，則將這一序列稱為從節(jié)點(diǎn) ni0 到 nik 的長(zhǎng)度為 k 的路徑。 nikni0如果從節(jié)點(diǎn) ni 到 nj 存在一條路徑，則稱節(jié)點(diǎn) nj 是從節(jié)點(diǎn) ni 可到達(dá)的節(jié)點(diǎn)，或者稱 nj 是 ni 的后裔節(jié)點(diǎn)、稱 ni 是 nj 的祖先。 njni祖先后裔當(dāng)用有向圖來(lái)表示狀態(tài)空間法時(shí)，對(duì)應(yīng)關(guān)系：圖中的一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于某一個(gè)狀態(tài)圖中的一個(gè)有向弧對(duì)應(yīng)于某一個(gè)算符 注：有向

7、弧的旁邊可以標(biāo)以具體算符狀態(tài)節(jié)點(diǎn)操作符有向弧問(wèn)題：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某個(gè)操作符序列問(wèn)題：尋找圖中初始節(jié)點(diǎn)（對(duì)應(yīng)初始狀態(tài)）到目標(biāo)節(jié)點(diǎn)（對(duì)應(yīng)于目標(biāo)狀態(tài)）的一條路徑轉(zhuǎn)化為c (ni , nj) 表示從節(jié)點(diǎn) ni 指向節(jié)點(diǎn) nj （相鄰）的那一段弧的代價(jià) n jn i在某些情況下，每個(gè)操作符作用、成本是不一樣的，需要引入代價(jià)的概念（不相鄰的）兩個(gè)節(jié)點(diǎn)間路徑的代價(jià)等于連接該路徑的各個(gè)節(jié)點(diǎn)的所有弧線的代價(jià)之和 nkn0c(n0,n1)c(nk-1,nk)引入代價(jià)的概念后，我們的問(wèn)題可能是：尋找初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的代價(jià)最小的路徑對(duì)應(yīng)的原始問(wèn)題：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的操作符代價(jià)之和最小的操作符

8、序列利用圖論的技術(shù)，我們要解決兩個(gè)問(wèn)題：第一、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑。對(duì)應(yīng)于尋找初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列第二、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條代價(jià)最小的路徑。對(duì)應(yīng)于尋找將初始狀態(tài)變換到目標(biāo)狀態(tài)所用操作符代價(jià)之和最小的操作符序列3. 例子 例1：八數(shù)碼問(wèn)題 八數(shù)碼的任何一種擺法是一個(gè)狀態(tài)，狀態(tài)總數(shù)為9！。用一個(gè)長(zhǎng)度為9的一維數(shù)組來(lái)描述狀態(tài)：（q1, q2, ,q9）其中，qi 取0, 1, , 8個(gè)數(shù)，0表示空格，且取值互不相同。 算符是空格的上、下、左、右移動(dòng) 如果記空格的位置為P，這時(shí)空格的移動(dòng)規(guī)則是：12385674123856740PP-3P+1P+3P-1表示位置1 2 3

9、 4 5 6 7 8 9P 代碼規(guī)則前提條件應(yīng)用結(jié)果1左移P1,4,7P 位置與 P-1 位置上的元素互換2上移P1,2,3 P-33右移P3,6,9 P+14下移P7,8,9 P+3空格移動(dòng)規(guī)則123456789表示位置初始狀態(tài)：(2，0，3，1，8，4，5，6，7）目標(biāo)狀態(tài):（1，2，3，8，0，4，5，6，7） 部分狀態(tài)空間圖注意：事先規(guī)定操作符的前后順序，便于編程不要生成已有的狀態(tài)（節(jié)點(diǎn)），防止進(jìn)入死循環(huán)例2：迷宮問(wèn)題 給圖上加一個(gè)坐標(biāo)系，定義每一個(gè)分叉路口為一個(gè)狀態(tài)。操作符為人的上、下、左、右走動(dòng)初始狀態(tài)為（1，1）目標(biāo)狀態(tài)為（4，4）部分狀態(tài)空間圖例3：梵塔問(wèn)題（三個(gè)盤(pán)） 對(duì)于 n 個(gè)盤(pán)的問(wèn)題，我們用 n 維向量 （a1 a2an）表示問(wèn)題的一個(gè)狀態(tài)其中ai = 1, 2, 3 表示第i個(gè)盤(pán)位于第一、二、三個(gè)柱子上，a1 an中盤(pán)的大小從大到小初始狀態(tài)為（11），目標(biāo)狀態(tài)為（33）操作符m(i, j)：表示一個(gè)盤(pán)從 i 根柱子搬到第 j 根柱子。T(k)：表示第 k 根柱子上（最上面）的盤(pán)的大小。操作符集合為： O=m( i , j ) | T( i ) 人數(shù)：野人2 - 傳教士0此岸野人數(shù)3, 傳教士數(shù)3渡河方向：人數(shù)：野人2 - 傳教士0此岸野人數(shù)2, 傳教士數(shù)3渡河方向：人數(shù)：野人0 - 傳教士2此岸野人數(shù)1, 傳教士數(shù)3渡河