《人工智能》課程教案

《人工智能》課程教案

第一章緒論

教學內容：本章首先介紹人工智能的定義、發(fā)展概況及相關學派和他們的認知觀，接著

討論人工智能的研究和應用領域，最后簡介本書的主要內容和編排。

教學重點:1.從不同科學或學科出發(fā)對人工智能進行的定義；

2.介紹人工智能的起源與發(fā)展過程；

3.討論人工智能與人類智能的關系；

4.簡介目前人工智能的主要學派；

5.簡介人工智能所研究的范圍與應用領域。

教學難點：1.怎么樣理解人工智能；

2.人工智能作為一門學科有什么意義；

3.人工智能的主要學派與其爭論焦點；

教學方法：課堂教學為主，充分利用網絡課程中的多媒體素

材來表示抽象概念。

教學要求：重點掌握人工智能的幾種定義，掌握目前人工智

能的三個主要學派及對人工智能的理解，一般了解人工智能

的主要研究范圍和應用領域。

1.1人工智能的定義與發(fā)展

教學內容：本小節(jié)主要介紹目前對人工智能的幾種定義，并對人工智能的起源和發(fā)展

進行了總結和分析。

教學重點：幾種人工智能的定義和人工智能發(fā)展的幾個重要時期。

教學難點：理解人工智能的定義與本質。

教學方法：課堂講授為主。

教學要求：從學科和能力的角度深刻理解人工智能的定義,

初步了解人工智能的起源及其發(fā)展過程。

1.1.1人工智能的定義

定義1智能機器

能夠在各類環(huán)境中臼主:地或交互地執(zhí)行各種擬人任務(anthropomorphictasks)的機器。

定義2人工智能(學科)

人工智能(學科)是計算機科學中涉及研究、設計和應用智能機器的一個分支。它的近期

主要目標在于研究用機器來模仿和執(zhí)行人腦的某些智力功能，并開發(fā)相關理論和技術。

定義3人工智能(能力)

人工智能(能力)是智能機器所執(zhí)行的通常與人類智能有關的智能行為，如判斷、推理、

證明、識別、感知、理解、通信、設計、思考、規(guī)劃、學習和問題求解等思維活動。

為了讓讀者對人工智能的定義進行討論，以便更深刻地理解人工智能，下面綜述其它幾

種關于人工智能的定義。

定義4人工智能是一種使計算機能夠思維，使機器具有智力的激動人心的新嘗試

(Haugeland,1985)o

定義5人工智能是那些與人的思維、決策、問題求解和學習等有關活動的自動化

(Bellman,1978)o

定義6人工智能是用計算模型研究智力行為(Charniak和McDermoll,1985)。

定義7人工智能是研究那些使理解、推理和行為成為可能的計算(Winston,1992)。

定義8人工智能是一種能夠執(zhí)行需要人的智能的創(chuàng)造性機器的技術(Kurzweil,1990).

定義9人工智能研究如何使計算機做事讓人過得更好(Rick和Knight,1991)。

定義10人工智能是一門通過計算過程力組理解和模仿智能行為的學科

(Schalkoff,1990)o

定義11人工智能是計算機科學中與智能行為的自動化有關的一個分支(Luger和

Stubblefield,1993).

其中，定義4和定義5涉及擬入思維；定義6和定義7與理

性思維有關；定義8和定義9涉及姒人行為；定義10和定

義11與擬人理性行為有關。

1.1.2人工智能的起源與發(fā)展

人工智能的發(fā)展是以硬件與軟件為基礎的，經歷了漫長的發(fā)展歷程。特別是20世紀30

年代和40年代的智能界，發(fā)現(xiàn)了兩件重要的事情：數理邏輯和關于計算的新思想。以維納

(Wiener).弗雷治、羅素等為代表對發(fā)展數理邏輯學科的貢獻及丘奇(Church)、圖靈和其它

一些人關于計算本質的思想，為人工智能的形成產生了重要影響。

1956年夏季，人類歷史上第一次人工智能研討會在美國的達特茅斯(Dartmouth)大學舉

行，標志著人工智能學科的誕生。

1969年召開了第一屆國際人工智能聯(lián)合會議(InlemationalJointConferenceonALIJCAI),

此后每兩年召開一次。

1970年《人工智能》國際雜志(InlemaiionalJournalofAI)創(chuàng)刊。這些對開展人工智能國

際學術活動和交流、促進人工智能的研究和發(fā)展起到積極作用。

提問：為什

20世紀70?80年代，知識工程的提出與專家系統(tǒng)的成功應用，確定

么人工智能

了知識在人工智能中的地位。

在1956年才

近十多年來，機器學習、計算智能、人工神經網絡等和行為主義的研

正式誕生？

究深入開展，形成高潮。同時，不同人工智能學派間的爭論也非常熱烈。

這些都推動人工智能研究的進一步發(fā)展。

1.2人類智能與人工智能

教學內容：本節(jié)主要討論人類智能與人工智能的關系問題。

教學重點：智能信息處理系統(tǒng)，人類智能與人工智能的關系。

教學難點：智能信息處理系統(tǒng)的假設。

教學方法：課堂講授為主。

教學要求：了解人類認知活動與計算機的比較關系，基本了

解智能信息處理系統(tǒng)。

1.2.1智能處理信息系統(tǒng)的假設

1.符號處理系統(tǒng)的六種基本功能

信息處理系統(tǒng)又叫符號操作系統(tǒng)(SymbolOperationSystem)或物理符號系統(tǒng)(Physical

SymbolSystem)o所謂符號就是模式(paltern)。

一個完善的符號系統(tǒng)應具有下列6種基本功能：

⑴輸入符號(input)；

(2)輸出符號(output);

⑶存儲符號(store);

(4)復制符號(copy);

(5)建立符號結構：通過找出各符號間的關系，右符號系統(tǒng)中形成符號結構：

⑹條件性遷移(condidonaltransfer):根據已有符號，維續(xù)完成活動過程。

2.可以把人看成一個智能信息處理系統(tǒng)

如果一個物理符號系統(tǒng)具有上述全部6種功能，能夠完成這個全過程，那么它就是一個

完整的物理符號系統(tǒng)。人具有上述6種功能;現(xiàn)代計算機也具備物理符號系統(tǒng)的這6種功能。

