人工智能原理與方法

魏長華DepartmentofComputerScienceCCNUEmail:Chwei@

人工智能原理與方法

ArtificialIntelligence2023/1/121WeiChanghua內容第一章緒論

●什么是人工智能？

●人工智能研究的目標

●人工智能研究途徑

●人工智能研究的內容

人工智能研究中的學派

人工智能研究的內容

●人工智能研究領域

2023/1/122WeiChanghua內容第二章人工智能的數(shù)學基礎

●命題邏輯和謂詞邏輯

●概率論

●模糊理論

2023/1/123WeiChanghua內容第三章知識表示

●

知識與知識表示

●對知識表示的要求

●知識表示方法

一階謂詞邏輯

產生式規(guī)則

語義網絡

框架

狀態(tài)空間

腳本

Petri網

2023/1/124WeiChanghua內容第四章基本的問題求解方法●基本概念

●狀態(tài)空間搜索

●與/或樹搜索

●博弈樹的啟發(fā)式搜索

2023/1/125WeiChanghua內容第五章基本推理方法●推理的基本概念

●推理方式和分類

●推理控制策略

●歸結反演

●基于規(guī)則的演繹系統(tǒng)

2023/1/126WeiChanghua內容第六章不確定性推理●不確定性推理的基本概念

●確定因子法

●主觀Bayes方法

●證據(jù)理論

●可能性理論

2023/1/127WeiChanghua內容第七章專家系統(tǒng)

●專家系統(tǒng)的基本概念

●專家系統(tǒng)分類

●專家系統(tǒng)的一般結構

●專家系統(tǒng)的建造與評價

●專家系統(tǒng)開發(fā)工具

●專家系統(tǒng)開發(fā)環(huán)境●新一代專家系統(tǒng)的研究

●幾個著名的專家系統(tǒng)

2023/1/128WeiChanghua內容第八章機器學習

●機器學習的概念

●學習系統(tǒng)模型

●機器學習分類

●機器學習研究歷史

●機器學習的研究目標

●幾個著名的學習系統(tǒng)

2023/1/129WeiChanghua第一章緒論

1

什么是人工智能？人工智能是研究知識的一門科學，即如何表示知識，如何獲取知識和如何利用知識的科學。2023/1/1210WeiChanghua第一章緒論

2

人工智能研究的目標近期目標：在近期，人工智能研究的任務是利用馮.偌依曼型計算機模擬人類智力行為，研制智能程序；遠期目標：遠期是研制全新的計算機，即智能計算機。2023/1/1211WeiChanghua第一章緒論3

人工智能研究途徑人工智能研究可以有三種途徑進行：符號主義：（思維理論）符號主義認為人類認知的基本元素是符號，認知的過程就是符號處理的過程。（一階謂詞邏輯）連接主義：（閾值理論）連接主義認為人類認知的基本元素是神經元本身。人類的認知過程就是大量的神經元的整體活動。（研究方法：人工神經網絡）行為主義：（進化理論）由美國麻省理工學院的R.A.Brook教授提出的。該理論認為人的本質能力是在動態(tài)環(huán)境中的行走能力、對外界事物的感知能力、維持生命和繁衍生息的能力，正是這些能力對智能的發(fā)展提供了基礎，因此智能是某種復雜系統(tǒng)所浮現(xiàn)的性質。2023/1/1212WeiChanghua第一章緒論

4人工智能研究的內容

（1）

人工智能研究中的學派邏輯學派：以麥卡錫和尼爾遜為代表的研究基于邏輯的知識表示和推理機制。認知學派：以紐厄爾和西蒙為代表的研究對人類認知功能的模擬，試圖找出產生智能行為的原理。知識工程學派：以費根鮑姆為代表的研究知識在人類智能中的作用和地位，提出了知識工程概念。連接學派：以J.L.McClelland和J.D.Rumelhart為代表的研究神經網絡。分布式學派：以C.Hewitt為代表的研究智能系統(tǒng)中的知識分布行為。進化學派：R.A.Brook為代表。

2023/1/1213WeiChanghua第一章緒論（2）人工智能研究的內容●機器感知：所謂的機器感知就是使機器具有類似于人的感知能力，其中以機器視覺與機器聽覺為主。

●

機器思維：機器思維是指對通過感知得到的外部信息及機器內部的各種工作信息進行有目標的處理。

●

機器學習：研究使機器具有獲取新知識、學習新技巧，并在實踐中不斷完善、改進的能力。

●

機器行為：與人的行為相對應，機器行為主要是指計算機的表達能力，即“說”、“寫”、“畫”等。2023/1/1214WeiChanghua第一章緒論5人工智能研究領域

●模式識別（PatternRecognition）

●自然語言理解（NaturallangrageUnderstanding）

●專家系統(tǒng)（ExpertSystem）

●機器學習（MachineLearning）

●自動定理證明（AutomaticTheoremProving）●自動程序設計（AutomaticProgramming）

●機器人學（Robots）

●博弈（Game）

●智能決策支持系統(tǒng)（IntelligentDecisionSupportSystem）

●人工神經網絡（Artificialnaturalnetworks）

2023/1/1215WeiChanghua第一章緒論思考題1、什么是人工智能？2、人工智能研究的對象是什么？3、人工智能研究的途徑有那些？4、人工智能研究的領域有那些？5、人工智能研究的近期目的和遠期目的是什么？6、簡述圖靈試驗。

2023/1/1216WeiChanghua第二章人工智能的數(shù)學基礎

1命題邏輯和謂詞邏輯命題：命題是具有真假意義的語句。

謂詞：一個謂詞由謂詞名和個體兩部分組成。

