《人工智能》課程教案

PAGEPAGE131《人工智能》課程教案第一章緒論教學(xué)內(nèi)容:本章首先介紹人工智能的定義、發(fā)展概況及相關(guān)學(xué)派和他們的認(rèn)知觀,接著討論人工智能的研究和應(yīng)用領(lǐng)域,最后簡介本書的主要內(nèi)容和編排。教學(xué)重點:1.從不同科學(xué)或?qū)W科出發(fā)對人工智能進(jìn)行的定義；2.介紹人工智能的起源與發(fā)展過程；3.討論人工智能與人類智能的關(guān)系；4.簡介目前人工智能的主要學(xué)派；5.簡介人工智能所研究的范圍與應(yīng)用領(lǐng)域。教學(xué)難點:1.怎么樣理解人工智能；2.人工智能作為一門學(xué)科有什么意義；3.人工智能的主要學(xué)派與其爭論焦點；教學(xué)方法:課堂教學(xué)為主,充分利用網(wǎng)絡(luò)課程中的多媒體素材來表示抽象概念。教學(xué)要求：重點掌握人工智能的幾種定義,掌握目前人工智能的三個主要學(xué)派及對人工智能的理解,一般了解人工智能的主要研究范圍和應(yīng)用領(lǐng)域。1.1人工智能的定義與發(fā)展教學(xué)內(nèi)容:本小節(jié)主要介紹目前對人工智能的幾種定義,并對人工智能的起源和發(fā)展進(jìn)行了總結(jié)和分析。 教學(xué)重點:幾種人工智能的定義和人工智能發(fā)展的幾個重要時期。教學(xué)難點:理解人工智能的定義與本質(zhì)。教學(xué)方法:課堂講授為主。教學(xué)要求：從學(xué)科和能力的角度深刻理解人工智能的定義,初步了解人工智能的起源及其發(fā)展過程。1.1.1人工智能的定義定義1智能機(jī)器能夠在各類環(huán)境中自主地或交互地執(zhí)行各種擬人任務(wù)(anthropomorphictasks)的機(jī)器。定義2人工智能(學(xué)科)人工智能(學(xué)科)是計算機(jī)科學(xué)中涉及研究、設(shè)計和應(yīng)用智能機(jī)器的一個分支。它的近期主要目標(biāo)在于研究用機(jī)器來模仿和執(zhí)行人腦的某些智力功能,并開發(fā)相關(guān)理論和技術(shù)。定義3人工智能(能力)人工智能(能力)是智能機(jī)器所執(zhí)行的通常與人類智能有關(guān)的智能行為,如判斷、推理、證明、識別、感知、理解、通信、設(shè)計、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動。為了讓讀者對人工智能的定義進(jìn)行討論,以便更深刻地理解人工智能,下面綜述其它幾種關(guān)于人工智能的定義。定義4人工智能是一種使計算機(jī)能夠思維,使機(jī)器具有智力的激動人心的新嘗試（Haugeland,1985）。定義5人工智能是那些與人的思維、決策、問題求解和學(xué)習(xí)等有關(guān)活動的自動化（Bellman,1978）。定義6人工智能是用計算模型研究智力行為（Charniak和McDermott,1985）。定義7人工智能是研究那些使理解、推理和行為成為可能的計算（Winston,1992）。定義8人工智能是一種能夠執(zhí)行需要人的智能的創(chuàng)造性機(jī)器的技術(shù)（Kurzwell,1990）。定義9人工智能研究如何使計算機(jī)做事讓人過得更好（Rick和Knight,1991）。定義10人工智能是一門通過計算過程力圖理解和模仿智能行為的學(xué)科（Schalkoff,1990）。定義11人工智能是計算機(jī)科學(xué)中與智能行為的自動化有關(guān)的一個分支（Luger和Stubblefield,1993）。其中,定義4和定義5涉及擬人思維；定義6和定義7與理性思維有關(guān)；定義8和定義9涉及擬人行為；定義10和定義11與擬人理性行為有關(guān)。1.1.2人工智能的起源與發(fā)展人工智能的發(fā)展是以硬件與軟件為基礎(chǔ)的,經(jīng)歷了漫長的發(fā)展歷程。特別是20世紀(jì)30年代和40年代的智能界,發(fā)現(xiàn)了兩件重要的事情:數(shù)理邏輯和關(guān)于計算的新思想。以維納（Wiener）、弗雷治、羅素等為代表對發(fā)展數(shù)理邏輯學(xué)科的貢獻(xiàn)及丘奇(Church)、圖靈和其它一些人關(guān)于計算本質(zhì)的思想,為人工智能的形成產(chǎn)生了重要影響。1956年夏季,人類歷史上第一次人工智能研討會在美國的達(dá)特茅斯(Dartmouth)大學(xué)舉行,標(biāo)志著人工智能學(xué)科的誕生。1969年召開了第一屆國際人工智能聯(lián)合會議(InternationalJointConferenceonAI,IJCAI),此后每兩年召開一次。提問：為什么人工智能在1956年才正式誕生？提問：為什么人工智能在1956年才正式誕生？20世紀(jì)70～80年代,知識工程的提出與專家系統(tǒng)的成功應(yīng)用,確定了知識在人工智能中的地位。近十多年來,機(jī)器學(xué)習(xí)、計算智能、人工神經(jīng)網(wǎng)絡(luò)等和行為主義的研究深入開展,形成高潮。同時,不同人工智能學(xué)派間的爭論也非常熱烈。這些都推動人工智能研究的進(jìn)一步發(fā)展。1.2人類智能與人工智能教學(xué)內(nèi)容:本節(jié)主要討論人類智能與人工智能的關(guān)系問題。教學(xué)重點：智能信息處理系統(tǒng),人類智能與人工智能的關(guān)系。教學(xué)難點:智能信息處理系統(tǒng)的假設(shè)。教學(xué)方法:課堂講授為主。教學(xué)要求：了解人類認(rèn)知活動與計算機(jī)的比較關(guān)系,基本了解智能信息處理系統(tǒng)。1.2.1智能處理信息系統(tǒng)的假設(shè)1.符號處理系統(tǒng)的六種基本功能信息處理系統(tǒng)又叫符號操作系統(tǒng)(SymbolOperationSystem)或物理符號系統(tǒng)(PhysicalSymbolSystem)。所謂符號就是模式(pattern)。一個完善的符號系統(tǒng)應(yīng)具有下列6種基本功能:(1)輸入符號(input)；(2)輸出符號(output);(3)存儲符號(store);(4)復(fù)制符號(copy);(5)建立符號結(jié)構(gòu):通過找出各符號間的關(guān)系,在符號系統(tǒng)中形成符號結(jié)構(gòu)；(6)條件性遷移(conditionaltransfer):根據(jù)已有符號,繼續(xù)完成活動過程。2.可以把人看成一個智能信息處理系統(tǒng)如果一個物理符號系統(tǒng)具有上述全部6種功能,能夠完成這個全過程,那么它就是一個完整的物理符號系統(tǒng)。人具有上述6種功能；現(xiàn)代計算機(jī)也具備物理符號系統(tǒng)的這6種功能。3.理符號系統(tǒng)的假設(shè)任何一個系統(tǒng),如果它能表現(xiàn)出智能,那么它就必定能夠執(zhí)行上述6種功能。反之,任何系統(tǒng)如果具有這6種功能,那么它就能夠表現(xiàn)出智能；這種智能指的是人類所具有的那種智能。把這個假設(shè)稱為物理符號系統(tǒng)的假設(shè)。4.物理符號系統(tǒng)3個推論推論一既然人具有智能,那么他(她)就一定是個物理符號系統(tǒng)。人之所以能夠表現(xiàn)出智能,就是基于他的信息處理過程。推論二既然計算機(jī)是一個物理符號系統(tǒng),它就一定能夠表現(xiàn)出智能。這是人工智能的基本條件。推論三既然人是一個物理符號系統(tǒng),計算機(jī)也是一個物理符號系統(tǒng),那么就能夠用計算機(jī)來模擬人的活動。4.人類的認(rèn)知行為具有不同的層次認(rèn)知生理學(xué)研究認(rèn)知行為的生理過程,主要研究人的神經(jīng)系統(tǒng)（神經(jīng)元、中樞神經(jīng)系統(tǒng)和大腦）的活動,是認(rèn)知科學(xué)研究的底層。認(rèn)知心理學(xué)研究認(rèn)知行為的心理活動,主要研究人的思維策略,是認(rèn)知科學(xué)研究的頂層。認(rèn)知信息學(xué)研究人的認(rèn)知行為在人體內(nèi)的初級信息處理,主要研究人的認(rèn)知行為如何通過初級信息自然處理,由生理活動變?yōu)樾睦砘顒蛹捌淠孢^程,即由心理活動變?yōu)樯硇袨?。這是認(rèn)知活動的中間層,承上啟下。認(rèn)知工程學(xué)研究認(rèn)知行為的信息加工處理,主要研究如何通過以計算機(jī)為中心的人工信息處理系統(tǒng),對人的各種認(rèn)知行為（如知覺、思維、記憶、語言、學(xué)習(xí)、理解、推理、識別等）進(jìn)行信息處理。這是研究認(rèn)知科學(xué)和認(rèn)知行為的工具,應(yīng)成為現(xiàn)代認(rèn)知心理學(xué)和現(xiàn)代認(rèn)知生理學(xué)的重要研究手段。1.2.2人類智能的計算機(jī)模擬1.機(jī)器智能可以模擬人類智能物理符號系統(tǒng)假設(shè)的推論一告訴人們,人有智能,所以他是一個物理符號系統(tǒng)；推論三指出,可以編寫出計算機(jī)程序去模擬人類的思維活動。這就是說,人和計算機(jī)這兩個物理符號系統(tǒng)所使用的物理符號是相同的,因而計算機(jī)可以模擬人類的智能活動過程。2.智能計算機(jī)的功能如下棋、證明定理、翻譯語言文字和解決難題等。神經(jīng)計算機(jī)(neuralcomputer)能夠以類似人類的方式進(jìn)行“思考”,它力圖重建人腦的形象。一些國家對量子計算機(jī)的研究也已起步,希望通過對量子計算(quantumcomputing)的研究,產(chǎn)生量子計算機(jī)。1.3人工智能的學(xué)派教學(xué)內(nèi)容:本節(jié)主要介紹人工智能的幾個主要學(xué)派及認(rèn)知觀。教學(xué)重點：符號主義(Symbolicism),聯(lián)結(jié)主義(Connectionism),行為主義(Actionism)。教學(xué)難點:各學(xué)派的對人工智能的不同觀點。教學(xué)方法:課堂講授為主。教學(xué)要求:了解各派別之間的關(guān)系及對人工智能發(fā)展歷史的看法。1.人工智能三大學(xué)派·符號主義(Symbolicism),又稱為邏輯主義(Logicism)、心理學(xué)派(Psychlogism)或計算機(jī)學(xué)派(Computerism),其原理主要為物理符號系統(tǒng)(即符號操作系統(tǒng))假設(shè)和有限合理性原理。·聯(lián)結(jié)主義(Connectionism),又稱為仿生學(xué)派(Bionicsism)或生理學(xué)派(Physiologism),其原理主要為神經(jīng)網(wǎng)絡(luò)及神經(jīng)網(wǎng)絡(luò)間的連接機(jī)制與學(xué)習(xí)算法?！ば袨橹髁x(Actionism),又稱進(jìn)化主義(Evolutionism)或控制論學(xué)派(Cyberneticsism),其原理為控制論及感知—動作型控制系統(tǒng)。2.三大學(xué)派對人工智能發(fā)展歷史的不同看法符號主義認(rèn)為人工智能源于數(shù)理邏輯。符號主義仍然是人工智能的主流派。這個學(xué)派的代表有紐厄爾、肖、西蒙和尼爾遜(Nilsson)等。聯(lián)結(jié)主義認(rèn)為人工智能源于仿生學(xué),特別是人腦模型的研究。行為主義認(rèn)為人工智能源于控制論。這一學(xué)派的代表作首推布魯克斯(Brooks)的六足行走機(jī)器人,它被看做新一代的“控制論動物”,是一個基于感知—動作模式的模擬昆蟲行為的控制系統(tǒng)。1.4人工智能的研究與應(yīng)用領(lǐng)域教學(xué)內(nèi)容:本節(jié)主要討論人工智能的研究與應(yīng)用領(lǐng)域。教學(xué)重點:人工智能的一些主要研究與應(yīng)用領(lǐng)域。教學(xué)難點:處理好各領(lǐng)域間的交叉關(guān)系。教學(xué)方法:課堂講授為主。教學(xué)要求:初步了解人工智能的研究與應(yīng)用領(lǐng)域。1.4.1問題求解人工智能的第一個大成就是發(fā)展了能夠求解難題的下棋(如國際象棋)程序,它包含問題的表示、分解、搜索與歸約等。1.4.2邏輯推理與定理證明邏輯推理是人工智能研究中最持久的子領(lǐng)域之一,特別重要的是要找到一些方法,只把注意力集中在一個大型數(shù)據(jù)庫中的有關(guān)事實上,留意可信的證明,并在出現(xiàn)新信息時適時修正這些證明。定理證明的研究在人工智能方法的發(fā)展中曾經(jīng)產(chǎn)生過重要的影響。例如,采用謂詞邏輯語言的演繹過程的形式化有助于更清楚地理解推理的某些子命題。許多非形式的工作,包括醫(yī)療診斷和信息檢索都可以和定理證明問題一樣加以形式化。因此,在人工智能方法的研究中定理證明是一個極其重要的論題。我國人工智能大師吳文俊院士提出并實現(xiàn)了幾何定理機(jī)器證明的方法,被國際上承認(rèn)為“吳氏方法”,是定理證明的又一標(biāo)志性成果。1.4.3自然語言理解語言處理也是人工智能的早期研究領(lǐng)域之一,并引起了進(jìn)一步的重視。語言的生成和理解是一個極為復(fù)雜的編碼和解碼問題。一個能理解自然語言信息的計算機(jī)系統(tǒng)看起來就像一個人一樣需要有上下文知識以及根據(jù)這些上下文知識和信息用信息發(fā)生器進(jìn)行推理的過程。理解口頭的和書寫語言的計算機(jī)系統(tǒng)所取得的某些進(jìn)展,其基礎(chǔ)就是有關(guān)表示上下文知識結(jié)構(gòu)的某些人工智能思想以及根據(jù)這些知識進(jìn)行推理的某些技術(shù)。1.4.4自動程序設(shè)計對自動程序設(shè)計的研究不僅可以促進(jìn)半自動軟件開發(fā)系統(tǒng)的發(fā)展,而且也使通過修正自身數(shù)碼進(jìn)行學(xué)習(xí)(即修正它們的性能)的人工智能系統(tǒng)得到發(fā)展。程序理論方面的有關(guān)研究工作對人工智能的所有研究工作都是很重要的。自動程序設(shè)計研究的重大貢獻(xiàn)之一是作為問題求解策略的調(diào)整概念。已經(jīng)發(fā)現(xiàn),對程序設(shè)計或機(jī)器人控制問題,先產(chǎn)生一個不費事的有錯誤的解,然后再修改它(使它正確工作),這種做法一般要比堅持要求第一個解就完全沒有缺陷的做法有效得多。1.4.5專家系統(tǒng)一般地說,專家系統(tǒng)是一個智能計算機(jī)程序系統(tǒng),其內(nèi)部具有大量專家水平的某個領(lǐng)域知識與經(jīng)驗,能夠利用人類專家的知識和解決問題的方法來解決該領(lǐng)域的問題。發(fā)展專家系統(tǒng)的關(guān)鍵是表達(dá)和運用專家知識,即來自人類專家的并已被證明對解決有關(guān)領(lǐng)域內(nèi)的典型問題是有用的事實和過程。1.4.6機(jī)器學(xué)習(xí)學(xué)習(xí)是人類智能的主要標(biāo)志和獲得知識的基本手段；機(jī)器學(xué)習(xí)(自動獲取新的事實及新的推理算法)是使計算機(jī)具有智能的根本途徑；機(jī)器學(xué)習(xí)還有助于發(fā)現(xiàn)人類學(xué)習(xí)的機(jī)理和揭示人腦的奧秘。學(xué)習(xí)是一個有特定目的的知識獲取過程,其內(nèi)部表現(xiàn)為新知識結(jié)構(gòu)的不斷建立和修改,而外部表現(xiàn)為性能的改善。1.4.7神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)處理直覺和形象思維信息具有比傳統(tǒng)處理方式好得多的效果。神經(jīng)網(wǎng)絡(luò)已在模式識別、圖象處理、組合優(yōu)化、自動控制、信息處理、機(jī)器人學(xué)和人工智能的其它領(lǐng)域獲得日益廣泛的應(yīng)用。1.4.8機(jī)器人學(xué)人工智能研究日益受到重視的另一個分支是機(jī)器人學(xué),其中包括對操作機(jī)器人裝置程序的研究。這個領(lǐng)域所研究的問題,從機(jī)器人手臂的最佳移動到實現(xiàn)機(jī)器人目標(biāo)的動作序列的規(guī)劃方法,無所不包。目前已經(jīng)建立了一些比較復(fù)雜的機(jī)器人系統(tǒng)。機(jī)器人和機(jī)器人學(xué)的研究促進(jìn)了許多人工智能思想的發(fā)展。智能機(jī)器人的研究和應(yīng)用體現(xiàn)出廣泛的學(xué)科交叉,涉及眾多的課題,機(jī)器人已在各領(lǐng)域獲得越來越普遍的應(yīng)用。1.4.9模式識別人工智能所研究的模式識別是指用計算機(jī)代替人類或幫助人類感知模式,是對人類感知外界功能的模擬,研究的是計算機(jī)模式識別系統(tǒng),也就是使一個計算機(jī)系統(tǒng)具有模擬人類通過感官接受外界信息、識別和理解周圍環(huán)境的感知能力。1.4.10機(jī)器視覺實驗表明,人類接受外界信息的80%以上來自視覺,視覺對人類是非常重要的。機(jī)器視覺或計算機(jī)視覺已從模式識別的一個研究領(lǐng)域發(fā)展為一門獨立的學(xué)科；在視覺方面,已經(jīng)給計算機(jī)系統(tǒng)裝上電視輸入裝置以便能夠“看見”周圍的東西。機(jī)器視覺的前沿研究領(lǐng)域包括實時并行處理、主動式定性視覺、動態(tài)和時變視覺、三維景物的建模與識別、實時圖像壓縮傳輸和復(fù)原、多光譜和彩色圖像的處理與解釋等。1.4.11智能控制人工智能的發(fā)展促進(jìn)自動控制向智能控制發(fā)展。智能控制是一類無需(或需要盡可能少的)人的干預(yù)就能夠獨立地驅(qū)動智能機(jī)器實現(xiàn)其目標(biāo)的自動控制。智能控制是同時具有以知識表示的非數(shù)學(xué)廣義世界模型和數(shù)學(xué)公式模型表示的混合控制過程,也往往是含有復(fù)雜性、不完全性、模糊性或不確定性以及不存在已知算法的非數(shù)學(xué)過程,并以知識進(jìn)行推理,以啟發(fā)來引導(dǎo)求解過程。1.4.12智能檢索隨著科學(xué)技術(shù)的迅速發(fā)展,出現(xiàn)了“知識爆炸”的情況,研究智能檢索系統(tǒng)已成為科技持續(xù)快速發(fā)展的重要保證。智能信息檢索系統(tǒng)的設(shè)計者們將面臨以下幾個問題。首先,建立一個能夠理解以自然語言陳述的詢問系統(tǒng)本身就存在不少問題。其次,即使能夠通過規(guī)定某些機(jī)器能夠理解的形式化詢問語句來回避語言理解問題,但仍然存在一個如何根據(jù)存儲的事實演繹出答案的問題。第三,理解詢問和演繹答案所需要的知識都可能超出該學(xué)科領(lǐng)域數(shù)據(jù)庫所表示的知識。1.4.13智能調(diào)度與指揮確定最佳調(diào)度或組合的問題是人們感興趣的又一類問題,求解這類問題的程序會產(chǎn)生一種組合爆炸的可能性,這時,即使是大型計算機(jī)的容量也會被用光。人工智能學(xué)家們曾經(jīng)研究過若干組合問題的求解方法。他們的努力集中在使“時間-問題大小”曲線的變化盡可能緩慢地增長,即使是必須按指數(shù)方式增長。有關(guān)問題域的知識再次成為比較有效的求解方法的關(guān)鍵。為處理組合問題而發(fā)展起來的許多方法對其它組合上不甚嚴(yán)重的問題也是有用的。1.4.14分布式人工智能與Agent分布式人工智能(DistributedAI,DAI)是分布式計算與人工智能結(jié)合的結(jié)果。DAI系統(tǒng)以魯棒性作為控制系統(tǒng)質(zhì)量的標(biāo)準(zhǔn),并具有互操作性,即不同的異構(gòu)系統(tǒng)在快速變化的環(huán)境中具有交換信息和協(xié)同工作的能力。分布式人工智能的研究目標(biāo)是要創(chuàng)建一種能夠描述自然系統(tǒng)和社會系統(tǒng)的精確概念模型。多agent系統(tǒng)(MultiagentSystem,MAS)更能體現(xiàn)人類的社會智能,具有更大的靈活性和適應(yīng)性,更適合開放和動態(tài)的世界環(huán)境,因而倍受重視,已成為人工智能以至計算機(jī)科學(xué)和控制科學(xué)與工程的研究熱點。1.4.15計算智能與進(jìn)化計算計算智能(ComputingIntelligence)涉及神經(jīng)計算、模糊計算、進(jìn)化計算等研究領(lǐng)域。進(jìn)化計算(EvolutionaryComputation)是指一類以達(dá)爾文進(jìn)化論為依據(jù)來設(shè)計、控制和優(yōu)化人工系統(tǒng)的技術(shù)和方法的總稱,它包括遺傳算法(GeneticAlgorithms)、進(jìn)化策略(EvolutionaryStrategies)和進(jìn)化規(guī)劃(EvolutionaryProgramming)。1.4.16數(shù)據(jù)挖掘與知識發(fā)現(xiàn)知識獲取是知識信息處理的關(guān)鍵問題之一。數(shù)據(jù)挖掘是通過綜合運用統(tǒng)計學(xué)、粗糙集、模糊數(shù)學(xué)、機(jī)器學(xué)習(xí)和專家系統(tǒng)等多種學(xué)習(xí)手段和方法,從大量的數(shù)據(jù)中提煉出抽象的知識,從而揭示出蘊涵在這些數(shù)據(jù)背后的客觀世界的內(nèi)在聯(lián)系和本質(zhì)規(guī)律,實現(xiàn)知識的自動獲取。數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù)已獲廣泛應(yīng)用。1.4.17人工生命人工生命(ArtificialLife,ALife)旨在用計算機(jī)和精密機(jī)械等人工媒介生成或構(gòu)造出能夠表現(xiàn)自然生命系統(tǒng)行為特征的仿真系統(tǒng)或模型系統(tǒng)。自然生命系統(tǒng)行為具有自組織、自復(fù)制、自修復(fù)等特征以及形成這些特征的混沌動力學(xué)、進(jìn)化和環(huán)境適應(yīng)。人工生命所研究的人造系統(tǒng)能夠演示具有自然生命系統(tǒng)特征的行為,在“生命之所能”(lifeasitcouldbe)的廣闊范圍內(nèi)深入研究“生命之所知”(lifeasweknowit)的實質(zhì)。人工生命學(xué)科的研究內(nèi)容包括生命現(xiàn)象的仿生系統(tǒng)、人工建模與仿真、進(jìn)化動力學(xué)、人工生命的計算理論、進(jìn)化與學(xué)習(xí)綜合系統(tǒng)以及人工生命的應(yīng)用等。1.4.18系統(tǒng)與語言工具除了直接瞄準(zhǔn)實現(xiàn)智能的研究工作外,開發(fā)新的方法也往往是人工智能研究的一個重要方面。人工智能對計算機(jī)界的某些最大貢獻(xiàn)已經(jīng)以派生的形式表現(xiàn)出來。計算機(jī)系統(tǒng)的一些概念,如分時系統(tǒng)、編目處理系統(tǒng)和交互調(diào)試系統(tǒng)等,已經(jīng)在人工智能研究中得到發(fā)展。1.5本書概要本書包括下列內(nèi)容:1.簡述人工智能的起源與發(fā)展,討論人工智能的定義、人工智能與計算機(jī)的關(guān)系以及人工智能的研究和應(yīng)用領(lǐng)域。2.比較概括地論述知識表示的各種主要方法,包括狀態(tài)空間法、問題歸約法、謂詞邏輯法、結(jié)構(gòu)化表示法（語義網(wǎng)絡(luò)法、框架）、劇本和過程等。3.討論常用搜索原理,如盲目搜索、啟發(fā)式搜索和消解原理等；并研究一些比較高級的推理求解技術(shù),如規(guī)則演繹系統(tǒng)、專家系統(tǒng)、系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理等。4.介紹近期發(fā)展起來的已成為當(dāng)前研究熱點的人工智能技術(shù)和方法,即分布式人工智能與agent、計算智能（含神經(jīng)計算、邏輯計算與進(jìn)化計算）、數(shù)據(jù)挖掘與知識發(fā)現(xiàn)、人工生命等。5、比較詳細(xì)地分析人工智能的主要應(yīng)用領(lǐng)域,涉及專家系統(tǒng)、機(jī)器學(xué)習(xí)、自動規(guī)劃系統(tǒng)和自然語言理解等。6、敘述近年來人工智能研究中出現(xiàn)的爭論,展望人工智能的發(fā)展。1.6辯論會主題:人工智能能否超過人類智能？正方觀點:人工智能不會超過人類智能。反方觀點:人工智能能夠超過人類智能。第二章知識表示方法教學(xué)內(nèi)容:本章討論知識表示的各種方法,是人工智能課程三大內(nèi)容（知識表示、知識推理、知識應(yīng)用）之一,也是學(xué)習(xí)人工智能其他內(nèi)容的基礎(chǔ)。教學(xué)重點:狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡(luò)法。教學(xué)難點:狀態(tài)描述與狀態(tài)空間圖示、問題歸約機(jī)制、置換與合一。教學(xué)方法：課堂教學(xué)為主,同時結(jié)合《離散數(shù)學(xué)》等已學(xué)的內(nèi)容實時提問、收集學(xué)生學(xué)習(xí)情況,充分利用網(wǎng)絡(luò)課程中的多媒體素材來表示抽象概念。教學(xué)要求:重點掌握用狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法來描述問題；解決問題；掌握幾種主要方法之間的差別；并對其它幾種表示方法有一般了解。2.1狀態(tài)空間法教學(xué)內(nèi)容:本節(jié)是通過狀態(tài)空間法來求解問題,它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。 教學(xué)重點：問題的狀態(tài)描述,操作符。教學(xué)難點:選擇一個好的狀態(tài)描述與狀態(tài)空間表示方案。教學(xué)方法:以課堂教學(xué)為主；充分利用網(wǎng)絡(luò)課程中的多媒體素材來闡述抽象概念。教學(xué)要求：重點掌握對某個問題的狀態(tài)空間描述,學(xué)會組織狀態(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)為集合的分量,稱為狀態(tài)變量。給定每個分量的一組值就得到一個具體的狀態(tài),如Qk=［q０k,q1k,…,qnk］T(2.2)算符:使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運算符號或邏輯符號等。問題的狀態(tài)空間(statespace)是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖,它包含三種說明的集合,即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標(biāo)狀態(tài)集合G。因此,可把狀態(tài)空間記為三元狀態(tài)(S,F,G)。2.狀態(tài)空間的表示法對一個問題的狀態(tài)描述,必須確定3件事:(1)該狀態(tài)描述方式,特別是初始狀態(tài)描述；(2)操作符集合及其對狀態(tài)描述的作用；(3)目標(biāo)狀態(tài)描述的特性。2.1.2狀態(tài)圖示法圖的基本概念圖由節(jié)點(不一定是有限的節(jié)點)的集合構(gòu)成。一對節(jié)點用弧線連接起來,從一個節(jié)點指向另一個節(jié)點。這種圖叫做有向圖(directedgraph)。某個節(jié)點序列(ni1,ni2,…,nik)當(dāng)j=2,3,…,k時,如果對于每一個ni,j-1都有一個后繼節(jié)點nij存在,那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點nik的長度為k的路徑。代價(cost)是給各弧線指定數(shù)值以表示加在相應(yīng)算符上的代價。圖的顯式說明是指各節(jié)點及其具有代價的弧線由一張表明確給出。圖的隱式說明是指各節(jié)點及其具有代價的弧線不能由一張表明確給出。2.1.3狀態(tài)空間表示舉例1.產(chǎn)生式系統(tǒng)一個產(chǎn)生式系統(tǒng)由下列3部分組成:一個總數(shù)據(jù)庫(globaldatabase),它含有與具體任務(wù)有關(guān)的信息。一套規(guī)則,它對數(shù)據(jù)庫進(jìn)行操作運算。每條規(guī)則由左右兩部分組成,左部鑒別規(guī)則的適用性或先決條件,右部描述規(guī)則應(yīng)用時所完成的動作。應(yīng)用規(guī)則來改變數(shù)據(jù)庫。一個控制策略,它確定應(yīng)該采用哪一條適用規(guī)則,而且當(dāng)數(shù)據(jù)庫的終止條件滿足時,就停止計算。2.狀態(tài)空間表示舉例猴子與香蕉的問題狀態(tài)空間表示用四元組（W,x,y,z）其中:W—猴子的水平位置；x—當(dāng)猴子在箱子頂上時取x=1；否則取x=0；Y—箱子的水平位置；z—當(dāng)猴子摘到香蕉時取z=1；否則取z=0。算符goto(U)猴子走到水平位置U；（2）pushbox(V)猴子把箱子推到水平位置V；（3）climbbox猴子爬上箱頂；（4）grasp猴子摘到香蕉。求解過程令初始狀態(tài)為(a,0,b,0)。這時,goto(U)是唯一適用的操作,并導(dǎo)致下一狀態(tài)(U,0,b,0)?，F(xiàn)在有3個適用的操作,即goto(U),pushbox(V)和climbbox(若U=b)。把所有適用的操作繼續(xù)應(yīng)用于每個狀態(tài),我們就能夠得到狀態(tài)空間圖,如圖所示。從圖不難看出,把該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為:｛goto(b),pushbox(c),climbbox,grasp｝2.2問題歸約法教學(xué)內(nèi)容:知識表示的歸約法,即已知問題的描述,通過一系列變換把此問題最終變?yōu)橐粋€子問題集合；這些子問題的解可以直接得到,從而解決了初始問題的方法。教學(xué)重點:問題歸約的基本思想,問題描述,問題變換的操作符,與或圖表示。教學(xué)難點：如何把初始問題變換為子問題,與或圖表示方法。教學(xué)方法：課堂教學(xué)為主,充分利用網(wǎng)絡(luò)課程中的相關(guān)多媒體素材來表示抽象概念。教學(xué)要求:通過梵塔難題重點掌握問題歸約法的機(jī)理和問題歸約描述方法。學(xué)會用與或圖表示歸約問題。2.2.1問題歸約描述1.問題歸約法的概念已知問題的描述,通過一系列變換把此問題最終變?yōu)橐粋€子問題集合；這些子問題的解可以直接得到,從而解決了初始問題。該方法也就是從目標(biāo)(要解決的問題)出發(fā)逆向推理,建立子問題以及子問題的子問題,直至最后把初始問題歸約為一個平凡的本原問題集合。這就是問題歸約的實質(zhì)。2.問題歸約法的組成部分（1）一個初始問題描述； （2）一套把問題變換為子問題的操作符；（3）一套本原問題描述。3.示例:梵塔難題問題有3個柱子(1,2,3)和3個不同尺寸的圓盤(A,B,C)。在每個圓盤的中心有個孔,所以圓盤可以堆疊在柱子上。最初,全部3個圓盤都堆在柱子1上：最大的圓盤C在底部,最小的圓盤A在頂部。要求把所有圓盤都移到柱子3上,每次只許移動一個,而且只能先搬動柱子頂部的圓盤,還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。歸約過程講述：梵塔問題的來源。講述：梵塔問題的來源。提問：一圓盤問題要走幾步？兩圓盤問題要走幾步？三個、四個．．．等？（2）移動圓盤C至柱子3的單圓盤難題；（3）移動圓盤A和B至柱子3的雙圓盤難題。由上可以看出簡化了難題每一個都比原始難題容易,所以問題都會變成易解的本原問題。4.歸約描述問題歸約方法是應(yīng)用算符來把問題描述變換為子問題描述?？梢杂脿顟B(tài)空間表示的三元組合(S、F、G)來規(guī)定與描述問題；對于梵塔問題,子問題［（111）=>(122)］,［(122)=>(322)］以及［(322)=>(333)］規(guī)定了最后解答路徑將要通過的腳踏石狀態(tài)(122)和(322)。問題歸約方法可以應(yīng)用狀態(tài)、算符和目標(biāo)這些表示法來描述問題,這并不意味著問題歸約法和狀態(tài)空間法是一樣的。2.2.2與或圖表示1.與或圖的概念用一個類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合,畫出歸約問題圖。例如,設(shè)想問題A需要由求解問題B、C和D來決定,那么可以用一個與圖來表示；同樣,一個問題A或者由求解問題B、或者由求解問題C來決定,則可以用一個或圖來表示。2.與或圖的有關(guān)術(shù)語父節(jié)點是一個初始問題或是可分解為子問題的問題節(jié)點；舉例：對于一個與或圖。提問：舉例：對于一個與或圖。提問：指出圖中的父節(jié)點、子節(jié)點、或節(jié)點、與節(jié)點、弧線和終葉節(jié)點?；蚬?jié)點只要解決某個問題就可解決其父輩問題的節(jié)點集合；與節(jié)點只有解決所有子問題,才能解決其父輩問題的節(jié)點集合；弧線是父輩節(jié)點指向子節(jié)點的圓弧連線；終葉節(jié)點是對應(yīng)于原問題的本原節(jié)點。3.與或圖的有關(guān)定義可解節(jié)點與或圖中一個可解節(jié)點的一般定義可以歸納如下:(1)終葉節(jié)點是可解節(jié)點(因為它們與本原問題相關(guān)連)。(2)如果某個非終葉節(jié)點含有或后繼節(jié)點,那么只有當(dāng)其后繼節(jié)點至少有一個是可解的時,此非終葉節(jié)點才是可解的。(3)如果某個非終葉節(jié)點含有與后繼節(jié)點,那么只要當(dāng)其后繼節(jié)點全部為可解時,此非終葉節(jié)點才是可解的。不可解節(jié)點不可解節(jié)點的一般定義歸納于下:(1)沒有后裔的非終葉節(jié)點為不可解節(jié)點。(2)如果某個非終葉節(jié)點含有或后繼節(jié)點,那么只有當(dāng)其全部后裔為不可解時,此非終葉節(jié)點才是不可解的。(3)如果某個非終葉節(jié)點含有與后繼節(jié)點,那么只要當(dāng)其后裔至少有一個為不可解時,此非終葉節(jié)點才是不可解的。4.與或圖構(gòu)圖規(guī)則(1)與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。圖中所含起始節(jié)點對應(yīng)于原始問題。(2)對應(yīng)于本原問題的節(jié)點,叫做終葉節(jié)點,它沒有后裔。(3)對于把算符應(yīng)用于問題A的每種可能情況,都把問題變換為一個子問題集合；有向弧線自A指向后繼節(jié)點,表示所求得的子問題集合。(4)一般對于代表兩個或兩個以上子問題集合的每個節(jié)點,有向弧線從此節(jié)點指向此子問題集合中的各個節(jié)點。(5)在特殊情況下,當(dāng)只有一個算符可應(yīng)用于問題A,而且這個算符產(chǎn)生具有一個以上子問題的某個集合時,由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡化。2.3謂詞邏輯法教學(xué)內(nèi)容:本節(jié)主要講述問題的謂詞邏輯表示的基本方法。教學(xué)重點:謂詞邏輯、謂詞公式、謂詞演算、置換與合一。教學(xué)難點:如何選擇謂詞,問題的謂詞邏輯表示及運算。教學(xué)方法：課堂教學(xué)為主,充分利用網(wǎng)絡(luò)課程中的示例程序。教學(xué)要求：重點掌握謂詞邏輯表示的語言與方法,掌握謂詞公式的性質(zhì)及謂詞演算,學(xué)會謂詞公式的置換與合一,運用謂詞推理來解決問題。2.3.1謂詞演算1.語法和語義謂詞邏輯的基本組成部分是謂詞符號、變量符號、函數(shù)符號和常量符號,并用圓括弧、方括弧、花括弧和逗號隔開,以表示論域內(nèi)的關(guān)系。原子公式是由若干謂詞符號和項組成,只有當(dāng)其對應(yīng)的語句在定義域內(nèi)為真時,才具有值T(真)；而當(dāng)其對應(yīng)的語句在定義域內(nèi)為假時,該原子公式才具有值F(假)。2.連詞和量詞連詞有∧(與)、∨(或),全稱量詞(
x),存在量詞(
x)。原子公式是謂詞演算的基本積木塊,運用連詞能夠組合多個原子公式以構(gòu)成比較復(fù)雜的合適公式。3.幾個有關(guān)定義用連詞∧把幾個公式連接起來而構(gòu)成的公式叫做合取,而此合取式的每個組成部分叫做合取項。一些合適公式所構(gòu)成的任一合取也是一個合適公式。用連詞∨把幾個公式連接起來所構(gòu)成的公式叫做析取,而此析取式的每一組成部分叫做析取項。由一些合適公式所構(gòu)成的任一析取也是一個合適公式。用連詞=>連接兩個公式所構(gòu)成的公式叫做蘊涵。蘊涵的左式叫做前項,右式叫做后項。如果前項和后項都是合適公式,那么蘊涵也是合適公式。前面具有符號～的公式叫做否定。一個合適公式的否定也是合適公式。量化一個合適公式中的某個變量所得到的表達(dá)式也是合適公式。如果一個合適公式中某個變量是經(jīng)過量化的,就把這個變量叫做約束變量,否則就叫它為自由變量。在合適公式中,感興趣的主要是所有變量都是受約束的。這樣的合適公式叫做句子。2.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.合適公式的性質(zhì)(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∧PP∨Q等價于Q∨P(6)結(jié)合律(P∧Q)∧R等價于P∧(Q∧R)(P∨Q)∨R等價于P∨(Q∨R)(7)逆否律P=>Q等價于～Q=>～P此外,還可建立下列等價關(guān)系:(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)證明：否定之否定，～(～P)等價于P。(x)［P(x)∨Q(x)］等價于證明：否定之否定，～(～P)等價于P。(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產(chǎn)生合適公式W2的運算。全稱化推理,是由合適公式(
x)W(x)產(chǎn)生合適公式W(A),其中A為任意常量符號。一個表達(dá)式的置換就是在該表達(dá)式中用置換項置換變量。一般說來,置換是可結(jié)合的,但置換是不可交換的。2.合一尋找項對變量的置換,以使兩表達(dá)式一致,叫做合一(unification)。如果一個置換s作用于表達(dá)式集｛Ei｝的每個元素,則用｛Ei｝s來表示置換例的集。稱表達(dá)式集｛Ei｝是可合一的。如果存在一個置換s使得：E1s=E2s=E3s=…那么稱此s為｛Ei｝的合一者,因為s的作用是使集合｛Ei｝成為單一形式。2.4語義網(wǎng)絡(luò)法教學(xué)內(nèi)容:本節(jié)主要講述知識的語義網(wǎng)絡(luò)表示法。教學(xué)重點:語義網(wǎng)絡(luò)表示的詞法、結(jié)構(gòu)、過程、語義。教學(xué)難點:如何選擇節(jié)點和弧線來構(gòu)成語義網(wǎng)絡(luò)。教學(xué)方法:課堂教學(xué)。教學(xué)要求：重點掌握語義網(wǎng)絡(luò)的結(jié)構(gòu),掌握二元語義網(wǎng)絡(luò)表示方法,了解語義網(wǎng)絡(luò)的特點。2.4.1二元語義網(wǎng)絡(luò)的表示語義網(wǎng)絡(luò)的基本概念語義網(wǎng)絡(luò)是知識的一種結(jié)構(gòu)化圖解表示,它由節(jié)點和弧線或鏈線組成。節(jié)點用于表示實體、概念和情況等,弧線用于表示節(jié)點間的關(guān)系。語義網(wǎng)絡(luò)表示由下列4個相關(guān)部分組成:(1)詞法部分決定表示詞匯表中允許有哪些符號,它涉及各個節(jié)點和弧線。(2)結(jié)構(gòu)部分?jǐn)⑹龇柵帕械募s束條件,指定各弧線連接的節(jié)點對。(3)過程部分說明訪問過程,這些過程能用來建立和修正描述,以及回答相關(guān)問題。(4)語義部分確定與描述相關(guān)的(聯(lián)想)意義的方法即確定有關(guān)節(jié)點的排列及其占有物和對應(yīng)弧線。語義網(wǎng)絡(luò)具有下列特點:(1)能把實體的結(jié)構(gòu)、屬性與實體間的因果關(guān)系顯式地和簡明地表達(dá)出來,與實體相關(guān)的事實、特征和關(guān)系可以通過相應(yīng)的節(jié)點弧線推導(dǎo)出來。(2)由于與概念相關(guān)的屬性和聯(lián)系被組織在一個相應(yīng)的節(jié)點中,因而使概念易于受訪和學(xué)習(xí)。(3)表現(xiàn)問題更加直觀,更易于理解,適于知識工程師與領(lǐng)域?qū)＜覝贤ā?4)語義網(wǎng)絡(luò)結(jié)構(gòu)的語義解釋依賴于該結(jié)構(gòu)的推理過程而沒有結(jié)構(gòu)的約定,因而得到的推理不能保證像謂詞邏輯法那樣有效。(5)節(jié)點間的聯(lián)系可能是線狀、樹狀或網(wǎng)狀的,甚至是遞歸狀的結(jié)構(gòu),使相應(yīng)的知識存儲和檢索可能需要比較復(fù)雜的過程。二元語義網(wǎng)絡(luò)的表示用兩個節(jié)點和一條弧線可以表示一個簡單的事實,對于表示占有關(guān)系的語義網(wǎng)絡(luò),是通過允許節(jié)點既可以表示一個物體或一組物體,也可以表示情況和動作。每一情況節(jié)點可以有一組向外的弧(事例弧),稱為事例框,用以說明與該事例有關(guān)的各種變量。在選擇節(jié)點時,首先要弄清節(jié)點是用于表示基本的物體或概念的,或是用于多種目的的。否則,如果語義網(wǎng)絡(luò)只被用來表示一個特定的物體或概念,那么當(dāng)有更多的實例時就需要更多的語義網(wǎng)絡(luò)。選擇語義基元就是試圖用一組基元來表示知識。這些基元描述基本知識,并以圖解表示的形式相互聯(lián)系。2.4.2多元語義網(wǎng)絡(luò)的表示語義網(wǎng)絡(luò)是一種網(wǎng)絡(luò)結(jié)構(gòu)。節(jié)點之間以鏈相連。從本質(zhì)上講,接點之間的連接是二元關(guān)系。語義網(wǎng)絡(luò)從本質(zhì)上來說,只能表示二元關(guān)系,如果所要表示的事實是多元關(guān)系,則把這個多元關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合,或二元關(guān)系的合取。具體來說,多元關(guān)系R(X1,X2,…,Xn)總可以轉(zhuǎn)換成R1(X11,X12)∧R2(X21,X22)∧…∧Rn(Xn1,Xn2)。要在語義網(wǎng)絡(luò)中進(jìn)行這種轉(zhuǎn)換需要引入附加節(jié)點。2.4.3連詞和量化的表示可以用語義網(wǎng)絡(luò)表示謂詞邏輯法中的各種連詞及量化。合取多元關(guān)系可以被轉(zhuǎn)換成一組二元關(guān)系的合取,從而可以用語義網(wǎng)絡(luò)的形式表示出來。析取在語義網(wǎng)絡(luò)中,為與合取關(guān)系相區(qū)別,在析取關(guān)系的連接上加注析取界限,并標(biāo)記DIS。否定采用～I(xiàn)SA和～PARTOF關(guān)系或標(biāo)注NEG界限來表示否定。蘊涵在語義網(wǎng)絡(luò)中可用標(biāo)注ANTE和CONSE界限來表示蘊涵關(guān)系。量化存在量化在語義網(wǎng)絡(luò)中可直接用ISA鏈來表示。而全稱量化就要用分割方法來表示。2.5其他方法教學(xué)內(nèi)容:簡介知識表示的其他三種表示方法,即框架表示法、劇本表示法和過程表示法,闡述了三種表示法的原理和應(yīng)用范圍。教學(xué)重點:各方法的基本原理及基本結(jié)構(gòu)。教學(xué)難點:各方法的推理過程。教學(xué)方法：課堂教學(xué)為主。適當(dāng)提問,加深學(xué)生對概念的理解。教學(xué)要求:初步了解三種方法的基本原理。2.5.1框架1.框架的構(gòu)成框架通常由描述事物的各個方面的槽組成,每個槽可以擁有若干個側(cè)面,而每個側(cè)面又可以擁有若干個值。一個框架的一般結(jié)構(gòu)如下：〈框架名〉〈槽1〉〈側(cè)面11〉〈值111〉…〈側(cè)面12〉〈值121〉……〈槽2〉〈側(cè)面21〉〈值211〉………〈槽n〉〈側(cè)面n1〉〈值n11〉……〈側(cè)面nm〉〈值nm1〉…較簡單的情景是用框架來表示諸如人和房子等事物。例如,一個人可以用其職業(yè)、身高和體重等項描述,因而可以用這些項目組成框架的槽。當(dāng)描述一個具體的人時,再用這些項目的具體值填入到相應(yīng)的槽中。表2.2給出的是描述John的框架。表2.2簡單框架示例JOHNIsa:PERSONProfession:PROGRAMMERHeight:1.8mWeight:79kg框架是一種通用的知識表達(dá)形式,對于如何運用框架系統(tǒng)還沒有一種統(tǒng)一的形式,常常由各種問題的不同需要來決定。2.框架的推理如前所述,框架是一種復(fù)雜結(jié)構(gòu)的語義網(wǎng)絡(luò)。因此語義網(wǎng)絡(luò)推理中的匹配和特性繼承在框架系統(tǒng)中也可以實行。除此以外,由于框架用于描述具有固定格式的事物、動作和事件,因此可以在新的情況下,推論出未被觀察到的事實?？蚣苡靡韵聨追N途徑來幫助實現(xiàn)這一點：框架包含它所描述的情況或物體的多方面的信息?？蚣馨矬w必須具有的屬性。在填充框架的各個槽時,要用到這些屬性?？蚣苊枋鏊鼈兯淼母拍畹牡湫褪吕Ｓ靡粋€框架來具體體現(xiàn)一個特定情況的過程,經(jīng)常不是很順利的。但當(dāng)這個過程碰到障礙時,經(jīng)常不必放棄原來的努力去從頭開始,而是有很多辦法可想的:(1)選擇和當(dāng)前情況相對應(yīng)的當(dāng)前的框架片斷,并把這個框架片斷和候補框架相匹配。選擇最佳匹配。(2)盡管當(dāng)前的框架和要描述的情況之間有不相匹配的地方,但是仍然可以繼續(xù)應(yīng)用這個框架。(3)查詢框架之間專門保存的鏈,以提出應(yīng)朝哪個方向進(jìn)行試探的建議。(4)沿著框架系統(tǒng)排列的層次結(jié)構(gòu)向上移動(即從狗框架→哺乳動物框架→動物框架),直到找到一個足夠通用,并不與已有事實矛盾的框架。2.5.2劇本劇本是框架的一種特殊形式,它用一組槽來描述某些事件的發(fā)生序列,就像劇本中的事件序列一樣,故稱為“劇本”或腳本。一個劇本一般由以下各部分組成:(1)開場條件給出在劇本中描述的事件發(fā)生的前提條件。(2)角色用來表示在劇本所描述的事件中可能出現(xiàn)的有關(guān)人物的一些槽。(3)道具這是用來表示在劇本所描述的事件中可能出現(xiàn)的有關(guān)物體的一些槽。(4)場景描述事件發(fā)生的真實順序,可以由多個場景組成,每個場景又可以是其它的劇本。(5)結(jié)果給出在劇本所描述的事件發(fā)生以后通常所產(chǎn)生的結(jié)果。例子:以餐廳劇本為例說明劇本各個部分的組成。根據(jù)劇本的重要性,可以有二種準(zhǔn)備劇本的方法。(1)對于不屬于事件核心部分的劇本,只需設(shè)置指向該劇本的指針即可,以便當(dāng)它成為核心時啟用。(2)對于符合事件核心部分的劇本,則應(yīng)使用在當(dāng)前事件中涉及到的具體對象和人物去填寫劇本的槽。劇本的前提、道具、角色和事件等常能起到啟用劇本的指示器的作用。一旦劇本被啟用,則可以應(yīng)用它來進(jìn)行推理。其中最重要的是運用劇本可以預(yù)測沒有明顯提及的事件的發(fā)生。劇本結(jié)構(gòu),比起框架這樣的一些通用結(jié)構(gòu)來,要呆板得多,知識表達(dá)的范圍也很窄,因此不適用于表達(dá)各種知識,但對于表達(dá)預(yù)先構(gòu)思好的特定知識,如理解故事情節(jié)等,是非常有效的。2.5.3過程語義網(wǎng)絡(luò)、框架和劇本等知識表示方法,均是對知識和事實的一種靜止的表達(dá)方法,是知識的一種顯式表達(dá)形式。而對于如何使用這些知識,則通過控制策略來決定。和知識的陳述式表示相對應(yīng)的是知識的過程式表示。所謂過程式表示就是將有關(guān)某一問題領(lǐng)域的知識,連同如何使用這些知識的方法,均隱式地表達(dá)為一個求解問題的過程。它所給出的是事物的一些客觀規(guī)律,表達(dá)的是如何求解問題。知識的描述形式就是程序,所有信息均隱含在程序之中。從程序求解問題的效率上來說,過程式表達(dá)要比陳述式表達(dá)高得多。但因其知識均隱含在程序中,因而難于添加新知識和擴(kuò)充功能,適用范圍較窄。2.6小結(jié)知識表示方法很多,本章介紹了其中的7種,有圖示法和公式法,結(jié)構(gòu)化方法,陳述式表示和過程式表示等。狀態(tài)空間法是一種基于解答空間的問題表示和求解方法,它是以狀態(tài)和操作符為基礎(chǔ)的。在利用狀態(tài)空間圖表示時,從某個初始狀態(tài)開始,每次加一個操作符,遞增地建立起操作符的試驗序列,直到達(dá)到目標(biāo)狀態(tài)為止。由于狀態(tài)空間法需要擴(kuò)展過多的節(jié)點,容易出現(xiàn)“組合爆炸”,因而只適用于表示比較簡單的問題。問題歸約法從目標(biāo)(要解決的問題)出發(fā),逆向推理,通過一系列變換把初始問題變換為子問題集合和子子問題集合,直至最后歸約為一個平凡的本原問題集合。這些本原問題的解可以直接得到從而解決了初始問題,用與或圖來有效地說明問題歸約法的求解途徑。問題歸約法能夠比狀態(tài)空間法更有效地表示問題。狀態(tài)空間法是問題歸約法的一種特例。在問題歸約法的與或圖中,包含有與節(jié)點和或節(jié)點,而在狀態(tài)空間法中只含有或節(jié)點。謂詞邏輯法采用謂詞合適公式和一階謂詞演算把要解決的問題變?yōu)橐粋€有待證明的問題,然后采用消解定理和消解反演來證明一個新語句是從已知的正確語句導(dǎo)出的,從而證明這個新語句也是正確的。謂詞邏輯是一種形式語言,能夠把數(shù)學(xué)中的邏輯論證符號化。謂詞邏輯法常與其它表示方法混合使用,靈活方便,可以表示比較復(fù)雜的問題。語義網(wǎng)絡(luò)是一種結(jié)構(gòu)化表示方法,它由節(jié)點和弧線或鏈線組成。節(jié)點用于表示物體、概念和狀態(tài),弧線用于表示節(jié)點間的關(guān)系。語義網(wǎng)絡(luò)的解答是一個經(jīng)過推理和匹配而得到的具有明確結(jié)果的新的語義網(wǎng)絡(luò)。語義網(wǎng)絡(luò)可用于表示多元關(guān)系,擴(kuò)展后可以表示更復(fù)雜的問題?？蚣苁且环N結(jié)構(gòu)化表示方法?？蚣芡ǔＳ芍付ㄊ挛锔鱾€方面的槽組成,每個槽擁有若干個側(cè)面,而每個側(cè)面又可擁有若干個值。大多數(shù)實用系統(tǒng)必須同時使用許多框架,并可把它們聯(lián)成一個框架系統(tǒng)?？蚣鼙硎疽勋@廣泛應(yīng)用,然而并非所有問題都可以用框架表示。劇本是框架的一種特殊形式,它使用一組槽來描述事件的發(fā)生序列。劇本表示特別適用于描述順序性動作或事件,但使用不如框架靈活,因此應(yīng)用范圍也不如框架那么廣泛。過程是一種知識的過程式表示,它將某一有關(guān)問題領(lǐng)域知識同這些使用方法一起,隱式地表示為一個問題求解過程。過程表示用程序來描述問題,具有很高的問題求解效率。由于知識隱含在程序中難以操作,所以適用范圍較窄。在表示和求解比較復(fù)雜的問題時,采用單一的知識表示方法是遠(yuǎn)遠(yuǎn)不夠的。往往必須采用多種方法混合表示。例如,綜合采用框架、語義網(wǎng)絡(luò)、謂詞邏輯的過程表示方法(兩種以上),可使所研究的問題獲得更有效的解決。此外,在選擇知識表示方法時,還要考慮所使用的程序設(shè)計語言所提供的功能和特點,以便能夠更好地描述這些表示方法。第三章搜索推理技術(shù)教學(xué)內(nèi)容:本章在上一章知識表示的基礎(chǔ)上研究問題求解的方法,是人工智能研究的又一核心問題。內(nèi)容包括早期搜索推理技術(shù),如圖搜索策略和消解原理；以及高級搜索推理技術(shù),如規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)、系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理。教學(xué)重點:圖搜索策略、消解原理、規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)。教學(xué)難點:啟發(fā)式搜索、規(guī)則雙向演繹系統(tǒng)等。教學(xué)方法：課堂教學(xué)為主,輔以恰當(dāng)?shù)膶嶒?。注意結(jié)合前面所學(xué)知識表示的基礎(chǔ)內(nèi)容,將其與問題求解方法融為一體。及時提問、收集學(xué)生學(xué)習(xí)情況。盡量使用實例和網(wǎng)絡(luò)課程中的多媒體素材進(jìn)行講解。教學(xué)要求：重點掌握一般圖搜索策略和消解原理,掌握各種搜索方法和產(chǎn)生式系統(tǒng)原理,了解規(guī)則演繹系統(tǒng)的基本原理,對系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理等高級推理技術(shù)作一般性了解。3.1圖搜索策略教學(xué)內(nèi)容:本節(jié)介紹圖搜索的一般策略,作為各種圖搜索技術(shù)的基礎(chǔ)。教學(xué)重點:圖搜索的一般過程、OPEN表和CLOSE表的概念。教學(xué)難點:OPEN表和CLOSE表的物理意義。教學(xué)方法：課堂教學(xué)為主,通過提問徹底弄清圖搜索的基本概念。教學(xué)要求：重點掌握圖搜索一般策略,掌握OPEN表和CLOSE表的構(gòu)成及作用。1.圖搜索策略的定義圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點和目標(biāo)節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。研究圖搜索的一般策略,能夠給出圖搜索過程的一般步驟。2.圖搜索算法中的幾個重要名詞術(shù)語（1）OPEN表與CLOSE表（2）搜索圖與搜索樹3.圖搜索(GRAPHSEARCH)的一般過程(1)建立一個只含有起始節(jié)點S的搜索圖G,把S放到一個叫做OPEN的未擴(kuò)展節(jié)點表中。(2)建立一個叫做CLOSED的已擴(kuò)展節(jié)點表,其初始為空表。(3)LOOP:若OPEN表是空表,則失敗退出。(4)選擇OPEN表上的第一個節(jié)點,把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點為節(jié)點n。(5)若n為一目標(biāo)節(jié)點,則有解并成功退出,此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。(6)擴(kuò)展節(jié)點n,同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。(7)對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設(shè)置一個通向n的指針。把M的這些成員加進(jìn)OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個M成員,確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員,確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。(8)按某一任意方式或按某個探試值,重排OPEN表。(9)GOLOOP。4.圖搜索方法分析:圖搜索過程的第8步對OPEN表上的節(jié)點進(jìn)行排序,以便能夠從中選出一個“最好”的節(jié)點作為第4步擴(kuò)展用。這種排序可以是任意的即盲目的(屬于盲目搜索),也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù)(屬于啟發(fā)式搜索)。每當(dāng)被選作擴(kuò)展的節(jié)點為目標(biāo)節(jié)點時,這一過程就宣告成功結(jié)束。這時,能夠重現(xiàn)從起始節(jié)點到目標(biāo)節(jié)點的這條成功路徑,其辦法是從目標(biāo)節(jié)點按指針向S返回追溯。當(dāng)搜索樹不再剩有未被擴(kuò)展的端節(jié)點時,過程就以失敗告終(某些節(jié)點最終可能沒有后繼節(jié)點,所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下,從起始節(jié)點出發(fā),一定達(dá)不到目標(biāo)節(jié)點。3.2盲目搜索教學(xué)內(nèi)容:介紹三種盲目搜索方法,即寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價搜索。教學(xué)重點:盲目搜索的特點,寬度優(yōu)先搜索。教學(xué)難點:等代價搜索中代價的概念。教學(xué)方法：以實例強化內(nèi)容的學(xué)習(xí),通過提問引導(dǎo)學(xué)生對三種方法的特點進(jìn)行比較。教學(xué)要求：掌握盲目搜索的特點,比較三種盲目搜索方法的優(yōu)缺點。3.2.1寬度優(yōu)先搜索1.定義如果搜索是以接近起始節(jié)點的程度依次擴(kuò)展節(jié)點的,那么這種搜索就叫做寬度優(yōu)先搜索(breadth-firstsearch)。2.特點這種搜索是逐層進(jìn)行的；在對下一層的任一節(jié)點進(jìn)行搜索之前,必須搜索完本層的所有節(jié)點。3.寬度優(yōu)先搜索算法(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(jié)點,則求得一個解答)。(2)如果OPEN是個空表,則沒有解,失敗退出；否則繼續(xù)。(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出,并把它放入CLOSED的擴(kuò)展節(jié)點表中。(4)擴(kuò)展節(jié)點n。如果沒有后繼節(jié)點,則轉(zhuǎn)向上述第(2)步。(5)把n的所有后繼節(jié)點放到OPEN表的末端,并提供從這些后繼節(jié)點回到n的指針。(6)如果n的任一個后繼節(jié)點是個目標(biāo)節(jié)點,則找到一個解答,成功退出；否則轉(zhuǎn)向第(2)步。4.寬度優(yōu)先搜索方法分析:寬度優(yōu)先搜索是圖搜索一般過程的特殊情況,將圖搜索一般過程中的第8步具體化為本算法中的第6步,這實際是將OPEN表作為“先進(jìn)先出”的隊列進(jìn)行操作。寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在,那么對有限圖來說,我們就說該法失敗退出；對于無限圖來說,則永遠(yuǎn)不會終止)。5、例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹,這個問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題：123847653.2.2深度優(yōu)先搜索1.定義在此搜索中,首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。這種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-firstsearch)。2.特點首先,擴(kuò)展最深的節(jié)點的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個沒有后裔的狀態(tài)時,它才考慮另一條替代的路徑。3.深度界限為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴(kuò)展下去),往往給出一個節(jié)點擴(kuò)展的最大深度——深度界限。任何節(jié)點如果達(dá)到了深度界限,那么都將把它們作為沒有后繼節(jié)點處理。4.含有深度界限的深度優(yōu)先搜索算法請同學(xué)們課后自學(xué),并回答課后思考題。思考題:有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點的最短途徑嗎？3.2.3等代價搜索1.定義寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價的路徑問題,這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法。2.等代價搜索中的幾個記號起始節(jié)點記為S；從節(jié)點i到它的后繼節(jié)點j的連接弧線代價記為c(i,j)；從起始節(jié)點S到任一節(jié)點i的路徑代價記為g(i)。3.等代價搜索算法（請同學(xué)們課后認(rèn)真閱讀本算法,指出與寬度優(yōu)先、深度優(yōu)先算法有何特別之處。）4.等代價搜索方法分析如果所有的連接弧線具有相等的代價,那么等代價算法就簡化為寬度優(yōu)先搜索算法。3.3啟發(fā)式搜索教學(xué)內(nèi)容:啟發(fā)式搜索策略概述和有序搜索。啟發(fā)式搜索彌補盲目搜索的不足,提高搜索效率。教學(xué)重點:啟發(fā)式搜索策略、啟發(fā)信息和有序搜索。教學(xué)難點:估價函數(shù)的設(shè)計、A*算法原理。教學(xué)方法：通過實例加深對原理的理解,鼓勵同學(xué)擴(kuò)大閱讀范圍。教學(xué)要求：掌握啟發(fā)式搜索策略和估價函數(shù)的設(shè)計方法,了解A*算法原理。3.3.1啟發(fā)式搜索策略和估價函數(shù)1.為什么需要啟發(fā)式搜索盲目搜索效率低,耗費過多的計算空間與時間,這是組合爆炸的一種表現(xiàn)形式。2.定義進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息,把此種信息叫做啟發(fā)信息。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。3.啟發(fā)式搜索策略有關(guān)具體問題領(lǐng)域的信息常?？梢杂脕砗喕阉?。一個比較靈活(但代價也較大)的利用啟發(fā)信息的方法是應(yīng)用某些準(zhǔn)則來重新排列每一步OPEN表中所有節(jié)點的順序。然后,搜索就可能沿著某個被認(rèn)為是最有希望的邊緣區(qū)段向外擴(kuò)展。應(yīng)用這種排序過程,需要某些估算節(jié)點“希望”的量度,這種量度叫做估價函數(shù)(evalutionfunction)。4.估價函數(shù)為獲得某些節(jié)點“希望”的啟發(fā)信息,提供一個評定侯選擴(kuò)展節(jié)點的方法,以便確定哪個節(jié)點最有可能在通向目標(biāo)的最佳路徑上。

