《人工智能》課程教案

《人工智能》課程教案《人工智能》課程教案

第一章緒論

教學內容：本章首先介紹人工智能的定義、進展概況及相關學派和他們的認知觀，接著爭論人工智能的討論和應用領域，最終簡介本書的主要內容和編排。

教學重點：1．從不同科學或學科動身對人工智能進展的定義；

2．介紹人工智能的起源與進展過程；

3．爭論人工智能與人類智能的關系；

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

5．簡介人工智能所討論的范圍與應用領域。

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

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

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

教學方法：課堂教學為主，充分利用網絡課程中的多媒體素材來表示抽象概念。

教學要求：重點把握人工智能的幾種定義，把握目前人工智能的三個主要學派及對人工智能的理解，一般了解人工智能的主要討論范圍和應用領域。

1.1人工智能的定義與進展

教學內容：本小節(jié)主要介紹目前對人工智能的幾種定義，并對人工智能的起源和進展進展了總結和分析。

教學重點：幾種人工智能的定義和人工智能進展的幾個重要時期。

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

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

教學要求：從學科和力量的角度深刻理解人工智能的定義，初步了解人工智能的起源及其進展過程。

1.1.1人工智能的定義

定義1智能機器

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

定義2人工智能(學科)

人工智能(學科)是計算機科學中涉及討論、設計和應用智能機器的一個分支。它的近期主要目標在于討論用機器來仿照和執(zhí)行人腦的某些智力功能，并開發(fā)相關理論和技術。

定義3人工智能(力量)

人工智能(力量)是智能機器所執(zhí)行的通常與人類智能有關的智能行為，如推斷、推理、證明、識別、感知、理解、通信、設計、思索、規(guī)劃、學習和問題求解等思維活動。

1

為了讓讀者對人工智能的定義進展爭論，以便更深刻地理解人工智能，下面綜述其它幾種關于人工智能的定義。

定義4人工智能是一種使計算機能夠思維，使機器具有智力的感動人心的新嘗試（Haugeland,1985）。

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

定義6人工智能是用計算模型討論智力行為（Charniak和McDermott,1985）。

定義7人工智能是討論那些使理解、推理和行為成為可能的計算（Winston,1992）。

定義8人工智能是一種能夠執(zhí)行需要人的智能的制造性機器的技術（Kurzwell,1990）。

定義9人工智能討論如何使計算機做事讓人過得更好（Rick和Knight,1991）。

定義10人工智能是一門通過計算過程力圖理解和仿照智能行為的學科（Schalkoff,1990）。

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

其中，定義4和定義5涉及擬人思維；定義6和定義7與理性思維有關；定義8和定義9涉及擬人行為；定義10和定義11與擬人理性行為有關。

1.1.2人工智能的起源與進展

人工智能的進展是以硬件與軟件為根底的，經受了漫長的進展歷程。特殊是20世紀30年月和40年月的智能界，發(fā)覺了兩件重要的事情：數理規(guī)律和關于計算的新思想。以維納（Wiener）、弗雷治、羅素等為代表對進展數理規(guī)律學科的奉獻及丘奇(Church)、圖靈和其它一些人關于計算本質的思想，為人工智能的形成產生了重要影響。

1956年夏季，人類歷史上第一次人工智能研討會在美國的達特茅斯(Dartmouth)大學進行，標志著人工智能學科的誕生。

1969年召開了第一屆國際人工智能聯(lián)合會議(InternationalJointConferenceonAI,IJCAI),此后每兩年召開一次。

1970年《人工智能》國際雜志(InternationalJournalofAI)創(chuàng)刊。這些對開展人工智能國際學術活動和溝通、促進人工智能的討論和進展起到積極作用。

了學問在人工智能中的地位。

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

究深入開展，形成高潮。同時，不同人工智能學派間的爭辯也特別熱鬧。

這些都推動人工智能討論的進一步進展。

1.2人類智能與人工智能

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

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

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

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

教學要求：了解人類認知活動與計算機的比擬關系，根本了解智能信息處理系統(tǒng)。

2

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

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

信息處理系統(tǒng)又叫符號操作系統(tǒng)(SymbolOperationSystem)或物理符號系統(tǒng)(PhysicalSymbolSystem)。所謂符號就是模式(pattern)。

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

