第二講-知識表示

知識表示主講人：韓璐課前索引

【原因】

人工智能問題的求解是以知識和知識表示為基礎(chǔ)的。要使計(jì)算機(jī)具有智能，就必須使它具有知識，而要使計(jì)算機(jī)具有知識，首先必須解決知識的表示問題。智能活動過程主要是一個獲得并應(yīng)用知識的過程，而知識必須有適當(dāng)?shù)谋硎静疟阌谠谟?jì)算機(jī)中儲存、檢索、使用和修改?！菊n前思考】

什么是知識？

構(gòu)成知識的要素有哪些？

有哪些知識的表示觀？

有哪些知識表示方法？

如何針對具體的問題來選取不同的知識表示方法？第二章知識表示課前索引

【主要內(nèi)容】

本章主要內(nèi)容包括知識的定義、類別、要素等，知識表示的概念。重點(diǎn)掌握知識、知識表示等基本概念，會運(yùn)用一階謂詞邏輯表示法，產(chǎn)生式表示法進(jìn)行知識表達(dá)和推理。能用語義網(wǎng)絡(luò)表示法，框架表示法表達(dá)知識。了解各種主要知識表示方法的特點(diǎn)。

【知識點(diǎn)】

知識、知識表示

一階謂詞邏輯表示法，

產(chǎn)生式表示法，

語義網(wǎng)絡(luò)表示法，

框架表示法第二章知識表示概述

1.知識的定義：很難給知識以明確的定義，只能從不同側(cè)面加以理解，不同的人有不同的理解，例如：

知識是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。

知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。

知識是事實(shí)、信念和啟發(fā)式規(guī)則。

從知識庫的觀點(diǎn)看，知識是某領(lǐng)域中所涉及的各有關(guān)方面的一種符號表示。

另外有一種三維的描述方法：（范圍，目的，有效性）,其中知識的范圍由具體到一般，知識的目的從說明到指定，知識的有效性從確定到不確定。例如，“今天下雨”這種知識是具體的、說明性、不確定的，而“要證A→B，只需證明A∧~B是不可滿足的”這種知識是一般性的、指示性、確定性的。有研究報(bào)道認(rèn)為：嚴(yán)格地說AI對知識表示的認(rèn)真、系統(tǒng)的研究才剛剛開始。第二章知識表示概述

2.知識的分類：從不同的角度、不同的側(cè)面對知識有著不同的分類方法，在此，我們根據(jù)知識表達(dá)的內(nèi)容，將其簡單地分為如下幾類：

事實(shí)性知識

知識的一般直接表示，如果事實(shí)性知識是批量的、有規(guī)律的，則往往以表格、圖冊，甚至數(shù)據(jù)庫等形式出現(xiàn)。這種知識描述一般性的事實(shí)，如凡是冷血動物都要冬眠，哺乳動物都是胎生繁殖后代等。

過程性知識

表述做某件事的過程。標(biāo)準(zhǔn)程序庫也是常見的過程性知識，而且是系列化、配套的。如電視機(jī)維修法,怎樣烹制法國大餐等。

行為性知識

不直接給出事實(shí)本身，只給出它在某方面的行為。行為性知識經(jīng)常表示為某種數(shù)學(xué)模型，從某種意義上講，行為性知識描述的是事物的內(nèi)涵，而不是外延。如微分方程。第二章知識表示概述

2.知識的分類：

實(shí)例性知識

只給出一些實(shí)例。知識藏在實(shí)例中。感興趣的不是實(shí)例本身，而是隱藏在大量實(shí)例中的規(guī)律性知識。如舉例說明。

類比性知識

既不給出外延，也不給出內(nèi)涵，只給出它與其它事物的某些相似之處。類比性知識一般不能完整地刻畫事物，但它可以啟發(fā)人們在不同的領(lǐng)域中做到知識的相似性共享。如比喻，心如刀絞，謎語等。

元知識

有關(guān)知識的知識。最重要的元知識是如何使用知識的知識。例如，一個好的專家系統(tǒng)應(yīng)該知道自己能回答什么問題，不能回答什么問題，這就是關(guān)于自己知識的知識。元知識是用于如何從知識庫中找到想要的知識。第二章知識表示概述

3.知識的要素：知識的要素是指構(gòu)成知識的必需元素。一般而言，人工智能系統(tǒng)的知識包含事實(shí)、規(guī)則、控制和元知識。

事實(shí)：事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等。是有關(guān)問題環(huán)境的一些事物的知識，常以“┅是┅”形式出現(xiàn)，也是最低層的知識。例如：雪是白色的，人有四肢。

規(guī)則：事物的行動、動作和聯(lián)系的因果關(guān)系知識。這種知識是動態(tài)的，常以“如果┅那么┅”形式出現(xiàn)。例如啟發(fā)式規(guī)則，如果下雨，則出門帶傘。

控制：當(dāng)有多個動作同時被激活時，選擇哪一個動作來執(zhí)行的知識。是有關(guān)問題的求解步驟、規(guī)劃、求解策略等技巧性知識。

元知識：怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識。是有關(guān)知識的知識，是知識庫中的高層知識。元知識與控制知識有時有重疊。第二章知識表示概述

4.知識表示定義

知識表示方法是研究用機(jī)器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組事物的約定，即用一些約定的符號，把人類知識編碼表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu).

通常所說的算法，就是一種知識表示形式。因?yàn)樗虅澚私鉀Q問題的方法和步驟，又可以在計(jì)算機(jī)上用程序?qū)崿F(xiàn)。5.知識表示方法的分類

表示方法種類繁多,而且分類的標(biāo)準(zhǔn)也不大相同，通常有：直接表示，謂詞邏輯表示，產(chǎn)生式規(guī)則表示法，語義網(wǎng)絡(luò)表示法，框架表示法，腳本方法，過程表示，混合型知識表示方法，面向?qū)ο蟮谋硎痉椒ǖ?。一些主要的知識表示方法彼此間關(guān)系可用下圖表示：知識表示的研究內(nèi)容集中在兩個方面，其一是表示觀的研究，牽涉到認(rèn)識論、本體論、知識工程等方面；其二就是表示方法的研究，各種表示方法的應(yīng)用。第二章知識表示概述

知識表示方法體系圖第二章知識表示概述

