AI-9(本)人工智能課件

人工智能基礎(chǔ)三、知識表示人工智能研究的一個重要議題——如何表示知識?

智能體的問題求解能力取決于擁有的領(lǐng)域特有的知識知識表示技術(shù)——以計算機能自動處理的形式化方式來表示知識的技術(shù)，已趨于成熟。內(nèi)容：知識和知識表示的一般概念基本的知識表示方式——產(chǎn)生式表示和結(jié)構(gòu)化表示知識表示的實用化問題三、知識表示3.1知識和知識表示主要內(nèi)容：知識原則知識表示的作用知識表示的功能知識表示的性能基本的知識表示方法1.知識原則

里南(D.B.Lenat)&費根鮑姆(E.A.Feigenbaum)，IJCAI-10

一個系統(tǒng)展示高級的智能理解和行為，主要是因為擁有應(yīng)用領(lǐng)域特有的知識：概念、事實、表示、方法、模型、隱喻和啟發(fā)式。特有——意指應(yīng)用領(lǐng)域中有效地求解問題主要靠該領(lǐng)域特有的知識足夠的約束來自特別知識——通用知識作用微弱，不能為問題求解提供足夠的約束1.知識原則

系統(tǒng)擁有的知識和其性能(問題求解能力和效率)的關(guān)系,如圖:知識門檻：使能門檻W——指知識量超過該門檻時，系統(tǒng)就擁有了為執(zhí)行任務(wù)所需的最低限度知識。勝任門檻C——到達C點時成為某應(yīng)用領(lǐng)域中求解問題的專家，勝任只有專家才能解決的問題求解任務(wù)。全能門檻E——到此門檻，由于知識量的空前增加(豐富)，使系統(tǒng)能解決該應(yīng)用領(lǐng)域內(nèi)的幾乎所有問題，成為全能專家。知識門檻性能知識量1.知識原則知識門檻的分析：知識量差異——

達到C級，只需50~1000條規(guī)則；再加等量的規(guī)則，可達E級。智能體知識是逐步積累的，涉及到獲取、修正和學(xué)習(xí)新知識。智能系統(tǒng)的能力主要由知識庫中包含的領(lǐng)域特有的知識來決定——

作為啟發(fā)式知識(經(jīng)驗性關(guān)聯(lián)知識)高效地指導(dǎo)問題求解。70-80年代專家系統(tǒng)和知識工程的成功證明了知識原則的有效性。許多其它的人工智能研究也逐步轉(zhuǎn)向基于知識的觀點。性能知識量2.知識表示的作用以適當(dāng)?shù)姆绞奖硎局R，才導(dǎo)致智能體展示出智能行為。表示=數(shù)據(jù)結(jié)構(gòu)十處理機制恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)——用于存儲要解決的問題、可能的中間解答和最終解答以及解決問題涉及之世界的描述。符號結(jié)構(gòu)導(dǎo)致了知識的顯式表示。配套的處理機制——僅有符號結(jié)構(gòu)并不能體現(xiàn)出系統(tǒng)具有知識，符號結(jié)構(gòu)本身并不構(gòu)成意義，只有對其作適當(dāng)?shù)奶幚聿艠?gòu)成意義。

如：汽車自動駕駛系統(tǒng)規(guī)則：在路口遇紅燈時停下規(guī)則解釋程序2.知識表示的作用知識表示假設(shè)－史密斯(B.Simth)，1982

任何機械設(shè)置的智能過程均由結(jié)構(gòu)成分組成，人們作為外部觀察者,自然地引用這些結(jié)構(gòu)對該智能過程展示的知識作陳述性描述；獨立于這樣的外部語義，它們在產(chǎn)生顯示出有知識的行為中起到基本的作用。從概念上闡明了知識表示在建造智能化軟件系統(tǒng)中的作用把知識表示的研究與其它涉及符號處理的技術(shù)區(qū)分開來2.知識表示的作用結(jié)構(gòu)成分－KB系統(tǒng)中的符號結(jié)構(gòu)，滿足兩個主要特性：

1)可解釋為表示知識的命題知識表示隱含地要求符號結(jié)構(gòu)能以真值理論來解釋，從而可以因某些命題的存在而說世界必定是什么樣子的。符號結(jié)構(gòu)本身不必是命題形式，但我們作為KB系統(tǒng)的外部觀察者，能把它們解釋為命題而加以理解。例：語義網(wǎng)絡(luò)中的節(jié)點——包括若干槽的符號結(jié)構(gòu)(NodeG-alIsa:Grade-assignmentStudent:JohnCourse:CS100Mark:85)Grade-assignment(G-al)∧Student(G-al,John)∧

Course(G-al,CS100)∧Mark(G-al,85)

Grade(John，CS100，85)2.知識表示的作用－結(jié)構(gòu)成分的特性

