智能控制基礎：第二章 智能控制的知識工程基礎

第二章

智能控制的知識工程基礎

第二章智能控制的知識工程基礎

2.1

引言

2.2

知識的基本概念

2.3

知識的表示

2.4

知識的獲取

2.5知識的處理符號信息處理、啟發(fā)式程序設計、知識表示、自動推理、機器學習和決策智能控制研究需采用的相關技術：對實際環(huán)境或過程進行組織，即決策和規(guī)劃，實現(xiàn)廣義問題求解。智能控制的核心任務：2.1引言

2.2知識的基本概念2.2.1

什么是知識2.2.2

知識的分類人類智能活動是獲取和運用知識計算機要有智能就必須有知識知識必須要存儲到計算機

2.2.1什么是知識

知識是人們在長期生活、社會實踐、科學研究和實驗中積累起來的對客觀世界的認識和總結(jié)，然后將實踐中獲得的信息關聯(lián)在一起，也就構成了知識。

簡言之，知識是把有關信息關聯(lián)在一起所形成的信息結(jié)構。應用最多的關聯(lián)形式是“IF-THEN”形式，它反映了信息間的某種因果關系。知識、規(guī)則、數(shù)據(jù)、信息之間的關系

智能活動：是人類獲取知識并運用知識的過程。知識：是智能的基礎。人類大量的要使計算機具有智能的話，就必須使計算機具有獲取知識和運用知識的能力知識、規(guī)則、數(shù)據(jù)、信息之間的關系

規(guī)則：把關聯(lián)起來的知識稱為規(guī)則。事實或原子事實：把不與其他信息關聯(lián)的信息稱為事實或原子事實。

數(shù)據(jù)：描述客觀事物的屬性、數(shù)量、位置以及相互關系。是信息的載體和表示。它可以是數(shù)，也可以是字符串。信息：是數(shù)據(jù)在特定場合下的具體含義，或是數(shù)據(jù)的語義。知識、規(guī)則、數(shù)據(jù)、信息之間的關系同一個數(shù)據(jù)在不同的場合可能代表不同的信息同一個信息在不同的場合也可以用不同的數(shù)據(jù)表示

要使計算機具有智能，模擬人的智能活動，就必須使它有知識。而知識只有用適當?shù)哪Ｊ奖硎境鰜聿拍艽鎯Φ接嬎銠C中去。

知識的基本屬性有：真理性、相對性、相容性、不完全性、模糊性、可表達性、可存儲性、可傳遞性和可處理性。

2.2.2知識的分類共性知識（常識性知識）個性知識（領域性知識）

按知識的使用范圍分類按知識的功能分類按知識的確定性分類按知識結(jié)構及表現(xiàn)形式分類過程性知識事實性知識(描述性知識)控制性知識確定性知識不確定性知識邏輯型知識形象型知識數(shù)學、物理控制理論這是溫控裝置不精確真、假正處于升溫過程開大蒸氣閥人類經(jīng)驗樹2.3知識的表示

知識必須以適當?shù)男问奖硎境鰜聿疟阌谠谟嬎銠C中存儲、檢索、使用和修改等。

知識的表示

知識表示是一種計算機可接受的對人類智能行為的描述。它是一種符號模型的約定，將人類知識通過一個符號模型映射到計算機中。

知識表示法（知識表示模式/技術）狀態(tài)空間表示法一階謂詞邏輯表示法時序邏輯表示法產(chǎn)生式表示法語義網(wǎng)絡表示法Petri網(wǎng)絡表示法定性模型知識表示法可視知識模型表示法神經(jīng)網(wǎng)絡知識表示法不確定性（模糊）知識表示法…….框架表示法

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

狀態(tài)、操作和狀態(tài)空間的概念狀態(tài)空間圖示法

狀態(tài)、操作和狀態(tài)空間的概念

狀態(tài)：描述某些事物中各不同事物間的差異，而引入的一種最小變量的有序組合。狀態(tài)、操作和狀態(tài)空間的概念其中，是狀態(tài)變量，用于表示事物的某一特征，也可稱為特征量。如：臉像、指紋。