知識表示的研究內(nèi)容集中在兩個方面，一是表示觀的研究，牽涉到認(rèn)識論、本體論、知識工程、心理學(xué)等方面；二是表示方法的研究，各種表示方法的應(yīng)用。第二章知識表示2.1一階謂詞邏輯表示法

邏輯是一種重要的知識表示方法。使用邏輯法表示知識，須將以自然語言描述的知識，通過引入謂詞、函數(shù)加以形式描述，獲得有關(guān)的邏輯公式，進(jìn)而以機(jī)器內(nèi)碼表示。

一階謂詞邏輯是謂詞邏輯中最直觀的一種邏輯。它以謂詞形式來表示動作的主題、客體。客體可以多個。

謂詞邏輯規(guī)范表達(dá)式：

P(x1,x2,x3,…)，這里P是謂詞,xi是主體與客體。

如：小張與小李打網(wǎng)球（ZhangandLiplaytennis）可寫為：play(Zhang,Li,tennis)這里謂詞是play，動詞主體是Zhang和Li，而客體是tennis。第二章知識表示2.1一階謂詞邏輯表示法

謂詞在一下幾個方面可以比命題更加細(xì)致地刻畫知識：

表達(dá)能力強(qiáng)

如：北京是個城市，City(x)把城市這個概念分割出來。把“城市”與“北京”兩個概念連接在一起，而且說明“北京”是“城市”的子概念。（有層）

謂詞可以代表變化的情況

如：City(北京),真。City(煤球)，假

在不同的知識之間建立聯(lián)系

如：Human(x)→Lawed(x)，人人都受法律管制，x是同一個人。Commit(x)→Punished(x)，x不一定是人也可以是動物。而{[Human(x)→Lawed(x)]→[commit(x)→Punished(x)]}，意為如果由于某個x是人而受法律管制，則這個人犯了罪就一定要受到懲罰。

謂詞邏輯能表達(dá)無法用命題邏輯表達(dá)的事情。并且能夠判斷這個語句的正確性。謂詞邏輯法是應(yīng)用最廣的知識方法之一。第二章知識表示2.1一階謂詞邏輯表示法

謂詞邏輯法是應(yīng)用最廣的方法之一，其原因是：

謂詞邏輯與數(shù)據(jù)庫，特別是關(guān)系數(shù)據(jù)庫就有密切的關(guān)系。在關(guān)系數(shù)據(jù)庫中，邏輯代數(shù)表達(dá)式是謂詞表達(dá)式之一。因此，如果采用謂詞邏輯作為系統(tǒng)的理論背景，則可將數(shù)據(jù)庫系統(tǒng)擴(kuò)展改造成知識庫。

一階謂詞邏輯具有完備的邏輯推理算法。如果對邏輯的某些外延擴(kuò)展后，則可把大部分的知識表達(dá)成一階謂詞邏輯的形式.

謂詞邏輯本身具有比較扎實(shí)的數(shù)學(xué)基礎(chǔ)，知識的表達(dá)方式?jīng)Q定了系統(tǒng)的主要結(jié)構(gòu)。因此，對知識表達(dá)方式的科學(xué)嚴(yán)密性要求就比較容易得到滿足。這樣對形式理論的擴(kuò)展推動了整個系統(tǒng)框架的發(fā)展。

邏輯推理是公理集合中演繹而得出結(jié)論的過程。由于邏輯及形式系統(tǒng)具有的重要性質(zhì)，可以保證知識庫中新舊知識在邏輯上的一致性（或通過相應(yīng)的一套處理過程檢驗(yàn)）、和所演繹出來的結(jié)論的正確性。而其它的表示方法在這點(diǎn)上還不能與其相比。第二章知識表示2.1一階謂詞邏輯表示法

例：一個房間里，有一機(jī)器人Robot，一個積木塊Box，兩個桌子A和B，怎樣用邏輯法描述從初始狀態(tài)到目標(biāo)狀態(tài)的機(jī)器人操作過程？求解及知識表示過程：

先引入謂詞：

Table(A)表示A是桌子

EmptyHanded(Robot)機(jī)器人Robot雙手空空

At(Robot,A)表示機(jī)器人Robot在A旁

Holds(Robot,Box)機(jī)器人Robot拿著Box

On(Box,A)積木塊Box在A上

設(shè)定初始狀態(tài)：

EmptyHanded(Robot)

On(Box,A)

Table(A)

Table(B)

第二章知識表示2.1一階謂詞邏輯表示法

目標(biāo)狀態(tài)是：

EmptyHanded(Robot)

On(Box,B)

Table(A)

Table(B)

機(jī)器人的每個操作的結(jié)果所引起的狀態(tài)變化，可用對原狀態(tài)的增添表和刪除表來表示。如機(jī)器人有初始狀態(tài)是把Box從A桌移到B桌上，然后仍回到Alcove，這時同初始狀態(tài)相比有：

增添表On（Box，B）

刪除表On（Box，A）

又如機(jī)器人從初始狀態(tài)，走近A桌，然后拿起B(yǎng)ox。這時同初始狀態(tài)相比有：

增添表At（Robot，A）

Holds（Robot，Box）

刪除表At（Robot，Alcove）

EmptyHanded(Robot)

On（Box，A）第二章知識表示2.1一階謂詞邏輯表示法

進(jìn)一步說，機(jī)器人的每一操作還需要先決條件。如機(jī)器人拿起A桌上的Box這一操作，先決條件：

On（Box，A）（Box在A上）

At(Robot，A)（機(jī)器人在A旁邊）

EmptyHanded（robot）（機(jī)器人手空空）

先決條件成立與否的驗(yàn)證可以使用歸結(jié)法。如將初始狀態(tài)視作已知條件，而將要驗(yàn)證的先決條件作為結(jié)論，便可作為歸結(jié)法了。歸結(jié)過程如下：

1）At(Robot,A)

2）EmptyHanded(Robot)

3）On(Box,B)

4）Table(A)

5）Table(B)

第二章知識表示2.1一階謂詞邏輯表示法

6)~On(Box,B)∨~At(Robot,A)∨~EmptyHanded(Robot)（先決條件之否定）

7)~At(Robot,A)∨~EmptyHanded(Robot)

8)~EmptyHanded(Robot)

9)NULL

于是驗(yàn)證了先決條件的成立。

