1、1第二章第二章 知識表示方法知識表示方法狀態空間法問題歸約法謂詞邏輯法語義網絡法框架表示法劇本表示法過程表示法22.1 狀態空間法狀態空間法問題狀態描述狀態圖示法狀態空間表示舉例32.1.1 問題狀態描述問題狀態描述1、狀態（、狀態（State）的基本概念）的基本概念狀態狀態(state)是為描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合，其矢量形式如下：Q=q0,q1,qnT (2.1)式中每個元素qi(i=0,1，n)為集合的分量，稱為狀態變量。 給定每個分量的一組值就得到一個具體的狀態，如Qk=qk,q1k,，qnkT (2.2)4算符算符：使問題從一種狀態變化為

2、另一種狀態的手段稱為操作符或算符。操作符可為走步、過程、規則、數學算子、運算符號或邏輯符號等。5問題的狀態空間(state space)是一個表示該問題全部可能狀態及其關系的圖，它包含三種說明的集合，即所有可能的問題初始狀態集合S、操作符集合F以及目標狀態集合G。因此，可把狀態空間記為三元狀態(S，F，G)。6 2、狀態空間的表示法、狀態空間的表示法對一個問題的狀態描述，必須確定3件事：(1) 該狀態描述方式，特別是初始狀態描述；(2) 操作符集合及其對狀態描述的作用；(3) 目標狀態描述的特性。7 14376582八數碼問題的狀態空間S狀態集。八數碼的所有的擺法(9!)G指定的某個或某些八數

3、碼擺放狀態。操作算子數碼的移動。4(方向) 8(數碼)32個l將空格向上移Upl將空格向左移Leftl將空格向下移Downl將空格向右移 Right82.1 狀態空間法狀態空間法問題狀態描述狀態圖示法狀態空間表示舉例92.1.2 狀態圖示法狀態圖示法圖的基本概念圖由節點(不一定是有限的節點)的集合構成。一對節點用弧線連接起來，從一個節點指向另一個節點。這種圖叫做有向圖(directed graph)。某個節點序列(ni1,ni2,nik)當j=2，3，k時，如果對于每一個ni，j-1都有一個后繼節點nij存在，那么就把這個節點序列叫做從節點ni1至節點nik的長度為k的路徑。代價(cost)

4、是給各弧線指定數值以表示加在相應算符上的代價。10圖的顯式說明 是指各節點及其具有代價的弧線由一張表明確給出。圖的隱式說明 是指各節點及其具有代價的弧線不能由一張表明確給出。111 4 37 65 8 21 37 4 65 8 21 4 3 7 65 8 21 4 37 8 65 21 4 37 65 8 2 1 37 4 65 8 21 37 4 65 8 21 4 37 65 8 2 4 35 7 6 8 21 4 37 8 6 5 21 4 37 8 65 21 47 6 35 8 21 4 37 6 25 8UpLeftDownRightUpDownDownUpRightLeftLef

5、tRight122.1 狀態空間法狀態空間法問題狀態描述狀態圖示法狀態空間表示舉例132.1.3 狀態空間表示舉例狀態空間表示舉例1、產生式系統、產生式系統一個產生式系統由下列3部分組成：一個總數據庫(global database)，它含有與具體任務有關的信息。一套規則，它對數據庫進行操作運算。每條規則由左右兩部分組成，左部鑒別規則的適用性或先決條件，右部描述規則應用時所完成的動作。應用規則來改變數據庫。一個控制策略，它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。142、狀態空間表示舉例、狀態空間表示舉例 猴子與香蕉的問題acb15 狀態空間表示 設系統的狀態用四元

