人工智能與知識工程-知識表示1

2.1知識與知識表示的概念2.2狀態(tài)空間法2.3問題規(guī)約法2.4謂詞邏輯法2.5語義網(wǎng)絡(luò)法2.6框架表示法2.7劇本表示法2.8過程表示法2.9小結(jié)2知識表示方法12.1知識與知識表示的概念知識表示是人工智能研究中最基本的問題之一。在知識處理中總要問到：如何表示知識，怎樣使機器能懂這些知識，能對之進行處理，并能以一種人類能理解的方式將處理結(jié)果告訴人們。在人工智能系統(tǒng)中，給出一個清晰簡潔的有關(guān)知識的描述是很困難的。有研究報道認(rèn)為。嚴(yán)格地說人工智能對知識表示的認(rèn)真、系統(tǒng)的研究才剛剛開始。

22.1知識與知識表示的概念(續(xù))2.1.1知識是人們在改造客觀世界的實踐中積累起來的認(rèn)識和經(jīng)驗Feigenbaum認(rèn)為知識是經(jīng)過削減、塑造、解釋和轉(zhuǎn)換的信息。簡單地說，知識是經(jīng)過加工的信息。Bernstein說知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。Hayes-Roth認(rèn)為知識是事實、信念和啟發(fā)式規(guī)則。從知識庫觀點看，知識是某論域中所涉及的各有關(guān)方面、狀態(tài)的一種符號表示。

32.1知識與知識表示的概念（續(xù)）知識的特征相對正確性：知識在一定的條件下是正確的，但在另外一種情況下可能是不正確的。不確定性：事物之間的關(guān)系有時難以用真假狀態(tài)來描述，不確定性就是指這種介于真假之間的中間狀態(tài)?？杀硎拘裕褐R通常通過一定的方法進行表示，如：語言、文字、圖畫、姿勢、聲音等。可利用性：人們常用知識來認(rèn)識和改造世界

42.1知識與知識表示的概念（續(xù)）知識的分類事實知識：是有關(guān)問題環(huán)境的一些事物的知識，常以“…是…”的形式出現(xiàn)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實、客觀事實等，事實是靜態(tài)的為人們共享的可公開獲得的公認(rèn)的知識，在知識庫中屬低層的知識。如雪是白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的。規(guī)則知識：是有關(guān)問題中與事物的行動、動作相聯(lián)系的因果關(guān)系知識，是動態(tài)的，常以“如果…那么…”形式出現(xiàn)。特別是啟發(fā)式規(guī)則是屬專家提供的專門經(jīng)驗知識，這種知識雖無嚴(yán)格解釋但很有用處。控制知識：是有關(guān)問題的求解步驟、技巧性知識，告訴怎么做一件事。也包括當(dāng)有多個動作同時被激活時應(yīng)選哪一個動作來執(zhí)行的知識。元知識：是有關(guān)知識的知識，是知識庫中的高層知識。包括怎樣使用規(guī)則、解釋規(guī)則、校驗規(guī)則、解釋程序結(jié)構(gòu)等知識。元知識與控制知識是有重迭的，對一個大的程序來說，以元知識或說元規(guī)則形式體現(xiàn)控制知識更為方便，因為元知識存于知識庫中，而控制知識常與程序結(jié)合在一起出現(xiàn)，從而不容易修改。52.1知識與知識表示的概念（續(xù)）2.1.2知識表示知識表示是研究用機器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組描述事物的約定，以把人類知識表示成機器能處理的數(shù)據(jù)結(jié)構(gòu)。從實用觀點看，人工智能是一門知識工程學(xué)：以知識為對象，研究知識的表示方法、知識的運用和知識獲取。

62.1知識與知識表示的概念（續(xù)）2.1.3知識表示分類稱述性知識表示：語義網(wǎng)絡(luò)、框架和劇本等知識表示方法，均是對知識和事實的一種靜止的表達方法，稱這類知識表達方式為陳述式知識表達，它所強調(diào)的是事物所涉及的對象是什么，是對事物有關(guān)知識的靜態(tài)描述，是知識的一種顯式表達形式。而對于如何使用這些知識，則通過控制策略來決定過程式知識表示：就是將有關(guān)某一問題領(lǐng)域的知識，連同如何使用這些知識的方法，均隱式地表達為一個求解問題的過程。它所給出的是事物的一些客觀規(guī)律，表達的是如何求解問題。知識的描述形式就是程序，所有信息均隱含在程序，因而難于添加新知識和擴充功能，適用范圍較窄。