從初始狀態(tài)出發(fā)，每實(shí)現(xiàn)機(jī)器人的一個操作都驗(yàn)證先決條件，并建立相應(yīng)的增添表和刪除表，便可逐步達(dá)到目標(biāo)狀態(tài)。這里僅是說明邏輯法可以描述這類問題。1972年FIKS建立的STRIPS機(jī)器人規(guī)劃系統(tǒng)就是使用的邏輯法表示的。第二章知識表示2.1一階謂詞邏輯表示法

結(jié)論

邏輯是一種重要的知識表示方法。知識在邏輯法表示下可采用歸結(jié)法或其它方法進(jìn)行準(zhǔn)確的推理。當(dāng)然一階邏輯的表達(dá)能力是有限的，其局限性如下：

不能表示不確定知識，如：tom可能不是IS系的學(xué)生。

組合爆炸，如：在有大量的事實(shí)情況下，盲目使用規(guī)則，會導(dǎo)致組合爆炸。

效率低，謂詞表示越細(xì)，越清楚，推理越慢、效率越低。實(shí)際的系統(tǒng)是在兩者之間的一種折衷。第二章知識表示2.2產(chǎn)生式表示法

2.2.1產(chǎn)生式與產(chǎn)生式系統(tǒng)產(chǎn)生式知識表示方法由美國數(shù)學(xué)家E.Post于1943提出，具有和Turing機(jī)一樣的表達(dá)能力。也有心理學(xué)家認(rèn)為人腦對知識的存儲就是產(chǎn)生式形式的。

產(chǎn)生式的一般形式為“前件十后件”。前件就是前提，后件是結(jié)論或動作。給定一組事實(shí)后，可用匹配技術(shù)尋找可用產(chǎn)生式，將已知事實(shí)代入產(chǎn)生式的前件，如果前件滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動作，即后件由前件來觸發(fā)。產(chǎn)生式表示方法容易描述事實(shí)、規(guī)則以及它們的不確定性度量。在產(chǎn)生式表示法中，對確定性知識，一個事實(shí)可用“關(guān)系（對象，……，對象）”來表示；

對不確定性知識，一個事實(shí)可用“關(guān)系（對象，……，對象，可信度因子）”來表示。“可信度因子”是指該事實(shí)為真的相信程度，可用一個0到1之間的數(shù)來表示。第二章知識表示2.2產(chǎn)生式表示法

事實(shí)的表示：

可看成是斷言一個語言變量的值或是多個語言變量間的關(guān)系的陳述句，語言變量的值或語言變量間的關(guān)系可以是一個詞，不一定是數(shù)字。

如：

實(shí)例1：香蕉是黃色的。語言變量——香蕉，值——黃色的

實(shí)例2：小李喜歡小莉。語言變量——小李、小莉，關(guān)系值——喜歡

一般使用三元組（對象，屬性，值）或（關(guān)系，對象1，對象2）來表示事實(shí)，其中對象就是語言變量，若考慮不確定性就成四元組（對象，屬性，值，不確定度量值）表示了。這種表示的機(jī)器內(nèi)部實(shí)現(xiàn)就是一個表。第二章知識表示2.2產(chǎn)生式表示法

如：對事實(shí)“老李年齡今年是65歲”可表示成：

（Li，Age，65）

而“老趙和老張是朋友”可寫成：

（Friend，Zhao，Zhang）

規(guī)則的表示：

表示事物間的因果關(guān)系，以：“ifconditionthenaction”的單一形式來表示，將規(guī)則作為知識的單位。其中的Condition部分稱作條件式前件或模式，而Action部分稱作動作或后件或結(jié)論。條件部分常是一些事實(shí)的合取而結(jié)論常是某一事實(shí)B，如果考慮不確定性，需另附可信度度量值。

規(guī)則描述的是事物間的因果關(guān)系。其基本形式為：“PQ”或“IFPTHENQ”，含義是：如果前提P滿足，則可推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作。例如：

規(guī)則1：IF天陰and空氣中濕度很大THEN可能要下雨第二章知識表示2.2產(chǎn)生式表示法

產(chǎn)生式系統(tǒng)：

以產(chǎn)生式表示知識的系統(tǒng)稱作產(chǎn)生式系統(tǒng)。一個產(chǎn)生式系統(tǒng)由知識庫和推理機(jī)兩部分組成。

知識庫:由規(guī)則庫和數(shù)據(jù)庫組成。規(guī)則庫是產(chǎn)生式規(guī)則的集合，數(shù)據(jù)庫存放輸入事實(shí)、外部數(shù)據(jù)庫輸入的事實(shí)以及中間結(jié)果和最后結(jié)果。

推理機(jī):

是一個程序，控制協(xié)同規(guī)則庫與數(shù)據(jù)庫的運(yùn)行，包含了推理方式和控制策略。推理方式有正向推理、反向推理和雙向推理。

把一組產(chǎn)生式放在一起，讓它們互相配合，協(xié)同工作，一個產(chǎn)生式生成的結(jié)論可以供另一個產(chǎn)生式作為前提使用，以這種方式求得問題的解決的系統(tǒng)就叫做產(chǎn)生式系統(tǒng)。第二章知識表示推理機(jī)規(guī)則庫綜合數(shù)據(jù)庫2.2產(chǎn)生式表示法

產(chǎn)生式系統(tǒng)中，從前提到結(jié)論通常也是一棵與或樹(各個事實(shí)之間的邏輯關(guān)系圖)。下圖就是一個與或樹的實(shí)例。圖中的弧線表示兄弟結(jié)點(diǎn)之間是“與”的關(guān)系；沒有弧線的地方，表示兄弟結(jié)點(diǎn)之間是“或”的關(guān)系。與或樹第二章知識表示2.2產(chǎn)生式表示法

例:一個動物識別系統(tǒng)的產(chǎn)生式R1：若某動物有奶，則它是哺乳動物。R2：若某動物有毛發(fā)，則它是哺乳動物。R3：若某動物吃肉，則它是食肉動物。R4：若某動物有爪且有犬齒且眼視前方，則它是食肉動物。R5：若某動物是哺乳動物且有蹄，則它是有蹄動物。R6：若某動物是有蹄動物且反芻食物，則它是有蹄動物。R7：若某動物是哺乳動物且食肉動物且黃褐色且有黑色條紋，則它是老虎。R8：若某動物是哺乳動物且食肉動物且黃褐色且有暗斑點(diǎn)，則它是金錢豹。R9：若某動物是有蹄動物且有黑色條紋，則它是斑馬。R10：若某動物是有蹄動物且長腿且長脖子且有暗斑點(diǎn)，則它是長頸鹿。第二章知識表示2.2產(chǎn)生式表示法