狀態(tài)、操作和狀態(tài)空間的概念操作：能夠引起狀態(tài)中某些分量發(fā)生變化，從而使一個狀態(tài)轉(zhuǎn)移為另一個狀態(tài)。

狀態(tài)、操作和狀態(tài)空間的概念狀態(tài)空間：描述全部可能狀態(tài)及其相互關系的三重序元<S,F,G>。

S是事物可能的初始狀態(tài)集合F是操作集合G是可能的目標狀態(tài)集合

狀態(tài)空間圖示法

用右向圖來表示狀態(tài)空間。

狀態(tài)空間圖示法

把狀態(tài)集合映射為結(jié)點集合。操作所引起的狀態(tài)轉(zhuǎn)移映射為標注該操作的有向邊。問題求解通過操作從初始結(jié)點到目標結(jié)點尋找一條有效的途徑。

2.3.2一階謂詞表示法

取值為真或假的句子稱為命題。（1）12>5;（2）3是12的約數(shù);（3）0.5是整數(shù);（4）X>5.（5）今天上課點名嗎？（6）把門關上（7）10000000是一個好大的數(shù)啊!疑問句、祈使句、感嘆句、開語句都不是命題。在命題演算中，對下述論斷無法判斷其正確性?！疤K格拉底三段論”：所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。

2.3.2一階謂詞表示法在謂詞演算中，命題可分為謂詞和個體兩部分。謂詞：用于刻劃個體的性質(zhì)、狀態(tài)或個體間的關系，用大寫字母表示。個體：表示某個獨立存在的事物或某個抽象的概念，用小寫字母表示。謂詞的一般形式是：其中P是謂詞，有n個個體，稱之為n元謂詞。例如：（1）李明是學生；（2）張亮比陳華高；（3）陳華坐在張亮與李明之間。

一階謂詞中的基本概念基本要素：常量、變量、函數(shù)、謂詞、聯(lián)接詞、量詞用謂詞邏輯表示狀態(tài)和操作。

例：關于積木世界的問題。

基本要素常量：具體的特定的個體變量：抽象的、泛指的個體函數(shù)：由其他事物所確定的事物聯(lián)接詞：聯(lián)接謂詞的邏輯符號量詞：分為全稱量詞和存在量詞

一階謂詞中的聯(lián)接詞

：否定詞（非）(非P)

：合取詞（與）(P與Q)

：析取詞（或）(P或Q)

：蘊含詞（條件）(如果P，則Q)

：雙蘊含詞（等價）(P當且僅當Q)PQP

QP

Q

PP→QTTTTFTFTTFTTTFTFFFFFFFTT實質(zhì)蘊含：P→Q=

P

Q如果拉登沒死，則股市天天大漲蘊含怪論：P

→（Q→P

）

P

→（P→Q

）如果P為真，則由任何命題Q可推出P如果P為假，則P可以蘊含任何Q質(zhì)疑：“任何命題蘊含真命題”證明“2+2=5蘊含雪是白的”直覺：有些命題彼此無關，不能相互蘊含，實質(zhì)蘊含沒有考慮這種情況挑戰(zhàn)羅素：已知：假命題2+2=5

證明：羅素與某主教是一個人羅素證明：假設2+2=5，又∵2+2=4,∴4=5

兩邊減1得：3=4，2=3，1=2∴羅素與某主教是一個人斷言得證

一階謂詞中的聯(lián)接詞由聯(lián)接詞構成的謂詞稱為復合謂詞公式，聯(lián)接詞的優(yōu)先級別是，，，，。

一階謂詞中的量詞

：全稱量詞，表示所有個體中的全體。：存在量詞，表示存在某一些。

x(P(x))表示對于所有個體，謂詞P(x)成立。

x(P(x))表示存在某些個體，謂詞P(x)成立。位于量詞后面的單個謂詞或復合謂詞稱為量詞的轄域，轄域內(nèi)與量詞同名的變元稱為約束變元，不受約束的稱為自由變元。用謂詞表示知識時，需要先定義謂詞，指出每個謂詞的含義，然后用聯(lián)接詞把有關的謂聯(lián)接起來，形成一個謂詞公式，表示一個完整的意義。