72.2狀態(tài)空間法在分析了人工智能研究中運用的問題求解方法之后，就會發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個可能的解空間內(nèi)尋找一個解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。狀態(tài)空間法的三要點狀態(tài)（state）：表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)；算符（operator）：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段；狀態(tài)空間方法：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。

82.2.1問題狀態(tài)描述定義狀態(tài)(state)：為描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0，q1，...，qn]T

式中每個元素qi(i=0,1，…，n)為集合的分量，稱為狀態(tài)變量。算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運算符號或邏輯符號等。操作的條件(對狀態(tài)的要求)和對狀態(tài)的改變。問題的狀態(tài)空間(statespace)：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標(biāo)狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。

92.2.1問題狀態(tài)描述（續(xù)）舉例 例1:二階梵塔問題.設(shè)有三根柱子,它們的編號分別是1號,2號,3號.在初始情況下,1號柱子上穿有A,B兩個園盤,A比B小,A位于B的上面.要求把這兩個園盤全部移到第3號柱子上,而且規(guī)定每次只能移動一個園盤,任何時刻都不能使大園盤位于小園盤的上面.

102.2.1問題狀態(tài)描述（續(xù)）狀態(tài)

用Sk={Sk0,Sk1}表示問題狀態(tài),其中Sk0表示園盤A所在的柱子號,Sk1表示園盤B所在的柱子號。112.2.1問題狀態(tài)描述（續(xù)）算符算符定義： 操作A(i,j)表示把園盤A從i號柱子移到j(luò)號柱子，操作B(i,j)表示把園盤B從i號柱子移到j(luò)號柱子。 一種得到解的操作序列:A(1,3),B(1,2),A(3,2)操作的條件:B(1,2):Sk=(x,1)x≠1操作的結(jié)果:B(1,2):Sk=(x,1)Sk=(x,2)122.2.1問題狀態(tài)描述（續(xù)）例2

修道士和野人問題：設(shè)在河的左岸有三個野人,三個修道士和一條船,修道士想用這條船把所有的人運到河對岸,但受以下條件的約束: 1.修道士和野人都會劃船; 2.船每次至多可載兩個人; 3.在河的任一岸,如果野人數(shù)目超過修道士數(shù),修道士就會被野人吃掉。 假設(shè)野人會服從任何一次過河安排,請規(guī)劃一個確保修道士和野人都能過河,且沒有修道士被野人吃掉的安全過河計劃。132.2.1問題狀態(tài)描述（續(xù)）狀態(tài)