(1)輸入符號(input)；

(2)輸出符號(output);

(3)存儲符號(store);

(4)復制符號(copy);

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

(6)條件性遷移(conditionaltransfer):依據已有符號，連續(xù)完成活動過程。

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

假如一個物理符號系統(tǒng)具有上述全部6種功能，能夠完成這個全過程，那么它就是一個完整的物理符號系統(tǒng)。人具有上述6種功能；現代計算機也具備物理符號系統(tǒng)的這6種功能。

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

任何一個系統(tǒng)，假如它能表現出智能，那么它就必定能夠執(zhí)行上述6種功能。反之，任何系統(tǒng)假如具有這6種功能，那么它就能夠表現出智能；這種智能指的是人類所具有的那種智能。把這個假設稱為物理符號系統(tǒng)的假設。

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

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

推論二既然計算機是一個物理符號系統(tǒng)，它就肯定能夠表現出

智能。這是人工智能的根本條件。

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

系統(tǒng)，那么就能夠用計算機來模擬人的活動。

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

認知生理學討論認知行為的生理過程，主要討論人的神經系統(tǒng)（神經元、中樞神經系統(tǒng)和大腦）的活動，是認知科學討論的底層。

認知心理學討論認知行為的心理活動，主要討論人的思維策略，是認知科學討論的頂層。

認知信息學討論人的認知行為在人體內的初級信息處理，主要討論人的認知行為如何通過初級信息自然處理，由生理活動變?yōu)樾睦砘顒蛹捌淠孢^程，即由心理活動變?yōu)樯硇袨?。這是認知活動的中間層，承上啟下。

認知工程學討論認知行為的信息加工處理，主要討論如何通過以計算機為中心的人工信息處理系統(tǒng)，對人的各種認知行為（如知覺、思維、記憶、語言、學習、理解、推理、識別等）進展信息處理。這是討論認知科學和認知行為的工具，應成為現代認知心理學和現代認知生理學的重要討論手段。

1.2.2人類智能的計算機模擬

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

3

物理符號系統(tǒng)假設的推論一告知人們，人有智能，所以他是一個物理符號系統(tǒng)；推論三指出，可以編寫出計算機程序去模擬人類的思維活動。這就是說，人和計算機這兩個物理符號系統(tǒng)所使用的物理符號是一樣的，因而計算機可以模擬人類的智能活動過程。

2、智能計算機的功能

(neuralcomputer)能夠以類似人類的方式進展“思索”，它力圖重建人

腦的形象。一些國家對量子計算機的討論也已起步，盼望通過對量子

計算(quantumcomputing)的討論，產生量子計算機。

1.3人工智能的學派

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

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

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

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

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

1、人工智能三大學派

·符號主義(Symbolicism)，又稱為規(guī)律主義(Logicism)、心理學派(Psychlogism)或計算機學派(Computerism)，其原理主要為物理符號系統(tǒng)(即符號操作系統(tǒng))假設和有限合理性原理。

·聯(lián)結主義(Connectionism)，又稱為仿生學派(Bionicsism)或生理學派(Physiologism)，其原理主要為神經網絡及神經網絡間的連接機制與學習算法。

·行為主義(Actionism)，又稱進化主義(Evolutionism)或掌握論學派(Cyberneticsism)，其原理為掌握論及感知—動作型掌握系統(tǒng)。

2、三大學派對人工智能進展歷史的不同看法

符號主義認為人工智能源于數理規(guī)律。符號主義仍舊是人工智能的主流派。這個學派的代表有紐厄爾、肖、西蒙和尼爾遜(Nilsson)等。

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

行為主義認為人工智能源于掌握論。這一學派的代表作首推布魯克斯(Brooks)的六足行走機器人，它被看做新一代的“掌握論動物”，是一個基于感知—動作模式的模擬昆蟲行為的掌握系統(tǒng)。

1.4人工智能的討論與應用領域

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

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

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

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

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

4

1.4.1問題求解

人工智能的第一個大成就是進展了能夠求解難題的下棋(如國際象棋)程序，它包含問題的表示、分解、搜尋與歸約等。

1.4.2規(guī)律推理與定理證明