關于積木世界的問題BACACB初始狀態(tài)目標狀態(tài)

關于積木世界的問題定義謂詞：ON(x,y):表示x在y上CLEAR(x):表示x頂上是空的ONTABLE(x):表示x在桌子上HOLDING(x):表示手里拿著xHANDEMPTY:表示手是空的大寫字母表示謂詞

關于積木世界的問題以上謂詞中，x和y是個體，個體域為A，B和C。

關于積木世界的問題初始狀態(tài)QS：CLEAR(C)CLEAR(B)ONTABLE(A)ONTABLE(B)ON(C，A)HANDEMPTYBAC

關于積木世界的問題目標狀態(tài)Qg：ONTABLE(C)ON(B，C)ON(A，B)CLEAR(A)HANDEMPTYACB

關于積木世界的問題操作1：PICKUP(x):拿起xP.D:CLEAR(x),ONTABLE(x),HANDEMPTYA:HOLDING(x)

關于積木世界的問題操作2：PUTDOWN(x):放x在桌上P.D:HOLDING(x)A:CLEAR(x),ONTABLE(x),HANDEMPTY

關于積木世界的問題操作3：STACK(x,y):把x放在y上P.D:CLEAR(y),HOLDING(x)A:ON(x,y),CLEAR(x),HANDEMPTY

關于積木世界的問題操作4：UNSTACK(x,y):把x從y上拿開P.D:ON(x,y),CLEAR(x),HANDEMPTYA:CLEAR(y),HOLDING(x)

關于積木世界的問題操作序列：UNSTACK(C,A)PUTDOWN(C)PICKUP(B)STACK(B，C)PICKUP(A)STACK(A，B)BACACB例：設個體域是整數(shù)集合，請利用給出的謂詞將下列命題符號化。

N(e)：e是自然數(shù)

P(e)：e是素數(shù)

Q(e)：e是偶數(shù)

E(e1,e2)：e1=e2

L(e1,e2)：e1

e2

D(e1,e2)：e1

e2

a)凡素數(shù)均為自然數(shù)。

x(P(x)

N(x))b)沒有最大的素數(shù)。

x(P(x)

y(P(y)

L(y,x)))c)有些自然數(shù)不是素數(shù)。

x(N(x)

P(x))d)并非所有的素數(shù)都不是偶數(shù)。

x(P(x)

Q(x))

一階謂詞表示法

也稱一階謂詞邏輯表示法，用一階謂詞邏輯表示人們在問題求解時的邏輯演繹推理過程。例：關于海豚的定理證明形式

關于海豚的定理證明形式已知：

①無論什么動物，能閱讀即識字②海豚不識字③某些海豚有智能證明：某人或動物有智能卻不能閱讀

關于海豚的定理證明形式定義謂詞：R(x):動物x能閱讀L(x):動物x能識字D(x):x是海豚I(x):x有智能X是個體，域是每個人或動物

關于海豚的定理證明形式已知：F1:(

x)(R(x)→L(x))F2:(

x)(D(x)→L(x))F3:(x)(D(x)I(x))G:(

x)(I(x)R(x))(F1

F2F3)

→G是永真公式證明：將已知條件,求證結(jié)論的反化成子句集

①～R(x)∨L(x)

②～D(y)∨～L(y)

③D(a)

④I(a)

⑤～I(z)∨R(z)（結(jié)論的否定）

⑥～L(a)......2,3歸結(jié)｛a/y｝

⑦～R(a)......1,6歸結(jié)｛a/x｝

⑧R(a)......4,5歸結(jié)｛a/z｝

⑨□......7,8歸結(jié)

2.3.3時序邏輯表示法

將時間及其次序關系引入謂詞表達式之中，利用謂詞邏輯的概念和方法，便構成了時序邏輯知識模型。

例：Holds(u1,t1)Holds(u2,t2)After(t2,t1)After(t3,t2)Holds(y,t3)

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

又稱為規(guī)則或產(chǎn)生式規(guī)則。通常用于表示具有因果關系的知識?；拘问綖椋?/p>

IFPTHENQ或P

Q

（前提條件）