謂詞公式：連接詞、量詞。合適公式：原子是合適公式；若A是合適公式，則A也是合適公式；若A、B都是合適公式，則AB，AB，AB，也都是合適公式；若A是合適公式則，、也是合適公式。謂詞公式的永真性、可滿足性和不可滿足性

2023/1/1217WeiChanghua第二章人工智能的數(shù)學基礎2概率論

條件概率：設A，B是兩個事件，，則稱為在A事件已經發(fā)生的條件下B事件發(fā)生的概率。

全概率公式和Bayes公式的條件概率：設事件滿足：⑴兩兩互不相容，即當時，有

⑵

⑶則對任何事件有下式成立：

為全概率公式，它提供了一種計算的方法。

2023/1/1218WeiChanghua第二章人工智能的數(shù)學基礎Bayes公式：稱公式

為Bayes公式。

2023/1/1219WeiChanghua第二章人工智能的數(shù)學基礎3模糊理論

模糊集：設是論域，是把任意映射為[0，1]上某個值的函數(shù)，即，則稱由所構成的集合A,稱為U上的一個模糊集。

隸屬函數(shù)：稱為定義在U上的一個隸屬函數(shù)。

語言變量：用自然語言表示變量的值和描述變量之間的內在聯(lián)系的一種變量。比如，年齡就是個語言變量，它可以取值為年輕、很年輕、不很年輕、老、很老、不很老等。

語言真值

模糊推理

2023/1/1220WeiChanghua第二章人工智能的數(shù)學基礎思考題1、什么是合適公式？2、試寫出Bayes公式。3、什么是語言變量？4、試論述信息（知識）不確定性及其處理的途徑2023/1/1221WeiChanghua第三章知識表示1

知識與知識表示知識是人類認識自然界的精神產物，是人類進行智能活動的基礎。知識可以分為五類：●描述性知識●判斷性知識

●過程性知識

●對象級知識，或稱為領域相關的知識

●元級知識

2023/1/1222WeiChanghua2對知識表示的要求

●表示能力

●可理解性

●可訪問性

●可擴展性

3知識表示方法

●一階謂詞邏輯：它是一種描述性的表示方法，它的推理機制是歸結原理。主要應用于定理證明。

●語義網絡：是由Quillian等人于1968年提出的，它在知識表示中可以表示對象、概念及其相互間的關系。它廣泛用于基于知識的系統(tǒng)。

●

產生式規(guī)則：產生式系統(tǒng)把知識表示成“模式→動作”對，表示方式自然、簡潔。它的推理機制以演繹為基礎。它是專家系統(tǒng)的知識表示的主要方法。

2023/1/1223WeiChanghua

●框架：框架理論是Minsky于1974年提出的，它將知識表示成高度模塊的結構，它是把關于一個概念或對象的所有信息和知識都存儲在一起的數(shù)據(jù)結構?？蚣艿膶哟谓Y構可以表示對象之間的相互關系，用框架表示知識的系統(tǒng)稱為框架的系統(tǒng)。

●狀態(tài)空間：狀態(tài)空間表示法把求解問題表示成問題狀態(tài)、操作、約束、初始狀態(tài)和目標狀態(tài)。狀態(tài)空間是所有狀態(tài)的集合。

●腳本：腳本也稱為劇本。它是用來描述固定事件序列，它的結構類似于框架。劇本更強調事件間的因果關系。

●Petri網：Petri網是由德國計算機科學家Petri提出的，由于它很好的模擬異步操作，所以在并行處理和分布式計算機領域中應用很多。

2023/1/1224WeiChanghua

⑴

一階謂詞邏輯表示法：謂詞邏輯適合于表示事物的狀態(tài)、屬性、概念等事物之間的知識，也可以用來表示事物之間的因果關系，謂詞公式一般用合適公式表示。

●謂詞的選取

●量詞的選取（作用的范圍）

●從自然語言翻譯成謂詞公式不能丟失信息●易于理解●謂詞公式表示法的特點：自然性、精確性、嚴密性、容易實現(xiàn)。

2023/1/1225WeiChanghua產生式表示法：產生式表示具有因果關系的知識，其基本形式是

或者其中P是產生式前提，Q是一組結論或操作。

●產生式組成：規(guī)則庫，綜合數(shù)據(jù)庫，控制系統(tǒng)。●

產生式系統(tǒng)分類：可交換的產生式系統(tǒng)，可分解的產生式系統(tǒng)，可恢復的產生式系統(tǒng)●產生式表示法的特點：自然性，有效性，模塊性，清晰性，效率不高，不能表示具有結構性的知識

2023/1/1226WeiChanghua框架：框架是一種描述所論對象（一個事物、一個事件、一個概念）屬性的數(shù)據(jù)結構?！窨蚣艿慕Y構：一個框架是由若干槽組成，每個槽又可以有若干個側面。槽用來描述所論對象的某方面的屬性，側面用來描述相應屬性的一個方面。槽和側面所具有的屬性值分別稱為槽值和側面值。

●框架網絡：框架中的槽值或側面值可以是另一個框架的名字，這就在框架之間建立了聯(lián)系，構成了框架網絡。通過框架網絡可以找到另一個框架。

●繼承性是框架表示法的一個重要特征。它不僅可以在兩層框架之間實現(xiàn)繼承關系，而且可以通過兩兩的繼承關系，從最底層追溯到最高層，使最高層的信息逐層向底層傳遞。

●

框架中槽的設置與組織：

2023/1/1227WeiChanghua充分表達事物個有關方面的屬性

充分表達相關事物間的各種關系

ISA槽

AKO槽

Subclass槽

Instance槽

Partof槽

Infer槽

Possible-Reason槽

●有利于進行框架的推理2023/1/1228WeiChanghua框架表示法的特點