規(guī)律推理是人工智能討論中最長久的子領域之一，特殊重要的是要找到一些方法，只把留意力集中在一個大型數據庫中的有關事實上，留意可信的證明，并在消失新信息時適時修正這些證明。

定理證明的討論在人工智能方法的進展中曾經產生過重要的影響。例如，采納謂詞規(guī)律語言的演繹過程的形式化有助于更清晰地理解推理的某些子命題。很多非形式的工作，包括醫(yī)療診斷和信息檢索都可以和定理證明問題一樣加以形式化。因此，在人工智能方法的討論中定理證明是一個極其重要的論題。

我國人工智能大師吳文俊院士提出并實現了幾何定理機器證明的方法，被國際上成認為“吳氏方法”，是定理證明的又一標志性成果。

1.4.3自然語言理解

語言處理也是人工智能的早期討論領域之一，并引起了進一步的重視。語言的生成和理解是一個極為簡單的編碼和解碼問題。

一個能理解自然語言信息的計算機系統(tǒng)看起來就像一個人一樣需要有上下文學問以及依據這些上下文學問和信息用信息發(fā)生器進展推理的過程。理解口頭的和書寫語言的計算機系統(tǒng)所取得的某些進展，其根底就是有關表示上下文學問構造的某些人工智能思想以及依據這些學問進展推理的某些技術。

1.4.4自動程序設計

對自動程序設計的討論不僅可以促進半自動軟件開發(fā)系統(tǒng)的進展，而且也使通過修正自身數碼進展學習(即修正它們的性能)的人工智能系統(tǒng)得到進展。程序理論方面的有關討論工作對人工智能的全部討論工作都是很重要的。

自動程序設計討論的重大奉獻之一是作為問題求解策略的調整概念。已經發(fā)覺，對程序設計或機器人掌握問題，先產生一個不費事的有錯誤的解，然后再修改它(使它正確工作)，這種做法一般要比堅持要求第一個解就完全沒有缺陷的做法有效得多。

1.4.5專家系統(tǒng)

一般地說，專家系統(tǒng)是一個智能計算機程序系統(tǒng)，其內部具有大量專家水平的某個領域學問與閱歷，能夠利用人類專家的學問和解決問題的方法來解決該領域的問題。

進展專家系統(tǒng)的關鍵是表達和運用專家學問，即來自人類專家的并已被證明對解決有關領域內的典型問題是有用的事實和過程。

5

1.4.6機器學習

學習是人類智能的主要標志和獲得學問的根本手段；機器學習(自動獵取新的事實及新的推理算法)是使計算機具有智能的根本途徑；機器學習還有助于發(fā)覺人類學習的機理和提醒人腦的神秘。學習是一個有特定目的的學問獵取過程，其內部表現為新學問構造的不斷建立和修改，而外部表現為性能的改善。

1.4.7神經網絡

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

神經網絡已在模式識別、圖象處理、組合優(yōu)化、自動掌握、信息處理、機器人學和人工智能的其它領域獲得日益廣泛的應用。

1.4.8機器人學

人工智能討論日益受到重視的另一個分支是機器人學，其中包括對操作機器人裝置程序的討論。這個領域所討論的問題，從機器人手臂的最正確移動到實現機器人目標的動作序列的規(guī)劃方法，無所不包。目前已經建立了一些比擬簡單的機器人系統(tǒng)。

機器人和機器人學的討論促進了很多人工智能思想的進展。

智能機器人的討論和應用表達出廣泛的學科穿插，涉及眾多的課題，機器人已在各領域獲得越來越普遍的應用。

1.4.9模式識別

人工智能所討論的模式識別是指用計算機代替人類或幫忙人類感知模式，是對人類感知外界功能的模擬，討論的是計算機模式識別系統(tǒng)，也就是使一個計算機系統(tǒng)具有模擬人類通過感官承受外界信息、識別和理解四周環(huán)境的感知力量。

1.4.10機器視覺

試驗說明，人類承受外界信息的80%以上來自視覺，視覺對人類是特別重要的。

機器視覺或計算機視覺已從模式識別的一個討論領域進展為一門獨立的學科；在視覺方面，已經給計算機系統(tǒng)裝上電視輸入裝置以便能夠“觀察”四周的東西。

機器視覺的前沿討論領域包括實時并行處理、主動式定性視覺、動態(tài)和時變視覺、三維景物的建模與識別、實時圖像壓縮傳輸和復原、多光譜和彩色圖像的處理與解釋等。