2)在KB系統(tǒng)的行為中起因果作用這種作用與將符號結(jié)構(gòu)理解為表示知識的命題是一致的能把系統(tǒng)的智能行為歸因為是系統(tǒng)具有某種表示于符號結(jié)構(gòu)中的知識注意：并不是系統(tǒng)能意識到它有知識，而是觀察者從觀察到的行為中認(rèn)為系統(tǒng)具有某種知識顏色問題例—說出雪、草和天空的顏色

2.知識表示的作用－知識表示假設(shè)

結(jié)構(gòu)成分－KB系統(tǒng)中的符號結(jié)構(gòu)，滿足兩個主要特性：

1)可解釋為表示知識的命題2)在KB系統(tǒng)的行為中起因果作用顏色問題例—說出雪、草和天空的顏色

系統(tǒng)應(yīng)如何設(shè)計才成為KB系統(tǒng)?

兩種設(shè)計方式等價？風(fēng)格很不相同

(2)以清晰的符號結(jié)構(gòu)表示關(guān)于顏色的知識顏色問題的KB系統(tǒng)：(1)PrintColour(snow):-!,write(“It’swhite.”).

PrintColour(grass):-!,write(“It’sgreen.”).

PrintColour(sky):-!,write(“It’syellow.”).

PrintColour(x):-!,write(“Beatsme!”).

若問題是：?-PrintColour(grass)，則系統(tǒng)回答：It’sgreen(2)PrintColour(x):-

Colour(x,y),!,write(“It’s”),write(y),write(“.”).

PrintColour(x):-write(“Beatsme!”).

Colour(snow,white).

Colour(grass,green).

Colour(sky,yellow).Prolog語言：Horn子句<結(jié)論>[:-[<前提>][!][<操作>]]2.知識表示的作用－知識表示假設(shè)

結(jié)構(gòu)成分－KB系統(tǒng)中的符號結(jié)構(gòu)，滿足兩個主要特性：

1)可解釋為表示知識的命題2)在KB系統(tǒng)的行為中起因果作用第二種方式設(shè)計了一個KB系統(tǒng)：以清晰的符號結(jié)構(gòu)表示關(guān)于顏色的知識；以規(guī)則的形式(逆向推理規(guī)則)表示“要打印x的顏色，必須知道x的顏色是y”；此符號結(jié)構(gòu)在系統(tǒng)回答關(guān)于顏色問題的行為中明顯地起到因果作用；因為系統(tǒng)擁有關(guān)于顏色的知識,當(dāng)接收關(guān)于顏色的問題時,系統(tǒng)才會作出正確回答.第一種方式設(shè)計的系統(tǒng)不能稱為KB系統(tǒng)未能清晰地表示關(guān)于顏色的知識奇怪的知識：寫字符串和打印顏色的關(guān)聯(lián)顏色問題的KB系統(tǒng)：(1)PrintColour(snow):-!,write(“It’swhite.”).

PrintColour(grass):-!,write(“It’sgreen.”).

PrintColour(sky):-!,write(“It’syellow.”).

PrintColour(x):-!,write(“Beatsme!”).

若問題是：?-PrintColour(grass)，則系統(tǒng)回答：It’sgreen(2)PrintColour(x):-

Colour(x,y),!,write(“It’s”),write(y),write(“.”).

PrintColour(x):-write(“Beatsme!”).

Colour(snow,white).

Colour(grass,green).

Colour(sky,yellow).2.知識表示的作用工作假設(shè)——用合理方式去建造智能軟件系統(tǒng)：從開發(fā)KB系統(tǒng)的實用角度，闡述設(shè)計符號結(jié)構(gòu)去表示知識在實現(xiàn)人工的智能行為中的關(guān)鍵作用，目的不是解釋認(rèn)知行為。KB系統(tǒng)的設(shè)計：知識表示：表示語言——以符號結(jié)構(gòu)描述獲取到的領(lǐng)域知識推理機制——應(yīng)用這些知識實現(xiàn)智能行為領(lǐng)域特有的知識知識表示假設(shè)－史密斯(B.Simth),1982

任何機械設(shè)置的智能過程均由結(jié)構(gòu)成分組成，人們作為外部觀察者,自然地引用這些結(jié)構(gòu)對該智能過程展示的知識作陳述性描述；獨立于這樣的外部語義，它們在產(chǎn)生顯示出有知識的行為中起到基本的作用。3.知識表示的功能解決復(fù)雜問題——知識的表示必須能支持多種不同的問題求解活動不同的活動往往需用不同方式表示的知識；知識表示面臨的抉擇：以統(tǒng)一的表示方式表示所有的知識——以統(tǒng)一的符號結(jié)構(gòu)來換取知識獲取和知識庫維護上的簡易性，但導(dǎo)致推理的低效性；以不同的表示方式表示特性不同的知識——知識表示的設(shè)計是一個要根據(jù)實際應(yīng)用加以權(quán)衡利弊的問題。支持三種類型的問題求解活動知識獲取——支持智能體漸增地獲取知識，使其內(nèi)部模型越來越精確地反映外部世界，以便有效地完成問題求解任務(wù)。(個性、共性)感知——感知其是否處于其擁有的知識可利用的世界狀態(tài)中。搜索行動規(guī)劃——能正確表示計劃、目標(biāo)、假設(shè)和期望。4.知識表示的性能