▼結構性

▼繼承性▼自然性

語義網絡表示法：語義網絡是通過概念及其語義關系表達知識的一種網絡圖。最簡單的語義網絡是如下的三元組：（節(jié)點1，弧，節(jié)點2）

●

知識的語義網絡表示

●

用語義網絡表示有關事實間的關系：分類關系；聚集關系；推論關系；時間、位置關系；多元關系

●

用語義網絡表示比較復雜的知識：把一個復雜的知識命題劃分為若干個子命題，每個子命題用一個較簡單的語義網絡表示，稱為子空間，多個子空間構成一個大空間。2023/1/1229WeiChanghua

●

常用的語義聯(lián)系

◆

A-Member-of

◆

Composed-of

◆

Have

◆

Before,After,At

◆

Located-on(-at,-under,-inside,-outside)等

◆

Similar-to,Near-to

●

語義網絡系統(tǒng)中求解問題的基本過程

◆

用語義網絡表示知識的問題求解系統(tǒng)稱為語義網絡系統(tǒng)。

◆

系統(tǒng)由語義網絡構成的知識庫；問題求解的解釋程序（語義網絡推理機）組成。

◆

問題求解一般是通過匹配實現(xiàn)的。2023/1/1230WeiChanghua

●

語義網絡表示法的特點

◆

結構性

◆

聯(lián)想性

◆

自然性2023/1/1231WeiChanghua

●

腳本表示法：腳本的知識表示方法是R.C.Schank

根據(jù)他的概念依賴理論提出的一種知識表示方法。它與框架類似，由一組槽組成，用來表示特定領域內一些事件的發(fā)生序列。

●

概念依賴理論：把人類生活中的各類故事情節(jié)的基本概念抽取出來，構成一組原子概念，確定這些原子概念之間的相互依賴關系，然后把所有故事情節(jié)都用這組原子概念及其依賴關系表示出來。

●

腳本一般由以下幾部分組成：進入條件；角色；道具；場景；結局。2023/1/1232WeiChanghua

●過程表示法：過程性表示方法著重于對知識的利用，它把問題有關的知識以及如何應用這些知識求解問題的控制策略都表述為一個或多個求解問題的過程。每一個過程是一個程序，用于完成對一個具體事件或情況的處理。

●

用過程規(guī)則表示過程

●

過程規(guī)則的一般結構：

◆

激發(fā)條件

◆

演繹操作

◆

狀態(tài)轉換

◆

返回

●

過程表示法的特點：效率較高；控制系統(tǒng)容易設計2023/1/1233WeiChanghua

●

Petri網表示法：對于不同的應用Petri網的構成及構成元素的意義均不相同，但有三種元素是基本的：位置、轉換、標記。

●

Petri網的特點

◆

便于描述系統(tǒng)狀態(tài)的變化

◆

便于對系統(tǒng)特點進行分析

◆

可以在不同層次上變換描述，而不必注意細節(jié)幾相應的物理表示。

●面向對象表示法：對象、類、封裝、繼承是面向對象技術的基本概念。

●

在面向對象方法中，類、子類、具體對象構成了一個層次結構，而且子類可以繼承父類的數(shù)據(jù)和操作。這種層次結構及繼承機制直接支持了分類知識的表示。2023/1/1234WeiChanghua第三章知識表示思考題1知識可以分為哪五類？2

知識表示主要有那些方法？3

用一階謂詞邏輯表示下列的句子（1）一個充分大的偶數(shù)（even）可以表示為兩個素數(shù)（prime）之和。（2）對于任意集合，存在有一個集合，使得集合的基大于集合的基。（3）Acomputersystemisintelligentifitcanperformataskwhich,ifperformedbyahuman,requiresintelligence.

（4）并非所有的有理數(shù)（rationalnumber）都是整數(shù)。（5）計算機系2001級的男生（manstudent）除了看電影的人外，其余的都去聽學術報告（academicreport）了。2023/1/1235WeiChanghua

3

用語義網絡表示下列句子（1）樹和草都是植物；（2）樹和草都是有根有葉的；（3）水草是草，且長在水中；（4）果樹是樹，且會結果；蘋果樹是果樹中的一種，它結蘋果。（5）典型的哺乳動物有毛發(fā)。（6）狗是哺乳動物，且吃肉。4