動物識別系統(tǒng)的產(chǎn)生式推理網(wǎng)絡(luò)：第二章知識表示2.2產(chǎn)生式表示法

2.4.2產(chǎn)生式系統(tǒng)的推理方式產(chǎn)生式系統(tǒng)的推理機(jī)的推理方式有正向推理、反向推理和雙向推理三種。正向推理：

是從已知事實(shí)出發(fā)，通過規(guī)則庫求得結(jié)論?；蚍Q為數(shù)據(jù)驅(qū)動方式，也稱為自底向上（Bottom-up）。推理過程：

規(guī)則集中的規(guī)則與數(shù)據(jù)庫中的事實(shí)進(jìn)行匹配，得到匹配的規(guī)則集合

從匹配的規(guī)則集合中選擇一條規(guī)則作為使用規(guī)則

執(zhí)行使用規(guī)則的后件。將該使用規(guī)則的后件輸入數(shù)據(jù)庫。

重復(fù)進(jìn)行，直到達(dá)到目標(biāo)第二章知識表示2.2產(chǎn)生式表示法

數(shù)據(jù)庫中有A，規(guī)則庫中有Rule1：A→B，那么Rule1就是匹配規(guī)則，進(jìn)而將后件B送入數(shù)據(jù)庫中。上述推理過程不斷進(jìn)行，即可不斷擴(kuò)大綜合數(shù)據(jù)庫中的事實(shí)數(shù)量，直至包含目標(biāo)便成功結(jié)束。

看一個具體的例子。

規(guī)則：事實(shí)中包含“有毛發(fā)”及“產(chǎn)乳”，根據(jù)規(guī)則“有毛發(fā)又產(chǎn)乳→哺乳動物”，匹配得到“哺乳動物”，則將“哺乳動物”送入數(shù)據(jù)庫中成為新的證據(jù)，作為新的前提，可以在隨后的推理中使用。

這種推理方式可能得出許多冗余規(guī)則和與目標(biāo)無關(guān)的事實(shí)，如果選擇的規(guī)則的控制策略不當(dāng)，求解效率會比較低。第二章知識表示2.2產(chǎn)生式表示法

反向推理：

從目標(biāo)出發(fā)，反向使用規(guī)則，求得已知事實(shí)，或稱為目標(biāo)驅(qū)動方式也稱自頂向下（Top-down）推理方式。

推理過程：

用規(guī)則集中的規(guī)則后件與目標(biāo)事實(shí)進(jìn)行匹配，得到匹配的規(guī)則集合

從匹配的規(guī)則集合中選擇一條規(guī)則作為使用規(guī)則

把執(zhí)行的使用規(guī)則的前件作為下一個循環(huán)的目標(biāo)事實(shí)

重復(fù)進(jìn)行，直到達(dá)到目標(biāo)

這種推理方式如果目標(biāo)明確，則推理的效率較高，常被人們所使用。第二章知識表示2.2產(chǎn)生式表示法

雙向推理：

既自頂向下（Top-down）又自底向上（bottom-down）直至達(dá)到某一個中間環(huán)節(jié)兩個方向的結(jié)果相符便成功結(jié)束。顯然，這種推理方式的推理網(wǎng)絡(luò)較小，效率也較高。

總結(jié)：采用產(chǎn)生式系統(tǒng)結(jié)構(gòu)求解問題的過程和人類求解問題時的思維很相像。因而可以用它來模擬人類求解問題的思維過程?？梢园旬a(chǎn)生式系統(tǒng)作為人工智能系統(tǒng)的基本結(jié)構(gòu)單元或基本模型看待。就好像是積木世界中的積木塊一樣。因而研究產(chǎn)生式系統(tǒng)的基本問題具有一般意義。產(chǎn)生式表示的格式固定、形式單一、規(guī)則間相互獨(dú)立。所以系統(tǒng)容易建立；推理方式單純、知識庫與推理機(jī)分離，修改方便、容易理解。

第二章知識表示2.2產(chǎn)生式表示法

產(chǎn)生式表示方法的優(yōu)點(diǎn)：

模塊性

產(chǎn)生式規(guī)則是規(guī)則庫中最基本的知識單元，各規(guī)則之間只能通過綜合數(shù)據(jù)庫發(fā)生聯(lián)系，不能相互調(diào)用，增加了規(guī)則的模塊性，有利于對知識的增加、刪除和修改。

有效性

產(chǎn)生式表示法既可以表示確定性知識，又可以表示不確定性知識，既有利于表示啟發(fā)性知識，又有利于表示過程性知識。

自然性

產(chǎn)生式表示法用“If…then…”的形式表示知識，這種表示形式與人類的判斷性知識基本一致，直觀、自然，便于推理。

第二章知識表示2.2產(chǎn)生式表示法

產(chǎn)生式表示方法的缺點(diǎn)：

求解效率低

在產(chǎn)生式表示中，各規(guī)則之間的聯(lián)系以數(shù)據(jù)庫為媒介，求解過程是一種反復(fù)進(jìn)行的“匹配－沖突消除－執(zhí)行”的過程：即先用規(guī)則的前提與已知事實(shí)匹配，再從規(guī)則庫中選取可用的規(guī)則（當(dāng)存在多條規(guī)則時，必須有合適的策略），去除規(guī)則之間的沖突，最后執(zhí)行相應(yīng)的規(guī)則。這樣的執(zhí)行效率較低。

不能表示結(jié)構(gòu)性的知識

產(chǎn)生式表示的知識有一定的格式，且規(guī)則之間不能直接調(diào)用，因此那些具有結(jié)構(gòu)關(guān)系或?qū)哟侮P(guān)系的知識不易用它表示出來。

產(chǎn)生式方法是目前專家系統(tǒng)首選的知識表示方法。用于化工工業(yè)測定分子結(jié)構(gòu)的系統(tǒng)，用于診斷腦膜炎和血液病毒感染的系統(tǒng)和用于估計(jì)礦藏的系統(tǒng)都是用這種方法進(jìn)行知識表示和推理的。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