需要表示出在某岸上的修道士人數(shù)和野人數(shù)及船在哪岸上。Sk=(m,c,b) 其中,m表示左岸的修道士人數(shù),c表示左岸的野人數(shù),b表示左岸的船數(shù)。 初始狀態(tài):S0=(3,3,1) 中間狀態(tài):S4=(1,1,1) 目標(biāo)狀態(tài):S15=(0,0,0)142.2.1問題狀態(tài)描述（續(xù)）算符算符定義： 用符號Pij表示從左岸到右岸運i個修道士,j個野人；用符號Qij表示從右岸到左岸運i個修道士,j個野人?？紤]到船每次最多只能載兩人,則所有操作集合:F={P01

,P10

,P11

,P02

,P20

,Q01

,Q10

,Q11

,Q02

,Q20

} 操作的條件:當(dāng)前狀態(tài)滿足可執(zhí)行條件操作不能產(chǎn)生非法狀態(tài) 例:P01的操作條件:b=1,m=0或m=3,c≥1 當(dāng)前狀態(tài):S4=(1,1,1) 可執(zhí)行的操作:P01,P11152.2.1問題狀態(tài)描述（續(xù)）操作的結(jié)果:操作執(zhí)行后對狀態(tài)的改變 例:P01的結(jié)果:b=0,c=c-1 P10的結(jié)果:b=0,m=m-1 P11的結(jié)果:b=0,c=c-1,m=m-1 P02的結(jié)果:b=0,c=c-2, P20的結(jié)果:b=0,m=m-2 Q01的結(jié)果:b=1,c=c+1 Q10的結(jié)果:b=1,m=m+1 ……162.2.1問題狀態(tài)描述（續(xù)） 要完成某個問題的狀態(tài)描述必須確定三件事情： 1、該狀態(tài)描述方式，特別是初始狀態(tài)的描述方式 2、操作符（算符）集合及其對狀態(tài)描述的作用 3、目標(biāo)狀態(tài)描述的特征172.2.2解題過程的表示圖的基本概念節(jié)點(node)：圖形上的匯合點，用來表示狀態(tài)、事件和時間關(guān)系的匯合，也可用來指示通路的匯合；弧線(arc)：節(jié)點間的連接線；有向圖(directedgraph)：一對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。后繼節(jié)點(descendantnode)與父輩節(jié)點(parentnode)：如果某條弧線從節(jié)點ni指向節(jié)點nj，那么節(jié)點nj就叫做節(jié)點ni的后繼節(jié)點或后裔，而節(jié)點ni叫做節(jié)點nj的父輩節(jié)點或祖先。路徑：某個節(jié)點序列(ni1,ni2,…,nik)當(dāng)j=2，3，…，k時，如果對于每一個ni，j-1都有一個后繼節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點nik的長度為k的路徑。代價：用c(ni,nj)來表示從節(jié)點ni指向節(jié)點nj的那段弧線的代價。兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。顯式表示：各節(jié)點及其具有代價的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點、它的后繼節(jié)點以及連接弧線的代價。隱式表示：節(jié)點的無限集合{si}作為起始節(jié)點是已知的。后繼節(jié)點算符Γ也是已知的，它能作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價。182.2.2解題過程的表示（續(xù)）狀態(tài)空間圖 把初始狀態(tài)可達到的各狀態(tài)所組成的空間用有向圖表示.用”狀態(tài)”標(biāo)識節(jié)點,用”操作”標(biāo)識有向邊,有向邊的方向由操作的施加對象狀態(tài)指向操作的結(jié)果狀態(tài)。192.2.2解題過程的表示（續(xù)）例1的狀態(tài)空間圖202.2.2解題過程的表示（續(xù)）例2的狀態(tài)空間圖212.2.3狀態(tài)空間問題求解狀態(tài)空間法:從某個初始狀態(tài)開始,每次加一個操作符,遞增地建立起操作符的試驗序列,直到達到目標(biāo)狀態(tài)為止.基本過程:1.為問題選擇適當(dāng)?shù)摹睜顟B(tài)”及”操作符”的形式化描述方法,定義初始狀態(tài)集合,目標(biāo)狀態(tài)集合及操作符集合;2.將操作符作用在初始狀態(tài)(新狀態(tài))上生成新狀態(tài)逐步構(gòu)造狀態(tài)空間,判斷新狀態(tài)是否為目標(biāo)狀態(tài),如果是轉(zhuǎn)3.否則轉(zhuǎn)2.3.尋找從初始狀態(tài)到目標(biāo)狀態(tài)的一個(最佳)路徑。路徑邊上所使用的操作符序列就是該問題的一個解.222.2.3狀態(tài)空間問題求解（續(xù)）例1的求解過程232.2.3狀態(tài)空間問題求解（續(xù)）使用狀態(tài)空間法求解問題的系統(tǒng)：產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)是描述搜索過程的方法，其構(gòu)成是：1.一個總數(shù)據(jù)庫（globaldatabase），它含與具體任務(wù)有關(guān)的信息。2.一套規(guī)則，它對數(shù)據(jù)庫進行操作運算。每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性和先決條件，右部描述規(guī)則應(yīng)用時所完成的動作。應(yīng)用規(guī)則來改變數(shù)據(jù)庫，就象應(yīng)用算符來改變狀態(tài)一樣。3.一個控制策略，它確定應(yīng)該采用哪一條使用規(guī)則，而且當(dāng)數(shù)據(jù)庫的終止條件滿足時，就停止計算。242.3問題規(guī)約法2.3.1問題歸約描述2.3.2問題歸約的與或圖表示2.3.3問題歸約法的問題求解252.3.1問題規(guī)約描述1.問題歸約:從較復(fù)雜難于求解的目標(biāo)問題出發(fā),進行分解或變換,將它轉(zhuǎn)化為一系列較簡單易于求解的子問題及子問題的子問題,直至歸約為一個平凡的易求解的本原問題集合。2.問題歸約表示的組成部分一個初始問題描述;一套把問題變換為子問題的操作符;一套本原問題描述。3.問題的描述:采用各種數(shù)據(jù)結(jié)構(gòu):表列,樹,字符串,矢量,數(shù)組等。262.3.1問題規(guī)約描述(續(xù))例3：三階梵塔問題，設(shè)有三根柱子,它們的編號分別是1號,2號,3號.在初始情況下,1號柱子上穿有A,B,C三個園盤,A比B小,B比C小,A位于B的上面,B位于C的上面.要求把這三個園盤全部移到第3號柱子上,而且規(guī)定每次只能移動一個園盤,任何時刻都不能使大園盤位于小園盤的上面。如果采用狀態(tài)空間法求解，其狀態(tài)空間圖包括27個節(jié)點，每個節(jié)點代表柱子上園盤的一個正確配置。272.3.1問題規(guī)約描述(續(xù))問題描述:例3:采用三元組表示狀態(tài):S=(a,b,c) 其中,a,b,c是整數(shù)分別表示園盤A,B,C所在的柱子號。 初始狀態(tài)：(1,1,1) 目標(biāo)狀態(tài)：(3,3,3)282.3.1問題規(guī)約描述(續(xù))292.3.2問題規(guī)約的與或圖表示1.問題的分解與等價變換