（結(jié)論或動作）產(chǎn)生式系統(tǒng)反映領域知識一種類似于緩沖器的數(shù)據(jù)結(jié)構，存放問題求解過程中的各種當前信息。如初始狀態(tài)、推理的中間結(jié)論、最終結(jié)論等匹配、沖突解決、操作

2.3.5語義網(wǎng)絡知識表示法

語義網(wǎng)絡（SematicNetwork)是通過概念及其語義關系來表達知識的一種網(wǎng)絡圖，由節(jié)點和連接節(jié)點的弧構成。其基礎是一種三元組結(jié)構（節(jié)點1、弧、節(jié)點2）。

（下層概念）（上層概念）是一種（?。ü?jié)點）（節(jié)點）狗狗獵

結(jié)構（節(jié)點1，弧，節(jié)點2）節(jié)點：表示各種事物、概念、情況、屬性、動作、狀態(tài)、地點等?；。罕硎靖鞣N語義聯(lián)系，指明所連接節(jié)點的某種關系。語義網(wǎng)絡除可表達事實外，還可表達規(guī)則。一條產(chǎn)生式規(guī)則R：IFATHENB，可表示成一個語義網(wǎng)絡規(guī)則如下：當多個三元組綜合在一起表達時，就可得到一個語義網(wǎng)絡。BAR語義網(wǎng)絡可以描述事物間復雜的語義關系圖書館語義網(wǎng)絡1）分類關系——事物間類屬關系張杰是一個讀者，師大附中是一個單位，圖書館是一種建筑2）聚集關系——下層概念是上層概念的一個方面或一個部分閱覽室是圖書館的一部分3）推論關系——一個概念可由另一個概念推出校園像公園推出風景美麗4）時間、位置關系校園在芙蓉山腳下5）相近關系校園像公園6）屬性關系閱覽室能開放，閱覽室有讀者

2.3.6框架知識表示法人工智能專家、minsky在1975年提出框架理論基本觀點：人腦中已存儲有大量事物的典型情境，也就是人們對這些事物的一種認識，這些典型情境是以一個稱作框架的基本知識結(jié)構存儲在記憶中的。當人面臨新的情境時，就從記憶中選擇一個合適的框架，這個框架是以前記憶的一個知識空框，而其具體內(nèi)容依新的情境而改變。通過對這個空框的細節(jié)加工、修改和補充，形成對新的事物情境的認識，而這種認識的新框架又可記憶于人腦中，以豐富人的知識。

舉例：組裝電腦，你需要了解硬件的細節(jié)，如：CPU的型號，價格，硬盤，大小，內(nèi)存，大小顯示器，型號，大小……

你的頭腦中很快建立了關于計算機硬件組成的基本框架?？蚣艿慕M成：一個框架由若干個“槽”的結(jié)構組成，每一個槽又可以根據(jù)實際情況擁有若干個側(cè)面，每個側(cè)面也可以再擁有若干個側(cè)面。在一個框架系統(tǒng)中，一般含有多個框架，為了區(qū)別這些不同的框架，需要分別給它們賦予不同名字，稱為框架名。同樣，對于不同的槽和側(cè)面也需要給予相應的槽名和側(cè)面名?？蚣艿囊话阈问?/p>

<框架名>槽名1：側(cè)面名11：值111，值112

側(cè)面名12：值121，值122

……

槽名2：側(cè)面名21：值211，值212

側(cè)面名22：值221，值222

……

槽名n：側(cè)面名n1：值n11，值n12

側(cè)面名n2：值n21，值n22框架表示知識實例：描述本科生情況的具體框架：

框架名：<本科生>

姓名：性別：年齡：院系：專業(yè)：課程：

2.3.6框架知識表示法框架網(wǎng)絡把多個相互關聯(lián)的框架連接起來組成框架網(wǎng)絡?？梢杂谜Z義網(wǎng)絡的形式表示，每個節(jié)點代表一個框架。注：

究竟采用哪一種表示模式，沒有統(tǒng)一的標準。在確定一個知識表示模式時，首先應考慮的是它能否充分地表示領域知識。

2.4知識的獲取