f(n)——表示節(jié)點n的估價函數(shù)值建立估價函數(shù)的一般方法:試圖確定一個處在最佳路徑上的節(jié)點的概率；提出任意節(jié)點與目標(biāo)集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點來決定棋局的得分?jǐn)?shù)。這些特點被認(rèn)為與向目標(biāo)節(jié)點前進(jìn)一步的希望程度有關(guān)。3.3.2有序搜索1.定義用估價函數(shù)f來排列GRAPHSEARCH第8步中OPEN表上的節(jié)點。應(yīng)用某個算法(例如等代價算法)選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴(kuò)展的節(jié)點。這種搜索方法叫做有序搜索(orderedsearch)或最佳優(yōu)先搜索(best-firstsearch),而其算法就叫做有序搜索算法或最佳優(yōu)先算法。尼爾遜(Nilsson)曾提出一個有序搜索的基本算法。估價函數(shù)f是這樣確定的：一個節(jié)點的希望程序越大,其f值就越小。被選為擴(kuò)展的節(jié)點,是估價函數(shù)最小的節(jié)點。2.實質(zhì)選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴(kuò)展的節(jié)點,即總是選擇最有希望的節(jié)點作為下一個要擴(kuò)展的節(jié)點。3.有序狀態(tài)空間搜索算法(1)把起始節(jié)點S放到OPEN表中,計算f(S)并把其值與節(jié)點S聯(lián)系起來。(2)如果OPEN是個空表,則失敗退出,無解。(3)從OPEN表中選擇一個f值最小的節(jié)點i。結(jié)果有幾個節(jié)點合格,當(dāng)其中有一個為目標(biāo)節(jié)點時,則選擇此目標(biāo)節(jié)點,否則就選擇其中任一個節(jié)點作為節(jié)點i。(4)把節(jié)點i從OPEN表中移出,并把它放入CLOSED的擴(kuò)展節(jié)點表中。(5)如果i是個目標(biāo)節(jié)點,則成功退出,求得一個解。(6)擴(kuò)展節(jié)點i,生成其全部后繼節(jié)點。對于i的每一個后繼節(jié)點j：(a)計算f(j)。(b)如果j既不在OPEN表中,又不在CLOSED表中,則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點i的指針,以便一旦找到目標(biāo)節(jié)點時記住一個解答路徑。(c)如果j已在OPEN表上或CLOSED表上,則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值。如果新的f值較小,則(i)以此新值取代舊值。(ii)從j指向i,而不是指向它的父輩節(jié)點。(iii)如果節(jié)點j在CLOSED表中,則把它移回OPEN表。(7)轉(zhuǎn)向(2),即GOTO(2)。4.有序搜索方法分析寬度優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。對于寬度優(yōu)先搜索,選擇f(i)作為節(jié)點i的深度。對于等代價搜索,f(i)是從起始節(jié)點至節(jié)點i這段路徑的代價。有序搜索的有效性直接取決于f的選擇,如果選擇的f不合適,有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準(zhǔn)確的希望量度,那么f的選擇將涉及兩個方面的內(nèi)容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。5、例:八數(shù)碼難題采用了簡單的估價函數(shù)f(n)=d(n)+W(n)其中:d(n)是搜索樹中節(jié)點n的深度；W(n)用來計算對應(yīng)于節(jié)點n的數(shù)據(jù)庫中錯放的棋子個數(shù)。因此,起始節(jié)點棋局28316475的f值等于0+4=4。3.3.3A*算法A*算法是一種有序搜索算法,其特點在于對估價函數(shù)的定義上。1.幾個記號令k(ni,nj)表示任意兩個節(jié)點ni和nj之間最小代價路徑的實際代價(對于兩節(jié)點間沒有通路的節(jié)點,函數(shù)k沒有定義)。于是,從節(jié)點n到某個具體的目標(biāo)節(jié)點ti,某一條最小代價路徑的代價可由k(n,ti)給出。令h*(n)表示整個目標(biāo)節(jié)點集合｛ti｝上所有k(n,ti)中最小的一個,因此,h*(n)就是從n到目標(biāo)節(jié)點最小代價路徑的代價,而且從n到目標(biāo)節(jié)點能夠獲得h*(n)的任一路徑就是一條從n到某個目標(biāo)節(jié)點的最佳路徑(對于任何不能到達(dá)目標(biāo)節(jié)點的節(jié)點n,函數(shù)h*沒有定義)。2.估價函數(shù)的定義定義g*為g*(n)=k(S,n)定義函數(shù)f*,使得在任一節(jié)點n上其函數(shù)值f*(n)就是從節(jié)點S到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到某目標(biāo)節(jié)點的一條最佳路徑的代價之和,即f*(n)=g*(n)+h*(n)希望估價函數(shù)f是f*的一個估計,此估計可由下式給出:f(n)=g(n)+h(n)其中:g是g*的估計；h是h*的估計。對于g(n)來說,一個明顯的選擇就是搜索樹中從S到n這段路徑的代價,這一代價可以由從n到S尋找指針時,把所遇到的各段弧線的代價加起來給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價路徑)。這個定義包含了g(n)≥g*(n)。h*(n)的估計h(n)依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù)W(n)所用的那種信息相似。把h叫做啟發(fā)函數(shù)。3.A*算法定義定義1在GRAPHSEARCH過程中,如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的,則稱該過程為A算法。定義2在A算法中,如果對所有的x存在h(x)≤h*(x),則稱h(x)為h*(x)的下界,它表示某種偏于保守的估計。定義3采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法,稱為A*算法。當(dāng)h=0時,A*算法就變?yōu)橛行蛩阉魉惴ā?.A*算法A*算法描述參考教材。3.4消解原理教學(xué)內(nèi)容:消解原理是針對謂詞邏輯知識表示的問題求解方法。本節(jié)內(nèi)容主要包括子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。教學(xué)重點:子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。教學(xué)難點:消解反演的思想。教學(xué)方法：實例講解,注重課堂練習(xí)。教學(xué)要求：重點掌握子句集的求解步驟和消解反演過程,掌握消解推理的規(guī)則。消解原理的基礎(chǔ)知識:（1）謂詞公式、某些推理規(guī)則以及置換合一等概念。（2）子句:由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。（3）消解：當(dāng)消解可使用時,消解過程被應(yīng)用于母體子句對,以便產(chǎn)生一個導(dǎo)出子句。例如,如果存在某個公理E1∨E2和另一公理～E2∨E3,那么E1∨E3在邏輯上成立。這就是消解,而稱E1∧E3為E1∨E2和～E2∨E3的消解式(resolvent)。提問：現(xiàn)有公式提問：現(xiàn)有公式[(AB)B]∨C，在消去蘊涵符號后得到公式：A．[～(AB)∨B]∨CB．[～(A∨B)∧B]∨CC．[～(～A∨B)∨B]∨CD．[(A∨B)∨B]∨C1.步驟(1)消去蘊涵符號只應(yīng)用∨和～符號,以～A∨B替換A=>B。(2)減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上,并反復(fù)應(yīng)用狄·摩根定律。例如:以～A∨～B代替～(A∧B)以～A∧～B代替～(A∨B)以A代替～(～A)以(x)｛～A｝代替～(x)A以(x)｛～A｝代替～(x)A(3)對變量標(biāo)準(zhǔn)化在任一量詞轄域內(nèi),受該量詞約束的變量為一啞元(虛構(gòu)變量),它可以在該轄域內(nèi)處處統(tǒng)一地被另一個沒有出現(xiàn)過的任意變量所代替,而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)化意味著對啞元改名以保證每個量詞有其自己唯一的啞元。(4)消去存在量詞用Skolem函數(shù)代替存在的x,就可以消去全部存在量詞,并寫成:(y)P［g(y),y］從一個公式消去一個存在量詞的一般規(guī)則是以一個Skolem函數(shù)代替每個出現(xiàn)的存在量詞的量化變量,而這個Skolem函數(shù)的變量就是由那些全稱量詞所約束的全稱量詞量化變量,這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所使用的函數(shù)符號必須是新的,即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號。例如:(
y)(
x)P(x,y)被〔(
y)P(g(y),y)〕代替,其中g(shù)(y)為一Skolem函數(shù)。如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi),則用不含變量的Skolem函數(shù)即常量。例如,(
x)P(x)化為P(A),其中常量符號A用來表示人們知道的存在實體。A必須是個新的常量符號,它未曾在公式中其它地方使用過。(5)化為前束形把所有全稱量詞移到公式的左邊,并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為前束形。(6)把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。(7)消去全稱量詞消去明顯出現(xiàn)的全稱量詞。(8)消去連詞符號∧用｛A,B｝代替(A∧B),以消去明顯的符號∧。反復(fù)代替的結(jié)果,最后得到一個有限集,其中每個公式是文字的析取。任一個只由文字的析取構(gòu)成的合適公式叫做一個子句。(9)更換變量名稱可以更換變量符號的名稱,使一個變量符號不出現(xiàn)在一個以上的子句中。2.例將下列謂詞演算公式化為一個子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝3.說明并不是所有問題的謂詞公式化為子句集都需要上述9個步驟。對于某些問題,可能不需要其中的一些步驟。3.4.2消解推理規(guī)則1.消解式令L1為任一原子公式,L2為另一原子公式；L1和L2具有相同的謂詞符號,但一般具有不同的變量。已知兩子句L1∨α和～L2∨β,如果L1和L2具有最一般合一者σ,那么通過消解可以從這兩個父輩子句推導(dǎo)出一個新子句(α∨β)σ。這個新子句叫做消解式。它是由取這兩個子句的析取,然后消去互補對而得到的。2.消解式求法(a)假言推理父輩子句P～P∨Q(即P=>Q)消解式Q