(1)分解:如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且只有當(dāng)所有子問題Ｐi(i=1,2,…,n)都有解時原問題P才有解,任何一個子問題Ｐi(i=1,2,…,n)無解都會導(dǎo)致原問題P無解,則稱此種歸約為問題的分解。即分解所得到的子問題的”與”與原問題P等價。302.3.2問題規(guī)約的與或圖表示（續(xù)）在例3中:原問題可分解為三個子問題:①把園盤A及B移到2號柱子上的雙園盤移動問題。[(1,1,1)→(2,2,1)]②把園盤C移到3號柱子上的單園盤移動問題。[(2,2,1)→(2,2,3)]③把園盤A及B移動到3號園盤的雙園盤移動問題。[(2,2,3)→(3,3,3)] 其中子問題①和③還可以繼續(xù)進行分解。而子問題②不需要再分解,稱為本原問題。312.3.2問題規(guī)約的與或圖表示（續(xù)）

(2)等價變換:如果一個問題P可以歸約為一組子問題P1,P2,…,Pn,并且這些子問題Pi(i=1,2,…,n)中只要有一個有解則原問題P就有解,只有當(dāng)所有子問題Pi(i=1,2,…,n)都無解時,原問題P才無解,則稱此種歸約為問題的等價變換,簡稱變換,即變換所得到的子問題的”或”與原問題P等價。322.3.2問題規(guī)約的與或圖表示（續(xù)）在例2中:原問題(3,3,1)→(0,0,0)可變換為以下三個子問題:①一個野人先過河:(3,3,1)→(3,2,0)和(3,2,0)→(0,0,0)②一個修道士和一個野人先過河:(3,3,1)→(2,2,0)和(2,2,0)→(0,0,0)③兩個野人先過河:(3,3,1)→(3,1,0)和(3,1,0)→(0,0,0)其中:只要有一個子問題可解,則原問題可解。每個子問題又分別由兩個”子”子問題組成。只有這兩個”子”子問題都可解時,子問題才可解。有些”子”子問題還可以進行再變換或分解。直到變換或分解為直接可解的本原問題。332.3.2問題規(guī)約的與或圖表示（續(xù)）從上例可以看出：在實際問題的歸約過程中,有可能需要同時采用變換和分解的方法。無論是分解還是變換,都是要將原問題最終歸約為一系列本原問題。本原問題:指那些不能(或不需要)再進行分解或變換,且可以直接解答的子問題。本原問題可以作為對問題進行歸約的限制條件(結(jié)束條件)。問題的變換或分解是通過操作符(算符)來實現(xiàn)的。342.3.2問題規(guī)約的與或圖表示（續(xù)）2.問題歸約的與或圖表示

(1)與圖

把一個原問題分解為若干個子問題P1，P2，P3，…可用一個”與圖”來表示。P1，P2，P3，…對應(yīng)的子問題節(jié)點稱為”與節(jié)點” 例:設(shè)P可以分解為三個子問題P1，P2，P3的與,則P和P1，P2，P3之間的關(guān)系可用下圖所示的一個”與圖”表示:352.3.2問題規(guī)約的與或圖表示（續(xù)）

(2)或圖

把一個原問題變換為若干個子問題P1，P2，P3,…,可用一個”或圖”來表示。子問題P1，P2，P3,…對應(yīng)的節(jié)點稱為”或節(jié)點”。 例:設(shè)P可以變換為三個子問題P1，P2，P3

的或,則P和P1，P2，P3下圖所示的一個”或圖”表示:362.3.2問題規(guī)約的與或圖表示（續(xù)）

(3)與或圖

如果一個原問題即需要通過分解又需要通過變換才能得到其本原問題,則其歸約過程可用一個”與或圖”來表示。在特殊情況下,根本不出現(xiàn)任何與節(jié)點,則變?yōu)槠胀▓D。