伍茲(Woods)，從兩方面評價:表示的充分性——作重要區(qū)分和避免不必要區(qū)分的能力才能恰當(dāng)?shù)孛枋鰡栴}求解涉及的事物，以及智能體對于外部世界的信念、目的和猜測等。表示法效用——支持被表示知識的使用，即表示知識的元素和處理這些元素的操作應(yīng)能有效地支持使用知識的推理活動。概念效率知識表示方式應(yīng)能有利于知識庫以自然的方式吸收隨意的新知識.利于知識庫的逐步精化，使包含于知識庫中的有關(guān)世界的內(nèi)部模型能逐步地精化和調(diào)整到接近于正確地反映外部世界。計算效率—推理的有效性，如推理的速度、結(jié)論的正確性和有效性…4.知識表示的性能－權(quán)衡分析兼顧概念效率和計算效率往往是困難的：概念效率－要求表示知識的符號結(jié)構(gòu)與知識的獲取和知識庫維護相容(人的思維方式)

計算效率－要求與推理機相容(計算機目標(biāo)代碼方式)提供兩套符號結(jié)構(gòu)，分別面向知識獲取和機器推理，并設(shè)計自動轉(zhuǎn)變程序來實現(xiàn)兩者間的映射。表示的充分性和表示法效用相互制約提高一個方面的性能以犧牲另一方面的性能為代價根據(jù)應(yīng)用環(huán)境和問題特征作取舍權(quán)衡，以能否滿足需求為最實用的評價準(zhǔn)則，否定絕對的性能比較準(zhǔn)則一階謂詞邏輯具有最好的表示充分性產(chǎn)生式系統(tǒng)、結(jié)構(gòu)化表示具有更好的表示法效用5.基本的知識表示方式－一階謂詞邏輯

知識表示方式——一階謂詞邏輯、產(chǎn)生式表示、結(jié)構(gòu)化表示表示元素：謂詞公式、連詞和量詞優(yōu)點：表示元素具有良好定義的語義,便于自然地表示概念,準(zhǔn)確靈活很好的表示充分性，能適用于各種應(yīng)用領(lǐng)域缺點：歸結(jié)演繹推理不能應(yīng)用啟發(fā)式知識控制推理，知識庫較大時推理效率極低不能保證在合理的時間內(nèi)給出解答(不可判定)，實用領(lǐng)域狹窄對一階謂詞邏輯作種種限制——Prolog和各種演繹推理系統(tǒng)以減弱表示的充分性為代價，大幅度增加了表示法的效用表示知識的符號結(jié)構(gòu)過于簡單，無法有效描述結(jié)構(gòu)復(fù)雜的事物5.基本的知識表示方式

－產(chǎn)生式表示

用產(chǎn)生式表示的系統(tǒng)(產(chǎn)生式系統(tǒng))由三個部分組成：規(guī)則庫——產(chǎn)生式的規(guī)則集合綜合數(shù)據(jù)庫——記載問題求解的初始狀態(tài)和中間結(jié)果控制子系統(tǒng)——執(zhí)行識別–行動循環(huán)，并在每一循環(huán)中選擇激活的規(guī)則和執(zhí)行規(guī)則右部擬定的動作例:設(shè)綜合數(shù)據(jù)庫的初始內(nèi)容db為集合{a,b,c},其中a、b、c均為字符；建立規(guī)則庫，其包含以下三條插入雙字符的規(guī)則：

R1:

(ab∈db)

insert(db,“ab”)R2:

(ac∈db)

insert(db,“ac”)R3:

(bc∈db)

insert(db,“bc”)推理的目標(biāo)是使db成為：

{a,b,c,ab,ac,bc}推理控制策略——無信息控制5.基本的知識表示方式

－產(chǎn)生式表示

用產(chǎn)生式表示的系統(tǒng)(產(chǎn)生式系統(tǒng))由三個部分組成：規(guī)則庫、綜合數(shù)據(jù)庫、控制子系統(tǒng)優(yōu)點：增加表示法的概念效率——規(guī)則的條件部分不限于謂詞公式：可以是關(guān)系表達式和真值函數(shù)；且動作可以是任何操作(演繹推理系統(tǒng)中規(guī)則的右部只能是推理結(jié)論)增加表示法的計算效率——通過設(shè)置控制元素于綜合數(shù)據(jù)庫和采用多規(guī)則激活情況下的沖突解法，可以有效地控制推理過程產(chǎn)生式規(guī)則最適合于表示各種啟發(fā)式知識以指示事物間的經(jīng)驗性關(guān)聯(lián)，廣泛應(yīng)用于專家系統(tǒng)的設(shè)計缺點：規(guī)則的堆積存儲，缺乏組織；沖突解法的單一性不能自然地適應(yīng)于許多場合通過設(shè)置控制元素來設(shè)計控制策略，在復(fù)雜的情況下常不可行缺乏結(jié)構(gòu)化手段，產(chǎn)生式表示無法有效地描述結(jié)構(gòu)復(fù)雜的事物例:設(shè)綜合數(shù)據(jù)庫的初始內(nèi)容db為集合{a,b,c},其中a、b、c均為字符；建立規(guī)則庫,其包含以下三條插入雙字符的規(guī)則：R1:

(ab∈db)

insert(db,“ab”)R2:

(ac∈db)

insert(db,“ac”)R3:

(bc∈db)

insert(db,“bc”)推理的目標(biāo)是使db成為：

{a,b,c,ab,ac,bc}

推理控制策略——無信息控制5.基本的知識表示方式

－結(jié)構(gòu)化表示：語義網(wǎng)絡(luò)、框架表示

表示知識的符號結(jié)構(gòu)——節(jié)點和框架：由一組slots(槽)構(gòu)成用于集中表示對象(概念或個體事物)的屬性和對象間的關(guān)系語義網(wǎng)絡(luò)——注重表示對象間的關(guān)系

框架系統(tǒng)——更強調(diào)對象的內(nèi)部結(jié)構(gòu)5.基本的知識表示方式

－結(jié)構(gòu)化表示：語義網(wǎng)絡(luò)、框架表示

表示知識的符號結(jié)構(gòu)——節(jié)點和框架：優(yōu)點：在知識庫中進行檢索時具有較高的效率節(jié)點(框架)集中了概念或個體的所有屬性描述和關(guān)系描述，又可用槽作為索引特性繼承和程序附加功能，使有效地組織和處理知識成為可能缺點：在刻畫真值理論方面過于自由化，易引起二義性甚至嚴(yán)重錯誤

－開發(fā)KB系統(tǒng)的陷阱框架的語義允許嚴(yán)格定義和典型范例這兩種不相容的解釋Isa鏈同時用于表示集合一子集關(guān)系、集合一成員關(guān)系表示集合概念的框架定義集合本身的特性，又記載其成員的共性由于結(jié)構(gòu)化表示的復(fù)雜性，知識庫維護需付出高得多的代價5.基本的知識表示方式－綜合分析

一階謂詞邏輯、產(chǎn)生式表示、結(jié)構(gòu)化表示一階邏輯是知識表示的基本手段，進而構(gòu)成人工智能研究的基礎(chǔ)；后二種均可轉(zhuǎn)變?yōu)榈葍r的一階邏輯表示方式。后二種減弱表示的充分性，卻提高了表示法效用，使這些表示方式能應(yīng)用于許多實際問題的解決。犧牲表示的充分性是允許的也是合理的，實用的人工智能系統(tǒng)往往只涉及到某些方面的表示充分性，其它方面可以忽略。綜合多種知識表示方式，利于充分、有效地表示和解決復(fù)雜問題。3.2產(chǎn)生式表示－起源美國數(shù)學(xué)家波斯特(Post)，1943年,產(chǎn)生式系統(tǒng)以產(chǎn)生式的規(guī)則描述符號串替代運算用于描述形式語言的語法，表示人類心理活動的認(rèn)知過程等現(xiàn)代產(chǎn)生式系統(tǒng)：與~模型很不相同，但基本概念相同(使用產(chǎn)生式規(guī)則表示知識)便于模擬人求解問題的思維方式,系統(tǒng)模塊性強,易于修改擴充,應(yīng)用廣泛目前大多數(shù)專家系統(tǒng)(尤其是中小型系統(tǒng))都采用產(chǎn)生式系統(tǒng)的結(jié)構(gòu)方式來建立。DENDRAL、MYCIN3.2產(chǎn)生式表示主要內(nèi)容：產(chǎn)生式系統(tǒng)控制策略產(chǎn)生式系統(tǒng)的分類3.2.1產(chǎn)生式系統(tǒng)

1.產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則——用于表示事物間的啟發(fā)式關(guān)聯(lián)

P

Q

或IFPthenQP——規(guī)則得以激活使用的條件(或稱前提)Q——指示規(guī)則激活時應(yīng)該執(zhí)行的動作(或應(yīng)該得出的結(jié)論)依據(jù)規(guī)則右部的表示方式，規(guī)則分類——條件-動作型、前提-結(jié)論型例：(前提-結(jié)論型)關(guān)于動物世界的產(chǎn)生式系統(tǒng)有規(guī)則：若某動物是哺乳動物，且吃肉；則這種動物是食肉動物。

(Mammal?x)∧(Eat?xMeat)(Carnivore?x)模式變量?x視為隱含地受全稱量詞約束，該規(guī)則實際為一條正向演繹推理規(guī)則產(chǎn)生式規(guī)則與演繹推理規(guī)則的比較：不要求遵從一階謂詞演算的表示形式前提-結(jié)論型規(guī)則前提——匹配模式(即謂詞公式)、關(guān)系表達式和真值函數(shù)的任意與、或、非組合

規(guī)則結(jié)論——任意數(shù)據(jù)結(jié)構(gòu)(向量、數(shù)組、表格等)條件-動作型規(guī)則的右部——任意操作函數(shù)例：x-1＞1∧null(y)