一個求職框架系統(tǒng)包含以下框架：(Frame求職類-A(Frame經理(Isa求職類)

(Isa招聘類)(學位Value：碩士以上)）(年齡Value：Always30以下)(Frame李明(學位Value：Always學士以上))(Isa求職類-A)(Frame銷售經理(年齡Value：40歲)(Isa經理)(公關能力Value：高)）(公關能力Value：高)）請問李明有資格申請銷售經理的職位嗎？為什么？2023/1/1236WeiChanghua

5

試用框架結構表示一個大學的人事組織結構。6

產生式系統(tǒng)由那些部分組成？它們的作用是什么？7

為什么說框架系統(tǒng)和語義網絡都是結構化的知識表示方法？兩者的共同和不同之處是什么？8

有3個積木塊（A、B、C）放在桌子上，且可以疊放在一起，要求在任意初始狀態(tài)，按自上而下A、B、C的順序迭放這3個積木塊。搬動積木塊應遵循以下約束：（1）

每次只能搬一塊（2）

只有頂空的積木塊才能搬動

請為機器人搬動積木塊設計一個產生式系統(tǒng)，包括綜合數(shù)據(jù)庫、規(guī)則庫和沖突消解算法。2023/1/1237WeiChanghua第四章基本的問題求解方法

1基本概念⑴什么是搜索人工智能要解決的問題大多數(shù)是結構不良或者非結構的問題，對這樣的問題一般不存在成熟的求解算法，而只能利用已有的知識一步步地摸索著前進。在這個過程中，存在著如何尋找一條推理路線，使得付出的代價盡可能地少，而問題又能夠得到解決。我們稱尋找這樣路線的過程為搜索。搜索分為盲目搜索和啟發(fā)式搜索：盲目搜索是按預定的控制策略進行，在搜索的過程中所獲得的信息不用來改進控制策略的一種搜索。啟發(fā)式搜索是在搜索中加入了與問題有關的啟發(fā)式信息，用來指導搜索朝著最有希望的方向前進，加速問題的求解過程，并找到最優(yōu)解。2023/1/1238WeiChanghua

⑵狀態(tài)空間表示法：狀態(tài)空間表示法是用“狀態(tài)”和“算符”來表示問題的一種方法。

●

狀態(tài)：狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結構。

●

算符：引起狀態(tài)的某些分量變化，從而使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。

●狀態(tài)空間：問題的全部狀態(tài)和一切算符所構成的集合成為狀態(tài)空間。例如二階梵塔問題。解：設立柱1、2和3以及兩個圓盤A和B

。用Sk=(Sk0,Sk1)表示問題狀態(tài)，Sk0表示圓盤A所在的立柱，Sk1表示圓盤B所在的立柱，全部可能的狀態(tài)共有九種：

S0=(1，1)，S1=(1，2)，S2=(1，3)S3=(2，1)，S4=(2，2)，S5=(2，3)S6=(3，1)，S7=(3，2)，S8=(3，3)問題的初始狀態(tài)集合是S={S0}，目標狀態(tài)集合是G={S4，S8}。2023/1/1239WeiChanghuaS0=（1，1）S1=（1，2）S2=（1，3）S3=（2，1）S4=（2，2）S5=（2，3）S6=（3，1）S7=（3，2）S8=（3，3）二階梵塔問題狀態(tài)表示2023/1/1240WeiChanghua

⑶與/或樹表示法：對于一個復雜的問題，可以通過“分解”和“等價變換”兩種手段相結合使用，得到一個圖，這個圖就是與/或圖。

●

等價變換：是一種同構或同態(tài)的變換。

●

本原問題：不能再分解或變換，而且直接可以求解的子問題，稱為本原問題。

●

終端節(jié)點與終止節(jié)點：在一棵與/或樹中，沒有子節(jié)點的節(jié)點稱為終端節(jié)點；本原問題所對應的節(jié)點稱為終止節(jié)點。

●

可解節(jié)點：在與/或樹中，滿足下列條件之一者就稱為可解節(jié)點：◆

它是一個終止節(jié)點◆

它是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點◆

它是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點

●

不可解節(jié)點：關于可解節(jié)點的三個條件全部不滿足的節(jié)點稱為不可解節(jié)點。

●

解樹：由可解節(jié)點構成，且由這些可解節(jié)點可推出初始節(jié)點（它對應于原始問題）為可解節(jié)點的子樹稱為解樹。

2023/1/1241WeiChanghua2狀態(tài)空間搜索

⑴狀態(tài)空間搜索的一般過程

●

OPEN表和CLOSED表：OPEN表是用于存放剛生成的節(jié)點；CLOSED表用于存放將要擴展的節(jié)點。

●

搜索的一般過程

⑵廣度優(yōu)先搜索：從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展并考查它是否為目標節(jié)點。在第n層的節(jié)點沒有全部擴展并考查之前，不對第n+1層節(jié)點進行擴展。OPEN表中的節(jié)點總是按進入的先后順序排列，先進入的節(jié)點排在前面，后進入的節(jié)點在后。

⑶深度優(yōu)先搜索：從初始節(jié)點S0開始，在其子節(jié)點中選擇一個子節(jié)點進行考查，若不是目標節(jié)點，則再在該子節(jié)點中選擇一個子節(jié)點進行考查，一直如此向下搜索。當?shù)竭_某個子節(jié)點，且該子節(jié)點既不是目標節(jié)點又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。與廣度優(yōu)先搜索不同，深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入OPEN表的首部。2023/1/1242WeiChanghua

⑷有界的深度優(yōu)先：對深度優(yōu)先搜索引入搜索深度的界限，當搜索深度達到了深度界限，而尚未出現(xiàn)目標節(jié)點，就換一個分支進行搜索。

⑸代價樹的廣度優(yōu)先搜索：與/或樹中，邊上有代價（或費用）的樹稱為代價樹。代價樹的廣度優(yōu)先搜索的基本思想是每次從OPEN表中選擇節(jié)點往CLOSED表中傳送時，總是選擇其代價最小的節(jié)點。

⑹代價樹的深度優(yōu)先搜索：基本思想是從剛擴展的子節(jié)點中選擇一個代價最小的節(jié)點送入CLOSED表進行考查。2023/1/1243WeiChanghua⑺啟發(fā)式搜索：啟發(fā)式搜索是利用問題本身的某些啟發(fā)信息，以制導搜索朝著最有希望的方向前進。

●

估價函數(shù)：用于估價節(jié)點重要性的函數(shù)稱為估價函數(shù)。它的一般形式為

●

局部擇優(yōu)搜索：當一個節(jié)點被擴展后，按f(x)對每個子節(jié)點計算估價值，并選擇最小者作為下一個要考查的節(jié)點。由于它每次都只是在子節(jié)點的范圍中選擇要考查的子節(jié)點，所以稱為局部擇優(yōu)搜索。

●

全局擇優(yōu)搜索：每次都是從OPEN表的全體節(jié)點中選擇一個估價值最小的節(jié)點進行擴展。2023/1/1244WeiChanghua

●

算法：把OPEN表中的節(jié)點按估價函數(shù)的值從小到大進行排序；g(x)是對g*(x)的估計，g(x)>0；h(x)是h*(x)的下界，即對所有x的均有：。其中g*(x)是從初始節(jié)點S0到節(jié)點x的最小代價；g*(x)是從x節(jié)點到目標節(jié)點的最小代價，若多個目標節(jié)點，則為其中的一個。2023/1/1245WeiChanghua3與/或樹搜索⑴與/或樹搜索的一般過程⑵與/或樹搜索的廣度優(yōu)先搜索⑶與/或樹搜索的深度優(yōu)先搜索⑷與/或樹搜索的有序搜索2023/1/1246WeiChanghua4博弈樹的啟發(fā)式搜索

⑴博弈樹的概念：博弈樹是與/或樹的一個特例；博弈的初始格局是初始節(jié)點；在博弈樹中與節(jié)點和或節(jié)點總是逐層交替出現(xiàn)的；所有能使自己一方獲勝的終局都是本原問題，相應的節(jié)點是可解節(jié)點。所有使對方獲勝的終局都是不可解節(jié)點。

⑵極大極小法⑶-剪枝技術

●值：對于一個或節(jié)點來說，取當前子節(jié)點中的最大倒推值作為它倒推值的下界，稱此值為值。

●值：對于一個與節(jié)點來說，取當前子節(jié)點中的最小倒推值作為它倒推值的上界，稱此值為值。

2023/1/1247WeiChanghua

●-剪枝技術：任何或節(jié)點x的值如果不能降低其父輩節(jié)點的值，則對節(jié)點x以下的分支可停止搜索，并使的倒推值為，這種剪枝稱為剪枝；任何“與”節(jié)點x的值如果不能升高其父輩節(jié)點的值，則對節(jié)點x以下的分支可停止搜索，并使的倒推值為，這種剪枝稱為剪枝。2023/1/1248WeiChanghua第四章基本的問題求解方法思考題1

什么是狀態(tài)和狀態(tài)空間？2

理解OPEN表和CLOSE表的作用。3

什么是盲目搜索？什么是啟發(fā)式搜索？4

寬度優(yōu)先與深度優(yōu)先的區(qū)別是什么？5

敘述可解節(jié)點和不可解節(jié)點的定義。6

在博弈樹中，-剪枝技術是如何進行的？7

試敘述搜索的估價函數(shù)的含義。8

試敘述A*算法的總體思路。9

有一農夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。假設船太小，農夫每次只能帶一樣東西過河，考慮到安全，無農夫看管時，狐貍和小羊不能在一起，小羊和那籃菜也不能在一起。請為該問題的解決設計狀態(tài)空間，并畫出狀態(tài)空間圖。10

應用啟發(fā)式搜索算法A解決八數(shù)碼問題。2023/1/1249WeiChanghua第五章基本推理方法1推理的基本概念推理通常是指從已知的事實出發(fā)，通過運用已掌握的知識，找出其中蘊藏的事實，或歸納出新的事實，這一過程就稱為推理。推理包括兩種判斷：一種是已知的判斷，它包括已掌握的求解問題有關的知識和關于問題的已知事實；另一種是由已知判斷推出新的判斷，即推理的結論。2推理方式和分類

⑴按推理機制劃分，可以有●

演繹推理：演繹推理是從全稱判斷推導出特稱或單稱判斷的過程。●

歸納推理：歸納推理是從足夠的事例中歸納出一般性結論的推理過程?！?/p>

默認推理：默認推理又稱缺省推理。它是在知識不完全的情況下假設某些條件已經具備所進行的推理。2023/1/1250WeiChanghua

⑵按所用知識的確定性劃分，可以有

●

確定性推理：確定性推理是指推理時所用的知識都是精確的，推理出的結論也是精確的。

●

不精確推理：不精確推理是指在推理時所用到的知識不都是精確的，推理出的結論也不完全是肯定的。⑶按推理過程劃分，可以有

●

單調推理：單調推理是指在推理的過程中隨著推理的向前推進及新知識的加入，推理的結論呈單調增長的趨勢，并越來越接近最終目標。

●非單調推理：非單調推理是指在推理的過程中，由于新的知識的加入，不僅沒有加強推出的結論，反而要否定它，使得推理退回到前面的一步，重新開始。

2023/1/1251WeiChanghua

⑷按啟發(fā)性知識劃分，可以有

●

啟發(fā)式推理：在推理的過程中利用了能夠加快推理進程、求得最優(yōu)解的啟發(fā)性知識的推理。

●

非啟發(fā)性推理：在推理的過程中并不利用能夠加快推理進程、求得最優(yōu)解的啟發(fā)性知識的推理。⑸按方法論劃分，可以有

●

基于知識的推理

●

統(tǒng)計推理

●

直覺推理：直覺推理又稱為常識性推理，是根據(jù)常識進行的一種推理。2023/1/1252WeiChanghua3推理控制策略

⑴正向推理：從用戶提供的初始事實出發(fā)，在知識庫中找出當前可適合的知識，構成可適用的知識集，然后按某種沖突消解策略從知識集中選出一條知識進行推理，并將推理出的新事實加入到數(shù)據(jù)庫作為下一步推理的已知事實，如此重復這一過程。

⑵逆向推理：首先選定一個假設目標，然后尋找支持該假設的證據(jù)，若所需要的證據(jù)都能找到，則說明假設是成立的；若無論如何都找不到所需要的證據(jù)，說明原假設不成立。

⑶混合推理：即有正向推理又有逆向推理的推理方法就是混合推理。

⑷雙向推理：所謂雙向推理是指正向推理和逆向推理同時進行，且在某一步驟上相遇?；舅枷胧牵阂环矫娓鶕?jù)已知事實進行正向推理，但并不推到最終目標；另一方面，從某一假設目標出發(fā)進行逆向推理，但并不推至原始事實，而是讓它們在途中相遇，既正向推理所得的中間結論恰好是逆向推理此時所需要求的證據(jù)。

2023/1/1253WeiChanghua

4歸結反演歸結反演就是用歸結和反演的方法實現(xiàn)定理證明。⑴子句定義為由文字的析取組成的公式謂詞公式化為子句集的過程

●

消去蘊涵符號

●

把否定符號移到每個謂詞符號的前面

●

變量標準化

●

消去存在量詞

●

將公式化為前束形

●

把母式化為合取范式

●

略去全稱量詞

●

把母式用子句表示

●

子句變量標準化2023/1/1254WeiChanghua

⑵歸結反演的一般過程：設有公式集S，希望從S證明某個目標公式W，證明的過程如下：

●

將W加入到S集合

●

將新的集合S轉換成一組子句，應用歸結原理推導出一個空子句歸結反演過程主要就是證明一個集合是不可滿足的過程，即從集合歸結出空子句的過程。

⑶歸結反演的控制策略

●

寬度優(yōu)先策略

●

支持集策略

●

單元優(yōu)先策略

●

線性輸入策略

●

祖先過濾策略2023/1/1255WeiChanghua5基于規(guī)則的演繹系統(tǒng)將問題的知識和信息劃分為規(guī)則和事實兩種類型。規(guī)則有包含蘊涵形式的表達式，事實由無蘊涵形式的表達式表示。這樣的推理系統(tǒng)稱為基于規(guī)則的演繹系統(tǒng)。

●

正向演繹系統(tǒng)：從事實出發(fā)，正向地使用蘊涵式（F規(guī)則）進行演繹推理，直到某個目標公式的一個終止條件為止。

◆

事實表達式：事實表達式為無蘊涵的任意與或形。

◆利用規(guī)則轉換與或圖：正向演繹系統(tǒng)應用規(guī)則作用于事實的與或圖，改變與或圖的結構，從而產生新的事實。規(guī)則形式為

其中L是單文字，W是任意的與或形表達式。L和W中的所有變量都是全稱量化的。

◆

利用目標公式做結束條件：正向演繹系統(tǒng)的目標公式定義為文字的析取，當一個目標文字與與或圖中的文字匹配時，系統(tǒng)便成功結束。2023/1/1256WeiChanghua

●

逆向演繹系統(tǒng)：在逆向演繹系統(tǒng)從目標表達式出發(fā)，應用逆向規(guī)則（規(guī)則），直到事實表達式。

◆

目標表達式：在逆向演繹系統(tǒng)中，目標公式為無蘊涵的任意與或形。

◆

規(guī)則應用：逆向演繹系統(tǒng)的規(guī)則稱為規(guī)則，形為其中W為任意的與或形，L為單文字。

◆

結束條件：逆向演繹系統(tǒng)的事實表達式限制為文字的合取，可表示為文字的集合。逆向演繹系統(tǒng)的結束條件就是與或圖中包括一個結束在事實結點上的一致解圖，該解圖的合一復合作用于目標表達式就是解答語句。2023/1/1257WeiChanghua第五章基本推理方法思考題

1敘述求公式子句集的全過程。2

歸結反演方法證明定理的基本思想是什么？3

歸結反演的控制策略是什么？4

正向演繹與逆向演繹各自的特點是什么？5

設有以下的謂詞演算公式，試寫出其轉換成子句集的過程。(1)(2)(3)(4)2023/1/1258WeiChanghua

6招聘工作人員，A、B、C三人應試，經面試后公司表示如下想法：（1）

三人中至少錄取一人（2）

如果錄取A而不錄取B，則一定錄取C（3）

如果錄取B，則一定錄取C試用歸結反演法證明公司一定錄取C。7假設已知下列事實：（1）

李華（LiHua）喜歡的容易的（Easy）課程（course）。（2）

李華（LiHua）不喜歡的難的（Difficult）課程（course）。（3）

工程類（Eng）的課程都是難的。（4）

物理類（Phy）的課程都是容易的。（5）

吳剛（Wugang）喜歡所有李華不喜歡的課程。（6）

Phy200是門物理類課程。（7）

Eng300是門工程類課程。

請用歸結反演方法回答下列問題：（1）

吳剛喜歡什么課程？（2）吳剛喜歡Eng300課程嗎？

2023/1/1259WeiChanghua8

已知事實表達式：F規(guī)則：

求目標公式：2023/1/1260WeiChanghua第六章不確定性推理1不確定性推理的基本概念⑴什么是不確定性推理所謂不確定性推理就是從不確定性的初始證據(jù)出發(fā)，通過運用不確定性的知識，最終推理出具有一定程度的不確定性，但又是合理或者似乎合理的結論的思維過程。⑵不確定性推理的一般算法

●

根據(jù)規(guī)則前提E的不確定性C(E)和規(guī)則強度f(H，E),求出假設H的不確定性C(H)，即定義一函數(shù)g1，使C(H)=g1[C(E),f(H,E)]●根據(jù)分別由獨立的證據(jù)E1和E2,求得的假設H的不確定性C1(H)和C2(H)，

2023/1/1261WeiChanghua求得證據(jù)E1和E2的組合所導致的假設的不確定性C(H)，即定義一函數(shù)g2，使C(H)=g2[C1(H),C2(H)]

●

根據(jù)兩個證據(jù)E1和E2的不確定性C(E1)和C(E2)，求出證據(jù)E1和E2的合取E1E2的不確定性，即定義一函數(shù)g3，使C(E1E2)=g3[C(E1),C(E2)]

●

根據(jù)兩個證據(jù)E1和E2的不確定性C(E1)和C(E2)，求出證據(jù)E1和E2的析取的不確定性，即定義函數(shù)g4，使C(E1E2)=g4[C(E1),C(E2)]

⑶幾種主要的不確定性推理方法

●

確定因子法（可信度方法）

●

主觀Bayes方法

●

證據(jù)理論

●

可能性理論

●

粗集理論

●

批注理論

2023/1/1262WeiChanghua2確定因子法⑴知識的不確定性表示MYCIN系統(tǒng)稱規(guī)則強度為規(guī)則確定性因子（CertaintyFactor）CF(H,E)，它表示在已知證據(jù)的情況下，對假設的確信程度。CF(H,E)定義如下：

⑵證據(jù)的不確定性2023/1/1263WeiChanghua⑶不確定性推理●

根據(jù)證據(jù)和規(guī)則的不確定性求假設的不確定性：

組合兩個獨立證據(jù)導出的同一個假設的不確定性：

由此計算：

2023/1/1264WeiChanghua●

證據(jù)的合取

●證據(jù)的析取

2023/1/1265WeiChanghua3主觀Bayes方法主觀Bayes方法是以概率論中的Bayes公式為基礎的一種不確定性推理算法，首先應用于專家系統(tǒng)PROSPECTOR系統(tǒng)。

⑴知識不確定性的表示：在該方法中知識的不確定性表示為其中規(guī)則強度由LS和LN表示。

⑵證據(jù)的不確定性：證據(jù)的不確定性用證據(jù)的概率P(E)表示，或者用證據(jù)的幾率(E)

2023/1/1266WeiChanghua

⑶不確定性推理算法：采用三點的線性插值方法。即

當時，有

當時，有

當時，有

分段插值的解析式為：

2023/1/1267WeiChanghua4證據(jù)理論證據(jù)理論是由Dempster和他的學生Shafer共同提出來的一種不確定性推理模型，所以也稱為D-S證據(jù)理論。證據(jù)理論可以滿足比概率更加弱的公里體系，當概率值已知的時候，證據(jù)理論就變成為概率論了。

⑴證據(jù)的不確定性設U的冪集2U上定義了一個基本概率賦值函數(shù)m：2U

[0,1]，使?jié)M足