1.4.11智能掌握

人工智能的進展促進自動掌握向智能掌握進展。智能掌握是一類無需(或需要盡可能少的)人的干預就能夠獨立地驅動智能機器實現其目標的自動掌握。

6

智能掌握是同時具有以學問表示的非數學廣義世界模型和數學公式模型表示的混合掌握過程，也往往是含有簡單性、不完全性、模糊性或不確定性以及不存在已知算法的非數學過程，并以學問進展推理，以啟發(fā)來引導求解過程。

1.4.12智能檢索

隨著科學技術的快速進展，消失了“學問爆炸”的狀況，討論智能檢索系統(tǒng)已成為科技持續(xù)快速進展的重要保證。

智能信息檢索系統(tǒng)的設計者們將面臨以下幾個問題。首先，建立一個能夠理解以自然語言陳述的詢問系統(tǒng)本身就存在不少問題。其次，即使能夠通過規(guī)定某些機器能夠理解的形式化詢問語句來回避語言理解問題，但仍舊存在一個如何依據存儲的事實演繹出答案的問題。第三，理解詢問和演繹答案所需要的學問都可能超出該學科領域數據庫所表示的學問。

1.4.13智能調度與指揮

確定最正確調度或組合的問題是人們感興趣的又一類問題，求解這類問題的程序會產生一種組合爆炸的可能性，這時，即使是大型計算機的容量也會被用光。

人工智能學家們曾經討論過若干組合問題的求解方法。他們的努力集中在使“時間-問題大小”曲線的變化盡可能緩慢地增長，即使是必需按指數方式增長。有關問題域的學問再次成為比擬有效的求解方法的關鍵。為處理組合問題而進展起來的很多方法對其它組合上不甚嚴峻的問題也是有用的。

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)更能表達人類的社會智能，具有更大的敏捷性和適應性，更適合開放和動態(tài)的世界環(huán)境，因而倍受重視，已成為人工智能以至計算機科學和掌握科學與工程的討論熱點。

1.4.15計算智能與進化計算

計算智能(ComputingIntelligence)涉及神經計算、模糊計算、進化計算等討論領域。

進化計算(EvolutionaryComputation)是指一類以達爾文進化論為依據來設計、掌握和優(yōu)化人工系統(tǒng)的技術和方法的總稱，它包括遺傳算法(GeneticAlgorithms)、進化策略(EvolutionaryStrategies)和進化規(guī)劃(EvolutionaryProgramming)。

7

1.4.16數據挖掘與學問發(fā)覺

學問獵取是學問信息處理的關鍵問題之一。

數據挖掘是通過綜合運用統(tǒng)計學、粗糙集、模糊數學、機器學習和專家系統(tǒng)等多種學習手段和方法，從大量的數據中提煉出抽象的學問，從而提醒出蘊涵在這些數據背后的客觀世界的內在聯(lián)系和本質規(guī)律，實現學問的自動獵取。

數據挖掘和學問發(fā)覺技術已獲廣泛應用。

1.4.17人工生命

人工生命(ArtificialLife,ALife)旨在用計算機和周密機械等人工媒介生成或構造出能夠表現自然生命系統(tǒng)行為特征的仿真系統(tǒng)或模型系統(tǒng)。自然生命系統(tǒng)行為具有自組織、自復制、自修復等特征以及形成這些特征的混沌動力學、進化和環(huán)境適應。

人工生命所討論的人造系統(tǒng)能夠演示具有自然生命系統(tǒng)特征的行為，在“生命之所能”(lifeasitcouldbe)的寬闊范圍內深入討論“生命之所知”(lifeasweknowit)的實質。

人工生命學科的討論內容包括生命現象的仿生系統(tǒng)、人工建模與仿真、進化動力學、人工生命的計算理論、進化與學習綜合系統(tǒng)以及人工生命的應用等。

1.4.18系統(tǒng)與語言工具

除了直接瞄準實現智能的討論工作外，開發(fā)新的方法也往往是人工智能討論的一個重要方面。人工智能對計算機界的某些最大奉獻已經以派生的形式表現出來。計算機系統(tǒng)的一些概念，如分時系統(tǒng)、編目處理系統(tǒng)和交互調試系統(tǒng)等，已經在人工智能討論中得到進展。