6、數組描述：S=(w, x, y, z) 其中w:猴子所處水平位置 x:箱子所在水平位置 y:猴子是否在箱子上(y=1,在; y=0，不在) z:猴子是否能拿到香蕉(z=1,拿到; z=0,沒有拿到)16可能出現的狀態如下：S0=(a,b,0,0)S1=(b,b,0,0)S2=(c,c,0,0)S3=(c,c,1,0)S4=(c,c,1,1)其中S0為初始狀態， S4為目標狀態。17 算符 F=(f1, f2, f3 , f4 )其中 f1 (u) 為猴子走到u處。(w, x, 0, z) (u, x, 0, z) f2 (u) 為猴子走到v處。(x, x, 0, 0 ) (v, v, 0, 0

7、) f3 為猴子爬上臺子。 (x, x, 0, z ) (x, x,1, z) f4 為猴子拿到香蕉。 (c, c, 1, 0) (c, c,1, 1 )18求解過程 S0S4P1：主操作f1P2：主操作f2P3：主操作f3P4：主操作f4S2S3S0S2S3S4S0S1S1S2P31(f1, f2)P32( f3)P33( f4)P312( f2)P311( f1)19旅行商問題（travelling salesman problem,TSP問題） 銷售員到幾個城市去推銷商品，城市之間的距離是已知的，他現在從某一個城市出發，經過每個城市一次，最后又回到出發的城市。要求歸劃好一條最短路線。77

8、10101013656ABEDC20第二章第二章 知識表示方法知識表示方法狀態空間法問題歸約法謂詞邏輯法語義網絡法框架表示法劇本表示法過程表示法212.2 問題歸約法問題歸約法問題歸約描述與或圖表示222.2.1 問題歸約描述問題歸約描述1、問題歸約法的概念已知問題的描述，通過一系列變換把此問題最終變為一個子問題集合；這些子問題的解可以直接得到，從而解決了初始問題。該方法也就是從目標(要解決的問題)出發逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。這就是問題歸約的實質。232、問題歸約法的組成部分 （1）一個初始問題描述；（2）一套把問題變換為子問題的

9、操作符；（3）一套本原問題描述。243、示例：梵塔難題問題 有3個柱子(1，2，3)和3個不同尺寸的圓盤(A，B，C)。在每個圓盤的中心有個孔，所以圓盤可以堆疊在柱子上。最初，全部3個圓盤都堆在柱子1上：最大的圓盤C在底部，最小的圓盤A在頂部。要求把所有圓盤都移到柱子3上，每次只許移動一個，而且只能先搬動柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。25132C123ABABC26歸約過程：（1）移動圓盤A和B至柱子2的雙圓盤難題；（2）移動圓盤C至柱子3的單圓盤難題；（3）移動圓盤A和B至柱子3的雙圓盤難題。27132C123ABABC28123ABC123ABC29123A

10、BC123ABC304、歸約描述問題歸約方法是應用算符來把問題描述變換為子問題描述?？梢杂脿顟B空間表示的三元組合(S、F、G)來規定與描述問題；對于梵塔問題，子問題（111）(122)，(122)(322)以及(322)(333)規定了最后解答路徑將要通過的腳踏石狀態(122)和(322)。問題歸約方法可以應用狀態、算符和目標這些表示法來描述問題，這并不意味著問題歸約法和狀態空間法是一樣的。31(1,1,1)(3,3,3)(1,1,1)(1,2,2) (1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,2,3)(1,2,2)(1,1,3)(1,2,3)(

11、3,2,2)(3,3,3)(3,2,2)(3,2,1)(3,3,1)(3,3,3)322.2 問題歸約法問題歸約法問題歸約描述與或圖表示332.2.2 2.2.2 與或圖表示與或圖表示1、與或圖的概念用一個類似圖的結構來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。例如，設想問題A需要由求解問題B、C和D來決定，那么可以用一個與圖來表示；同樣，一個問題A或者由求解問題B、或者由求解問題C來決定，則可以用一個或圖來表示。34352、與或圖的有關術語父節點父節點 是一個初始問題或是可分解為子問題的問題節點；子節點子節點 是一個初始問題或是子問題分解的子問題節點；或節點或節點 只要解決某個問題