，基本概率賦值函數(shù)m(A)表示了證據(jù)對U的子集A成立的一種信任程度。2023/1/1268WeiChanghua信任函數(shù)：信任函數(shù)定義為

似然函數(shù)：似然函數(shù)定義為

信任函數(shù)與似然函數(shù)的關系

2023/1/1269WeiChanghua⑵證據(jù)組合：對于相同的證據(jù)，由于來源不同，可能得到不同的基本概率賦值函數(shù)。D-S證據(jù)理論采取正交和來組合這些函數(shù)。

設是上的個基本概率賦值函數(shù)，它們的正交和，且定義為

其中

⑶證據(jù)理論的推理●

知識表示：系統(tǒng)的推理規(guī)則表示為●

證據(jù)的描述：對于任何命題，其信任函數(shù)為2023/1/1270WeiChanghua

●

似然函數(shù)為

●類概率函數(shù)：

⑷不確定性推理

●匹配度函數(shù)：

2023/1/1271WeiChanghua●

命題的邏輯組合的情況◆

合?。骸粑鋈。?/p>

◆如果幾種規(guī)則支持同一命題，總的概率賦值函數(shù)定義為各規(guī)則假設得到的基本概率賦值函數(shù)的正交和，即

2023/1/1272WeiChanghua5可能性理論