1.5本書概要

本書包括以下內容：

1、簡述人工智能的起源與進展，爭論人工智能的定義、人工智能與計算機的關系以及人工智能的討論和應用領域。

2、比擬概括地論述學問表示的各種主要方法，包括狀態(tài)空間法、問題歸約法、謂詞規(guī)律法、構造化表示法（語義網絡法、框架）、劇本和過程等。

3、爭論常用搜尋原理，如盲目搜尋、啟發(fā)式搜尋和消解原理等；并討論一些比擬高級的推理求解技術，如規(guī)章演繹系統(tǒng)、專家系統(tǒng)、系統(tǒng)組織技術、不確定性推理和非單調推理等。

4、介紹近期進展起來的已成為當前討論熱點的人工智能技術和方法，即分布式人工智能與agent、計算智能（含神經計算、規(guī)律計算與進化計算）、數據挖掘與學問發(fā)覺、人工生命等。

5、比擬具體地分析人工智能的主要應用領域，涉及專家系統(tǒng)、機器學習、自動規(guī)劃系統(tǒng)和自然語言理解等。

6、表達近年來人工智能討論中消失的爭辯，展望人工智能的進展。

8

1.6辯論會

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

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

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

9

其次章學問表示方法

教學內容：本章爭論學問表示的各種方法，是人工智能課程三大內容（學問表示、學問推理、學問應用）之一，也是學習人工智能其他內容的根底。

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

教學難點：狀態(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問題狀態(tài)描述

1、狀態(tài)（State）的根本概念

狀態(tài)(state)是為描述某類不同事物間的差異而引入的一組最少變量q0，q1，…，qn的有序集合，其矢量形式如下：

Q=［q0,q1,…,qn］T(2.1)

式中每個元素qi(i=0,1，…，n)為集合的重量，稱為狀Array態(tài)變量。給定每個重量的一組值就得到一個詳細的狀態(tài)，

如

Qk=［q０k,q1k,…，qnk］T(2.2)

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

為操作符或算符。操作符可為走步、過程、規(guī)章、數學算

子、運算符號或規(guī)律符號等。

問題的狀態(tài)空間(statespace)是一個表示該問題全部

可能狀態(tài)及其關系的圖，它包含三種說明的集合，即全部

可能的問題初始狀態(tài)集合S、操作符集合F以及目標狀態(tài)

集合G。因此，可把狀態(tài)空間記為三元狀態(tài)(S，F，G)。

10

112、狀態(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é)點序列(ni1,ni2,…,nik)當j=2，3，…，k時，假如對于每一個ni，j-1都有一個后繼節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)

點nik的長度為k的路徑。代價(cost)是給各弧線指定數值以表示加在相應算符上的代價。圖的顯式說明是指各節(jié)點及其具有代價的弧線由一張說明確給出。圖的隱式說明是指各節(jié)點及其具有代價的弧線不

能由一張說明確給出。

2.1.3狀態(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=1；否則取x=0；Y—箱子的水平位置；z—當猴子摘到香蕉時取z=1；否則取z=0。

算符

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

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

（3）climbbox猴子爬上箱頂；

（4）grasp猴子摘到香蕉。

12

求解過程令初始狀態(tài)為(a,0,b,0)。這時，goto(U)是唯一

適用的操作，并導致下一狀態(tài)(U，0，b,0)?，F在有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)橐粋€子問題集合；這些子問題的解可以直接得到，從而解決了初始問題的方法。

教學重點：問題歸約的根本思想，問題描述，問題變換的操作符，與或圖表示。教學難點：如何把初始問題變換為子問題，與或圖表示方法。

教學方法：課堂教學為主，充分利用網絡課程中的相關多媒體素材來表示抽象概念。教學要求：通過梵塔難題重點把握問題歸約法的機理和問題歸約描述方法。學會用與或圖表示歸約問題。

2.2.1問題歸約描述

1、問題歸約法的概念

已知問題的描述，通過一系列變換把此問題最終變?yōu)橐粋€子問題集合；這些子問題的解可以直接得到，從而解決了初始問題。