語義網(wǎng)絡(luò)是1968年Quillian在研究人類聯(lián)想記憶時提出的心理學(xué)模型，認(rèn)為記憶是由概含間的聯(lián)系實(shí)現(xiàn)的。1972年西蒙(Simmous)首先將語義網(wǎng)絡(luò)表示法用于自然語言理解系統(tǒng)。

邏輯和產(chǎn)生式表示方法常用于表示有關(guān)論域中各個不同狀態(tài)間的關(guān)系，然而用于一個事物同其各個部分間分類知識就不方便了。而語義網(wǎng)絡(luò)便于表示這種分類知識，它同一階邏輯有相同的表達(dá)能力。

語義網(wǎng)絡(luò)是一種用實(shí)體及其語義關(guān)系來表達(dá)知識的有向圖。語義網(wǎng)絡(luò)一般由一些最基本的語義單元（稱為語義基元）組成。可用三元組來表示：（結(jié)點(diǎn)1，弧，結(jié)點(diǎn)2）結(jié)點(diǎn)：代表實(shí)體，表示各種事物、概念、情況、屬性、狀態(tài)、事件、動作等；

?。赫Z義關(guān)系，表示它所連接的兩個實(shí)體之間的語義聯(lián)系。

在語義網(wǎng)絡(luò)中，弧的方向體現(xiàn)主次，每一個結(jié)點(diǎn)和弧都必須帶有標(biāo)識，這些標(biāo)識用來說明它所代表的實(shí)體或語義。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

語義基元的結(jié)構(gòu)：（結(jié)點(diǎn)1，弧，結(jié)點(diǎn)2）結(jié)點(diǎn)間的isa、part-of、is型關(guān)系可描述如下：

(1)isa鏈用來表示具體抽象關(guān)系，或說表示一種隸屬關(guān)系，體現(xiàn)某種層次分類。其中具體層結(jié)點(diǎn)可繼承抽象層結(jié)點(diǎn)的屬性。顧員是人，可表成：顧員具有人的所有屬性。

(2)Part-of鏈用來表示部分——全體關(guān)系，即表示包含關(guān)系.

Part-of關(guān)系下各層結(jié)點(diǎn)的屬性可能是很不相同的。

如兩只手是人體的一部分，可表成：其中兩只手不一定具有人體的某些屬性。

(3)is鏈用于表示一個結(jié)點(diǎn)是另一結(jié)點(diǎn)的屬性。

如：老張是40歲，老李很胖，可分別表示成：第二章知識表示2.3語義網(wǎng)絡(luò)表示法

當(dāng)把多個語義基元用相應(yīng)的語義聯(lián)系關(guān)聯(lián)在一起時，就形成了一個語義網(wǎng)絡(luò)?；〉姆较蚴怯幸饬x的，不能隨意調(diào)換。下圖是有關(guān)圖書館的一個語義網(wǎng)絡(luò)。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

拱的素描及相應(yīng)的語義網(wǎng)絡(luò)如下圖：一個簡單的語義網(wǎng)絡(luò)圖第二章知識表示2.3語義網(wǎng)絡(luò)表示法

從功能上講，語義網(wǎng)絡(luò)可以描述任何事物間的任意復(fù)雜關(guān)系。但是，這種描述是通過把許多基本的語義關(guān)系關(guān)聯(lián)到一起來實(shí)現(xiàn)的。最常用的基本語義關(guān)系有以下幾種：

1)類屬關(guān)系最主要特征是屬性的繼承性。具體層節(jié)點(diǎn)除具有抽象層節(jié)點(diǎn)的所有屬性外，還可以增加一些自己的個性，甚至還能夠?qū)Τ橄髮庸?jié)點(diǎn)的某些屬性加以更改。常用的類屬關(guān)系有：A-Kind-of（是一種）、A-Member-of(是一員)、Is-a(是一個)。圖書館是一種建筑物；張三是學(xué)會的一個成員；張三是一個讀者；理工大學(xué)是一個單位就屬于類屬關(guān)系。

2)包含關(guān)系包含關(guān)系也稱為聚類關(guān)系，是指具有組織或結(jié)構(gòu)特征的”部分與整體”之間的關(guān)系。常用的包含關(guān)系有：A-Part-of(是一部分)。閱覽室是圖書館的一部分屬于包含關(guān)系。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

3)屬性關(guān)系常用的屬性關(guān)系有：Have(有)、Can(能)、所有者(Owner)

閱覽室有讀者；張三能講英語；閱覽室會開放等關(guān)系。

4)時間關(guān)系先后次序關(guān)系。常用的時間關(guān)系有Before(在前)，After(在后)。圖書館開放以后讀者可進(jìn)行閱覽屬于時間關(guān)系。

5)推論關(guān)系推論關(guān)系用Fetch(推出)表示。由于校園像公園推出風(fēng)景美麗屬于推論關(guān)系。

6)位置關(guān)系位置關(guān)系有空間關(guān)系Located-on(在上)、Located-at(在)、Located-under(在下)、Located-inside(在內(nèi))、Located-outside。理工大學(xué)在海福巷；圖書館在校園內(nèi)；校園在鐘山腳下。

7)相近關(guān)系常用的相近關(guān)系有：Similar-to（相似）、Near-to（接近）。校園像公園；圖書館在大禮堂附近屬于相近關(guān)系。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

語義網(wǎng)絡(luò)表示法是依據(jù)匹配來進(jìn)行推理的，根據(jù)提出的問題可構(gòu)成局部網(wǎng)絡(luò)，其中有的結(jié)點(diǎn)或弧的標(biāo)注是空的，表示有待求解的。依這個局部網(wǎng)絡(luò)，到知識庫中尋找匹配的網(wǎng)絡(luò)，以便求得問題的解答。當(dāng)然這種匹配不是完全的匹配，需考慮匹配程度。

最簡單的isa關(guān)系下的推理是直接繼承。

如：便有也還可將語義網(wǎng)絡(luò)引入邏輯含義，表示出~,∨,∧關(guān)系，便可使用歸結(jié)推理法。

1977年Hendrix提出了網(wǎng)絡(luò)的分塊技術(shù)，將復(fù)雜問題分解成許多子問題，每個問題以一個語義網(wǎng)絡(luò)表示，這樣有助于推理。