人工智能或知識工程系統(tǒng)中，通過非自動方式或自動方式實現(xiàn)計算機從知識源獲取知識的過程。知識源包括專家、書本、數(shù)據(jù)庫和人的經(jīng)驗等。

知識的獲取目的

通過計算機對人類專家的豐富知識高速度地加以收集、整理，并在此基礎上建立各種高性能的知識系統(tǒng)，以幫助人類解決那些單獨依靠人難以解決或解決起來太慢、效率太低的各種問題。2.4.1

非自動知識獲取2.4.2自動知識獲取

2.4.1非自動知識獲取

非自動知識獲取是指知識是通過知識工程師和知識編輯器傳授給知識庫的。知識編輯器是一類程序設計系統(tǒng)，包括語法檢查、一致性檢查、自動薄記、知識抽取等功能。知識庫領域?qū)＜抑R編輯器知識工程師非自動知識獲取2.4.2自動知識獲取

全自動知識獲取是讓計算機直接從環(huán)境中獲取全部信息。包括機器感知（主要是計算機視覺和聽覺）、機器識別和機器學習等。環(huán)境機器感知機器學習機器識別知識庫全自動知識獲取模型

機器感知

機器感知接受外部環(huán)境的信息（語言、文字、圖像等），經(jīng)過感知系統(tǒng)的初步處理后，可以得到一些簡單的事實性知識。

機器識別系統(tǒng)

信息的分類知識信息的特征信息的結(jié)構知識

機器學習系統(tǒng)（提供更高層次知識）

根據(jù)環(huán)境信息形成概念歸納推理文法推斷假設猜想科學發(fā)現(xiàn)

學習系統(tǒng)的基本模型

學習是系統(tǒng)積累經(jīng)驗以改善其性能的過程，是知識的獲取與改進，是事物規(guī)律的發(fā)現(xiàn)過程。也就是，學習是一個有特定目的的知識獲取過程。

學習系統(tǒng)的基本模型學習系統(tǒng)內(nèi)在行為：獲取知識、積累經(jīng)驗、發(fā)現(xiàn)規(guī)律學習系統(tǒng)外部表現(xiàn)：改進性能、適應環(huán)境、實現(xiàn)系統(tǒng)的自我完善

學習系統(tǒng)的基本模型

學習系統(tǒng)是指，一個系統(tǒng)能夠從某個過程或環(huán)境的未知特征中學到有關信息，并且能把學到的信息用于未來的估計、分類、決策或控制，以便改進系統(tǒng)的性能。

學習系統(tǒng)的基本模型環(huán)境學習環(huán)節(jié)工作環(huán)節(jié)知識庫系統(tǒng)的外界信息源。有關環(huán)境的信息數(shù)據(jù)存在數(shù)據(jù)庫中，它處于在線學習時是可變的，屬于短期記憶范疇。代表知識信息（學習成果），用于存儲或記憶系統(tǒng)通過學習所獲得的各種知識。分長期和中期記憶兩部分。學習系統(tǒng)的核心。是對環(huán)境信息進行搜索、控制和邏輯思維。通過比較、抽象、概括、綜合、推理等，以產(chǎn)生、修改與補充知識。是智能系統(tǒng)的知識產(chǎn)生器。用于處理系統(tǒng)面臨的現(xiàn)實問題，如組合調(diào)度。從工作環(huán)節(jié)到學習環(huán)節(jié)必須有反饋信息，以便學習環(huán)節(jié)決定是否進行再學習。

學習系統(tǒng)的分類

機械式學習系統(tǒng)類比學習系統(tǒng)示例學習系統(tǒng)發(fā)現(xiàn)式學習系統(tǒng)指導學習系統(tǒng)

機械式學習系統(tǒng)（RoteLearning)又稱記憶學習。是一種最簡單、最基本的學習方法，無推理過程，是從特殊到特殊的學習過程。通過從知識庫中檢索相應的知識，直接求解問題。

機械式學習系統(tǒng)輸入：輸出：存儲聯(lián)想對：

類比學習系統(tǒng)(AnalogyLearning)在兩個相似域之間進行類比。源域S：目標域T：