3.理符號系統(tǒng)的假設

任何一個系統(tǒng)，如果它能表現(xiàn)出智能，那么它就必定能夠執(zhí)行上述6種功能。反之，任

何系統(tǒng)如果具有這6種功能，那么它就能夠表現(xiàn)出智能；這種智能指的是人類所具有的那種

智能。把這個假設稱為物理符號系統(tǒng)的假設。

4.物理符號系統(tǒng)3個推論

推論一既然人具有智能，那么他(她)就一定是個物理符號系統(tǒng)。

人之所以能夠表現(xiàn)出智能，就是基于他的信息處理過程。

推論二既然計算機是一個物理符號系統(tǒng)，它就一定能夠表現(xiàn)出智能。這是人工智能的

基本條件。

推論三既然人是一個物理符號系統(tǒng)，計算機也是一個物理符號系統(tǒng)，那么就能夠用

計算機來模擬人的活動。

4.人類的認知行為具有不同的層次

認知生理學研究認知行為的生理過程，主要研究人的神經系統(tǒng)(神經元、中樞神經系

統(tǒng)和大腦)的活動，是認知科學研究的底層。

認知心理學研究認知行為的心理活動，主要研究人的思維策略，是認知科學研究的

頂層。

認知信息學研究人的認知行為在人體內的初級信息處理，主要研究人的認知行為如

何通過初級信息自然處理，由生理活動變?yōu)樾睦砘顒蛹捌淠孢^程，即由心理活動變?yōu)樯?/p>

行為。這是認知活動的中間層，承上啟下。

認知工程學研究認知行為的信息加工處理，主要研究如何通過以計算機為中心的人

工信息處理系統(tǒng)，對人的各種認知行為(如知覺、思維、記憶、語言、學習、理解、推理、

識別等)進行信息處理。這是研究認知科學和認知行為的工具，應成為現(xiàn)代認知心理學和現(xiàn)

代認知生理學的重要研究手段。

1.2.2人類智能的計算機模擬

1.機器智能可以模擬人類智能

物理符號系統(tǒng)假設的推論一告訴人們，人有智能，所以他是一個物理符號系統(tǒng)；推論三

指出，可以編寫出計算機程序去模擬人類的思維活動。這就是說，人和計算機這兩個物理符

號系統(tǒng)所使用的物理符號是相同的，因而計算機可以模擬人類的智能活動過程。

2.智能計算機的功能

如下棋、證明定理、翻譯語言文字和解決難題等。神經計算機(neuralcomputer)能夠以

類似人類的方式進行“思考”，它力圖重建人腦的形象。一些國家對量子計算機的研究也已

起步，希望通過對量子計算(quantumcomputing)的研究，產生量子計算機。

1.3人工智能的學跟

教學內容：本節(jié)主要介紹人工智能的幾個主要學派及認知觀。

教學重點：符號主義(Symbolicism),聯(lián)結主義(Connectionism),行為主義(Actionism)。

教學難點：各學派的對人工智能的不同觀點。

教學方法：課堂講授為主。

教學要求：了解各派別之間的關系及對人工智能發(fā)展歷史的看法。

1.人工智能三大學派

?符號主義(Symbolicism),又稱為邏輯主義(Logicism)、心理學派(Psychlogism)或計算

機學派(Computerism),其原理主要為物理符號系統(tǒng)(即符號操作系統(tǒng))假設和有限合理性原

理。

?聯(lián)結主義(Conncctionism),又稱為仿生學派(Bionicsism)或生理學派(Physiologism),

其原理主要為神經網絡及神經網絡間的連接機制與學習算法。

?行為主義(Actionism),又稱進化主義(Evolutionism)或控制論學派(Cyberncticsism),

其原理為控制論及感知一動作型控制系統(tǒng)。

2.三大學派對人工智能發(fā)展歷史的不同看法

符號主義認為人工智能源于數理邏輯。符號主義仍然是人工智能的主流派。這個學派

的代表有紐厄爾、肖、西蒙和尼爾遜(Nilsson)等。

聯(lián)結主義認為人工智能源于仿生學，特別是人腦模型的研究。

行為主義認為人工智能源于控制論。這一學派的代表作首

推布魯克斯(Brooks)的六足行走機器人，它被看做新一代的

“控制論動物”，是一個基于感知一動作模式的模擬昆蟲行

為的控制系統(tǒng)。

1.4人工智能的研窕與應用領域

教學內容：本節(jié)主要討論人工智能的研究與應用領域。

教學重點：人工智能的一些主要研究與應用領域。

教學難點：處理好各領域間的交叉關系。

教學方法：課堂講授為主。

教學要求：初步了解人工智能的研究與應用領域。

1.4.1訶題求解

人工智能的第一個大成就是發(fā)展了能夠求斛難題的下棋（如

國際象棋）程序，它包含問題的表示、分斛、拽奈與歸約等。

1.4.2逐輯推理與定理證明

邏輯推理是人工智能研究中最持久的子領域之一，特別重要的是要找到一些方法，只把

注意力集中在一個大型數據庫中的有關事實上，留意可信的證明，并在出現(xiàn)新信息時適時修

正這些證明。

定理證明的研窕在人工智能方法的發(fā)展中曾較產生過重要

的影喻。例如，采用謂詞透科語言的演年過程的形式化有助

于更清楚地理斛推理的某些子命題。許多非形式的工作，包

括醫(yī)疔診斷和信息檢索都可以和定理證明問題一樣加以形

式化。因此，發(fā)人工智能方法的研究中定理證明是一個極其

重要的論題。

我國人工智能大師吳文俊院士提出并實現(xiàn)了幾何定理機森

證明的方施，破國際上豕認為“吳氏方法”,是定理證明的

又一標志性成果0

1.4.34然語言理解

語言處理也是人工智能的早期研窕領域之一，并引起了進一步的重視。語言的生成和理

解是一個極為復雜的編碼和解碼問題。

一個能理解4然語言信息的計算機條線看起來就像一個人

一樣需要有上下文知詼以及根據這些上下文知識和信息用

信息發(fā)生器進行推理的過程。理解口頭的和書寫語言的計算

機條院所取得的某些進展，其基礎就是有關表示上下文知出