Zadeh在1965年提出了模糊集合論，1978年又提出了可能性理論。

⑴模糊命題：含有模糊概念、模糊數(shù)據(jù)或帶有確信程度的語句稱為模糊命題。形式化為：xisA或者xisA(CF)其中，X是論域上的變量，用來代表所論對象的屬性；A是模糊概念或模糊數(shù)；CF是該模糊命題的確信度，它可以是一個確定的數(shù)，也可以是模糊數(shù)，還可以是模糊語言值。

⑵模糊知識的表示：模糊產生式規(guī)則的一般形式為

其中E是用模糊命題表示的模糊條件；H是用模糊命題表示的模糊結論；CF是該產生式規(guī)則所表示的知識可信度因子。

2023/1/1273WeiChanghua⑶語義距離：設A、B分別是論域上相應的模糊概念的模糊集，而和分別是它們的隸屬函數(shù)，則有

●

海明距離：海明距離定義為

●歐幾里德距離

●

明可夫斯基距離2023/1/1274WeiChanghua

●切比雪夫距離

⑷語言變量：用語言而不是用數(shù)字來表示變量的值和變量之間的關系，這種變量稱為語言變量。

⑸模糊命題的轉換規(guī)則

●

修正規(guī)則●

合取、析取和蘊含規(guī)則●