類比學習系統(tǒng)(AnalogyLearning)當出現(xiàn){s′,t′}，已經(jīng)發(fā)現(xiàn)s′具有特性P，則可類比地歸納出t′具有特性Q。

示例學習系統(tǒng)

（LearningfromExamples)是從許多示例中得出事物的特性或一般規(guī)律的一種學習方法。是從特殊到一般的學習過程。

示例學習系統(tǒng)

（LearningfromExamples)示例的質(zhì)量要求它能準確地反映實際問題的情況，因為它是學習的基礎，只有正確的示例才有可能得出正確的知識。

發(fā)現(xiàn)式學習系統(tǒng)

（DiscoveringLearning)又稱猜想-驗證式學習。首先對歷史經(jīng)驗進行分析總結(jié)，提出猜想，然后有意識地設計實驗以驗證猜想。包括歸納與演繹、綜合與分析、聯(lián)想與設計。在示例學習中，示例經(jīng)環(huán)境嚴格挑選，沒有干擾信息。發(fā)現(xiàn)式學習由環(huán)境提供的是未經(jīng)挑選的，信息是一種隨機多干擾信息。由學習環(huán)節(jié)對信息提純，以發(fā)現(xiàn)新概念。

應用謂詞，將下述推理符號化。每個學生或者聰明或者勤奮；所有勤奮的人都將有所作為；但并非所有學生都將有所作為。所以，一定有些學生是聰明的。

[解]令：個體域Ｉ是人的集合。

S(e):e是學生；A(e):e聰明；

B(e):e勤奮；C(e):e將有所作為。符號化為：

x(S(x)(A(x)B(x)))，x(B(x)C(x))，

x(S(x)C(x))，x(S(x)A(x))

2.5知識的處理運用知識的過程稱為推理過程。推理是指依據(jù)一定的規(guī)則從已有的事實推出結(jié)論的過程。其中的規(guī)則稱為控制策略。

知識的處理智能系統(tǒng)是以知識為基礎的系統(tǒng)，它根據(jù)已有的知識和事實去求解當前的問題。也叫基于知識的推理。推理由程序?qū)崿F(xiàn)，稱為推理機。

知識的處理推理是按某種策略從一個或幾個已知判斷推出另一個判斷的思維過程。

知識的處理推理所依據(jù)的判斷叫前提，包括知識庫中的領域知識及問題的初始證據(jù)。由前提推出的新判斷叫結(jié)論。推理存在一個置信度轉(zhuǎn)移的過程。2.5.1

推理的方式與分類2.5.2推理控制策略2.5.3

狀態(tài)空間的搜索策略

2.5.1推理的方式與分類

演繹推理歸納推理非單調(diào)推理

演繹推理（DeductionReasoning)前提與結(jié)論之間有蘊含關系的推理，或前提與結(jié)論之間有必然聯(lián)系的推理。即結(jié)論蘊含在已知的判斷之中，是一種由一般到個別的推理。

演繹推理（DeductionReasoning)

或例：已知：每個學術會的成員都是工人并且是專家，有些成員是青年人。求證：有的成員是青年專家。證明：定義謂詞：

F(x):x是學術會成員G(x):x是專家H(x):

x是工人R(x):x是青年人歸納推理（InductiveReasoning)指由個別事物或現(xiàn)象推出該類事物或現(xiàn)象一般性知識的過程。常用方法有枚舉法、類比法、統(tǒng)計法等。

非單調(diào)推理（Non-monotousReasoning)在信息或知識不完全的情況下，假設某些命題成立并進行推理。在推理過程中，如果發(fā)現(xiàn)原假設不正確，就撤銷原假設以及由此得出的結(jié)論，重新按新情況進行推理。非單調(diào)推理（Non-monotousReasoning)新事實或新知識的加入，不但沒有擴充可推出的命題，反面必須刪除一些原先推出的命題。常用的非單調(diào)推理為默認推理。默認推理：

α(x):mβ1(x),…mβm(x)w(x)

α(x):前提條件，β(x)缺省條件,w(x)是結(jié)論，m表示相容。當前提與缺省條件相容或不矛盾時，結(jié)論可信。例：已知x是一只鳥，正常情況下推斷或相信x能飛，用默認邏輯表述：鳥(x):m會飛(x)會飛(x)