轉構的某些人工智能思想以及根據這些知識進行推理的某

些技術。

1.4.4自動程序設計

對自動程序設計的研究不僅可以促進半自動軟件開發(fā)系統(tǒng)的發(fā)展，而目.也使通過修正

自身數碼進行學習（即修正它們的性能）的人工智能系統(tǒng)得到發(fā)展。程序理論方面的有關研究

工作對人工智能的所有研究工作都是很重要的。

4動程序設計研究的重大貢故之一是作為問題求解集睢的

調整概念。已經發(fā)現(xiàn)，對程序設計或機器人控制訶題，先產

生一個不賽事的有錯誤的解，然后再修改它（使它正確工作）,

這種做法一般要比堅持要求第一個群就完全沒有缺陷的做

法有效得多。

1.4.5專家樂統(tǒng)

一般地說，專家系統(tǒng)是一個智能計算機程序系統(tǒng)，其內部具有大量專家水平的某個領域

知識與經驗，能夠利用人類專家的知識和解決問題的方法來解決該領域的問題。

發(fā)展專家余統(tǒng)的關鍵是表達和適用專家知短，即來4人類專

象的并已被證明對解決有關領域內的典型問題是有用的事

實和過程。

1.4.6機器學習

學習是人類智能的主要標志和荻得知短的基本手段；機款學

習（4動獲取新的事實及新的推理算成）是使計算機具有智能

的根本速控；機器學習還有助于發(fā)現(xiàn)人類學習的機理和揭示

人腦的真秘。學2是一個有特定目的的知板獲取過程，其內

部表現(xiàn)為新知識結構的不斷建立和修女，而外部表現(xiàn)為性能

的友耳。

1.4.7神經網絡

神經網絡處理直覺和形象思維信息具有比傳統(tǒng)處理方式好得多的效果。

神經網絡已在模式識別、圖象處理、組合優(yōu)化、自動控制、信息處理、機器人學和人工

智能的其它領域獲得日益廣泛的應用。

1.4.8機器人學

人工智能研究口益受到重視的另一個分支是機器人學，其中包括對操作機器人裝置程

序的研究。這個領域所研究的問題，從機器人手憎的最佳移動到實現(xiàn)機器人目標的動作序列

的規(guī)劃方法，無所不包。目前已經建立了一些比較復雜的機器人系統(tǒng)。

機器人和機器人學的研究促進了許多人工智能思想的發(fā)展。

智能機器人的研究和應用體現(xiàn)出廣泛的學科交叉，陟及眾多

的課題，機器人已在各領域獲得越來越普遍的應用。

1.4.9模式板別

人工智能所研究的?；乙詣e是抽用計算機代稱人類或率助

人類感知模式，是對人類意知外界功能的模擬，研究的是計

算機康式竊別余然，也就是使一個計算機條統(tǒng)具有模擬人類

通過感畬接受外界信息、識別和理解周SI環(huán)境的感知能力。

1.4.10機器視競

實驗表明，人類接受外界信息的80%以上來自視覺，視覺對人類是非常重要的。

機器視覺或計算機視覺已從模式識別的一個研究領域發(fā)展為一門獨立的學科;在視覺方

面，已經給計算機系統(tǒng)裝上電視輸入裝置以便能夠“看見”周圍的東西。

機器視覺的前沿研究領域包括實時并行處理、主動式定性視覺、動態(tài)和時變視覺、三維

景物的建模與識別、實時圖像壓縮傳輸和復原、多光譜和彩色圖像的處理與解釋等。

1.4.11智能裝制

人工智能的發(fā)展促進自動控制向智能控制發(fā)展。智能控制是一類無需（或需要盡可能少

的）人的干預就能夠獨立地驅動智能機器實現(xiàn)其目標的自動控制。

智能搔制是同時具有以知例表示的非教學廣義世界模型和

教學公式模型表示的混合捏制過程，也往往是含有復雜性、

不完全性、模糊性或不確定性以及不存在已知算法的非教學

過程，并以知識進行推理，以啟發(fā)來引導求斛過程。

1.4.12智能檢奈

隨著科學技術的迅速發(fā)展，出現(xiàn)了“知識爆炸”的情況，研究智能檢索系統(tǒng)已成為科技

持續(xù)快速發(fā)展的重要保證，

智能信急檢親余統(tǒng)的設計者們將面臨以下幾個問題。譽先,

建立一個能夠理解以4然語守陳述的詢訶余統(tǒng)本身就存在

不少問題。其次，即使能夠通過規(guī)定某些機春能緲理解的形

式化詢問語句來回避語言理解問題，但仍然存在一個如何極

據存儲的事實演午出答案的問題。第三,理解詢問和演隼答

案所需要的知板都可能超出該學科領域數據庫所表示的知

識。

1.4.13智能陰度與指揮

確定最佳調度或組合的問題是人們感興趣的乂一類問題，求解這類問題的程序會產生

一種組合爆炸的可能性，這時，即使是大型計算機的容量也會被用光。

人工智能學家們瞥經研究過若干組合問題的求解方法。他們

的勢力集中在使“時間■問題大小”曲線的變化盡可能緩慢地

增長，即使是於須按指數方式增長。有關問題城的知物再次

成為比較有效的求解方法的關鍵。為處理組合問題而發(fā)展起

來的許多方法對其它姐合上不卷產童的問題也是有用的。

1.4.14分布式人工智能與Agent

分布式人工智能(DistributedAI,DAI)是分布式計算與人工智能結合的結果。DAI系統(tǒng)以

魯棒性作為控制系統(tǒng)質量的標準，并具有互操作性，即不同的異構系統(tǒng)在快速變化的環(huán)境中

具有交換信息和協(xié)同工作的能力。分布式人工智能的研究目標是要創(chuàng)建一種能夠描述自然系

統(tǒng)和社會系統(tǒng)的精確概念模型。

多agent系統(tǒng)(MultiagentSystem,MAS)更能體現(xiàn)人類的社

會智能，具有更大的靈活性和適應性，更適合開放和動志的

世界環(huán)境，因而福?受重視，巴成為人工智能以至計算機科學

和控制科學與工程的研究熱點。

1.4.15計算智能與進化計算