量化規(guī)則⑹模糊推理

●

廣義假言推理●

模糊量詞的近似推理●

模糊真值限定的近似推理2023/1/1275WeiChanghua

6粗集理論粗集理論是波蘭華沙理工大學的Z.Pawlak教授1982年首先提出的處理不確定性信息的理論。該方法特別實用于觀察和測量獲得的不精確數(shù)據(jù)的分類問題。

2023/1/1276WeiChanghua第六章不確定性推理思考題1

分別以不精確性、不完全性、模糊性、時變性和非單調性舉例說明現(xiàn)實世界知識的不確定性。2構造一個不確定性知識系統(tǒng)一般要涉及到那幾個問題？3說明確定因子法中的MB和MD的物理意義。4設學生考試成績的論域為，小王成績得A、得B、得A或B的基本概率分別分配到0.2,0.1,0.3，為0.2；請給出、和。

2023/1/1277WeiChanghua5設某問題求解用到下面的推理規(guī)則；

試用確定因子法求出的可信度。假定已知在當前觀察有

6設有一組規(guī)則，推理網絡如圖所示。

Rule1:IFE1∧E2THENE3={a1,a2}CF={0.2,0.6}Rule2:IFE5∧E8THENE4=CF={0.8}Rule3:IFE3

THENH={h1,h2,h3}CF={0.2,0.5,0.3}Rule4:IFE4