該方法也就是從目標(要解決的問題)動身逆向推理，建立子問題以及子問題的子問題，直至最終把初始問題歸約為一個平凡的本原問題集合。這就是問題歸約的實質。

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的雙圓盤難題。由上可以看出簡化了難題每一個都比原始難題簡單，所以問題都會變成易解的本原問題。

134、歸約描述

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

可以用狀態(tài)空間表示的三元組合(S、F、G)來規(guī)定與描述問題；對于梵塔問題，子問題［（111）=>(122)］，［(122)=>(322)］以及［(322)=>(333)］規(guī)定了最終解答路徑將要通過的腳踏石狀態(tài)(122)和(322)。

問題歸約方法可以應用狀態(tài)、算符和目標這些表示法來描述問題，這并不意味著問題歸約法和狀態(tài)空間法是一樣的。

2.2.2與或圖表示

1、與或圖的概念

用一個類似圖的構造來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。例如，設想問題A需要由求解問題B、C和D來打算，那么可以用一個與圖來表示；同樣，一個問題A或者由求解問題B、或者由求解問題C來打算，則可以用一個或圖來表示。

2、與或圖的有關術語

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

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

或節(jié)點只要解決某個問題就可解決其父輩問題的節(jié)點集合；與節(jié)點只有解決全部子問題，才能解決其父輩問題的節(jié)點集合；弧線是父輩節(jié)點指向子節(jié)點的圓弧連線；

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

3、與或圖的有關定義

可解節(jié)點與或圖中一個可解節(jié)點的一般定義可以歸納如下：(1)終葉節(jié)點是可解節(jié)點(由于它們與本原問題相關連)。(2)假如某個非終葉節(jié)點含有或后繼節(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謂詞規(guī)律法

教學內容：本節(jié)主要敘述問題的謂詞規(guī)律表示的根本方法。

教學重點：謂詞規(guī)律、謂詞公式、謂詞演算、置換與合一。

教學難點：如何選擇謂詞，問題的謂詞規(guī)律表示及運算。

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

教學要求：重點把握謂詞規(guī)律表示的語言與方法，把握謂詞公式的性質及謂詞演算，學會謂詞公式的置換與合一，運用謂詞推理來解決問題。

2.3.1謂詞演算

1、語法和語義

謂詞規(guī)律的根本組成局部是謂詞符號、變量符號、函數符號和常量符號，并用圓括弧、方括弧、花括弧和逗號隔開，以表示論域內的關系。

原子公式是由若干謂詞符號和項組成，只有當其對應的語句在定義域內為真時，才具有值T(真)；而當其對應的語句在定義域內為假時，該原子公式才具有值F(假)。

2、連詞和量詞

連詞有∧(與)、∨(或)，全稱量詞(?x)，存在量詞(?x)。

原子公式是謂詞演算的根本積木塊，運用連詞能夠組合多個原子公式以構成比擬簡單的適宜公式。

3、幾個有關定義

用連詞∧把幾個公式連接起來而構成的公式叫做合取，而此合取式的每個組成局部叫做合取項。一些適宜公式所構成的任一合取也是一個適宜公式。

用連詞∨把幾個公式連接起來所構成的公式叫做析取，而此析取式的每一組成局部叫做析取項。由一些適宜公式所構成的任一析取也是一個適宜公式。

用連詞=>連接兩個公式所構成的公式叫做蘊涵。蘊涵的左式叫做前項，右式叫做后項。假如前項和后項都是適宜公式，那么蘊涵也是適宜公式。

前面具有符號～的公式叫做否認。一個適宜公式的否認也是適宜公式。

量化一個適宜公式中的某個變量所得到的表達式也是適宜公式。假如一個適宜公式中某個變量是經過量化的，就把這個變量叫做約束變量，否則就叫它為自由變量。在適宜公式中，感興趣的主要是全部變量都是受約束的。這樣的適宜公式叫做句子。

14

152.3.2謂詞公式

1、謂詞適宜公式的定義

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

(1)原子謂詞公式是適宜公式。

(2)若A為適宜公式，則～A也是一個適宜公式。(3)若A和B都是適宜公式，則(A∧B)，(A∨B)，(A=>B)和(A←→B)也都是適宜公式。

(4)若A是適宜公式，x為A中的自由變元，則(?x)A和(?x)A都是適宜公式。

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

2、適宜公式的性質

(1)否認之否認

～(～P)等價于P

(2)P∨Q等價于～P=>Q

(3)狄·摩根定律

～(P∨Q)等價于～P∧～Q

～(P∧Q)等價于～P∨～Q

(4)安排律

P∧(Q∨R)等價于(P∧Q)∨(P∧R)

P∨(Q∧R)等價于(P∨Q)∧(P∨R)

(5)交換律

P∧Q等價于Q∧P

P∨Q等價于Q∨P

(6)結合律

(P∧Q)∧R等價于P∧(Q∧R)

(P∨Q)∨R等價于P∨(Q∨R)

(7)逆否律

P=>Q等價于～Q=>～P

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

(8)～(?x)P(x)等價于(?x)［～P(x)］

～(?x)P(x)等價于(?x)［～P(x)］

(9)(?x)［P(x)∧Q(x)］等價于

(?x)P(x)∧(?x)Q(x)

(?x)［P(x)∨Q(x)］等價于(?x)P(x)∨(?x)Q(x)(10)(?x)P(x)等價于(?y)P(y)

(?x)P(x)等價于(?y)P(y)

2.3.3置換與合一

1、置換

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

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

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

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

2、合一

(unification)。假如一個置換s作用于表達式集｛Ei｝的每個

元素，則用｛Ei｝s來表示置換例的集。稱表達式集｛Ei｝

是可合一的。假如存在一個置換s使得：E1s=E2s=E3s=…那

么稱此s為｛Ei｝的合一者，由于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)表現問題更加直觀，更易于理解，適于學問工程師與領域專家溝通。