12、就可解決其父輩問題的節點集合；與節點與節點 只有解決所有子問題，才能解決其父輩問題的節點集合；弧線弧線 是父輩節點指向子節點的圓弧連線；終葉節點終葉節點 是對應于原問題的本原節點。363、與或圖的有關定義可解節點可解節點 與或圖中一個可解節點的一般定義可以歸納如下：(1) 終葉節點是可解節點(因為它們與本原問題相關連)。(2) 如果某個非終葉節點含有或后繼節點，那么只有當其后繼節點至少有一個是可解的時，此非終葉節點才是可解的。(3) 如果某個非終葉節點含有與后繼節點，那么只要當其后繼節點全部為可解時，此非終葉節點才是可解的。37不可解節點不可解節點 不可解節點的一般定義歸納于下：(1) 沒有后

13、裔的非終葉節點為不可解節點。(2) 如果某個非終葉節點含有或后繼節點，那么只有當其全部后裔為不可解時，此非終葉節點才是不可解的。(3) 如果某個非終葉節點含有與后繼節點，那么只要當其后裔至少有一個為不可解時，此非終葉節點才是不可解的。384、與或圖構圖規則 代表一個要解決的單一問題或問題集合。圖中所含起始節點對應于原始問題。(2) 對應于本原問題的節點，叫做終葉節點，它沒有后裔。(3)對于把算符應用于問題A的每種可能情況，都把問題變換為一個子問題集合；有向弧線自A指向后繼節點，表示所求得的子問題集合。(4) 一般對于代表兩個或兩個以上子問題集合的每個節點，有向弧線從此節點指向此子問題集合中的各

14、個節點。(5) 在特殊情況下，當只有一個算符可應用于問題A，而且這個算符產生具有一個以上子問題的某個集合時，由上述規則3和規則4所產生的圖可以得到簡化。39第二章第二章 知識表示方法知識表示方法狀態空間法問題歸約法謂詞邏輯法語義網絡法框架表示法劇本表示法過程表示法402.3 謂詞邏輯法謂詞邏輯法 謂詞演算謂詞公式置換與合一412.3.1 謂詞演算謂詞演算1、語法和語義謂詞邏輯的基本組成部分是謂詞符號、變量符號、函數符號和常量符號，并用圓括弧、方括弧、花括弧和逗號隔開，以表示論域內的關系。原子公式是由若干謂詞符號和項組成，只有當其對應的語句在定義域內為真時，才具有值T(真)；而當其對應的語句在定

15、義域內為假時，該原子公式才具有值F(假)。422、連詞和量詞連詞有(與)、(或)，全稱量詞(x)，存在量詞(x)。原子公式是謂詞演算的基本積木塊，運用連詞能夠組合多個原子公式以構成比較復雜的合適公式。433、幾個有關定義 用連詞把幾個公式連接起來而構成的公式叫做合取，而此合取式的每個組成部分叫做合取項。一些合適公式所構成的任一合取也是一個合適公式。 用連詞把幾個公式連接起來所構成的公式叫做析取，而此析取式的每一組成部分叫做析取項。由一些合適公式所構成的任一析取也是一個合適公式。 用連詞連接兩個公式所構成的公式叫做蘊涵。蘊涵的左式叫做前項，右式叫做后項。如果前項和后項都是合適公式，那么蘊涵也是合