(b)合并(c)重言式(d)空子句(矛盾)說明：說明：對合并、重言式、鏈?zhǔn)?三段論)請同學(xué)們自行閱讀?！玃PNIL(e)鏈?zhǔn)?三段論)即取各子句的析取,然后消去互補對。3.4.3含有變量的消解式1.消解式求法為了對含有變量的子句使用消解規(guī)則,必須找到一個置換,作用于父輩子句使其含有互補文字。2.例子P(x)∨Q(x)～Q［f(y)］置換σ=｛f(y)/x｝P［f(y)］3.4.4消解反演求解過程1.基本思想把要解決的問題作為一個要證明的命題,其目標(biāo)公式被否定并化成子句形,然后添加到命題公式集中去,把消解反演系統(tǒng)應(yīng)用于聯(lián)合集,并推導(dǎo)出一個空子句(NIL),產(chǎn)生一個矛盾,這說明目標(biāo)公式的否定式不成立,即有目標(biāo)公式成立,定理得證,問題得到解決,與數(shù)學(xué)中反證法的思想十分相似。2.消解反演反演求解的步驟給出一個公式集S和目標(biāo)公式L,通過反證或反演來求證目標(biāo)公式L,其證明步驟如下:(1)否定L,得～L；(2)把～L添加到S中去；(3)把新產(chǎn)生的集合｛～L,S｝化成子句集；(4)應(yīng)用消解原理,力圖推導(dǎo)出一個表示矛盾的空子句NIL。反演求解的正確性設(shè)公式L在邏輯上遵循公式集S,那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足～L的,所以不存在能夠滿足并集S∪｛～L｝的解釋。如果一個公式集不能被任一解釋所滿足,那么這個公式是不可滿足的。因此,如果L在邏輯上遵循S,那么S∪｛～L｝是不可滿足的?？梢宰C明,如果消解反演反復(fù)應(yīng)用到不可滿足的子句集,那么最終將要產(chǎn)生空子句NIL。因此,如果L在邏輯上遵循S,那么由并集S∪｛～L｝消解得到的子句,最后將產(chǎn)生空子句；反之,可以證明,如果從S∪｛～L｝的子句消解得到空子句,那么L在邏輯上遵循S。3.反演求解過程步驟:(1)把由目標(biāo)公式的否定產(chǎn)生的每個子句添加到目標(biāo)公式否定之否定的子句中去。(2)按照反演樹,執(zhí)行和以前相同的消解,直至在根部得到某個子句止。(3)用根部的子句作為一個回答語句。分析:答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個語句的一顆證明樹。由于變換關(guān)系涉及到把由目標(biāo)公式的否定產(chǎn)生的每個子句變換為一個重言式,所以被變換的證明樹就是一棵消解的證明樹,其在根部的語句在邏輯上遵循公理加上重言式,因而也單獨地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。例:儲蓄問題前提:每個儲蓄錢的人都獲得利息。結(jié)論：如果沒有利息,那么就沒有人去儲蓄錢3.5規(guī)則演繹系統(tǒng)教學(xué)內(nèi)容:規(guī)則演繹系統(tǒng)屬于高級搜索推理技術(shù),用于解決比較復(fù)雜的系統(tǒng)和問題。本節(jié)介紹規(guī)則演繹系統(tǒng)的定義及其三種推理方法:規(guī)則正向演繹系統(tǒng)、規(guī)則逆向演繹系統(tǒng)和規(guī)則雙向演繹系統(tǒng)。教學(xué)重點:規(guī)則演繹系統(tǒng)的定義、正向推理和逆向推理過程。教學(xué)難點:雙向演繹的匹配問題等。教學(xué)方法:課堂教學(xué)為主。通過比較揭示正向推理、逆向推理和雙向推理的特點。教學(xué)要求：掌握規(guī)則演繹系統(tǒng)的定義和正向推理、逆向推理的過程,了解規(guī)則雙向演繹系統(tǒng)。規(guī)則演繹系統(tǒng)的定義:基于規(guī)則的問題求解系統(tǒng)運用下述規(guī)則來建立:If→Then其中,If部分可能由幾個if組成,而Then部分可能由一個或一個以上的then組成。在所有基于規(guī)則系統(tǒng)中,每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中,then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rulebaseddeductionsystem)。在這種系統(tǒng)中,通常稱每個if部分為前項(antecedent),稱每個then部分為后項(consequent)。3.5.1規(guī)則正向演繹系統(tǒng)1.定義正向規(guī)則演繹系統(tǒng)是從事實到目標(biāo)進(jìn)行操作的,即從狀況條件到動作進(jìn)