THENH={h1,h2,h3}CF={0.3,0.4,0.1}Rule5:IFE6∨E7THENE8CF={0.8}2023/1/1278WeiChanghua已知：CF(E1)=0.7

CF(E2)=0.8CF(E5)=0.6CF(E6)=0.4CF(E7)=0.9

試用D-S證據(jù)理論求出CF（H）。H={h1,h2,h3}E1E2E5E6E7E3E4E52023/1/1279WeiChanghua第七章專家系統(tǒng)1專家系統(tǒng)的基本概念

⑴什么是專家系統(tǒng)：專家系統(tǒng)是一個智能程序，它具有相關領域的大量專家知識，它可以模擬人類專家解決問題的思維過程，且解決問題的能力不低于人類領域專家。

⑵專家系統(tǒng)的特征

●

具有專家水平的專門知識

●

能進行有效的推理

●

具有獲取知識的能力

●

具有靈活性

●

具有透明性

●

具有交互性

●

具有一定的復雜性和難度2023/1/1280WeiChanghua⑶專家系統(tǒng)與常規(guī)程序的區(qū)別

●

常規(guī)程序=數(shù)據(jù)結構+算法專家系統(tǒng)=知識+推理

●

常規(guī)程序將知識組織成數(shù)據(jù)級和程序級；而專家系統(tǒng)將知識組織成數(shù)據(jù)級、知識庫級和控制級。

●

常規(guī)程序一般是通過查找或計算獲取問題的解，本質上是數(shù)值計算；而專家系統(tǒng)是通過推理獲取問題的解或證明某個假設，本質上是符號處理。

●

常規(guī)程序處理的數(shù)據(jù)多數(shù)是精確的；而專家系統(tǒng)處理的數(shù)據(jù)大多數(shù)是不精確的、模糊的。

●

常規(guī)程序一般不需要具備解釋功能；而專家系統(tǒng)一般具有解釋機構，它可以對自己的行為作出解釋。

●

常規(guī)程序與專家系統(tǒng)具有不同的軟件體系結構。2023/1/1281WeiChanghua⑷專家系統(tǒng)研究的歷史●世界上第一個專家系統(tǒng)

1965年，A.Feigenbum,DENDRAL●中國第一個專家系統(tǒng)

1978年，中國科學院自動化研究所涂序彥：關幼波肝病診斷與治療專家系統(tǒng)2023/1/1282WeiChanghua2專家系統(tǒng)分類

⑴按專家系統(tǒng)的特征分類

●

解釋型

●

診斷型

●

預測型

●

設計型

●

規(guī)劃型

●

控制型

●

檢測型

●

維修型

●

教育型

●

調試型2023/1/1283WeiChanghua⑵按系統(tǒng)的體系結構分類

●

集中式專家系統(tǒng)

●

分布式專家系統(tǒng)

●

神經網絡專家系統(tǒng)

●

符號系統(tǒng)與神經網絡相結合的專家系統(tǒng)3專家系統(tǒng)的一般結構

⑴專家系統(tǒng)的基本結構專家系統(tǒng)的基本結構由五部分組成：

●

知識庫；用于存放問題求解所需要的知識

●

綜合數(shù)據(jù)庫：用于存放系統(tǒng)運行過程中所需要的原始數(shù)據(jù)和產生的所有信息。

●

推理機：根據(jù)綜合數(shù)據(jù)庫當前的狀態(tài)，利用知識庫中的知識進行推理。

●

知識獲取程序：這個部件負責建立、修改和擴充知識庫，并對知識庫中的知識進行一致性、完整性進行維護。

●

解釋程序：解釋程序用于對求解過程作出說明，并回答用戶提出的問題。

2023/1/1284WeiChanghua人機接口推理機解釋程序知識獲取程序數(shù)據(jù)庫及其管理系統(tǒng)知識庫及其管理系統(tǒng)專家系統(tǒng)的一般結構用戶領域專家2023/1/1285WeiChanghua4專家系統(tǒng)的建造與評價

⑴專家系統(tǒng)建造的原則

●

恰當劃定求解問題的領域

●

獲取完備的知識

●

知識庫與推理機的分離

●

選擇、設計合適的知識表示

●

推理機應模擬領域專家求解問題的思維過程

●

建立良好的交互環(huán)境

●

漸增式的開發(fā)策略2023/1/1286WeiChanghua⑵專家系統(tǒng)的開發(fā)過程

●

需求分析

●

系統(tǒng)設計

●

知識獲取

●

編程、調試

●

原型測試

●

修正與擴充

●

系統(tǒng)包裝及總調

●

系統(tǒng)維護2023/1/1287WeiChanghua⑶專家系統(tǒng)的評價

●

知識的完備性

●

表示方法及組織方法的適應性

●

求解問題的質量

●

系統(tǒng)的效率

●

人機交互的便利性

●

系統(tǒng)的可維護性

●

解釋能力

●

系統(tǒng)的研制時間與效益2023/1/1288WeiChanghua5專家系統(tǒng)開發(fā)工具

⑴人工智能語言

●