x:=0規(guī)則的左部(前件)、右部(后件)

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

1.產(chǎn)生式規(guī)則

2.產(chǎn)生式系統(tǒng)組成

前二者構(gòu)成產(chǎn)生式系統(tǒng)的問題表示(描述)后者控制應(yīng)用規(guī)則推出解答的全過程規(guī)則庫——存放應(yīng)用領(lǐng)域的常識和啟發(fā)式知識產(chǎn)生式規(guī)則的集合綜合數(shù)據(jù)庫——描述問題求解狀態(tài)(簡稱問題狀態(tài))表示為謂詞公式的事實元素集或任何數(shù)據(jù)結(jié)構(gòu)，如向量、數(shù)組和表格等

例：關(guān)于動物世界的產(chǎn)生式系統(tǒng)有：推理過程中間結(jié)果的存貯池

控制系統(tǒng)——產(chǎn)生式系統(tǒng)的推理機(規(guī)則的解釋器)

2.產(chǎn)生式系統(tǒng)組成

控制系統(tǒng)——產(chǎn)生式系統(tǒng)的推理機(規(guī)則的解釋器)驅(qū)動和控制整個系統(tǒng)的運行基本的控制流程：識別——行動循環(huán)識別階段——在規(guī)則庫中識別條件為真的規(guī)則,使它們激活；行動階段——執(zhí)行激活的規(guī)則，即執(zhí)行規(guī)則右部指定的對于綜合數(shù)據(jù)庫的操作和任何其它合適的操作。沖突——多于一條的規(guī)則激活沖突解決——基于某種控制策略去選定需要執(zhí)行的規(guī)則First——選用首條激活的規(guī)則加以執(zhí)行Best——選用已激活規(guī)則中最好的加以執(zhí)行“最好”的評價依賴于應(yīng)用領(lǐng)域制定的準(zhǔn)則All——執(zhí)行所有激活的規(guī)則2.產(chǎn)生式系統(tǒng)組成規(guī)則庫——存放應(yīng)用領(lǐng)域的常識和啟發(fā)式知識綜合數(shù)據(jù)庫——描述問題求解狀態(tài)(簡稱問題狀態(tài))控制系統(tǒng)——產(chǎn)生式系統(tǒng)的推理機(規(guī)則的解釋器)控制機制就是不斷地挑選可激活的規(guī)則對綜合數(shù)據(jù)庫進行操作,直至得到解答

綜合數(shù)據(jù)庫內(nèi)容轉(zhuǎn)變>描述的目標(biāo)狀態(tài)失敗結(jié)束

(Mammal?x)∧(Eat?xMeat)(Carnivore?x)(MammalDog)(EatDogMeat)(CarnivoreDog)3.應(yīng)用實例產(chǎn)生式系統(tǒng)問題表示的設(shè)計:綜合數(shù)據(jù)庫——問題狀態(tài)規(guī)則庫——操作算子實例：八數(shù)碼游戲傳教士與野人問題旅行商問題：R1:not-visit(x)

move(x),R2:visit-all()

move(A)文法分析問題：設(shè)計一組重寫規(guī)則作為產(chǎn)生式規(guī)則問題狀態(tài)：3×3矩陣每個矩陣元素Sij∈{0,1,…,8}；其中，1≤i,j≤3數(shù)字0－空格數(shù)字1-8－相應(yīng)棋牌。操作算子：L(0),R(0),U(0),D(0)

約束：空格不能移出棋盤。

評價函數(shù)：f(n)=d(n)+w(n)d(n)——當(dāng)前被考察的節(jié)點n在搜索圖中的節(jié)點深度；w(n)——其值是節(jié)點n與目標(biāo)狀態(tài)節(jié)點相比較，錯位棋牌個數(shù)應(yīng)用算法A的八數(shù)碼問題搜索圖綜合數(shù)據(jù)庫－表示棋盤布局(問題狀態(tài))的矩陣定義一組產(chǎn)生式規(guī)則－由于改變棋盤布局的操作可通過空格移動實現(xiàn)，建立4個條件-動作型規(guī)則來為空格的左、上、右、下移動操作建立激活條件設(shè)Sij指示矩陣第i行第j列的數(shù)碼(1≤i,j≤3)，i0,j0指示空格所在的行、列數(shù)，則有：

R1:j0–1≥1

Siojo:=Sio(jo-1)∧Sio(jo-1):=0(空格左移)R2:i0–1≥1

Siojo:=S(io-1)jo∧S(io-1)jo:=0(空格上移)R3:j0+1≤3

Siojo:=Sio(jo+1)∧Sio(jo+1):=0(空格右移)R4:i0+1≤3

Siojo:=S(io+1)jo∧S(io+1)jo:=0(空格下移)3.應(yīng)用實例