根據(jù)常規(guī)，鳥t會飛，如果得知鳥t受傷或是只鴕鳥，則推斷是不可信的。得出一個新的理論：理論＝規(guī)則＋事實鳥(x):m會飛(x)會飛(x)，鴕鳥(x)→~會飛(x);

導致原有邏輯結(jié)論發(fā)生改變。

2.5.2推理控制策略

正向推理（數(shù)據(jù)驅(qū)動推理）

反向推理（目標驅(qū)動推理）

正反向混合推理解決知識的選擇與應用的順序問題

正向推理正向推理是事實驅(qū)動。過程是從問題所有可能的初始證據(jù)（事實）開始，正向使用規(guī)則，通過匹配每條知識的前提，識別出所有可用的知識而形成一個可用知識集（沖突集），然后以某種沖突求解方式在沖突集中選取一條知識。這條知識的使用又會得出新的事實。新的事實和原有事實又引起知識庫中新的知識匹配，從而繼續(xù)問題的求解，直至達到某一狀態(tài)。若問題的結(jié)論已包含在所產(chǎn)生的事實中，則說明問題有解，否則無解或已給出所有解。例：已知：初始事實是有毛發(fā)、會吃肉、有斑點，現(xiàn)在要求專家系統(tǒng)判斷這是什么動物？IF該動物用乳汁哺育幼子=trueTHEN哺乳動物=trueIF該動物有毛發(fā)=trueTHEN哺乳動物=trueIF該動物會吃肉=trueTHEN食肉動物=trueIF哺乳動物=trueAND該動物是反芻動物=trueTHEN蹄類動物=trueIF哺乳動物=trueAND食肉動物=trueAND有暗斑點=trueTHEN該動物是金錢豹=true…………

根據(jù)上面事實，匹配成功了三條規(guī)則：規(guī)則2被激活，增加新事實：哺乳動物規(guī)則3被激活，增加新事實：食肉動物規(guī)則５被激活，增加新事實：金錢豹得出結(jié)論：該動物是金錢豹

反向推理反向推理是目標驅(qū)動。過程是首先從提出目標假設開始，然后從知識庫中找出其結(jié)論部分能與假設相匹配的所有知識，得到一個可用的知識集。若可用知識集為空集，則推理失敗。若可用知識集非空，則從可用知識集中選取一條驗證前提部分。若驗證成功，就從目標或假設集中找出該知識的結(jié)論，且由該知識計算出可信度放入上下文。若該知識中的某一前提被用戶或上下文否定，則該知識的結(jié)論部分不能被這條知識所驗證，可以返回到可用知識集中重新選擇一條可用知識。當所有知識都不能驗證成功時，該結(jié)論應從假設目標中刪除，直到上下文中含有原提出的目標或假設。這說明問題有解，當所有目標都測試過，而上下文中找不到原提出的目標或假設時，則說明該問題無解。證據(jù)節(jié)點：不能作為其他規(guī)則結(jié)論的假設。

正反向混合推理

先根據(jù)數(shù)據(jù)庫中的原始數(shù)據(jù)，通過正向推理幫助系統(tǒng)提出假設，再運用反向推理，進一步尋求支持假設的證據(jù)，如此反復，直到得出結(jié)論或不再有新的事實加到數(shù)據(jù)庫為止。是壓縮空間，提高搜索效率的有效途徑。

2.5.3狀態(tài)空間的搜索策略對于結(jié)構不良或非結(jié)構化的問題，不存在成熟的求解算法可供利用，只能一步步地摸索前進。這種不斷搜尋前進方向求解問題的過程稱為搜索

狀態(tài)空間的搜索策略狀態(tài)空間隱式圖的基本搜索：盲目搜索（寬度/深度優(yōu)先搜索策略）啟發(fā)式搜索

狀態(tài)空間隱式圖搜索在不斷的搜索過程中，產(chǎn)生新的狀態(tài)空間，逐步地生成問題的狀態(tài)空間圖，即采用隱式存儲。這種狀態(tài)空間的生成過程就稱為隱式圖搜索。