16

17(4)語義網絡構造的語義解釋依靠于該構造的推理過程而沒有構造的商定，因而得到的推理不能保證像謂詞規(guī)律法那樣有效。

(5)節(jié)點間的聯(lián)系可能是線狀、樹狀或網狀的，甚至是遞歸狀的構造，使相應的學問存儲和檢索可能需要比擬簡單的過程。

2．二元語義網絡的表示

用兩個節(jié)點和一條弧線可以表示一個簡潔的事實，對于表示占有關系的語義網絡，是通過允許節(jié)點既可以表示一個物體或一組物體，也可以表示狀況和動作。每一狀況節(jié)點可以有一組向外的弧(事例弧)，稱為事例框，用以說明與該事例有關的各種變量。

在選擇節(jié)點時，首先要弄清節(jié)點是用于表示根本的物體或

概念的，或是用于多種目的的。否則，假如語義網絡只被用來表示一個特定的物體或概念，那么當有更多的實例時就需要更多的語義網絡。選擇語義基元就是試圖用一組基元來表示學問。這些基元描述根本學問，并以圖解表示的形式相互聯(lián)系。

2.4.2多元語義網絡的表示

語義網絡是一種網絡構造。節(jié)點之間以鏈相連。從本質上

講，接點之間的連接是二元關系。語義網絡從本質上來說，只

能表示二元關系，假如所要表示的事實是多元關系，則把這個

多元關系轉化成一組二元關系的組合，或二元關系的合取。具

體來說，多元關系R(X1，X2，…，Xn)總可以轉換成R1(X11，

X12)∧R2(X21，X22)∧…∧Rn(Xn1,Xn2)。要在語義網絡中進展

這種轉換需要引入附加節(jié)點。

2.4.3連詞和量化的表示

可以用語義網絡表示謂詞規(guī)律法中的各種連詞及量化。

1．合取

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

2．析取

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

3．否認

采納～ISA和～PARTOF關系或標注NEG界限來表示否認。

4．蘊涵

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

5．量化

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

2.5其他方法

教學內容：簡介學問表示的其他三種表示方法，即框架表示法、劇本表示法和過程表示法，闡述了三種表示法的原理和應用范圍。

教學重點：各方法的根本原理及根本構造。

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

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

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

2.5.1框架

1、框架的構成

框架通常由描述事物的各個方面的槽組成，每個槽可以擁有若干個側面，而每個側面又可以擁有若干個值。一個框架的一般構造如下：

〈框架名〉

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

〈側面12〉〈值121〉…

…

〈槽2〉〈側面21〉〈值211〉…

…

…

〈槽n〉〈側面n1〉〈值n11〉…

…