八數(shù)碼游戲(2.1.1.1節(jié))－設(shè)計為產(chǎn)生式系統(tǒng)問題狀態(tài)：3×3矩陣每個矩陣元素Sij∈{0,1,…,8}；其中,1≤i,j≤3數(shù)字0－空格數(shù)字1-8－相應(yīng)棋牌。操作算子：L(0),R(0),U(0),D(0)

約束：空格不能移出棋盤。綜合數(shù)據(jù)庫－表示棋盤布局(問題狀態(tài))的矩陣產(chǎn)生式規(guī)則－建立4個條件-動作型規(guī)則為空格的移動操作建立激活條件設(shè)Sij指示矩陣第i行第j列的數(shù)碼(1≤i,j≤3),i0,j0指示空格所在的行、列數(shù),則有:

R1:j0–1≥1

Siojo:=Sio(jo-1)∧Sio(jo-1):=0(空格左移)R2:i0–1≥1

Siojo:=S(io-1)jo∧S(io-1)jo:=0(空格上移)R3:j0+1≤3

Siojo:=Sio(jo+1)∧Sio(jo+1):=0(空格右移)R4:i0+1≤3

Siojo:=S(io+1)jo∧S(io+1)jo:=0(空格下移)例如當(dāng)前棋盤布局為:

則綜合數(shù)據(jù)庫內(nèi)容為:

規(guī)則R2、R3和R4均可激活3.應(yīng)用實例

八數(shù)碼游戲(2.1.1.1節(jié))－設(shè)計為產(chǎn)生式系統(tǒng)若沖突解決策略采用First,則執(zhí)行R2右部操作，綜合數(shù)據(jù)庫內(nèi)容變換為:

采用Best策略選取激活的規(guī)則：用啟發(fā)式函數(shù)W(n)判別導(dǎo)致下一狀態(tài)與目標(biāo)狀態(tài)差距最小的規(guī)則，可快速搜索到解答(即目標(biāo)狀態(tài))綜合數(shù)據(jù)庫－表示棋盤布局(問題狀態(tài))的矩陣定義一組產(chǎn)生式規(guī)則－由于改變棋盤布局的操作可通過空格移動實現(xiàn)，建立4

個條件-動作型規(guī)則來為空格的左、上、右、下移動操作建立激活條件設(shè)Sij指示矩陣第i行第j列的數(shù)碼(1≤i,j≤3)，i0,j0指示空格所在的行、列數(shù)，則有：

R1:j0–1≥1

Siojo:=Sio(jo-1)∧Sio(jo-1):=0(空格左移)R2:i0–1≥1

Siojo:=S(io-1)jo∧S(io-1)jo:=0(空格上移)R3:j0+1≤3

Siojo:=Sio(jo+1)∧Sio(jo+1):=0(空格右移)R4:i0+1≤3

Siojo:=S(io+1)jo∧S(io+1)jo:=0(空格下移)例如當(dāng)前棋盤布局為:則綜合數(shù)據(jù)庫內(nèi)容為:規(guī)則R2、R3和R4均可激活若沖突解決策略采用First,則執(zhí)行R2右部操作，綜合數(shù)據(jù)庫內(nèi)容變換為:

采用Best策略選取激活的規(guī)則：用啟發(fā)式函數(shù)W(n)判別導(dǎo)致下一狀態(tài)與目標(biāo)狀態(tài)差距最小的規(guī)則，可快速搜索到解答(即目標(biāo)狀態(tài))3.應(yīng)用實例

八數(shù)碼游戲(2.1.1.1節(jié))－設(shè)計為產(chǎn)生式系統(tǒng)狀態(tài)空間表示－"傳教士和野人問題"

3個傳教士帶領(lǐng)3個野人劃船渡河

m－傳教士在左岸或船上的實際人數(shù)

c－野人在左岸或船上的實際人數(shù)

b－1船在左岸，否則為0約束條件：m>=c,船上人數(shù)<=2設(shè)初始狀態(tài)下傳教士、野人和船都在左岸，目標(biāo)狀態(tài)下三者均在右岸。問題狀態(tài)以三元組(m,c,b)表示，則問題求解任務(wù)可描述為：

(3，3，1)→(0，0，0)

操作算子(10個)：L(m,c)－從左岸到右岸的劃船操作

R(m,c)－從右岸回到左岸的劃船操作

m和c取值的可能組合(5個)：10，20，11，01，023.應(yīng)用實例

2)傳教士與野人問題綜合數(shù)據(jù)庫－三元組：(m，c，b)10個可能的操作算子表示為10條規(guī)則：

L(1,0):m≥1∧b=1

m:=m-1∧b:=0;L(0,1):c≥1∧b=1

c:=c-1∧b:=0;L(1,1):m≥1∧c≥1∧b=1

m:=m-1∧c:=c-1∧b:=0;L(2,0):m≥2∧b=1

m:=m-2∧b:=0;L(0,2):c≥2∧b=1

c:=c-2∧b:=0;R(1,0):m≤2∧b=0

m:=m+1∧b:=1;R(0,1):c≤2∧b=0

c:=c+1∧b:=1;R(1,1):m≤2∧c≤2∧b=0