狀態(tài)空間隱式圖搜索首先把問題的初始狀態(tài)作為當前狀態(tài)，選擇適用的算符對其進行操作，生成一組子狀態(tài)（子節(jié)點），然后檢查目標狀態(tài)是否在其中出現(xiàn)，若出現(xiàn)，則搜索成功，找到了問題的解，若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個狀態(tài)作為當前狀態(tài)，重復上述過程，直到目標狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符為止?；舅枷耄?/p>

狀態(tài)空間隱式圖搜索過程OPEN：存放等待擴展的結(jié)點的表

CLOSED：存放已擴展的結(jié)點的表

(標注部分已生成的狀態(tài)空間，可得到解徑)

狀態(tài)空間隱式圖搜索過程

初始狀態(tài)結(jié)點S0放入OPEN表中；從OPEN表中取出第一個結(jié)點N放到CLOSED表中；

狀態(tài)空間隱式圖搜索過程

(3)若N可擴展，則擴展結(jié)點N產(chǎn)生其所有子結(jié)點Ni，將Ni放入OPEN表中，并按控制性知識對OPEN表中所有結(jié)點排序，把最有希望在解徑上的結(jié)點放在第一位置上；

狀態(tài)空間隱式圖搜索過程(4)測試剛生成的結(jié)點Ni中是否有目標結(jié)點Sg，若Sg已生成，則搜索成功；(5)若Sg尚未生成，則返回到(2)，搜索進入循環(huán)過程，直到OPEN表為空，搜索失敗。

狀態(tài)空間隱式圖搜索過程擴展節(jié)點N即是對操作集合F中的每個操作的前提部分與結(jié)點N的狀態(tài)描述進行匹配，并執(zhí)行所有被N滿足的操作fi，定義獲得的由新狀態(tài)描述所對應的結(jié)點分別為N的子結(jié)點。例：用狀態(tài)空間搜索法求解走迷宮問題。設用Si表示各個格子的狀態(tài)，把入口、出口、每一個格子都作為節(jié)點。設向上、向下、向左、向右的算符分別為U、D、L、R，應用狀態(tài)空間搜索，得到搜索圖。從入口到出口有很多條通道，每條通道都是問題的一個解，其中最短的路徑長度是5，由5個算符組成：

S0S4S5S8S9Sg

盲目搜索只是按預定的控制策略進行搜索，沒有考慮到問題的特性，具有盲目性，效率較低，一般只適于求解比較簡單的問題。

寬度優(yōu)先搜索（廣度優(yōu)先搜索）從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展，并考察它是否為目標節(jié)點，在對第n層的節(jié)點沒有全部擴展并考察完以前，不對第n+1層的節(jié)點進行擴展。

寬度優(yōu)先搜索（廣度優(yōu)先搜索）節(jié)點順序：S0，S1，S2，S3，…每次新生成的結(jié)點從尾部放入表，而已有結(jié)點從頭部取出，即先進先出，后進后出。例：用寬度優(yōu)先搜索策略求解重排九宮問題。在3*3的方格棋盤上放置1、2、3、4、5、6、7、8共8個棋子，初始狀態(tài)為s0，目標狀態(tài)為sg。

規(guī)則：（1）在移動時，只允許把位于空格上、下、左、右的鄰近棋子移入空格（2）棋子移入空格的次序是由空格左邊開始，沿順時針方向移動，即每一層都按空格左移、上移、右移、下移的順序進行（3）不允許斜方向移動，不允許返回

解的路徑是：1（s0

）381626（sg

）

深度優(yōu)先搜索從初始節(jié)點S0開始，在其子節(jié)點中選擇一個節(jié)點進行考察，若不是目標節(jié)點，則在該節(jié)點的子節(jié)點中選擇一個節(jié)點進行考察，一直如此向下搜索。

深度優(yōu)先搜索（有界深度）OPEN表中，后生成的節(jié)點優(yōu)先擴展，即后進先出。為了克服陷入無窮分支死循環(huán)的問題，提出了有界深度優(yōu)先搜索方法。例：用深度優(yōu)先搜索策略求解重排九宮問題。在3*3的方格棋盤上放置1、2、3、4、5、6、7