計算智能(Computing【ntelligence)涉及神經計算、模糊計算、進化計算等研究領域,

進化計算(EvolutionaryComputation)是指一類以達東丈進

化價為依據來設計、放制和優(yōu)化人工系統(tǒng)的技術和方法的總

稱，它包括遺傳算法(GeneticAlgorithms).進化兼唱

(EvolutionaryStrategies)和進化規(guī)劃(Evolutionary

Programming)?

1.4.16數據托爆與知識發(fā)現(xiàn)

知識獲取是知識信息處理的關鍵問題之一。

數據挖掘是通過綜合運用統(tǒng)計學、粗糙集、模糊數學、機器學習和專家系統(tǒng)等多種學習

手段和方法，從大量的數據中提煉出抽象的知識，從而揭示出蘊涵在這些數據背后的客觀世

界的內在聯(lián)系和本質規(guī)律.實現(xiàn)知識的自動獲取。

數據挖掘和知識發(fā)現(xiàn)技術已獲廣泛應用。

1.4.17人工生命

人工生命(ArtificialLife,ALife)旨在用計算機和精密機械等人工媒介生成或構造出能夠

表現(xiàn)自然生命系統(tǒng)行為特征的仿真系統(tǒng)或模型系統(tǒng)。自然生命系統(tǒng)行為具有自組織、自復制、

自修復等特征以及形成這些特征的混沌動力學、進化和環(huán)境適應。

人工生命所研究的人造系統(tǒng)能夠演示具有自然生命系統(tǒng)特征的行為，在“生命之所能”

(lifeasitcouldbe)的廣闊范圍內深入研究“生命之所知"(lifeasweknowit)的實質。

人工生命學科的研究內容包括生.命現(xiàn)象的仿生系統(tǒng)'人工建模與仿真、進化動力學、人

工生命的計算理論、進化與學習綜合系統(tǒng)以及人工生命的應用等。

1.4J8系線與語言工具

除了直接解準實現(xiàn)智能的研究工作外，開發(fā)新的方法也往往

是人工智能研究的一個重要方面。人工智能對計算機界的某

些景大貢故巳經以派生的形式表現(xiàn)出來。計算機系統(tǒng)的一些

概念，如分時余統(tǒng)、編日處理系統(tǒng)和交互調成系統(tǒng)等，巳經

在人工智能研究中得到發(fā)筱。.

1.5本書概要

本書包括下列內容：

1.簡述人工智能的起源與發(fā)展，討論人工智能的定義、人工智能與計算機的關系以及人

工智能的研究和應用領域，

2.比較概括地論述知識表示的各種主要方法，包括狀態(tài)空間法、問題歸約法、謂詞邏輯

法、結構化表示法（語義網絡法、框架）、劇本和過程等。

3.討論常用搜索原理，如盲目搜索、啟發(fā)式搜索和消解原理等：并研究?些比較高級的

推理求解技術，如規(guī)則演繹系統(tǒng)、專家系統(tǒng)、系統(tǒng)組織技術、不確定性推理和非單調推理等。

4.介紹近期發(fā)展起來的已成為當前研究熱點的人工智能技術

和方盅,即分布式人工智能與agent、計算智能（合神經計算、

透科計算與進化計算人數據挖掘與知板發(fā)現(xiàn)、人工生命等。

5、比較詳細地分析人工智能的主要應用領域，涉及專家余

統(tǒng)、機器學習、自動規(guī)劃未統(tǒng)和4然語言理解等。

6、敘述近年來人工智能研究中出現(xiàn)的爭論，猥里人工智能的

發(fā)展。

1.6辯論會

主題：人工智能能否超過人類智能？

正方觀點：人工智能不會超過人類智能。

反方觀點：人工智能能夠超過人類智能。

第二章知識表示方法

教學內容：本章討論知識表示的各種方法，是人工智能課程三大內容(知識表示、知識

推理、知識應用)之一，也是學習人工智能其他內容的基礎。

教學重點：狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網絡法。

教學難點：狀態(tài)描述與狀態(tài)空間圖示、問題歸約機制、置換與合一。

教學方法：課堂教學為主，同時結合《離散數學》等已學的

內容實時提問、收集學生學習情況，充分利用網絡課程中的

多媒體素材來表示抽象概念。

教學要求：重點掌握用狀態(tài)空間法、問題歸約法、謂詞演算

法、語義網絡法來描述問題；解決問題；掌握幾種主要方法

之間的差別；并對其它幾種表示方法有一般了解。

2.1狀態(tài)空同法

教學內容：本節(jié)是通過狀態(tài)空間法來求解問題，它是以狀態(tài)和算符(operator)為基礎來

表示和求解問題的。

教學重點：問題的狀態(tài)描述，操作符。

教學難點：選擇一個好的狀態(tài)描述與狀態(tài)空間表示方案。

教學方法：以課堂教學為主；充分利用網絡課程中的多媒體

素材來闡述抽象概念。

教學要求：重點掌握對某個問題的狀態(tài)空間描述，學會組織

狀態(tài)空間圖，用搜索圖來求解問題。

2.1.1問題狀忠出述

1.狀態(tài)(State)的基本概念

狀態(tài)(state)是為描述某類不同事物間的差別而引入的一組最少變量q。，ql,…，qn的有

序集合，其矢■形式如下：

Q=[qo,qi,….qJT(2.1)

式中每個元素qi(i=O,L…，n)為集合的分量，稱為狀態(tài)變量。給定每個分量的一組值就得到

一個具體的狀態(tài)，如

Qk=[qOk,qlk,…,qnk]T(2.2)

算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走

步、過程、規(guī)則、數學算子、運算符號或邏輯符號等。

問題的狀態(tài)空間(statespace)是一個表示該問題全部可能狀態(tài)及其關系的圖，它包含三

種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標狀態(tài)集合G.因

此，可把狀態(tài)空間記為三元狀態(tài)⑸F,G)o

2.狀態(tài)空間的表示法

對一個問題的狀態(tài)描述，必須確定3件事：

(1)該狀態(tài)描述方式，特別是初始狀態(tài)描述;

(2)操作符集合及其對狀態(tài)描述的作用；

(3)目標狀態(tài)描述的特性。

2.1.2狀態(tài)圖示樂

圖的基本概念