16、適公式。44 前面具有符號的公式叫做否定。一個合適公式的否定也是合適公式。 量化一個合適公式中的某個變量所得到的表達式也是合適公式。如果一個合適公式中某個變量是經過量化的，就把這個變量叫做約束變量，否則就叫它為自由變量。在合適公式中，感興趣的主要是所有變量都是受約束的。這樣的合適公式叫做句子。452.3 謂詞邏輯法謂詞邏輯法 謂詞演算謂詞公式置換與合一462.3.2 2.3.2 謂詞公式謂詞公式1、謂詞合適公式的定義在謂詞演算中合適公式的遞歸定義如下：(1) 原子謂詞公式是合適公式。(2) 若A為合適公式，則A也是一個合適公式。(3) 若A和B都是合適公式，則(AB)，(AB)，(A=B)和(

17、AB)也都是合適公式。(4) 若A是合適公式，x為A中的自由變元，則(x)A和(x)A都是合適公式。(5) 只有按上述規則(1)至(4)求得的那些公式，才是合適公式。472、合式公式的性質(1) 否定之否定(P)等價于P(2) PQ等價于PQ(3) 狄摩根定律(PQ)等價于PQ(PQ)等價于PQ(4) 分配律P(QR)等價于(PQ)(PR)P(QR)等價于(PQ)(PR)48(5) 交換律PQ等價于QPPQ等價于QP(6) 結合律(PQ)R等價于P(QR)(PQ)R等價于P(QR)(7) 逆否律PQ等價于QP49此外，還可建立下列等價關系：(8) ( x)P(x)等價于( x)P(x)( x)

18、P(x)等價于( x)P(x)(9) ( x)P(x)Q(x)等價于( x)P(x)( x)Q(x)( x)P(x)Q(x)等價于( x)P(x)( x)Q(x) (10) ( x)P(x)等價于( y)P(y)( x)P(x)等價于( y)P(y)502.3 謂詞邏輯法謂詞邏輯法 謂詞演算謂詞公式置換與合一512.3.3 置換與合一置換與合一1、置換假元推理，就是由合適公式W1和W1W2產生合適公式W2的運算。全稱化推理，是由合適公式(x)W(x)產生合適公式W(A)，其中A為任意常量符號。一個表達式的置換就是在該表達式中用置換項置換變量。一般說來，置換是可結合的，但置換是不可交換的。522

19、、合一尋找項對變量的置換，以使兩表達式一致，叫做合一(unification)。如果一個置換s作用于表達式集Ei的每個元素，則用Eis來表示置換例的集。稱表達式集Ei是可合一的。如果存在一個置換s使得：E1s=E2s=E3s=那么稱此s為Ei的合一者，因為s的作用是使集合Ei成為單一形式。53舉例：表達式Px,f(y),B的一個置換為s1=z/x,w/y， 則：Px,f(y),Bs1=Pz,f(w),B542.4 語義網絡法語義網絡法 二元語義網絡的表示多元語義網絡的表示連詞和量化的表示語義網絡的推理過程552.4.1 二元語義網絡的表示二元語義網絡的表示、語義網絡的基本概念 語義網絡是知識的

20、一種結構化圖解表示，它由節點和弧線或鏈線組成。節點用于表示實體、概念和情況等，弧線用于表示節點間的關系。56語義網絡表示由下列4個相關部分組成： (1) 詞法部分 決定表示詞匯表中允許有哪些符號，它涉及各個節點和弧線。(2) 結構部分 敘述符號排列的約束條件，指定各弧線連接的節點對。(3) 過程部分 說明訪問過程，這些過程能用來建立和修正描述，以及回答相關問題。(4) 語義部分 確定與描述相關的(聯想)意義的方法即確定有關節點的排列及其占有物和對應弧線。57語義網絡具有下列特點：(1) 能把實體的結構、屬性與實體間的因果關系顯式地和簡明地表達出來，與實體相關的事實、特征和關系可以通過相應的節點

21、弧線推導出來。(2) 由于與概念相關的屬性和聯系被組織在一個相應的節點中，因而使概念易于受訪和學習。(3) 表現問題更加直觀，更易于理解，適于知識工程師與領域專家溝通。(4) 語義網絡結構的語義解釋依賴于該結構的推理過程而沒有結構的約定，因而得到的推理不能保證像謂詞邏輯法那樣有效。(5) 節點間的聯系可能是線狀、樹狀或網狀的，甚至是遞歸狀的結構，使相應的知識存儲和檢索可能需要比較復雜的過程。582、二元語義網絡的表示 用兩個節點和一條弧線可以表示一個簡單的事實，對于表示占有關系的語義網絡，是通過允許節點既可以表示一個物體或一組物體，也可以表示情況和動作。每一情況節點可以有一組向外的弧(事例弧)