還有人將語義網(wǎng)絡(luò)中的結(jié)點(diǎn)看成有限自動機(jī)，為尋求幾個概念間的聯(lián)系，起動相應(yīng)的自動機(jī)，如有會合點(diǎn)便可求得解答。

語義網(wǎng)絡(luò)是一種重要的知識表示方法，然而相應(yīng)的推理方法還不完善。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

目前，語義網(wǎng)絡(luò)所采用的推理機(jī)制主要有匹配和繼承兩種。1．匹配在語義網(wǎng)絡(luò)中，事物是通過語義網(wǎng)絡(luò)這種結(jié)構(gòu)來描述的，事物的匹配則為結(jié)構(gòu)上的匹配，包括節(jié)點(diǎn)和弧的匹配。用匹配的方法進(jìn)行推理時，首先構(gòu)造問題的目標(biāo)網(wǎng)絡(luò)塊，然后在事實(shí)網(wǎng)絡(luò)中尋找匹配。推理從一條弧連接的兩個節(jié)點(diǎn)的匹配開始，再匹配與該兩個節(jié)點(diǎn)相連接的所有其他節(jié)點(diǎn)，直到問題得到解答。

例：假設(shè)在知識庫中存放著有關(guān)圖書館的語義網(wǎng)絡(luò)，問圖書館會干什么呢？根據(jù)這個問題的要求，可構(gòu)造如下所示的語義網(wǎng)絡(luò)片斷第二章知識表示2.3語義網(wǎng)絡(luò)表示法

當(dāng)用該語義網(wǎng)絡(luò)片斷與知識庫中的語義網(wǎng)絡(luò)進(jìn)行匹配時，由“Can”弧所指的節(jié)點(diǎn)可知，圖書館會開放，這就得到了問題的答案。如果還想知道圖書館的其他情況，可通過在語義網(wǎng)絡(luò)中增加相應(yīng)的空節(jié)點(diǎn)來實(shí)現(xiàn)。當(dāng)事實(shí)網(wǎng)絡(luò)較大或較復(fù)雜時，在匹配算法中可加入一些含有啟發(fā)式知識的選擇器函數(shù)，以提供事實(shí)網(wǎng)絡(luò)中哪些節(jié)點(diǎn)和弧可以優(yōu)先考慮匹配和怎樣匹配的建議。這種選擇器函數(shù)能加速匹配的搜索過程。2．繼承所謂繼承是指把對事物的描述從抽象節(jié)點(diǎn)傳遞到具體節(jié)點(diǎn)。通過繼承可以得到所需節(jié)點(diǎn)的一些屬性值，它通常是沿著Is-a、A-Kind-of等繼承弧進(jìn)行的。繼承的一般過程為：

(1)

建立一個節(jié)點(diǎn)表，用來存放待求解節(jié)點(diǎn)和所有以Is-a、A-Kind-of等繼承弧與此節(jié)點(diǎn)相連的那些節(jié)點(diǎn)。初始情況下，表中只有待求解節(jié)點(diǎn)。第二章知識表示2.3語義網(wǎng)絡(luò)表示法

(2)檢查表中的第一個節(jié)點(diǎn)是否有繼承弧。如果有，就把該弧所指的所有節(jié)點(diǎn)放入節(jié)點(diǎn)表的末尾，記錄這些節(jié)點(diǎn)的所有屬性，并從節(jié)點(diǎn)表中刪除第一個節(jié)點(diǎn)。如果沒有，僅從節(jié)點(diǎn)表中刪除第一個節(jié)點(diǎn)。

(3)重復(fù)(2)，直到節(jié)點(diǎn)表為空。此時，記錄下來的所有屬性都是待求解節(jié)點(diǎn)繼承來的屬性。例如，在有關(guān)圖書館的語義網(wǎng)絡(luò)中，通過繼承關(guān)系可以得到：張三不僅會講英語，而且會閱覽；閱覽室在校園內(nèi)，會開放，而且周圍風(fēng)景很美。第二章知識表示2.4框架表示法

1975年，Minsky提出了框架理論。其基本觀點(diǎn)是人腦已存儲有大量的典型情景，當(dāng)人們面臨新的情景時，就從記憶中選擇一個稱作框架的基本知識結(jié)構(gòu)，這個框架是以前記憶的一個知識空框，而其具體內(nèi)容依照新的情景而改變，對這空框的細(xì)節(jié)加工修改和補(bǔ)充，形成對新情景的認(rèn)識又記憶于人腦中。

框架理論將框架視作知識的單位，將一組有關(guān)的框架連接起來形成框架系統(tǒng)。系統(tǒng)中不同的框架可以有共同的結(jié)點(diǎn)，系統(tǒng)的行為由系統(tǒng)內(nèi)框架的變化來表現(xiàn)。推理過程是由框架間的協(xié)調(diào)來完成的。第二章知識表示2.4框架表示法

2.4.1框架結(jié)構(gòu)

框架是由若干結(jié)點(diǎn)和關(guān)系（統(tǒng)稱為槽）構(gòu)成的網(wǎng)絡(luò)，是語義網(wǎng)絡(luò)一般化的形式，與后者沒有本質(zhì)的差別?？蚣苁潜硎灸骋活惽榫暗慕Y(jié)構(gòu)化的一種數(shù)據(jù)結(jié)構(gòu)，框架的最頂層是固定的一類事物，基于概念的抽象程度表現(xiàn)出自上而下的分層結(jié)構(gòu)?？蚣苡煽蚣苊鸵恍┎劢M成，每個槽有槽值，槽值就代表信息。如將語義網(wǎng)絡(luò)表示的

表示成框架也即將結(jié)點(diǎn)間弧上的標(biāo)注也放入槽內(nèi)就成了框架表示形式。

第二章知識表示2.4框架表示法

框架可以表示為如下格式：

簡單框架的例子：

Micheal

Isa：man

Profession:singer

Height:185cm

Weight:79kg

Age:27

復(fù)雜的框架常常包含一些嵌套的框架結(jié)構(gòu)。例如一個教室框架可以是墻框架、黑板框架、天花板框架和地板框架的組合。第二章知識表示2.4框架表示法

較復(fù)雜的框架：例1:

一個教室A的框架表示

教室A框架的上層依次是：事物－物體―房間―教室―教室A,其框架表示如下圖。