m:=m+1∧c:=c+1∧b:=1;R(2,0):m≤1∧b=0

m:=m+2∧b:=1;R(0,2):c≤1∧b=0

c:=c+2∧b:=1.問題狀態(tài)以三元組(m,c,b)表示，問題求解任務(wù)描述為：(3,3,1)→(0,0,0)操作算子(10個)：L(m,c)

R(m,c)m和c取值的可能組合(5個)：10,01,11,20,02規(guī)則激活：初始狀態(tài)(3,3,1)*

違反安全約束*啟發(fā)式函數(shù),舍去

**違反安全約束

*3.應(yīng)用實例

2)傳教士與野人問題綜合數(shù)據(jù)庫－三元組：(m，c，b)10個可能的操作算子表示為10條規(guī)則：

L(1,0):m≥1∧b=1

m:=m-1∧b:=0;L(0,1):c≥1∧b=1

c:=c-1∧b:=0;L(1,1):m≥1∧c≥1∧b=1

m:=m-1∧c:=c-1∧b:=0;L(2,0):m≥2∧b=1

m:=m-2∧b:=0;L(0,2):c≥2∧b=1

c:=c-2∧b:=0;R(1,0):m≤2∧b=0

m:=m+1∧b:=1;R(0,1):c≤2∧b=0

c:=c+1∧b:=1;R(1,1):m≤2∧c≤2∧b=0

m:=m+1∧c:=c+1∧b:=1;R(2,0):m≤1∧b=0

m:=m+2∧b:=1;R(0,2):c≤1∧b=0

c:=c+2∧b:=1.

每一條規(guī)則的右部增加一個函數(shù)顯示執(zhí)行的渡河操作，例如

write(“L(1,0)”)(對應(yīng)于面向渡河操作L(1,0)的規(guī)則)，和

write(“R(1,0)”)(對應(yīng)于面向渡河操作R(1,0)的規(guī)則)；增加一條規(guī)則：

m=0∧c=0∧b=0

halt()；

halt函數(shù)指示推理結(jié)束(到達目標(biāo)狀態(tài))

則產(chǎn)生式系統(tǒng)能在綜合數(shù)據(jù)庫的內(nèi)容變遷為表示目標(biāo)狀態(tài)時成功結(jié)束推理，并顯示出使初始狀態(tài)變遷到目標(biāo)狀態(tài)的渡河操作(規(guī)則)序列。3.應(yīng)用實例

2)傳教士與野人問題綜合數(shù)據(jù)庫－三元組：(m，c，b)10個可能的操作算子表示為10條規(guī)則：

L(1,0):m≥1∧b=1

m:=m-1∧b:=0;L(0,1):c≥1∧b=1

c:=c-1∧b:=0;L(1,1):m≥1∧c≥1∧b=1

m:=m-1∧c:=c-1∧b:=0;L(2,0):m≥2∧b=1

m:=m-2∧b:=0;L(0,2):c≥2∧b=1

c:=c-2∧b:=0;R(1,0):m≤2∧b=0

m:=m+1∧b:=1;R(0,1):c≤2∧b=0

c:=c+1∧b:=1;R(1,1):m≤2∧c≤2∧b=0

m:=m+1∧c:=c+1∧b:=1;R(2,0):m≤1∧b=0

m:=m+2∧b:=1;R(0,2):c≤1∧b=0

c:=c+2∧b:=1.

每一條規(guī)則的右部增加一個函數(shù)顯示執(zhí)行的渡河操作，例如write(“L(1,0)”)(對應(yīng)于面向渡河操作L(1,0)的規(guī)則)，和write(“R(1，0)”)(對應(yīng)于面向渡河操作R(1,0)的規(guī)則)；增加一條規(guī)則：

m=0∧c=0∧b=0

halt()；

halt是一個指示推理結(jié)束(到達目標(biāo)狀態(tài))的函數(shù)則產(chǎn)生式系統(tǒng)能在綜合數(shù)據(jù)庫的內(nèi)容變遷為表示目標(biāo)狀態(tài)時成功結(jié)束推理，并顯示出使初始狀態(tài)變遷到目標(biāo)狀態(tài)的渡河操作(規(guī)則)序列。*違反安全約束*啟發(fā)式函數(shù),舍去**違反安全約束*3.2.2控制策略

選用合適的規(guī)則推進問題求解與一般圖搜索策略相比較：試探性選擇的對象：產(chǎn)生式系統(tǒng)——激活的規(guī)則一般圖搜索——問題狀態(tài)推理(搜索)失敗回溯時問題狀態(tài)的恢復(fù)：產(chǎn)生式系統(tǒng)——綜合數(shù)據(jù)庫只反映某條規(guī)則執(zhí)行后的當(dāng)前問題狀態(tài)，前一狀態(tài)未加保留；必須設(shè)法恢復(fù)到規(guī)則執(zhí)行前的狀態(tài)；再選別的可激活規(guī)則作試探性推理，或作某些彌補、修正工作，再繼續(xù)進行推理。一般圖搜索——記載了節(jié)點相應(yīng)狀態(tài)下的綜合數(shù)據(jù)庫內(nèi)容，不存在問題狀態(tài)恢復(fù)的需求。3.2.2控制策略－分類無信息控制