圖由節(jié)點(不一定是有限的節(jié)點)的集合構成。一對節(jié)點用弧線連接起來，從一個節(jié)點指

向另一個節(jié)點。這種圖叫做有向圖(directedgraph)?

某個節(jié)點序列(nil,ni2「?,nik)當j=2,3,…，k時，如果對于每一個ni,卜1都有一個后繼節(jié)點

nij存在，那么就把這個節(jié)點序列叫做從節(jié)點nil至節(jié)點nik的長度為k的路徑。

代價(cost)是給各弧線指定數值以表示加在相應算符上的代價。

圖的顯式說明是指各節(jié)點及其具有代價的弧線由一張表明確給出。

圖的隱式說明是指各節(jié)點及其具有代價的弧線不能由一張表明確給出。

2.13狀態(tài)變間表示舉例

1.產生式系統(tǒng)

一個產生式系統(tǒng)由下列3部分組成：

一個總數據庫(globaldatabase),它含有與具體任務有關的信息。

一套規(guī)則，它對數據庫進行操作運算。每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適

用性或先決條件，右部描述規(guī)則應用時所完成的動作。應用規(guī)則來改變數據庫。

一個控制策略，它確定應該采用哪一條適用規(guī)則，而且當數據庫的終止條件滿足時，就

停止計算。

2.狀態(tài)空間表示舉例

猴子與香蕉的問題

狀態(tài)空間表示用四元組(W,x,y,z)其中：W一猴子的水平位置；X—當猴子在箱子頂

上時取x=l；否則取x=0；Y一箱子的水平位置；Z—當猴子摘到香蕉時取2=1；否則取2=0。

算符

(1)goto(U)猴子走到水平位置U；

(2)pushbox(V)猴子把箱子推到水平位置V；

(3)climbbox猴子爬上箱頂；

(4)grasp猴子摘到香蕉。

求解過程令初始狀態(tài)為(a,0,b,0)。這時，goto(U)是唯一適用的操作，并導致下一狀態(tài)(U,0,

b,0)。現(xiàn)在有3個適用的操作，即goto(U),pushbox(V)和climbbox(若U=b)。把所有適用的操作繼

續(xù)應用于每個狀態(tài)，我們就能夠得到狀態(tài)空間圖，如圖所示。從圖不難看出，把該初始狀態(tài)變換

為目標狀態(tài)的操作序列為：

{goto(b),pushbox(c),climbbox,grasp)

2.2問題歸約法

教學內容：知識表示的歸約法，即已知問題的描述，通過一系列變換把此問題最終變?yōu)?/p>

一個子問題集合；這些子問題的解可以直接得到，從而解決了初始問題的方法。

教學重點：問題歸約的基本思想，問題描述，問題變換的操作符，與或圖表示。

教學難點：如何把初始問題變換為子問題，與或圖表示方法。

教學方法：課堂教學為主，充分利用網絡課程中的相關多媒

體素材來表示抽象概念。

教學要求：通過梵塔難題重點掌握問題歸約法的機理和問題

歸約描述方法。學會用與或圖表示歸約問題。

2.2.1問題歸約指述

1.問題歸約法的概念

已知問題的描述，通過一系列變換把此問題最終變?yōu)橐粋€子問題集合；這些子問題的解

可以直接得到，從而解決了初始問題。

該方法也就是從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子,可題,

直至最后把初始問題歸約為一個平凡的本原問題集合。這就是問題歸約的實質。

2.問題歸約法的組成部分

(1)一個初始問題指述；

(2)一套把問題變換為子問題的操作符；

(3)一套本原問題措述。

3.示例：梵塔難題

問題有3個柱子(1,2,3)和3個不同尺寸的圓盤(A,B,C)。在每個圓盤的中心有個孔，所

以圓盤可以堆疊在柱子上。最初，全部3個圓盤都堆在柱子1上：最大的圓盤C在底弟，最

小的圓盤A在頂部。要求把所有圓盤都移到柱子3上，每次只許移動一個，而且只能先搬動

柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。

歸約過程

(1)移動圓盤A和B至柱子2的雙圓盤難題；講述：梵塔問題的來源。

(2)移動圓盤C至柱子3的單圓盤難題：提問：一圓盤問題要走幾

(3)移動圓盤A和B至柱子3的雙圓盤難題。步？兩圓盤問題要走幾

由上可以看出簡化了難題每一個都比原始難題容易，所以步？三個、四個...等？

問題都會變成易解的本原問題。_____/

4.歸約描述

問題歸約方法是應用算符來把問題描述變換為子問題描述。

可以用狀態(tài)空間表示的三元組合(S、F、G)來規(guī)定與描述問題；對于梵塔問題，子問題

[(111)=>(122)],[(122)=>(322)]以及[(322)=>(333)]規(guī)定了最后解答路徑將要通過的

腳踏石狀態(tài)(122)和(322)。

問題歸約方法可以應用狀忠，算符和?標這些表示法來拈述

問題，這并不意味著問題歸妁法和狀忐變同法是一樣的。

2.2.2與或圖表示

i.與或圖的概念

用一個類似圖的結構來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。

例如，設想問題A需要由求解問題B、C和D來決定，那么可以用一個與圖來表示；同

樣，一個問題A或者由求解問題B、或者由求解問題C來決定，則可以用一個或圖來表示。

2,與或圖的有關術語

父節(jié)點是一個初始問題或是可分解為子問題的問題節(jié)點；

子節(jié)點是一個初始問題或是子問題分解的子問題節(jié)點：

或節(jié)點只要解決某個問題就可解決其父輩問題的節(jié)點集舉例：對于一個與或圖。

合；提問：指出圖中的父節(jié)點、

與節(jié)點只有解決所有子問題，才能解決其父輩問題的節(jié)子節(jié)點、或節(jié)點、與節(jié)點、

點集合；弧線和終葉節(jié)點。

弧線是父輩節(jié)點指向子節(jié)點的圓弧連線；_________N

終葉節(jié)點是對應于原問題的本原節(jié)點。

3.與或圖的有關定義

可解節(jié)點與或圖中一個可解節(jié)點的一般定義可以歸納如下：

(1)終葉節(jié)點是可解節(jié)點(因為它們與本原問題相關連)。