其中范圍槽的槽值是個條件值，人數(shù)30-50；用途槽的槽值是個默認(rèn)值，一般上課用。這個例子上下層是Part-of關(guān)系，如黑板是教室A的一部分，但黑板的結(jié)構(gòu)、性能是與教室完全不同的。第二章知識表示2.4框架表示法

較復(fù)雜的框架：例2:

動物分類框架表示，如下圖:

上述例子上下層關(guān)系屬isa型。各層僅存有特有的信息。如金絲鳥就不必填入金絲鳥框架的槽中，因?yàn)榻鸾z鳥是鳥，依屬性可知具有鳥的屬性。第二章知識表示2.4框架表示法

2.4.2框架推理

若將一個子框架視作知識單位，如一條產(chǎn)生式規(guī)則，這樣可將一個問題的求解，通過匹配分散為各個有關(guān)的子框架的協(xié)調(diào)過程，當(dāng)然實(shí)現(xiàn)起來較為困難。這個過程可以描述為：

框架推理過程圖第二章知識表示2.4框架表示法

附加過程ASK和CHECK（程序）在推理中的作用，可由例子來說明，如確定一個人的年齡，已匹配的知識庫中的框架為：

【槽名

年齡NIL

Ifneeded

ASK

Ifadded

CHECK】

啟動過程如下：

1）如果沒有默認(rèn)值，ifneeded條件滿足

2）自動啟動ifneeded槽的附加過程ASK，向用戶查詢并等待輸入。當(dāng)用戶輸入“25”后便將25設(shè)定為所要求的年齡了。

3）若有輸入（ifadded），則執(zhí)行附加過程CHECK，檢查輸入年齡值的合法性。若有默認(rèn)值為20，而不為NIL，且無輸入，則不執(zhí)行CHECK，那就默認(rèn)年齡為20了。第二章知識表示2.4框架表示法

產(chǎn)生式系統(tǒng)框架系統(tǒng)知識表示單位推理機(jī)理建立知識庫通用性應(yīng)用用戶規(guī)則固定、與知識庫獨(dú)立容易低簡單問題初學(xué)者框架可變、與知識庫成一體困難高復(fù)雜問題專家

框架表示法沒有固定的推理機(jī)理。但框架系統(tǒng)的推理遵循匹配和繼承的原則。

繼承性是框架最重要的特性。為了很好的表達(dá)這個特性，一個框架系統(tǒng)常常被表達(dá)為樹形結(jié)構(gòu)。樹的每個結(jié)點(diǎn)也是一個框架結(jié)構(gòu)，子結(jié)點(diǎn)和父結(jié)點(diǎn)之間通過Is－a關(guān)系或A－Kind－Of關(guān)系連接。當(dāng)子結(jié)點(diǎn)的某些槽值或側(cè)面沒有被直接記錄時，可以從父結(jié)點(diǎn)繼承這些值。這樣表達(dá)的另一個好處就是，相同的信息不必重復(fù)存儲，節(jié)省了空間。產(chǎn)生式系統(tǒng)與框架系統(tǒng)的區(qū)別：第二章知識表示2.5面向?qū)ο蟊硎痉?/p>

人工智能語言有Lisp(函數(shù)型)、Prolog(邏輯型)和Smalltalk(面向?qū)ο笮?。Smalltalk語言是基于對知識的面向?qū)ο蟊硎镜摹?/p>

人們認(rèn)識世界是以世界劃分為一些事和物為基礎(chǔ)的，這里的物指物體，事指物體間的聯(lián)系。面向?qū)ο蟊硎痉ㄖ械膶ο笾肝矬w，消息指物體間的聯(lián)系，通過發(fā)送消息使對象間相互作用來求得所需的結(jié)果。

對象是由一組數(shù)據(jù)和與該組數(shù)據(jù)相關(guān)的操作構(gòu)成的實(shí)體。如一個對象叫me，會有一組表征自身的數(shù)據(jù)：

name:Liming

age:20

相應(yīng)地操作為

birthday(歲數(shù))：每年實(shí)現(xiàn)age+1

消息是由(object,Selector,arguments)表示。其中object是消息要發(fā)往的對象，Selector是要求該對象完成的操作，arguments是Selector可選的參數(shù)。第二章知識表示2.5面向?qū)ο蟊硎痉?/p>

在面向?qū)ο蟊硎局蓄惡皖惱^承是重要概念。類由一組變量和一組操作組成，它描述了一組具有相同屬性和操作的對象。每一個對象都屬于某一類，每個對象都可由相關(guān)的類生成，類生成對象的過程就是例化。一個類擁有另一個類的全部變量和操作，這種擁有就是繼承，繼承是面向?qū)ο蟊硎痉ǖ闹饕评硇问健?/p>

第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法一切問題都有三個重要的共有特征，就是狀態(tài)、操作和目標(biāo)。狀態(tài)是指各種相關(guān)對象的可能的排列、情況、形勢和現(xiàn)狀，通常用一組指標(biāo)、變量或數(shù)組來表示系統(tǒng)事實(shí)的狀態(tài)。操作是用于表示引起狀態(tài)變化的過程性知識的一組規(guī)則、關(guān)系或函數(shù)。目標(biāo)，就是從初始狀態(tài)出發(fā)，應(yīng)用操作符想要得到的那個狀態(tài)。

為提供某個問題的形式描述，需要做以下工作：

(1)定義一狀態(tài)空間，它包含有相關(guān)對象的各種可能的排列;(2)規(guī)定一個或多個屬于此空間的開始狀態(tài)；

(3)規(guī)定一個或多個屬于此空間的目標(biāo)狀態(tài)；

(4)規(guī)定一組規(guī)則，用來描述可采取的操作或算子；

(5)將非形式的問題描述轉(zhuǎn)換成形式描述；畫出狀態(tài)圖；

(6)分析問題：分析哪些特征對求解問題影響最大，用規(guī)則和相應(yīng)的控制策略去遍歷問題空間。