深度優(yōu)先的盲目搜索方式應(yīng)用“First”沖突解法去控制整個問題求解過程每個循環(huán)的識別階段按排列順序自上而下地對規(guī)則庫中的規(guī)則作激活檢查，第一條激活的規(guī)則就用于推進問題求解。優(yōu)化控制：不可回溯的優(yōu)化控制

應(yīng)用啟發(fā)式知識的搜索方式可回溯的優(yōu)化控制3.2.2控制策略－分類優(yōu)化控制：不可回溯的優(yōu)化控制

應(yīng)用啟發(fā)式知識的搜索方式應(yīng)用“Best”沖突解法去控制整個問題求解過程

爬山法啟發(fā)式知識用于作為“元知識”(Metaknowledge)，選擇“最好”的規(guī)則去推進問題求解選用的規(guī)則在執(zhí)行后發(fā)現(xiàn)不合適(甚至錯誤)，也不撤銷它們，而是選擇新的更合適的規(guī)則去彌補它們的不良影響簡單易行，適于注重找到解答而不留意解答步驟(識別一行動循環(huán)個數(shù))多少的應(yīng)用問題(八數(shù)碼、下棋)可回溯的優(yōu)化控制

3.2.2控制策略－可回溯的優(yōu)化控制允許在推理進入失敗點時返回到按時序最接近的推理分支點通過遞歸過程實現(xiàn)的可回溯優(yōu)化控制算法PS-BACKTRACK(db)：

識別-行動循環(huán)——搜索循環(huán)

推理失敗時的回溯——若遞歸調(diào)用進入失敗狀態(tài)->算法的上次調(diào)用->7->4從rs取用表首規(guī)則，從另一推理分支前進

由于遞歸算法，從失敗狀態(tài)回溯上一狀態(tài)時，上一狀態(tài)的描述即db仍保留，回溯時不需作任何狀態(tài)恢復(fù)工作。缺點：若啟發(fā)式知識不健全，過多的回溯影響推理效率按時序回溯的盲目性——只能回溯到上一個推理分支點，不能準(zhǔn)確地直接返回到推理失敗的根源相應(yīng)的推理分支點，使許多回溯工作白白浪費.(圖)1.若db指示了目標(biāo)狀態(tài)，則輸出(顯示)db

作為解答，算法成功結(jié)束；2.若db指示了失敗狀態(tài)，則返回真值F；3.rs:=RULE-ACTIVATE(db)，并用啟發(fā)式知識對rs中的規(guī)則按從優(yōu)到劣的次序排列;4.若rs為空，則返回真值F；5.r:=MOVE-FIRST(rs)；6.PS-BACKTRACK(TRANSFORM(db,r));7.返回語句(4)db’回溯策略

－四皇后問題例綜合數(shù)據(jù)庫的內(nèi)容db設(shè)置為列表L，

L中元素為皇后在棋盤中的位置ij建立由4條規(guī)則構(gòu)成的規(guī)則庫，每條規(guī)則指示在第i行放置皇后(i=1,2,3,4)

每條規(guī)則都將產(chǎn)生4條規(guī)則例，相應(yīng)于在同一行的第j列放置皇后(j=1,2,3,4)R1:length(db)=0=>APPEND(db,(1j))R2:length(db)=1=>APPEND(db,(2j))R3:length(db)=2=>APPEND(db,(3j))R4:length(db)=3=>APPEND(db,(4j))設(shè)計啟發(fā)式函數(shù)D(r)–規(guī)則例r下最新一個皇后位置所在長對角線長度排序每個識別-動作循環(huán)的識別階段激活的4條規(guī)則例

2次回溯，目標(biāo)狀態(tài)db(12243143)四皇后問題棋盤布局的變遷過程四皇后問題搜索圖3.2.2控制策略－推理修補技術(shù)需求：克服時序回溯的缺點，免除回溯的需要有些問題求解任務(wù)不允許回溯或不需要回溯方法：基于從屬導(dǎo)向的回溯(圖)：.分析失敗的原因，直接確定導(dǎo)致失敗的推理分支點

(不是按時序簡單地回溯到上一推理分支點).依據(jù)記載的推理前提和結(jié)果間的從屬關(guān)系信息，僅撤銷那些與失敗相應(yīng)的結(jié)果

(不撤銷失敗點到失敗根源之間的所有推理結(jié)果)修補規(guī)則PP3.2.2控制策略－推理修補技術(shù)設(shè)置修補規(guī)則－在推理失敗的情況下激活這些規(guī)則，對推理的中間結(jié)果(綜合數(shù)據(jù)庫的內(nèi)容)作某些變換，進而使失敗的推理能繼續(xù)下去。例，對如下英語句子作文法分析：

Have

theStudentswhoMissedtheexam

takeittoday.“Have”－①助動詞、②主動詞

①名詞短語“thestudentwhomi