(2)如果某個非終葉芍點含有或后繼節(jié)點，那么只有當其后繼節(jié)點至少有一個是可解的

時，此非終葉節(jié)點才是可解的。

(3)如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當其后繼節(jié)點全部為可解時，此非終葉

節(jié)點才是可解的。

不可解節(jié)點不可解節(jié)點的一般定義歸納于下：

(1)沒有后裔的非終葉節(jié)點為不可解節(jié)點。

(2)如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只有當其全部后裔為不可解時，此非終

葉節(jié)點才是不可解的。

(3)如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當其后裔至少有一個為不可解時,

此非終葉節(jié)點才是不可解為。

4.與或圖構圖規(guī)則

(1)與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。圖中所含起始節(jié)點對

應于原始問題。

(2)對應于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔。

(3)對于把算符應用于問題A的每種可能情況，都把問題變換為一個子問題集合；有向

弧線自A指向后繼節(jié)點，表示所求得的子問題集合。

(4)一般對于代表兩個或兩個以上子問題集合的每個節(jié)點,

有向弧線從此節(jié)點指向此子訶題集合中的各個節(jié)點。

(5)在特殊情況下，當只有一個算件可應用于訶題A,而且

這個算符產生具有一個以上子問題的某個集合對，由上述規(guī)

則3和規(guī)則4所產生的圖可以得到簡化。

2.3謂詞迷科法

教學內容：本節(jié)主要講述問題的謂詞邏輯表示的基本方法。

教學重點：謂詞邏輯、謂詞公式、謂詞演算、置換與合一。

教學難點：如何選擇謂詞，問題的謂詞邏輯表示及運算。

教學方法：課堂教學為主，充分利用網絡課程中的示例程序。

教學要求：重點掌握謂詞邏輯表示的語言與方法，掌握謂詞

公式的性質及謂詞演算，學會謂詞公式的置換與合一，運用

謂詞推理來解決問題。

2.3.1謂詞演算

1.語法和語義

謂詞邏輯的基本組成部分是謂詞符號、變量符號、函數符號和常量符號，并用圓括弧、

方括弧、花括弧和逗號隔開，以表示論域內的關系。

原子公式是由若干謂詞符號和項組成，只有當其對應的語句在定義域內為真時，才具

有值T（真）；而當其對應的語句在定義域內為假時，該原子公式才具有值F（假）。

2.連詞和量詞

連詞有人（與）、V（或），全稱量詞（x）,存在量詞（x）o

原子公式是謂詞演算的基本積木塊，運用連詞能夠組合多個原子公式以構成比較復雜

的合適公式。

3.幾個有關定義

用連詞人把幾個公式連接起來而構成的公式叫做合取，而此合取式的每個組成部分叫

做合取項。一些合適公式所構成的任一合取也是一個合適公式。

用連詞V把幾個公式連接起來所構成的公式叫做析取，而此析取式的每一組成部分叫

做析取項。由一些合適公式所構成的任一析取也是一個合適公式。

用連詞=＞連接兩個公式所構成的公式叫做蘊涵。蘊涵的左式叫做前項，右式叫做后項。

如果前項和后項都是合適公式，那么蘊涵也是合適公式。

前面具有符號?的公式叫做否定。一個合適公式的否定也是合適公式。

量化一個合適公式中的某個變量所得到的表達式也是合適

公式。如果一個合適公式中某個支量是^過量化的，就把這

個變量叫做約束變量，否則就叫它為自由變量。在合適公式

中，感興起的主要是所有變量都是受約束的。這樣的合適公

式叫做句子。

2.3.2謂詞公式

i.謂詞合適公式的定義

在謂詞演算中合適公式的遞歸定義如下：