22、，稱為事例框，用以說明與該事例有關的各種變量。60 舉例：用二元語義網絡表示：小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。62分清概念節點與實例節點 在選擇節點時，首先要弄清節點是用于表示基本的物體或概念的，或是用于多種目的的。否則，如果語義網絡只被用來表示一個特定的物體或概念，那么當有更多的實例時就需要更多的語義網絡。64 選擇語義基元 試圖用一組基元來表示知識。這些基元描述基本知識，并以圖解表示的形式相互聯系。用這種方式，可以用簡單的知識來表示更復雜的知識。662.4 語義網絡法語義網絡法 二元語義網絡的表示多元語義網絡的表示連詞和量化的表示語義網絡的推理過程672.4

23、.2 2.4.2 多元語義網絡的表示多元語義網絡的表示 語義網絡是一種網絡結構。節點之間以鏈相連。從本質上講，接點之間的連接是二元關系。語義網絡從本質上來說，只能表示二元關系，如果所要表示的事實是多元關系，則把這個多元關系轉化成一組二元關系的組合，或二元關系的合取。具體來說，多元關系R(X1，X2，Xn)總可以轉換成R1 (X11，X12)R2 (X21，X22)Rn (Xn1,Xn2)。要在語義網絡中進行這種轉換需要引入附加節點。68692.4 語義網絡法語義網絡法 二元語義網絡的表示多元語義網絡的表示連詞和量化的表示語義網絡的推理過程702.4.3 連詞和量化的表示連詞和量化的表示可以用語

24、義網絡表示謂詞邏輯法中的各種連詞及量化。1.合取 多元關系可以被轉換成一組二元關系的合取，從而可以用語義網絡的形式表示出來。2.析取 在語義網絡中，為與合取關系相區別，在析取關系的連接上加注析取界限，并標記DIS。713.否定 采用ISA和PART OF關系或標注NEG界限來表示否定。4.蘊涵 在語義網絡中可用標注ANTE和CONSE界限來表示蘊涵關系。5.量化 存在量化在語義網絡中可直接用ISA鏈來表示。而全稱量化就要用分割方法來表示。722.4 語義網絡法語義網絡法 二元語義網絡的表示多元語義網絡的表示連詞和量化的表示語義網絡的推理過程732.4.4 2.4.4 語義網絡的推理過程語義網絡

25、的推理過程741.繼承75 值繼承 如果需要繼承 缺省繼承762.匹配772.5 其他方法其他方法 框架表示法劇本表示法過程表示法782.5.1 框架框架1、框架的構成框架通常由描述事物的各個方面的槽組成，每個槽可以擁有若干個側面，而每個側面又可以擁有若干個值。一個框架的一般結構如下： 框架名槽1側面11值111側面12值121槽2側面21值211 槽n側面n1值n11側面nm值nm179 較簡單的情景是用框架來表示諸如人和房子等事物。例如，一個人可以用其職業、身高和體重等項描述，因而可以用這些項目組成框架的槽。當描述一個具體的人時，再用這些項目的具體值填入到相應的槽中。80JOHNISA:P

26、ERSONProfession:PROGRAMMERHeight:1.8mWeight:79kg簡單框架示例81框架是一種通用的知識表達形式，對于如何運用框架系統還沒有一種統一的形式，常常由各種問題的不同需要來決定。822、框架的推理如前所述，框架是一種復雜結構的語義網絡。因此語義網絡推理中的匹配和特性繼承在框架系統中也可以實行。除此以外，由于框架用于描述具有固定格式的事物、動作和事件，因此可以在新的情況下，推論出未被觀察到的事實。83框架用以下幾種途徑來幫助實現這一點：(1) 框架包含它所描述的情況或物體的多方面的信息。(2) 框架包含物體必須具有的屬性。在填充框架的各個槽時，要用到這些屬性