(7)選擇最佳技術(shù)去求解待解問題，找出從一開始狀態(tài)到一目標(biāo)狀態(tài)的某條路徑第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法狀態(tài)圖是由點(diǎn)及其連線所構(gòu)成的圖，這里的點(diǎn)稱為節(jié)點(diǎn)。連接節(jié)點(diǎn)的有向線稱為弧。如果弧線從節(jié)點(diǎn)A指向節(jié)點(diǎn)B，就說A是B的前驅(qū)，而B是A的后繼。在狀態(tài)圖中，節(jié)點(diǎn)對應(yīng)于狀態(tài)，而弧的標(biāo)記對應(yīng)于操作符。其中一個節(jié)點(diǎn)代表初始狀態(tài)，還有一個或多個節(jié)點(diǎn)對應(yīng)于目標(biāo)狀態(tài)。問題的解就是從對應(yīng)于初始狀態(tài)的節(jié)點(diǎn)連接到一個對應(yīng)于目標(biāo)狀態(tài)的節(jié)點(diǎn)形成的路徑。第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法

例：

水壺問題：有兩個水壺，一個盛滿為4公斤水，另一個盛滿為3公斤水，水壺上沒有任何度量標(biāo)記。怎樣在能裝4公斤的水壺里恰好只裝2公斤水。此問題的狀態(tài)空間可以描述為一組整數(shù)序列(X,Y)，其中X＝0,1,2,3,4(公斤)；Y＝0,l,2,3(公斤)；X表示在4公斤水壺中的含水量；Y表示在3公斤水壺中的含水量。顯然，初始狀態(tài)是(0,0)；目標(biāo)狀態(tài)為(2,n)。

用來解題的操作可用如下十條規(guī)則來描述:(l)(X，Y|X<4)(4,Y)把4公斤的水壺裝滿

(2)(X，Y|Y<3)(X,3)把3公斤的水壺裝滿

(3)（X，Y|X>0)(X-D,Y)從4公斤的水壺倒出一些水

(4)（X，Y|Y＞0(X,Y-D)從3公斤的水壺倒出一些水

(5)（X,Y|X＞0(0,Y)把4公斤水壺中的水全部倒掉

(6)（X，Y|Y>0(X,0)把3公斤水壺中的水全部倒掉第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法

(7)(X，Y|X＋Y>=4Y>0)(4，Y-(4-X))把3公斤水壺中的水往4公斤水壺里倒，直到4公斤水壺滿

(8)(X，Y|X＋Y>=3X>0)(X-(3-Y),3)把4公斤水壺中的水往3公斤水壺里倒，直到3公斤水壺滿

(9)(X，Y|X＋Y＜=3X>0)(0，X＋Y)把4公斤水壺中水全部倒入3公斤水壺

(10)(X,Y|X＋Y＜=4Y>0)(X＋Y，0)把3公斤水壺中水全部倒入4公斤水壺為了求解水壺問題，選擇其左部匹配當(dāng)前狀態(tài)的某條規(guī)則，并按照該規(guī)則右部的行為對此狀態(tài)做適當(dāng)?shù)母淖儯粰z查改變后的狀態(tài)是否為其一目標(biāo)狀態(tài)，若不是，則繼續(xù)循環(huán)。第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法顯然，求解問題的速度取決選擇下一步操作的機(jī)制，對可應(yīng)用規(guī)則的任一選擇都能導(dǎo)出一合法的狀態(tài)，但其中僅有部分選擇導(dǎo)致目標(biāo)狀態(tài)。在狀態(tài)空間表示法中，通向目標(biāo)的路徑不止一條，因此存在許多關(guān)于解的操作序列。第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法

例:修道士和野人問題在河的左岸有3個修道士，3個野人和1條船，修道士們想用這條船將所有的人都運(yùn)過河去，但是受到以下條件的限制：

(1)修道士和野人都會劃船，但船一次只能裝運(yùn)兩個人；

(2)修道士的人數(shù)必須大于野人數(shù)；

(3)野人不知道是個騙局。試問修道士如何用這條船將這些人全部都渡到河的對岸？

1．定義狀態(tài)空間設(shè)X為在左岸的修道土人數(shù)，則X的取值為0,1,2,3;設(shè)Y為在左岸的野人人數(shù)，Y的取值也為0,l,2,3;設(shè)Z為船是否在左岸，Z為1表示船在左岸，Z為0不在左岸在右岸。因此狀態(tài)空間為:(X,Y,Z|X＝0,l,2,3;Y＝0,l,2,3;Z＝0,l)

對于左岸來說初始狀態(tài)為(3,3,1);目標(biāo)狀態(tài)為(0,0,0)。對于右岸來說初始狀態(tài)為(0,0,0)；目標(biāo)狀態(tài)為(3,3,l)。第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法實(shí)際的問題空間僅由16個狀態(tài)構(gòu)成

第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法

2.定義操作符

修道士和野人問題的所用操作符的描述如下：

(1)將一個修道士從左岸運(yùn)到右岸；

(2)將一個野人從左岸運(yùn)到右岸；

(3)將一個修道士和一個野人從左岸運(yùn)到右岸；

(4)將二個修道士從左岸運(yùn)到右岸；

(5)將二個野人從左岸運(yùn)到右岸；

(6)將一個修道士從右岸運(yùn)到左岸；

(7)將一個野人從右岸運(yùn)到左岸；

(8)將一個修道士和一個野人從右岸運(yùn)到左岸；

(9)將二個修道士從右岸運(yùn)到左岸；

(10)將二個野人從右岸運(yùn)到左岸。第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法

3.問題的解第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法

4.狀態(tài)圖表示該問題的最短路徑有4條。也就是說，有4種最佳解法，每一種最佳解法要渡河達(dá)11次，才能將全部的修道士和野人渡過河。這樣，在求解的路徑上所經(jīng)過的狀態(tài)就不會重復(fù)，求解的步數(shù)也是最少的。否則，反反復(fù)復(fù)重復(fù)所經(jīng)過的狀態(tài)，求解既費(fèi)力又費(fèi)時，對于復(fù)雜問題來說，很難達(dá)到所要求的解。第二章知識表示2.6其他知識表示法

一、狀態(tài)空間表示法在傳教士和野人問題中，假定了傳教士和野人都可以劃船，由于每次擺渡船上最多可以有2個人，最少也必須有一個人(船不會自己前進(jìn))，因此在船上共有(2,0)、(0,2)、(1,1)、(1,0)和(0,1)這5種組合。其中第一個數(shù)字表示在船上的傳教士數(shù),第二個數(shù)字表示在船上的野人數(shù)。再加上從左岸到右岸和從右岸到左岸這兩種情況，所以共有10種擺渡方法。在該例題中，將這10種擺渡方法全部以規(guī)則的形式，一一列舉出來。這種方法的好處是