(D原子謂詞公式是合適公式。

(2)若A為合適公式，則?A也是一個合適公式。

(3)若A和B都是合適公式，則(A/\B),(AVB),(A=>B)和(A--B)也都是合適公式。

(4)若A是合適公式,x為A中的自由變元，則(乂認和(x)A都是合適公式。

(5)只有按上述規(guī)則⑴至(4)求得的那些公式，才是合適公式。

2.合適公式的性質

(1)否定之否定

?(?P)等價于P

(2)PVQ等價于?P=>Q

(3)狄?摩根定律

?(PVQ)等價于?PA?Q

?(P八Q)等價于?PV?Q

(4)分配律

PA(QVR)等價于(PAQ)V(PAR)

PV(QAR)等價于(PVQ)A(PVR)

(5)交換律

PAQ等價于QAP

PVQ等價于QVP

(6)結合律

(PAQ)AR等價于PA(QAR)

(PVQ)VR等價于PV(QVR)

(7)逆否律

P=>Q等價于?Q=>?P

此外，還可建立下列等價關系：

(8)?(3x)P(x)等價于(Vx)[?P(x)]

?(\/x)P(x)等價于(mx)[?P(x)]

(9)(Vx)[P(x)AQ(x)]等價于

(Vx)P(x)A(Vx)Q(xJ

(Vx)[P(x)VQ(x)]等價于

證明：否定之否定，，

(Vx)P(x)V(Vx)Q(x)

(?P)等價于P。

(10)(、x)P(x)等價于(Vy)P(y)_______________勿

(mx)P(x)等價于(my)P(y)

2.3.3JL換與合一

1.置換

假元推理，就是由合適公式W1和W1=>W2產生合適公式W2的運算。

全稱化推理，是由合適公式(x)W(x)產生合適公式W(A),其中A為任意常量符號。

一個表達式的置換就是在該表達式中用置換項置換變量。

一般說來，置換是可結合的，但置換是不可交換的。

2.合一

尋找項對變量的置換.以使兩表達式一致，叫做合一(unificalion)。如果一個置換s作用

于表達式集｛Ei｝的每個元素，則用｛Ei｝s來表示置換例的集。稱表達式集｛Ei｝是可合

一的。如果存在一個置換s使得：Els=E2s=E3sh??那么稱此s為｛臼｝的合一者，因為s的

作用是使集合｛Ei｝成為單一形式。

2.4語義網絡法

教學內容：本節(jié)主要講述知識的語義網絡表示法。

教學重點：語義網絡表示的詞法、結構、過程、語義。

教學難點：如何選擇節(jié)點和弧線來構成語義網絡。

教學方法：課堂教學。

教學要求：重點掌握語義網絡的結構，掌握二元語義網絡表

示方法，了解語義網絡的特點。

2.4.1二元語義網絡的表示

1.語義網絡的基本概念

語義網絡是知識的一種結構化圖解表示，它由節(jié)點和弧線或鏈線組成。節(jié)點用于表示實

體、概念和情況等，弧線用于表示節(jié)點間的關系。

語義網絡表示由下列4個相關部分組成：

(1)詞法部分決定表示詞匯表中允許有哪些符號，它涉及各個節(jié)點和弧線。

(2)結構部分敘述符號排列的約束條件，指定各弧線連接的節(jié)點對。

(3)過程部分說明訪問過程，這些過程能用來建立和修正描述，以及回答相關問題。

(4)語義部分確定與描述相關的(聯(lián)想)意義的方法即確定有關節(jié)點的排列及其占有物

和對應弧線。

語義網絡具有下列特點：

(1)能把實體的結構、屬性與實體間的因果關系顯式地和簡明地表達出來，與實體相關

的事實、特征和關系可以通過相應的節(jié)點弧線推導出來.

(2)由于與概念相關的屬性和聯(lián)系被組織在一個相應的節(jié)點中，因而使概念易于受訪和

學習。

(3)表現(xiàn)問題更加直觀，更易于理解，適于知識工程師與領域專家溝通。

2.(4)語義網絡結構的語義解釋依賴于該結構的推理過程而沒有結構的約定，因而得

到的推理不能保證像謂詞邏輯法那樣有效。

3.(5)節(jié)點間的聯(lián)系可能是線狀、樹狀或網狀的，甚至是遞歸狀的結構，使相應的知

識存儲和檢索可能需要比較復雜的過程。

4.二元語義網絡的表示

用兩個節(jié)點和一條弧線可以表示一個簡單的事實，對于表示占有關系的語義網絡，是通

過允許節(jié)點既可以表示一個物體或一組物體，也可以表示情況和動作。每一情況節(jié)點可以有

一組向外的弧(事例弧)，稱為事例框，用以說明與該事例有關的各種變量。

在選擇節(jié)點時，首先要弄清節(jié)點是用于表示基本的物體或概念的，或是用于多種目的的。否

則，如果語義網絡只被用來表示一個特定的物體或概念，那么當有更多的實例時就需要更多的語

義網絡。

選擇語義基元就是試圖用一組基元來表示知識。這些基元描述基本知識，并以圖解表示

的形式相互聯(lián)系。

2.4.2多元語義網絡的表示

語義網絡是一種網絡結構。節(jié)點之間以鏈相連。從本質上講，接點之間的連接是二元關系。

語義網絡從本質上來說，只能表示二元關系，如果所要表示的事實是多元關系，則把這個多元關

系轉化成一組二元關系的組合，或二元關系的合取。具體來說，多元關系R(X1,X2,…,Xn)總可

以轉換成RI(Xil,X12)AR2(X21,X22)A-ARn(Xnl,Xn2)o要在語義網絡中進行這種轉換需

要引入附加節(jié)點。

2.4.3連詞和量化的裊示

可以用語義網絡表示謂詞邏輯法中的各種連詞及量化。

1.合取

2.多元關系可以被轉換成一組二元關系的合取，從而可以用語義網絡的形式表示出

來。

3.析取

4.在語義網絡中，為與合取關系相區(qū)別，在析取關系的連接上加注析取界限，并標記

DISo

5.否定

采用?ISA和?PARTOF關系或標注NEG界限來表示否定。

6.蘊涵

在語義網絡中可用標注ANTE和CONSE界限來表示蘊涵關系。

7.量化

存在量化在語義網絡中可直接用ISA鏈來表示。而全稱最化就要用分割方法來表示。

2.5其他方法

教學內容：簡介知識表示的其他三種表示方法，即框架表示法、劇本表示法和過程表示

法，聞述了三種表示法的原理和應用范圍。

教學重點：各方法的基本原理及基本結構。

教學難點：各方法的推理過程。

教學方法：課堂教學為主。適當提問，加深學生對概念的理

解。

教學要求：初步了解三種方法的基本原理。

2.5.1罐舞

L框架的構成

框架通常由描述事物的各個方面的槽組成，每個槽可以擁有若干個側面，而每個側面又

可以擁有若干個值。一個框架的一般結構如下：

〈框架名）

〈槽1〉〈側面11）〈值111〉…

〈側面⑵〈值121）…

???

〈槽2〉〈側面2D〈值2⑴…

〈槽n〉《側面nD〈值nil）…

???

〈側面nm）〈值nmD…

較簡單的情景是用框架來表示諸如人和房子等事物。例如，一個人可以用其職業(yè)、身高

和體重等項描述，因而可以用這些項目組成框架的槽。當描述?個具體的人時，再用這些項

目的具體值填入到相應的槽中。表2.2給出的是描述John的框架。

表2.2簡單框架示例

JOHN

Isa:PERSON

Profession:PROGRAMMER

Height:1.8m

Weight:79kg

框架是一種通用的知識表達形式，對于如何運用框架系統(tǒng)還沒有一種統(tǒng)一的形式，常常

由各種問題的不同需要來決定。

2.框架的推理

(I)如前所述，框架是一種復雜結構的語義網絡。因此語義網絡推理中的匹配和特性繼

承在框架系統(tǒng)中也可以實行。除此以外，由于框架用于描述具有固定格式的事物、動作和事

件，因此可以在新的情況下，推論出未被觀察到的事實?？蚣苡靡韵聨追N途徑來幫助實現(xiàn)這

一點：

(2)框架包含它所描述的情況或物體的多方面的信息。

(3)框架包含物體必須具有的屬性。在填充框架的各個槽時，要用到這些屬性。

(4)框架描述它們所代表的概念的典型事例。

用一個框架來具體體現(xiàn)一個特定情況的過程，經常不是很順利的。但當這個過程碰到障

礙時，經常不必放棄原來的努力去從頭開始，而是有很多辦法可想的：

(1)選擇和當前情況相對應的當前的框架片斷，并把這個框架片斷和候補框架相匹配。

選擇最佳匹配。

(2)盡管當前的框架和要描述的情況之間有不相匹配的地方，但是仍然可以繼續(xù)應用這

個框架。

(3)查詢程東之間專門保存的錢，以提出應朝哪個方向進行

試探的爽權。

(4)沿著框架系統(tǒng)挑列的層次偌構向上移動(即從狗根務一

哺乳動物框架一動物框架)，直到找到一個足夠通用，并不與

已有事實矛盾的板架。

2.5.2劇本

劇本是框架的一種特殊形式，它用一組槽來描述某些事件的發(fā)生序列，就像劇本中的事

件序列一樣，故稱為“劇本”或腳本。

一個劇本一般由以下各部分組成：

(1)開場條件給出在劇本中描述的事件發(fā)生的前提條件。

(2)角色用來表示在劇本所描述的事件中可能出現(xiàn)的有關人物的一些槽。

(3)道具這是用來表示在劇本所描述的事件中可能出現(xiàn)的有關物體的一些槽。

(4)場景描述事件發(fā)生的真實順序，可以由多個場景組成，每個場景又可以是其它

的劇本。

(5)結果給出在劇本所描述的事件發(fā)生以后通常所產生的結果。

例子：以餐廳劇本為例說明劇本各個部分的組成。

根據劇本的重要性，可以有二種準備劇本的方法。

(1)對于不屬于事件核心部分的劇本，只需設置指向該劇本的指針即可，以便當它成為

核心時啟用。

(2)對于符合事件核心部分的劇本，則應使用在當前事件中涉及到的具體對象和人物去

填寫劇本的槽。劇本的前提、道具、角色和事件等常能起到啟用劇本的指示器的作用。

一旦劇本被啟用，則可以應用它來進行推理。其中錄重要的

是運用劇本可以預測沒有明顯提及的事件的發(fā)生。

劇本站構，比起修架這樣的一些通用轉構來，要呆板得多,

知盟表達的范崗也很幸，因此不適用于表達各種知鍍，但對

于表達預先構思好的特定知如理斛故事情節(jié)等，是非帶

有效的。

2.5.3過程

語義網絡、框架和劇本等知識表示方法，均是對知識和事實的一種靜止的表達方法，是

知識的?種顯式表達形式，而對于如何使用這些知識，則通過控制策略來決定。

和知識的陳述式疑示相對度的是知規(guī)的過程式表示。所謂過

程式表示就是將有關某一訶題領域的知識，連同如何使用這

些知板的方法，均障式地表達為一個求斛問題的過程。它所

給出的是事物的一些家見規(guī)律，表達的是如何求解問題。知

識的描述形式就是程序，所有信息均隱含在程序之中。從程

序求解問題的效率上來說，過程式表達要比陳述太表達志得

多。但因其知鎮(zhèn)均障舍在程序中，因而難于添加新知識和療

充功能，適用范圈較率。

2.6小結

知識表示方法很多，本章介紹了其中的7種，有圖示法和公式法，結構化方法，陳述式

表示和過程式表示等。

狀態(tài)空間法是一種基F解答空間的問題表示和求解方法，它是以狀態(tài)和操作符為基礎

的。在利用狀態(tài)空間圖表示時，從某個初始狀態(tài)開始，每次加一個操作符，遞增地建立起操

作符的試驗序列，直到達到目標狀態(tài)為止。由于狀態(tài)空間法需要擴展過多的節(jié)點，容易出現(xiàn)

“組合爆炸”，因而只適用于表示比較簡單的問題。

問題歸約法從目標（要解決的問題）出發(fā)，逆向推理，通過?系列變換把初始問題變換為

子問題集合和子子問題集合，直至最后歸約為一個平凡的本原問題集合。這些本原問題的解

可以直接得到從而解決了初始問題，用與或圖來有效地說明問題歸約法的求解途徑。問題歸

約法能夠比狀態(tài)空間法更有效地表示問題。狀態(tài)空間法是問題歸約法的一種特例。在問題歸

約法的與或圖中，包含有與節(jié)點和或節(jié)點，而在狀態(tài)空間法中只含有或節(jié)點。

謂詞邏輯法采用謂詞合適公式和一階謂詞演算把要解決的問題變?yōu)橐粋€有待證明的問

題，然后采用消解定理和消解反演來證明一個新語句是從已知的正確語句導出的，從而證明

這個新語句也是正確的。渭詞邏輯是一種形式語言，能夠把數學中的邏輯論證符號化。謂詞

邏輯法常與其它表示方法混合使用，靈活方便，可以表示比較復雜的問題。

語義網絡是一種結構化表示方法，它由節(jié)點和弧線或鏈線組成。節(jié)點用于表示物體、概

念和狀態(tài)，弧線用于表示節(jié)點間的關系。語義網絡的解答是一個經過推理和匹配而得到的具

有明確結果的新的語義網絡。語義網絡可用于表示多元關系，擴展后可以表示更復雜的問

題。

框架是一種結構化表示方法?？蚣芡ǔＳ芍付ㄊ挛锔鱾€方面的槽組成，每個槽擁有若干

個側面，而每個側面又可擁有若干個值。大多數實用系統(tǒng)必須同時使用許多框架，并可把它

們聯(lián)成一個框架系統(tǒng)?？蚣鼙硎疽勋@廣泛應用，然而并非所有問題都可以用框架表示。

劇本是框架的一種特殊形式，它使用一組槽來描述事件的發(fā)生序列。劇本表示特別適用

于描述順序性動作或事件.但使用不如框架靈活，因此應用范圍也不如框架那么廣泛。

過程是一種知識的過程式表示，它將某一有關問題領域知識同這些使用方法一起，隱式

地表示為一個問題求解過程。過程表示用程序來描述問題，具有很高的問題求解效率。由于

知識隱含在程序中難以操作，所以適用范圍較窄。

在表示和求解比較復雜的問題時，采用單一的知識表示方法是遠遠不夠的。往往必須采用多

種方法混合表示。例如，綜合采用框架、語義網絡、謂詞邏輯的過程表示方法（兩種以上），可

使所研究的問題獲得更有效的解決。

此外，在選擇知識表示方法時，還要考慮所使用的程序設計語言所提供的功能和特點，以便

能夠更好地描述這些表示