〈側面nm〉〈值nm1〉…

較簡潔的情景是用框架來表示諸如人和房子等事物。例如，一個人可以用其職業(yè)、身高和體重等項描述，因而可以用這些工程組成框架的槽。當描述一個詳細的人時，再用這些工程的詳細值填入到相應的槽中。表2.2給出的是描述John的框架。

表2.2簡潔框架例如

JOHN

Isa:PERSON

Profession:PROGRAMMER

Height:1.8m

Weight:79kg

框架是一種通用的學問表達形式，對于如何運用框架系統(tǒng)還沒有一種統(tǒng)一的形式，經常由各種問題的不同需要來打算。

2、框架的推理

如前所述，框架是一種簡單構造的語義網絡。因此語義網絡推理中的匹配和特性繼承在框架系統(tǒng)中也可以實行。除此以外，由于框架用于描述具有固定格式的事物、動作和大事，因此可以在新的狀況下，推論出未被觀看到的事實?？蚣苡靡韵聨追N途徑來幫忙實現這一點：

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

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

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

18

用一個框架來詳細表達一個特定狀況的過程，常常不是很順當的。但當這個過程遇到障礙時，常常不必放棄原來的努力去從頭開頭，而是有許多方法可想的：

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

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

(3)查詢框架之間特地保存的鏈，以提出應朝哪個方向進展摸索的建議。

(4)沿著框架系統(tǒng)排列的層次構造向上移動(即從狗框架→哺乳動物框架→動物框架)，直到找到一個足夠通用，并不與已有事實沖突的框架。

2.5.2劇本

劇本是框架的一種特別形式，它用一組槽來描述某些大事的發(fā)生序列，就像劇本中的大事序列一樣，故稱為“劇本”或腳本。

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

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

(2)角色用來表示在劇本所描述的大事中可能消失的有關人物的一些槽。

(3)道具這是用來表示在劇本所描述的大事中可能消失的有關物體的一些槽。

(4)場景描述大事發(fā)生的真實挨次，可以由多個場景組成，每個場景又可以是其它的劇本。

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

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

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

(1)對于不屬于大事核心局部的劇本，只需設置指向該劇本的指針即可，以便當它成為核心時啟用。

(2)對于符合大事核心局部的劇本，則應使用在當前大事中涉及到的詳細對象和人物去填寫劇本的槽。劇本的前提、道具、角色和大事等常能起到啟用劇本的指示器的作用。

一旦劇本被啟用，則可以應用它來進展推理。其中最重要的是運用劇本可以猜測沒有明顯提及的大事的發(fā)生。

劇本構造，比起框架這樣的一些通用構造來，要呆板得多，學問表達的范圍也很窄，因此不適用于表達各種學問，但對于表達預先構思好的特定學問，如理解故事情節(jié)等，是特別有效的。

2.5.3過程

語義網絡、框架和劇本等學問表示方法，均是對學問和事實的一種靜止的表達方法，是學問的一種顯式表達形式。而對于如何使用這些學問，則通過掌握策略來打算。

和學問的陳述式表示相對應的是學問的過程式表示。所謂過程式表示就是將有關某一問題領域的學問，連同如何使用這些學問的方法，均隱式地表達為一個求解問題的過程。它所給出的是事物的一些客觀規(guī)律，表達的是如何求解問題。學問的描述形式就是程序，全部信息均隱含在程序之中。從程序求解問題的效率上來說，過程式表達要比陳述式表達高得多。但因其學問均隱含在程序中，因而難于添加新學問和擴大功能，適用范圍較窄。

19

2.6小結

學問表示方法許多，本章介紹了其中的7種，有圖示法和公式法，構造化方法，陳述式表示和過程式表示等。

狀態(tài)空間法是一種基于解答空間的問題表示和求解方法，它是以狀態(tài)和操作符為根底的。在利用狀態(tài)空間圖表示時，從某個初始狀態(tài)開頭，每次加一個操作符，遞增地建立起操作符的試驗序列，直到到達目標狀態(tài)為止。由于狀態(tài)空間法需要擴展過多的節(jié)點，簡單消失“組合爆炸”，因而只適用于表示比擬簡潔的問題。

問題歸約法從目標(要解決的問題)動身，逆向推理，通過一系列變換把初始問題變換為子問題集合和