27、。(3) 框架描述它們所代表的概念的典型事例。 84 用一個框架來具體體現一個特定情況的過程，經常不是很順利的。但當這個過程碰到障礙時，經常不必放棄原來的努力去從頭開始，而是有很多辦法可想的：(1) 選擇和當前情況相對應的當前的框架片斷，并把這個框架片斷和候補框架相匹配。選擇最佳匹配。(2) 盡管當前的框架和要描述的情況之間有不相匹配的地方，但是仍然可以繼續應用這個框架。(3) 查詢框架之間專門保存的鏈，以提出應朝哪個方向進行試探的建議。(4) 沿著框架系統排列的層次結構向上移動(即從狗框架哺乳動物框架動物框架)，直到找到一個足夠通用，并不與已有事實矛盾的框架。852.5 其他方法其他方法 框

28、架表示法劇本表示法過程表示法862.5.2 2.5.2 劇本劇本劇本是框架的一種特殊形式，它用一組槽來描述某些事件的發生序列，就像劇本中的事件序列一樣，故稱為“劇本”或腳本。87一個劇本一般由以下各部分組成：(1) 開場條件 給出在劇本中描述的事件發生的前提條件。(2) 角色 用來表示在劇本所描述的事件中可能出現的有關人物的一些槽。(3) 道具 這是用來表示在劇本所描述的事件中可能出現的有關物體的一些槽。(4) 場景 描述事件發生的真實順序，可以由多個場景組成，每個場景又可以是其它的劇本。(5) 結果 給出在劇本所描述的事件發生以后通常所產生的結果。88例子：以餐廳劇本為例說明劇本各個部分的組

29、成。91根據劇本的重要性，可以有二種準備劇本的方法。(1) 對于不屬于事件核心部分的劇本，只需設置指向該劇本的指針即可，以便當它成為核心時啟用。(2) 對于符合事件核心部分的劇本，則應使用在當前事件中涉及到的具體對象和人物去填寫劇本的槽。劇本的前提、道具、角色和事件等常能起到啟用劇本的指示器的作用。92 一旦劇本被啟用，則可以應用它來進行推理。其中最重要的是運用劇本可以預測沒有明顯提及的事件的發生。劇本結構，比起框架這樣的一些通用結構來，要呆板得多，知識表達的范圍也很窄，因此不適用于表達各種知識，但對于表達預先構思好的特定知識，如理解故事情節等，是非常有效的。932.5 其他方法其他方法 框架

30、表示法劇本表示法過程表示法942.5.3 2.5.3 過程過程語義網絡、框架和劇本等知識表示方法，均是對知識和事實的一種靜止的表達方法，是知識的一種顯式表達形式。而對于如何使用這些知識，則通過控制策略來決定。95 和知識的陳述式表示相對應的是知識的過程式表示。所謂過程式表示就是將有關某一問題領域的知識，連同如何使用這些知識的方法，均隱式地表達為一個求解問題的過程。它所給出的是事物的一些客觀規律，表達的是如何求解問題。知識的描述形式就是程序，所有信息均隱含在程序之中。從程序求解問題的效率上來說，過程式表達要比陳述式表達高得多。但因其知識均隱含在程序中，因而難于添加新知識和擴充功能，適用范圍較窄。962.6 2.6 小小 結結 知識表示方法很多，本章介紹了其中的7種，有圖示法和公式法，結構化方法，陳述式表示和過程式表示等。97狀態空間法是一種基于解答空間的問題表示和求解方法，它是以狀態和操作符為基礎的。在利用狀態空間圖表示時，從某個初始狀