人工智能(講稿)

1、 人工智能ArtificialIntelligence-Al第一章：概述產(chǎn)業(yè)革命成功地實(shí)現(xiàn)了用機(jī)器來(lái)替代人類長(zhǎng)期從事的一些笨重、危險(xiǎn)的體力勞動(dòng)，可以說(shuō)人類的體能在力量和速度上被機(jī)器放大了。機(jī)器甚至能完成人類手工不能完成的許多工作，機(jī)器使人類從繁重的體力勞動(dòng)中解放出來(lái)。人類很早就開(kāi)始了智能問(wèn)題的研究和探索，到20世紀(jì)50年代(1950)，隨著數(shù)字計(jì)算機(jī)的發(fā)明和快速發(fā)展，被日益廣泛的應(yīng)用于替代人類進(jìn)行數(shù)字運(yùn)算處理，極大的提高了數(shù)字運(yùn)算的速度和效率。人們自然聯(lián)想到能否用這樣的“機(jī)器”來(lái)替代人類非數(shù)字運(yùn)算的其它智力勞動(dòng)，放大人類的智能。許多學(xué)科的一大批科學(xué)家和工程技術(shù)人員投入到這一領(lǐng)域的研究和開(kāi)發(fā)。人

2、工智能經(jīng)過(guò)長(zhǎng)期的孕育過(guò)程，終于誕生了。人工智能是當(dāng)前科學(xué)技術(shù)發(fā)展中的一門(mén)前言學(xué)科；是一門(mén)新思想、新觀念、新理論、新技術(shù)不斷出現(xiàn)的科學(xué)，正在迅速發(fā)展的學(xué)科。它是在計(jì)算機(jī)科學(xué)、控制論、信息論、神經(jīng)心理學(xué)、哲學(xué)、語(yǔ)言學(xué)等眾多學(xué)科的基礎(chǔ)上發(fā)展起來(lái)的，是一門(mén)綜合性的邊緣學(xué)科。什么是人工智能智能(Intelligence)什么是智能？智能的本質(zhì)是什么？是古今中外許多科學(xué)家至今仍在努力探索的問(wèn)題，一直沒(méi)有完全解決。智能問(wèn)題被列為四大自然奧秘之一：智能的發(fā)生、物質(zhì)的本質(zhì)、宇宙的起源、生命的本質(zhì)。一、關(guān)于智能的理論目前人們通常基于對(duì)人的大腦的已有認(rèn)識(shí)，將其與智能的外在表現(xiàn)結(jié)合起來(lái)，從不同角度、不同側(cè)面、用不同的

3、方法對(duì)智能進(jìn)行研究，提出的觀點(diǎn)和得出的結(jié)論也不相同。很難給出一個(gè)統(tǒng)一的、科學(xué)的智能定義。其中比較有影響的思維理論、知識(shí)閾值理論、進(jìn)化理論等。1思維理論認(rèn)為智能的核心是思維，人的一切智慧或智能都來(lái)自于大腦的思維活動(dòng)，人的一切知識(shí)都是人們思維的產(chǎn)物，因而通過(guò)對(duì)思維規(guī)律和方法的研究可望揭示智能的本質(zhì)。2知識(shí)閾值理論強(qiáng)調(diào)知識(shí)對(duì)于智能的重要性和作用。認(rèn)為智能行為取決于知識(shí)的數(shù)量及其一般化程度，一個(gè)系統(tǒng)之所以具有智能是因?yàn)樗哂锌蛇\(yùn)用的知識(shí)。將智能定義為：智能就是在巨大搜索空間中找到滿意解的能力。這一理論在人工智能發(fā)展史上有著重要的影響，知識(shí)工程、專家系統(tǒng)等都是在這一理論影響下發(fā)展起來(lái)的。3進(jìn)化理論有MI

4、T的R.A.Brook教授提出，1991年提出“沒(méi)有表達(dá)的智能”，1992年提出“沒(méi)有推理的智能”。認(rèn)為人的本質(zhì)能力是在動(dòng)態(tài)環(huán)境中的對(duì)外界事物的感知能力、行動(dòng)能力、維持生命的能力和繁衍生息的能力等，正是這些能力為智能的發(fā)展提供了基礎(chǔ)。這個(gè)理論的核心是用控制取代表式，從而去消概念、模型、及顯示表示的知識(shí)，否定抽象對(duì)于智能及智能模擬的必要性，強(qiáng)調(diào)分層結(jié)構(gòu)對(duì)于智能進(jìn)化的可能性和必要性。尚未形成完整的理論體系。二、智能的特征1具有感知能力通過(guò)視覺(jué)、聽(tīng)覺(jué)、觸覺(jué)、味覺(jué)、嗅覺(jué)等感知器官獲取外界環(huán)境信息，經(jīng)過(guò)大腦加工為知識(shí)。人類感知的信息80%通過(guò)視覺(jué)、10%通過(guò)聽(tīng)覺(jué)。2具有記憶及思維能力記憶和思維是人腦的重

5、要功能，是人類具有智能的根本原因之所在。記憶-存儲(chǔ)感知的環(huán)境信息和有思維產(chǎn)生的值是。思維-對(duì)記憶的信息進(jìn)行處理，即利用已有知識(shí)對(duì)信息進(jìn)行分析、計(jì)算、比較、判斷、推理、決策等。思維是一個(gè)動(dòng)態(tài)的過(guò)程，是獲取知識(shí)和運(yùn)用知識(shí)求解問(wèn)題的根本途徑。三種思維方式：邏輯思維(抽象思維)形象思維(直感思維)頓悟思維(靈感思維)3具有學(xué)習(xí)能力和自適應(yīng)能力學(xué)習(xí)是人的本能，每個(gè)人隨時(shí)隨地都在學(xué)習(xí)。自覺(jué)的、有意識(shí)的學(xué)習(xí)；不自覺(jué)、無(wú)意識(shí)的學(xué)習(xí)；有教師指導(dǎo)的學(xué)習(xí)；通過(guò)自身實(shí)踐的學(xué)習(xí)。人類通過(guò)和環(huán)境的相互作用，不斷的進(jìn)行學(xué)習(xí)、積累知識(shí)、增長(zhǎng)能力，適應(yīng)環(huán)境的變化。由于人類個(gè)體所出的環(huán)境不同、條件不同，學(xué)習(xí)的效果不同，體現(xiàn)出個(gè)體

6、智能的差異性。4具有行為能力響應(yīng)感知的環(huán)境輸入信息，自覺(jué)或下意識(shí)的做出動(dòng)作行為。人工智能ArtificialIntelligence1智能機(jī)器能夠在各種環(huán)境下，自主地或交互地執(zhí)行各種擬人任務(wù)的機(jī)器。2人工智能學(xué)科是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和使用智能機(jī)器的一個(gè)分支。它的近期目標(biāo)在于研究用機(jī)器來(lái)模仿和執(zhí)行人腦的某些功能，并開(kāi)發(fā)相關(guān)理論和技術(shù)。3人工智能能力智能機(jī)器執(zhí)行的通常與人類智能有關(guān)的功能，如感知、分析、判斷、推理、證明、識(shí)別、理解、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng)。4人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，是研究使用計(jì)算機(jī)來(lái)完成能表現(xiàn)人類智能任務(wù)的科學(xué)。主要包括計(jì)算機(jī)實(shí)現(xiàn)智能的原理，制造

7、類似人腦的智能計(jì)算機(jī)，以及使計(jì)算機(jī)更巧妙地實(shí)現(xiàn)更高級(jí)的應(yīng)用。它涉及到計(jì)算機(jī)科學(xué)、心理學(xué)、哲學(xué)和語(yǔ)言學(xué)等?？偟哪繕?biāo)是擴(kuò)展人類的智能活動(dòng)。5從實(shí)用的觀點(diǎn)看，是一門(mén)知識(shí)工程學(xué)，以知識(shí)為對(duì)象，研究知識(shí)的獲取、知識(shí)的表示方法、知識(shí)的實(shí)用。6NilsJ.Nilsson(U.S.A)ArtificialIntelligence(AI),Broadly(andsomewhatcircularly)defined,isconcernedwithintelligentbehaviorinartifacts.Intelligentbehavior,inturn,involvesperception,reasonin

8、g,learning,communicating,andactingincomplexenvironments.AIhasasoneofitslong-termgoalsthedevelopmentofmachinesthatcandothesethingsaswellashumanscan,orpossiblyevenbetter.AnothergoalofAIistounderstandthiskindofbehaviorwhetheritoccursinmachinesorinhumansorotheranimals.Thus,AIhasbothengineeringandscienti

9、ficgoals.機(jī)器智能實(shí)驗(yàn)圖靈實(shí)驗(yàn)A.M.Turing19241954英國(guó)超時(shí)代的天才數(shù)學(xué)家。1950年發(fā)表論文”ComputingMachineryandIntelligence”，文中提出CanMachinesthink?并給出了著名的TuringTest圖靈測(cè)試，用于測(cè)試一臺(tái)機(jī)器是否具有智能。圖靈測(cè)試：將智力健全的人和智能機(jī)器分別置于兩個(gè)房間，彼此不可見(jiàn)，但可以通話。通過(guò)交談，如果人不能辨別對(duì)方是計(jì)器或是人，那么這臺(tái)機(jī)器即具有智能。圖靈還設(shè)計(jì)了成為“圖靈夢(mèng)想”的問(wèn)題對(duì)答：人一詢問(wèn)者、機(jī)器一智者；假設(shè)兩者都讀過(guò)狄更斯(C.Dickens)的小說(shuō)匹克威克外傳。詢問(wèn)者智者詢問(wèn)者智者詢問(wèn)者智

10、者詢問(wèn)者智者你的14行詩(shī)的首行為“你如同夏日”，你不覺(jué)得“春日”更好嗎？：它不合韻?！岸铡比绾?？它可是完全合韻的。它確是合韻的，但沒(méi)有人愿被比為“冬日”。：你不是說(shuō)過(guò)匹克威克先生能讓你想起圣誕節(jié)嗎？：是的。：圣誕節(jié)是冬天的一個(gè)日子，我想匹克威克先生對(duì)這個(gè)比喻不會(huì)介意吧？我認(rèn)為你不夠嚴(yán)謹(jǐn)，“冬日”指的是一般的冬天的日子，而不是某個(gè)特別的日子，如圣誕節(jié)。圖靈測(cè)試存在的問(wèn)題：1。人的智力水平；2。問(wèn)題的智力標(biāo)準(zhǔn)；3。實(shí)驗(yàn)強(qiáng)調(diào)了結(jié)果，不能反映思維的過(guò)程。人工智能與傳統(tǒng)程序的區(qū)別研究符號(hào)表示的知識(shí)，而不只是數(shù)值、數(shù)據(jù)；啟發(fā)式推理方法，而不是傳統(tǒng)算法；控制結(jié)構(gòu)和領(lǐng)域知識(shí)分離；允許結(jié)果誤差、甚至錯(cuò)誤。人工

11、智能發(fā)展簡(jiǎn)史“人工智能”，1956年首次作為一門(mén)新興學(xué)科正式提出，現(xiàn)在已經(jīng)成為一門(mén)充滿生機(jī)和希望的前沿學(xué)科，是涉及到計(jì)算機(jī)科學(xué)、心理學(xué)、哲學(xué)、數(shù)學(xué)等許多學(xué)科的交叉學(xué)科。已經(jīng)獲得了許多重要的理論和技術(shù)成果。它的發(fā)展經(jīng)歷了孕育、形成、發(fā)展等幾個(gè)階段。一、孕育(1956年之前)公元前，亞里斯多德(Aristotle,公元前384322年)在其名著工具論中提出了形式邏輯的一些主要定律，他提出的三段論至今仍是演繹推理的基本依據(jù)。英國(guó)科學(xué)家培根(F.Bacon,1562-1626)曾系統(tǒng)提出了歸納法。3德國(guó)數(shù)學(xué)家萊布尼茲(G.Leibniz,16461761)提出了萬(wàn)能符號(hào)和推理計(jì)算的思想英國(guó)邏輯學(xué)家布爾

12、(G.Boole,18151864)布爾代數(shù)在思維法則中首先用符號(hào)語(yǔ)言描述了思維活動(dòng)的基本推理規(guī)則。英國(guó)數(shù)學(xué)家圖靈(Turing)1936年提出理想計(jì)算的數(shù)字模型圖靈機(jī)為數(shù)字計(jì)算機(jī)誕生奠定理論基礎(chǔ)。美國(guó)神經(jīng)生理學(xué)家麥克洛奇(W.Moculloch)與匹滋(W.pits)1947年提出一個(gè)神經(jīng)網(wǎng)絡(luò)模型(MP)模型，至今仍在使用。美國(guó)數(shù)學(xué)家莫克利(J.W.Mauchly)和?？颂?J.P.Eckert)在1946年研制出的第一臺(tái)電子計(jì)算機(jī)ENIAC。二、形成(1956-1969)1956年夏天，美國(guó)Dartmouth大學(xué)年輕的數(shù)學(xué)助教J.W.McCarthy聯(lián)合他的三個(gè)朋友：M.L.Minsky-

13、哈佛大學(xué)年輕的數(shù)學(xué)家和神經(jīng)學(xué)家，N.Lochester-IBM信息研究中心負(fù)責(zé)人，C.E.Shannon-貝爾實(shí)驗(yàn)室研究信息的數(shù)學(xué)家，四人共同發(fā)起并邀請(qǐng)：T.More-IBMA.L.Samuel-IBMO.Selfredge-MITR.Solomonff-MITA.Newell-RANDH.A.Simon-Carnagie(卡奈基一梅隆大學(xué))舉辦長(zhǎng)達(dá)兩個(gè)月的夏季研討班。這次會(huì)上首次使用”ArtificialIntelligence-AI”一詞，標(biāo)志著AI學(xué)科的正式誕生。自這次會(huì)議后10年，人工智能研究取得了許多令人矚目的成就。紐厄爾.肖和西蒙合作編制了稱邏輯理論機(jī)的程序系統(tǒng)，模擬人用數(shù)學(xué)邏輯證

14、明定理的思維規(guī)律，用分解(分解為子問(wèn)題)，代入(常量代入變量)，替換等方法，處理待定的定理。該程序證明了數(shù)學(xué)原理第二章中的38條定理，改進(jìn)后，1963年證明了該章全部52條定理。1956年塞繆爾研制跳棋程序具有自學(xué)習(xí)、自組織和自適應(yīng)能力，是一個(gè)啟發(fā)式程序。可以向人學(xué)習(xí)下棋經(jīng)驗(yàn)，自己積累經(jīng)驗(yàn)，學(xué)習(xí)棋譜。1959年擊敗本人，1960年擊敗一個(gè)洲冠軍。1958年美籍華人數(shù)理邏輯學(xué)家王浩，在IBM704上證明了數(shù)學(xué)原理中有關(guān)命題演算的全部220條定理，150條謂詞演算定理中的80%。1959年用8.4分鐘完成上述全部工作。1965年Robinson提出歸結(jié)原理。5.模式識(shí)別方面1959年O.Selfr

15、edge模式識(shí)別程序。1965年Roberts編制出分辨積木結(jié)構(gòu)程序。題求解方面1960年Newell等通過(guò)心理學(xué)實(shí)驗(yàn)總結(jié)出了人們求解問(wèn)題的規(guī)律，編制了通用問(wèn)題求解程序GPS,可用來(lái)求解11種問(wèn)題，GPS研究共持續(xù)10年。家系統(tǒng)方面E.A.Feigenbaum自1965年開(kāi)始研究DENDRAL，1968年完成并進(jìn)入使用。質(zhì)譜儀數(shù)據(jù),推斷化合物的分子結(jié)構(gòu)。8.人工智能語(yǔ)言1960年McCarthy研制出Lisp語(yǔ)言。1969年成立了國(guó)際人工智能聯(lián)合會(huì)(IJCAI),InternationalJointConferencesOnArtificialIntelligence里程碑，標(biāo)志人工智能學(xué)科得

16、到肯定與公認(rèn)。三、發(fā)展(1970年后)世界范圍的研究和探索。1972年法國(guó)馬賽大學(xué)的A.Comerauer,實(shí)現(xiàn)prolog。1972年MYCIN診斷和治療感染新性疾病專家系統(tǒng)。1970年InternationalJournalofAI創(chuàng)刊。1972年WinograelShrdlv自然語(yǔ)言理解系統(tǒng)。1974年Minsky框架表示法。1977年Feignbaum知識(shí)工程。其它專家系統(tǒng)：80年代專家系統(tǒng)和知識(shí)工程迅速發(fā)展，推理技術(shù)、知識(shí)獲取、自然語(yǔ)言理解、機(jī)器視覺(jué)研究、不確定、非單調(diào)推理、定性推理。神經(jīng)網(wǎng)絡(luò)提出Hopfield網(wǎng)絡(luò)，Rumelhart提出BP學(xué)習(xí)算法。90年代，理論化、實(shí)用化方向迅

17、速發(fā)展。四、中國(guó)人工智能研究1978年智能模擬研究納入國(guó)家計(jì)劃。1984年智能計(jì)算機(jī)及其系統(tǒng)全國(guó)學(xué)術(shù)討論。年智能計(jì)算機(jī)系統(tǒng)、智能機(jī)器人和智能信息處理（含模式識(shí)別）納入高技術(shù)計(jì)劃。1993年智能控制和智能自動(dòng)化納入攀登計(jì)劃。1981年后相繼成立：中國(guó)人工智能學(xué)會(huì)（CAAL）;全國(guó)高校人工智能研究會(huì)；中國(guó)計(jì)算機(jī)學(xué)會(huì)人工智能與模式識(shí)別專業(yè)；中國(guó)自動(dòng)化學(xué)會(huì)模式識(shí)別委員會(huì)與機(jī)器智能委員會(huì)；中國(guó)軟行業(yè)協(xié)會(huì)人工智能協(xié)會(huì)；中國(guó)智能機(jī)器人專業(yè)委員會(huì)；中國(guó)計(jì)算機(jī)視覺(jué)與智能制專業(yè)委員會(huì)；中國(guó)智能自動(dòng)化專業(yè)委員會(huì)。1989年召開(kāi)中國(guó)人工智能控制聯(lián)合會(huì)議。年模式識(shí)別與人工智能創(chuàng)刊。五、曲折經(jīng)歷Newell和Simon1

18、958年預(yù)言：不出十年計(jì)算機(jī)將成為世界象棋冠軍，除非通過(guò)一個(gè)比賽規(guī)則不準(zhǔn)它參加。不出十年計(jì)算機(jī)將發(fā)現(xiàn)并證明那時(shí)還未明的數(shù)字定理。不出十年計(jì)算機(jī)將譜寫(xiě)出具有相當(dāng)美學(xué)價(jià)值并被評(píng)論家們認(rèn)可的樂(lè)曲。不出十年大多數(shù)心里學(xué)家的理論將采用計(jì)算機(jī)程序來(lái)形成。然而多年過(guò)去了，沒(méi)有一樣完全實(shí)現(xiàn)。塞繆爾的下棋程序與世界冠軍對(duì)弈時(shí)，5：4敗。機(jī)器翻譯更是出了很多問(wèn)題，只依賴一部雙向字典進(jìn)行互譯：英語(yǔ)：outofsight,outofmind;俄語(yǔ)：又瞎又瘋；英語(yǔ)：Timeflieslikeanarrow光陰似箭日語(yǔ)，回譯變成：蒼蠅喜歡箭-Flieslikeanarrow.俄語(yǔ)：Thespiritiswilling，b

19、utthefleshisweak心有余而力不足英語(yǔ)：Thewineisgood，butthemeatisspoiled酒是好的，但肉變質(zhì)了。英美減少對(duì)人工智能研究的資助。前蘇聯(lián)將其視為異端邪說(shuō)。中國(guó)更沒(méi)有涉入該領(lǐng)域。1圖靈機(jī)和馮.諾依曼機(jī)處理智能活動(dòng)的不足。2博弈的困難：組合爆炸，狀態(tài)空間巨大，跳棋：1010,國(guó)際象棋10100,圍棋101000,如此巨大的狀態(tài)空間，現(xiàn)有計(jì)算機(jī)無(wú)法忍受。1997年5月3日5月11日世界國(guó)際象棋大師卡斯帕羅夫與IBM公司的RS/6000SP（深藍(lán)）計(jì)算機(jī)下棋，深藍(lán)以3.5:2.5勝，其并速計(jì)算能力為2x10100步/S。3機(jī)器翻譯。4自動(dòng)定理證明和GPS局限。5

20、模式識(shí)別困惑。6自動(dòng)程序設(shè)計(jì)的困難。Simon1988年12月，日本東京第二次第五代計(jì)算機(jī)系統(tǒng)國(guó)際會(huì)議說(shuō)：從一開(kāi)始，人工智能和認(rèn)知科學(xué)工作者就因過(guò)分樂(lè)觀而受人指責(zé)。我希望我們已為某些樂(lè)觀而感到內(nèi)疚了，而且對(duì)于一個(gè)經(jīng)歷了30多年歷程才走到今天這一步的一個(gè)領(lǐng)域來(lái)說(shuō)，我也不認(rèn)為這種指責(zé)和內(nèi)疚是過(guò)分的。人工智能的研究與應(yīng)用領(lǐng)域問(wèn)題求解通過(guò)搜索方法尋找問(wèn)題求解操作的一個(gè)合適序列以滿足問(wèn)題的要求邏輯推理和定理證明自然語(yǔ)言理解自動(dòng)程序設(shè)計(jì)程序驗(yàn)證，程序綜合。專家系統(tǒng)機(jī)器學(xué)習(xí)機(jī)器人模式識(shí)別人工神經(jīng)網(wǎng)絡(luò)十機(jī)器視覺(jué)十一智能控制十二智能檢索十三智能決策支持（專家系統(tǒng)）十四Agent及應(yīng)用人工智能的研究途徑以符號(hào)處理

21、為核心的方法功能模擬，不管人腦思維過(guò)程。以網(wǎng)絡(luò)連接為主的連接機(jī)制方法模擬人腦的物理結(jié)構(gòu)，思維過(guò)程。系統(tǒng)集成兩者集成人工智能的研究目標(biāo)一近期目標(biāo)1、如何用計(jì)算機(jī)去做過(guò)去只有靠人的智力才能完成的工作2、依賴現(xiàn)有計(jì)算機(jī)去模擬人類某些智能行為的基本理論、基本技術(shù)和基本方法3、探討智能的基本機(jī)理。二最終目標(biāo)1、造出智能機(jī)器。2、李艾特和費(fèi)根鮑姆提出9個(gè)最終目標(biāo)（1）理解人知識(shí)；（2）有效的自動(dòng)化；（3）有效的智能拓展；（4）超人智力（5）通用問(wèn)題解；（6）連貫性交談；（7）自治自主決策；（8）學(xué)習(xí)；（9）儲(chǔ)存信息。人工智能的爭(zhēng)論與展望一、爭(zhēng)論1、信與不信2、學(xué)派之爭(zhēng)二、對(duì)人類的影響1、經(jīng)濟(jì)影響2、社會(huì)影

22、響3、文化影響三、展望第二章：知識(shí)表示方法將要求解的問(wèn)題以計(jì)算機(jī)能理解并能有效處理的知識(shí)的表達(dá)方法狀態(tài)空間法問(wèn)題的狀態(tài)描述1狀態(tài)(state)為描述某類不同事物間差別而引入的一組最少變量ql、q2、.、qn的有序集合。矢量形式：Q=q0,q1,.,qnT狀態(tài)變量：qi(1=0,1,，n)給定每個(gè)變量的一組值就得到一個(gè)具體的狀態(tài)。Q1=q01,q11,q21,.,qn1T例如：確定地球表面位臵經(jīng)、緯度矩形面積長(zhǎng)、高2操作符(算符)(Operator)使問(wèn)題從一種狀態(tài)變?yōu)榱硪环N狀態(tài)的手段。3問(wèn)題的狀態(tài)空間(StateSpace)一個(gè)表示該問(wèn)題空間全部可能狀態(tài)及其關(guān)系的圖。概括起來(lái)可以用一個(gè)三元集合

23、來(lái)表示問(wèn)題的狀態(tài)空間。丄問(wèn)題所有可能的初始狀態(tài)描述集合一一S集合丄操作符(算符)集合F集合丄目標(biāo)狀態(tài)描述一一G集合可以抽象地表示為：(S，F(xiàn)，G)例：15PuzzleProblem3587MoveUp6214MoveDown91514MoveLeft13121110操作符初始狀態(tài)MoveRightn1415目標(biāo)狀態(tài)狀態(tài)圖示法圖示方法形象、直觀，幫助對(duì)問(wèn)題的理解顯式圖示、隱式圖示Ni（父節(jié)點(diǎn)、祖先節(jié)點(diǎn)）1有向圖（DirectedGraph）節(jié)點(diǎn)，及連接節(jié)點(diǎn)的有向弧線的集合。Nj（子節(jié)點(diǎn)、后裔節(jié)點(diǎn)）2狀態(tài)空間圖示用節(jié)點(diǎn)表示狀態(tài)弧線連接表示狀態(tài)之間的關(guān)系，變化方向?？梢栽诨【€上標(biāo)注操作符，以及可能的

24、路徑代價(jià)。OperatorC（Ni,Nj）Ni（父節(jié)點(diǎn)、祖先節(jié)點(diǎn)）Nj（子節(jié)點(diǎn)、后裔節(jié)點(diǎn)）路徑代價(jià)：C（Ni,Nj）用來(lái)幫助確定使用某條路線求解問(wèn)題的花費(fèi)。狀態(tài)空間表示舉例例一：（Page20）個(gè)推銷(xiāo)員從A城市出發(fā)，旅行經(jīng)過(guò)B、C、D、E四個(gè)城市，然后回到A市，其他城市只能經(jīng)過(guò)一次，尋找一條花費(fèi)最少的旅行路徑。其中x,y,z,u為B,D,C,E之一,x,y,z,u,A)(A,C,D,E,B,A)總的路徑代價(jià)：Cost=6+5+6+10+7=34例二：(Page21)猴子和香蕉問(wèn)題(MonkeyandBananaProblem)在房間的a處有一只猴子，b處有一個(gè)箱子，c處掛著一串香蕉，猴子欲想拿

25、取香蕉，他必須首先走到b處，推動(dòng)箱子到C處，然后爬上箱子才可以。假設(shè)猴子和箱子都只能做一維運(yùn)動(dòng)。用狀態(tài)空間求解此問(wèn)題。cCCB解：1引入狀態(tài)變量W表示猴子的水平位臵；x布爾變量，標(biāo)記猴子是否在箱子上。x=1猴子在箱子上,X=0不在箱子上;Y箱子的水平位臵；z布爾變量，標(biāo)記猴子是否已經(jīng)拿到香蕉。z=1猴子拿到香蕉。用狀態(tài)集合表示：(W,x,Y,z)初始狀態(tài)：(a,0,b,0)目標(biāo)狀態(tài)：(c,1,c,1)2引入操作算符goto(U)一猴子走到U位置使用條件：y=0即猴子不能在箱子上。使用goto(U)產(chǎn)生的狀態(tài)變化：goto(U)(W,0,Y,z)(U,0,Y,z)pushbox(U)使用條件：y

26、=0ANDW=Y即猴子不能在箱子上,且兩者在同一位置。使用pushbox(U)產(chǎn)生的狀態(tài)變化：pushbox(U)(W,0,W,z)(U,0,U,z)climbbox()使用條件：y=0ANDW=Y即猴子不能在箱子上,且兩者在同一位置。使用climbbox()產(chǎn)生的狀態(tài)變化：climbbox()(W,0,W,z)(U,1,U,z)grasp()使用條件：x=1ANDW=Y=c即猴子在箱子上，且兩者都在c位置。使用climbbox()產(chǎn)生的狀態(tài)變化：climbbox()(W,0,W,z)(U,1,U,z)(3)用狀態(tài)圖求解22問(wèn)題歸約法(ProblemReduction)問(wèn)題歸約法是通過(guò)操作符(

27、算符)變換將初始問(wèn)題集合，簡(jiǎn)化為一個(gè)簡(jiǎn)單的子問(wèn)題的集合，直到這個(gè)子問(wèn)題集合可以直接求解，從而使原問(wèn)題得到解決。2.2.1問(wèn)題的歸約描述、梵塔問(wèn)題(TowerofHanoiPuzzle)在三根柱子的一根上，按大小依次放有N個(gè)圓盤(pán)，現(xiàn)在要將這些盤(pán)子移動(dòng)到另一根柱子上，可以借助第三根柱子。移動(dòng)規(guī)則：每次只能移動(dòng)一片；任何時(shí)候大盤(pán)子都不能壓在小盤(pán)子上。使用狀態(tài)空間法求解，共有27個(gè)節(jié)點(diǎn)（狀態(tài)）。問(wèn)題規(guī)約分析：1要將所有的盤(pán)子都移動(dòng)到3柱上，首先必須將C移動(dòng)到3柱，且移動(dòng)之前3柱為空。只有在移開(kāi)A、B后，才能移C,且A、B最好不要放在3柱上，即A、B應(yīng)移動(dòng)到2柱子上。完成上述移動(dòng)后，關(guān)鍵一步是將C從1移

28、動(dòng)到3，并繼續(xù)上述過(guò)程，直至完成。由上述分析可見(jiàn)，可以將三盤(pán)子的移動(dòng)問(wèn)題，簡(jiǎn)化為一個(gè)盤(pán)子（C），和兩個(gè)盤(pán)子（A、B）的移動(dòng)問(wèn)題，進(jìn)一步分析，可將兩個(gè)盤(pán)子的問(wèn)題化也簡(jiǎn)為一個(gè)盤(pán)子的問(wèn)題。通過(guò)分析將初始問(wèn)題歸約為三個(gè)子問(wèn)題：I.移動(dòng)A、B到2柱的兩盤(pán)問(wèn)題II移動(dòng)C盤(pán)到3柱的一盤(pán)問(wèn)題III.移動(dòng)A、B到3柱的兩盤(pán)問(wèn)題解決了這三個(gè)子問(wèn)題，則初始的三盤(pán)問(wèn)題亦得到解決二、本原問(wèn)題本原問(wèn)題：可以直接求解的問(wèn)題叫做本原問(wèn)題。例：上面的移動(dòng)一個(gè)盤(pán)子的問(wèn)題。三、問(wèn)題的規(guī)約表示（描述）初始問(wèn)題S即要求解問(wèn)題的數(shù)學(xué)描述。算子集合一一0通過(guò)操作算子將一個(gè)問(wèn)題轉(zhuǎn)換成若干個(gè)子問(wèn)題。本原問(wèn)題集合一一P其中的每一個(gè)問(wèn)題都不需要再

29、證明，自然成立的問(wèn)題。如公理、已知事實(shí)、或已經(jīng)證明過(guò)的問(wèn)題。這樣問(wèn)題歸約法也可以抽象表示為：（S，0，P）歸約目的：最終產(chǎn)生本原問(wèn)題。算子算子算子初始問(wèn)題子問(wèn)題集合子問(wèn)題集合本原問(wèn)題問(wèn)題歸約中，如果每運(yùn)用一次操作算子，只產(chǎn)生一個(gè)子問(wèn)題，即為狀態(tài)空間法。2.2.2歸約問(wèn)題的與或圖表示與或圖起始節(jié)點(diǎn)對(duì)應(yīng)初始問(wèn)題描述其他節(jié)點(diǎn)對(duì)應(yīng)子問(wèn)題描述表示或關(guān)系G1ORG2ORG3S表示G1、G2、G3中只要有一個(gè)可解，則S可解表示與關(guān)系在節(jié)點(diǎn)間加連接線，表示與關(guān)系。G1ANDG2ANDG3S表示Gl、G2、G3同時(shí)可解，則S可解。終葉節(jié)點(diǎn)對(duì)應(yīng)于本原問(wèn)題描述的節(jié)點(diǎn)?？山夤?jié)點(diǎn)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(對(duì)應(yīng)本原問(wèn)題)如果某

30、個(gè)非終葉節(jié)點(diǎn)有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)中至少有一個(gè)節(jié)點(diǎn)可解，則此非終葉節(jié)點(diǎn)可解。如果某個(gè)非終葉節(jié)點(diǎn)有與后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后繼節(jié)點(diǎn)可解時(shí)，此非終葉節(jié)點(diǎn)可解。不可解節(jié)點(diǎn)沒(méi)有后裔、并且不是終葉節(jié)點(diǎn)的節(jié)點(diǎn)不可解。如果某非終葉節(jié)點(diǎn)有或后繼節(jié)點(diǎn)，當(dāng)其所有后裔節(jié)點(diǎn)都不可解時(shí)，此非終葉節(jié)點(diǎn)不可解。如果某非終葉節(jié)點(diǎn)有與后繼節(jié)點(diǎn)，其后裔節(jié)點(diǎn)只要有一個(gè)不可解，此非終葉節(jié)點(diǎn)不可解。問(wèn)題歸約機(jī)理謂詞邏輯法(PredicateLogic)邏輯證明符號(hào)化邏輯方法是一種形式語(yǔ)言，也是到目前為止能夠表達(dá)人類思維活動(dòng)的一種最精確的語(yǔ)言，它與人類的自然語(yǔ)言較為接近，有很方便計(jì)算機(jī)處理和存儲(chǔ)，最早成為人工智能的一種知

31、識(shí)表示方法現(xiàn)在已經(jīng)發(fā)展有命題邏輯、謂詞邏輯和多值邏輯三個(gè)層次，我們這里著重介紹一階謂詞邏輯謂詞演算(PredicateCalculus)一、語(yǔ)法和語(yǔ)義謂詞邏輯組成謂詞符號(hào)表示事實(shí)、個(gè)體性質(zhì)、個(gè)體之間關(guān)系、事件、情形等等。變量符號(hào)常量符號(hào)函數(shù)符號(hào)其他輔助符號(hào)括號(hào)、標(biāo)點(diǎn)符號(hào)等。例：(1)機(jī)器人(Robot)在1號(hào)房間(Rooml)里。INR00M(Robot,Room1)事實(shí)，INR00M，謂詞符號(hào)；Robot,Room1常量符號(hào)。INROOM(x,y)x,y變量符號(hào)。(2)李的父親和母親結(jié)婚。MARRIEDfather(Li)，Mother(Li)MARRIED謂詞符號(hào)；father(Li),M

32、other(Li)函數(shù)。項(xiàng)常量符號(hào)、變量符號(hào)是項(xiàng)；申6，x，x)是任意n元函數(shù)，t，t，t是項(xiàng)，則，t,，)是項(xiàng)；12n12n12n有限次使用(1)、(2)生成的符號(hào)串叫做項(xiàng)。原子公式r6,x,x)是任意n元謂詞，t，t，t是項(xiàng)，則RG，t，t)是原子公式。12n12n12n二、連(接)詞和量詞連詞合取(與)符號(hào)：八定義：AAB為真，當(dāng)且僅當(dāng)A、B同時(shí)為真。例子：我喜歡音樂(lè)和繪畫(huà)。LIKE(I，Music)ALIKE(I，Painting)同時(shí)性李住在一幢黃色的房子里。LIVES(Li，House1)ALIVES(House1，Yellow)同時(shí)性析取(或)符號(hào)：V定義：AVB為假，當(dāng)且僅當(dāng)A

33、、B同時(shí)為假。例子：李明大籃球或踢足球。PLAYS(LiMing，Basketball)VPLAYS(LiMing，F(xiàn)ootball)排斥或：一種可能發(fā)生，另一種可能性不可能發(fā)生的情形。李現(xiàn)在在教室，或在實(shí)驗(yàn)室。李在教室，就不可能在實(shí)驗(yàn)室；反之亦然。否定(非)符號(hào)：S、定義：SA為真，當(dāng)且僅當(dāng)A為假。例子：機(jī)器人不在2號(hào)房間里。sINROOM(Robot,Room2)排斥或例子：李現(xiàn)在在教室，或在操場(chǎng)。IN(Li,Classroom)AsiN(Li,Field)VsiN(Li,Classroom)AIN(Li,Field)李在教室，不在操場(chǎng)；李在操場(chǎng)，不在教室(4)蘊(yùn)涵符號(hào)：，=定義：A=B為

34、假，當(dāng)且僅當(dāng)A為真，B為假。等價(jià)式：sAVB表達(dá)語(yǔ)義：如果A，則B。例子：如果劉華跑得最快，那么他取得冠軍。RUNS(LiuHua,Fastest)=WINS(LiuHua,Champion)量詞全稱量詞表達(dá)變量x在其論域內(nèi)的所有可能取值，即對(duì)所有的x。記為：(FX)例子：對(duì)所有的x,P(x)為真。(Fx)P(x)所有的狗都有尾巴。(Fx)DOG(x)=HAVE(x,Tail)存在量詞表達(dá)變量x在其論域內(nèi)，存在著、有一個(gè)、或至少有一個(gè)取值，使P(x)為真。記為：(x)例子：至少有一個(gè)x,是P(x)為真。(x)P(x)1號(hào)房間內(nèi)有一個(gè)物體。(%)INR00M(x,Rooml)有的狗是黃色的。(x

35、)DOG(x)=C0L0R(x,Yellow)謂詞公式(合適、合式)一、謂詞公式定義1原子公式是謂詞公式；若A是謂詞公式，則sA也是謂詞公式；3若A、B是謂詞公式，則AVB、AAB、A=B也是謂詞公式；若A是謂詞公式，x為A的自由變?cè)?，則(Fx)A、(x)A也是謂詞公式;按14運(yùn)算得出的表達(dá)式是謂詞公式。例子：任何整數(shù)或?yàn)檎?，或?yàn)樨?fù)。引入謂詞：I(x)x為整數(shù)P(x)x為正數(shù)N(x)x為負(fù)數(shù)(*X)I(x)=(P(x)AsN(x)V(sp(x)AN(x)二、謂詞公式性質(zhì)兩個(gè)概念：真值表pQsPsQPVQPAQP=QsPVQFFTTFFTTFTTFTFTTTFFTTFFFTTFFTTTT謂詞公式

36、的等價(jià)公式兩個(gè)謂詞公式，無(wú)論如何解釋，若兩者的真值表相同，則兩公式為等價(jià)謂詞公式1s(sP)P(否定之否定肯定)PVQsP=Q德.摩根定律(De.Morgen)s(PVQ)sPAsQs(PAQ)sPVsQ分配率PA(QVR)(PAQ)V(PAR)PV(QAR)(PVQ)A(PVR)交換率PAQQAPPVQQVP結(jié)合率(PVQ)VRPV(QVR)(PAQ)ARPA(QAR)逆否率P=QsQ=spIIspVQqVsPs(*x)p(x)(Hx)sp(x)s()p(x)()sp(x)驗(yàn)證：假定x的論域?yàn)榉强沼邢藜?，即x=a,a,a12ns(Vx)p(x)sP(a)aP(a)aaP(a)12n-P(a

37、)v-P(a)v_P(a)12n(Hx)sp(x)(FX)p(x)AQ(x)(FX)P(x)A(FX)Q(x)(3X)P(x)VQ(x)(3X)P(x)V(3X)Q(x)(3x)p(x)(3y)p(y)(FX)P(x)(Fy)P(y)Example:Foreverysety,thereisasety,suchthatthecardinalityofyisgreaterthanthecardinalityofx.ImportPredicate:SET(x)CARD(x,y)GREAT(x,y)xisaset.yisthecardinalityofx,andxisaset.xisgreaterth

38、any.(Fx)SET(x)=(3y)(3u)(3v)SET(y)ACARD(x,u)ACARD(y,v)AGREAT(v,u)臵換與合一Pz,f(w),BPA,f(y),BPq(z),F(a),BPc,f(A),B、置換(Substitution)在表達(dá)式中，用特定的項(xiàng)去代換原來(lái)的變量例子：Px,f(y),Bs1=z/x,w/y,s2=A/y,s3=q(z)/x,A/y,s4=c/x,A/y,置換能結(jié)合，但不一定能交換。L個(gè)表達(dá)式；s1,s2為兩個(gè)置換，則(L)=Ls1s2(s1s2)但是：L主L(s1s2)(s2s1)二、合一(Unification)尋找項(xiàng)對(duì)變量的置換，使得兩個(gè)可合一(具

39、有相同規(guī)律)的公式一致Ei為可合一公式集合；s尋找到的置換。做置換Es,使得:iEs=Es=二Es，即使得可合一公式集合中的每一個(gè)表達(dá)式，通過(guò)置換變的相同。12n例子：Px,f(y),B,Px,f(B),Bs=A/x,B/yPx,f(y),Bs=PA,f(B),BPx,f(B),bs=PA,f(B),B三、最通用(一般)合一者mgu(mostgeneralunifier)如果Ei是一個(gè)可合一公式集合，s是任一合一者，使得Eis=Eigs成立，則稱g為最一般合一者。上例中：g=B/y;s=A/x 32 四、合一算法分歧集合(DisagreementSet)設(shè)有一非空有限公式集合F=F1,F2,F

40、n,從F中各個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較,知道發(fā)現(xiàn)第一個(gè)不盡相同的符號(hào)為止，從F的各個(gè)公式中取出那些以第一個(gè)不一致符號(hào)開(kāi)始的最大的子表達(dá)式為元素，組成一個(gè)集合D，稱為F的分歧集合。合一算法設(shè)F為非空有限公式集合，求mgu:置k=0,Fk=F,g=&,其中&為空集合，是不含任何元素的空置換；k若Fk只含有一個(gè)表達(dá)式，算法停止，g就是mgu；k否則，找出Fk的分歧集Dk;若Dk中存在元素a,t，其中a是變?cè)莟項(xiàng)，且a不在t中出現(xiàn)，則置：kkkkkkg=gX/ak+1kkkF二Fx/ak+1kkkk=k+1GOTO算法停止，F(xiàn)的mgu不存在。例1：F=Pa,x,f(g(y),Pz,h(z,u)

41、,f(u)求mguk=0,F=F,g=&00不是單一表達(dá)式，D=a,z0g=gxa/z=a/z10F=Fxa/z=Pa,x,f(g(y),Pa,h(a,u),f(u)10k=1D=x,h(a,u)1g=gxh(a,u)/x=a/z,h(a,u)/x21F=Fxh(a,u)/x=Pa,h(a,u),f(g(y),Pa,h(a,u),f(u)21k=2D2=g(y),ug=gxig(y)/u=a/z,h(a,g(y)/x,g(y)/u32F=Fxg(y)/u=Pa,h(a,g(y),f(g(y),Pa,h(a,g(y),f(g(y)k=3F為單一表達(dá)式，3mgu=g=gxg(y)/u=a/z,h(

42、a,g(y)/x,g(y)/u32例2：P(x),P(A)mgu=A/x例3：Pf(x),y,g(y),Pf(x),x,g(y)mgu=x/y例4：Pf(x,g(A,y),g(A,y),Pf(x,z),zmgu=g(A,y)/z24語(yǔ)義網(wǎng)絡(luò)法SemanticNetwork1968年J.R.Quillian在其博士論文中，將語(yǔ)義網(wǎng)絡(luò)作為人類聯(lián)想記憶的一個(gè)顯式心理學(xué)模型提出，認(rèn)為聯(lián)想記憶由概念之間的聯(lián)系實(shí)現(xiàn)，概念的理解需要根據(jù)它所處的上下文結(jié)構(gòu)才能正確把握。1972年R.Simons和J.Slocum提出改進(jìn)，并運(yùn)用于自然語(yǔ)言理解。是一種結(jié)構(gòu)化的知識(shí)表示方法。二元語(yǔ)義網(wǎng)絡(luò)的表示一、語(yǔ)義網(wǎng)絡(luò)結(jié)構(gòu)語(yǔ)義

43、網(wǎng)絡(luò)是對(duì)知識(shí)的一種結(jié)構(gòu)化的有向圖表示。節(jié)點(diǎn)描述物體、事實(shí)、規(guī)律、公理、屬性、狀態(tài)；概念、情形、動(dòng)作等弧線例：描述和標(biāo)注節(jié)點(diǎn)之間關(guān)系。二、常用語(yǔ)義聯(lián)系分類關(guān)系ISA、A_Kind_Of(AKO)表達(dá)事物的類屬關(guān)系。聚集關(guān)系Part_Of、Has_Part表達(dá)整體與其組成部分的關(guān)系。HandPartOfMan屬性關(guān)系一一IS等等描述一個(gè)節(jié)點(diǎn)是另一個(gè)節(jié)點(diǎn)的屬性。4擁有關(guān)系5.時(shí)間關(guān)系Before、After、AtTangDynaStyABeforeSongDynasty位置關(guān)系Located_on(_at,-inside,_outside等)BookLocate-OnTable相似、相近關(guān)系Simi

44、lar-to,Near-to8.推論關(guān)系9.構(gòu)成、組成關(guān)系Composed-of2.4.2多元語(yǔ)義網(wǎng)絡(luò)引入情形、事件、動(dòng)作、概念Z等虛擬接點(diǎn)，將復(fù)雜的多元關(guān)系轉(zhuǎn)例子：1.李給了張一本書(shū)。其中：Give一概念節(jié)點(diǎn)；G-Book一為事件節(jié)點(diǎn)。2北京大學(xué)邀請(qǐng)清華大學(xué)本月25日籃球比賽，比分：85/89。sISA(A,B)APart-Of(B,NEG,CONJisaart-Of四、蘊(yùn)涵定界、標(biāo)記：條件連接詞和量詞的語(yǔ)義網(wǎng)絡(luò)表示對(duì)語(yǔ)義網(wǎng)絡(luò)進(jìn)行分塊，標(biāo)記網(wǎng)絡(luò)塊的分界線、用字符標(biāo)注類型情況，必要時(shí)引入情形、事件概念節(jié)點(diǎn)。一、合取定界、標(biāo)注CONJ(Conjunction),合取一般作為缺省情況而不標(biāo)出。例：

45、LigaveZhangabook.二、析取定界、標(biāo)注DISJ(Disjunction)例：學(xué)生中有男有女。三、否定定界、標(biāo)注NEG(Negation)例：1.作為一種動(dòng)物，麻雀是沒(méi)有智能的。conjANTEn(Antecedent);結(jié)果一CONSn(Consequence)例：Thedogisakindofanimal.Ifitisadog,thenithasatail.五、存在量詞引入實(shí)例節(jié)點(diǎn)，表示變量的特定取值；再規(guī)定這些實(shí)例節(jié)點(diǎn)的類屬例：Thedogbitthepostman.六、全稱量詞引入實(shí)例節(jié)點(diǎn)，表示變量的特定取值；再規(guī)定這些實(shí)例節(jié)點(diǎn)的類屬；將網(wǎng)絡(luò)分塊，取出具有全稱量詞約束的變量

46、，畫(huà)出分界線；引入虛擬概念節(jié)點(diǎn)GS表示具有全稱化量詞的一般性事件，只是一種標(biāo)記，沒(méi)有實(shí)際含義。引入全稱斷言（推斷）虛擬節(jié)點(diǎn)G作為GS的一個(gè)實(shí)例，在G和標(biāo)出的全稱化網(wǎng)絡(luò)塊之間標(biāo)記FROM在G和塊中的具體全稱變量之間標(biāo)記Vo例：1.Everydoghasbittenapostman.謂詞公式：(Vx)D0G(x)nGy)POSTMAN(y)2.每個(gè)學(xué)生都背誦了“靜夜思”這首唐詩(shī)。aBITE(x,y)語(yǔ)義網(wǎng)絡(luò)推理語(yǔ)義網(wǎng)絡(luò)知識(shí)表示中沒(méi)有形式語(yǔ)義，對(duì)給定的網(wǎng)絡(luò)表示什么語(yǔ)義沒(méi)有統(tǒng)一的表示法，賦予網(wǎng)絡(luò)結(jié)構(gòu)的含義完全取決于管理這個(gè)網(wǎng)絡(luò)的過(guò)程特性。一、繼承把事物的描述從概念節(jié)點(diǎn)，或類節(jié)點(diǎn)傳遞到實(shí)例節(jié)點(diǎn)。1值繼承

47、搜索某節(jié)點(diǎn)的取值，如果沒(méi)有直接給出，則試探搜素其類節(jié)點(diǎn)上有沒(méi)有這個(gè)值，有則繼承到這個(gè)實(shí)例節(jié)點(diǎn)。2附加過(guò)程繼承（如果需要IF-NEEDED）如果節(jié)點(diǎn)的某個(gè)值不能直接給出，而必須通過(guò)AKTrianguleWedgeShapeISABlockAKOBrickShapeRectangule調(diào)用某個(gè)過(guò)程來(lái)處理，則調(diào)用該節(jié)點(diǎn)或其類屬節(jié)點(diǎn)的附加過(guò)程進(jìn)行處理,3.默認(rèn)繼承與值繼承類似，只是繼承的值具有Default標(biāo)記，作為節(jié)點(diǎn)的缺省、默認(rèn)值，在沒(méi)有反對(duì)意見(jiàn)的前提下作為節(jié)點(diǎn)的可能取值Block-WeightProcessing4400ISAW1B1然后給出節(jié)點(diǎn)的這個(gè)取值。If-NeededWeightBloc

48、kAKOBrick400B1ISADensityVolume11例：要取得B1的Shape值，推理機(jī)首先在B1上尋找其值；沒(méi)有則找B1的ISA、AKO連接的節(jié)點(diǎn)，尋找有沒(méi)有Shape的值，有則繼承；沒(méi)有再尋找由ISA，和AKO弧連接的上一層類節(jié)點(diǎn)，直至找到，或已沒(méi)有上一層類接點(diǎn)。例：一般人都喜歡花，考慮張三這個(gè)具體的人，他可能就喜歡花，除非有明顯的反對(duì)意見(jiàn)，如花粉過(guò)敏。二、匹配將實(shí)例節(jié)點(diǎn)與類節(jié)點(diǎn)進(jìn)行匹配，由類節(jié)點(diǎn)結(jié)構(gòu)組成推斷實(shí)例節(jié)點(diǎn)的結(jié)構(gòu)組成2.5框架表示法（Frame）1975年，Minsky在一篇論文“AFrameworkforRepresentingKnowledge”首先提出，認(rèn)為人類

49、面對(duì)的知識(shí)信息量太大，無(wú)法對(duì)所有細(xì)節(jié)都進(jìn)行存儲(chǔ)，只能以一種結(jié)構(gòu)一致的、抽象概括的數(shù)據(jù)結(jié)構(gòu)框架-來(lái)存儲(chǔ)。當(dāng)人們見(jiàn)到一個(gè)事物時(shí)，首先搜索記憶中同類、或近似事物的框架，如果先前已經(jīng)遇見(jiàn)過(guò)，則調(diào)出記憶，給出事物的大概信息，再根據(jù)實(shí)際情況進(jìn)行修正；如果是新的事物則抽象成框架結(jié)構(gòu)存儲(chǔ)在記憶中，以備后用。比如你見(jiàn)到教室，甚至是提到，你的大腦會(huì)立即浮現(xiàn)黑板、課桌、椅子、講臺(tái)等情景，然后修正；而不是見(jiàn)到一個(gè)教室就記憶一個(gè)教室的細(xì)節(jié)。用在表示自然語(yǔ)言理解、視覺(jué)理解等方面?？蚣艿臉?gòu)成一、什么是框架？框架是一種描述所討論對(duì)象（事物、事件、概念等）屬性的數(shù)據(jù)結(jié)構(gòu)。在用框架表示知識(shí)時(shí)，框架是知識(shí)的基本單位，一個(gè)知識(shí)系統(tǒng)往

50、往有多個(gè)框架構(gòu)成二、框架構(gòu)成1框架名每個(gè)框架都有一個(gè)框架名。槽（Slot）、槽名、槽值一個(gè)框架由若干個(gè)槽構(gòu)成，每個(gè)槽都有槽名；一個(gè)槽用于說(shuō)明框架某一方面的屬性；屬性的值即為槽值。側(cè)面（Facet）、側(cè)面名、側(cè)面值一個(gè)槽有可能劃分為若干個(gè)側(cè)面，具有相應(yīng)的側(cè)面名；一個(gè)槽可能含有若干屬性，一個(gè)側(cè)面用來(lái)說(shuō)明其中的一個(gè)屬性；屬性的值即為側(cè)面值。約束條件用來(lái)約束、限制槽值、側(cè)面值的填寫(xiě)。5框架圖示例子例1：商品名稱：生產(chǎn)廠家：出售商店：處罰：處理方式：處罰依據(jù)：處罰時(shí)間：?jiǎn)挝唬辍⒃?、日）?jīng)辦部門(mén)：本例中框架有4個(gè)槽，其中處罰槽有4個(gè)側(cè)面，處罰時(shí)間側(cè)面填寫(xiě)的約束條件：按年、月日順序。例2：姓名：?jiǎn)挝唬ㄐ铡?/p>

51、名）年齡：?jiǎn)挝唬q）性別：?jiǎn)挝唬?、女）缺?。耗新毞Q：范圍（教授、副教授、講師、助教）缺省：講師部門(mén)：?jiǎn)挝唬ㄏ?、教研室）住址：工資：開(kāi)始時(shí)間：?jiǎn)挝唬?、月）終止時(shí)間：?jiǎn)挝唬?、月）缺省：?dāng)前時(shí)間比如現(xiàn)在有一個(gè)具體的教師夏冰，調(diào)出教師框架，進(jìn)行填值姓名：夏冰年齡：36性別：女職稱：副教授部門(mén)：計(jì)算機(jī)軟件教研室住址：工資：開(kāi)始時(shí)間：1986.9終止時(shí)間：2000.9框架網(wǎng)絡(luò)為了表示某一方面的知識(shí)，往往有若干個(gè)框架組成網(wǎng)絡(luò)來(lái)完成，那么這個(gè)網(wǎng)絡(luò)又是怎樣構(gòu)成的呢？一、槽值、側(cè)面值的填寫(xiě)1通過(guò)已知情況、或事物的屬性；2通過(guò)缺省、默認(rèn)值；3通過(guò)繼承；4通過(guò)調(diào)用其它框架、或附加過(guò)程。二、框架網(wǎng)絡(luò)舉例12.今天

52、一次強(qiáng)度為里氏8.5級(jí)的強(qiáng)烈地震襲擊了下斯洛文尼亞（LowSlovenia）地區(qū)，造成25人死亡和5億美元的財(cái)產(chǎn)損失，下斯洛文尼亞地區(qū)主席說(shuō)：多年來(lái)，靠近薩迪豪金斯斷層的重災(zāi)區(qū)一直是一個(gè)危險(xiǎn)區(qū)?？蚣芡评硪?、匹配根據(jù)提供的已知線索，到系統(tǒng)知識(shí)庫(kù)中尋找合適的侯選框架，對(duì)侯選框架進(jìn)行評(píng)估，選出最合適框架，然后填值；否則構(gòu)建新框架。二、填槽對(duì)選出的框架所有槽、或側(cè)面填值以發(fā)現(xiàn)新的知識(shí)。劇本表示法(Scenario、Script)1975年左右，R.C.Schank依據(jù)他的概念依賴?yán)碚撎岢龅囊环N知識(shí)表示方法。與框架類似，由一組槽組成，用來(lái)表示特定領(lǐng)域一些事件的發(fā)生序列。一、概念依賴人類的各種知識(shí)中，常識(shí)

53、性知識(shí)是數(shù)量最大、涉及面最廣、關(guān)系最為復(fù)雜的知識(shí)，很難把它們形式化地表示出來(lái)交給計(jì)算機(jī)處理，R.C.Schank由此提出概念依賴?yán)碚摚夯舅枷耄喊讶祟惿钪懈黝惞适虑楣?jié)的基本概念抽取出來(lái)，構(gòu)成一組原子概念，確定這些原子概念間的相互依賴關(guān)系，然后把所有故事情節(jié)都用這組原子概念及其依賴關(guān)系表示出來(lái)。原子概念不能有二義性，相互獨(dú)立。R.C.Schank在其研制的SAM(ScriptApplierMechanism)將人類動(dòng)作概念化為11個(gè)原子動(dòng)作：(1)Propel-對(duì)某一對(duì)象施加外力，如推、拉、打擊等；Grasp-行為主體控制某一對(duì)象，如抓、扔等；Move-行為主題變換身體的某一部位，如抬手、伸腿

54、、搖頭、坐下；Atrans-抽象關(guān)系轉(zhuǎn)移，如將某物體交給另一人；Ptrans-某物理對(duì)象位置變化，如人從一處走到另一處；(6)Attend-用感覺(jué)器官獲取外部信息；)Ingest-把某物放入體內(nèi)，如吃飯、喝水等；)Expel-排泄物體，如嘔吐、落淚等(9)Speak-發(fā)出聲音；)Mtrans-信息轉(zhuǎn)移，如看電視、竊聽(tīng)、交談、看書(shū)等；)Mbuild-由已有信息形成新的知識(shí)。利用這11種原子概念及依賴關(guān)系把生活中的事件編成劇本，每個(gè)腳本代表一類事件，并把事件的典型情節(jié)規(guī)范化。當(dāng)接受一個(gè)故事時(shí)，就找出一個(gè)相應(yīng)的腳本與之匹配，來(lái)理解故事。二、腳本的構(gòu)成進(jìn)入條件-指出腳本描述的事件可能發(fā)生的先決條件，或

55、前提條件;角色-描述事件中可能出現(xiàn)的人物；道具-描述事件中可能出現(xiàn)的有關(guān)物體；場(chǎng)景-描述事件的過(guò)程序列，可以有多個(gè)場(chǎng)景；結(jié)局-描述事件發(fā)生后的結(jié)果。三、餐廳腳本腳本名：餐廳進(jìn)入條件：顧客餓了，需要進(jìn)餐；顧客有錢(qián)角色：顧客、服務(wù)員、廚師、老板。道具：食品、桌子、椅子、菜單、錢(qián)。場(chǎng)景：第一場(chǎng)：進(jìn)入餐廳第二場(chǎng)：定菜第三場(chǎng)：上菜、進(jìn)餐第四場(chǎng)：付款、離開(kāi)結(jié)局：顧客吃了飯，花了錢(qián)；老板掙了錢(qián)；食品減少第三章一般搜索原理盲目搜索通過(guò)問(wèn)題的狀態(tài)空間，尋找從初始狀態(tài)到目標(biāo)狀態(tài)的求解路徑。盲目搜索由叫做無(wú)信息搜索、窮搜索。圖搜索策略在狀態(tài)空間圖中尋找解路徑。一、圖搜索的一般過(guò)程(GraphSearch)建立一個(gè)只

56、含起始節(jié)點(diǎn)S的搜索圖G,建立一個(gè)OPEN表，用來(lái)存放未擴(kuò)展節(jié)點(diǎn)，將S放入OPEN表中；建立一個(gè)CLOSE表，用來(lái)存放已擴(kuò)展節(jié)點(diǎn)，初始為空；LOOP:若OPEN為空，則失敗、退出;選擇OPEN表中的第一個(gè)節(jié)點(diǎn)，將其移到CLOSE表中，稱此節(jié)點(diǎn)為n節(jié)點(diǎn);若n為目標(biāo)節(jié)點(diǎn)，則成功、退出；此解是追蹤圖G沿著指針從n到s這條路徑得到的。擴(kuò)展n節(jié)點(diǎn)，生成n的后繼節(jié)點(diǎn)集合M，在M中除去n的祖先節(jié)點(diǎn)，將M中剩下的后繼節(jié)點(diǎn)加入到圖G中；7(1)對(duì)那些未曾在G中出現(xiàn)過(guò)的節(jié)點(diǎn)，即未在OPEN表，也未在CLOSE表出現(xiàn)，M成員設(shè)置一個(gè)通向n節(jié)點(diǎn)的指針，把M的這些成員加入OPEN表中；對(duì)已經(jīng)在OPEN，或CLOSE表中的

57、M成員，確定是否需要修改指向n的指針；對(duì)已經(jīng)在CLOSE表中的M成員，確定是否修改其后裔節(jié)點(diǎn)的指針；按某一控制策略，重新排序OPEN表Goto寬度優(yōu)先搜索(BreadthFirstSearch)搜索以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)；即搜索逐層進(jìn)行，同一層節(jié)點(diǎn)擴(kuò)展完成，才開(kāi)始擴(kuò)展下一層。排序OPEN表：擴(kuò)展n節(jié)點(diǎn)產(chǎn)生的新的后裔節(jié)點(diǎn)，放到OPEN表的末端。深度優(yōu)先搜索(DepthFirstSearch)一、節(jié)點(diǎn)深度起始節(jié)點(diǎn)深度為0，其他節(jié)點(diǎn)深度為父節(jié)點(diǎn)深度加1。二、優(yōu)先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)(最深的節(jié)點(diǎn))。OPEN表排序策略：新產(chǎn)生的節(jié)點(diǎn)放到OPEN表的前端，優(yōu)先擴(kuò)展。.胃sLM*FtPN0XyZ三、

58、深度界限(有界深度優(yōu)先)指點(diǎn)深度優(yōu)先搜索的最大深度。如果全部到達(dá)深度界限未得出目標(biāo)節(jié)點(diǎn)，視為無(wú)解。等代價(jià)搜索一、等代價(jià)搜索尋找從起始節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)路徑代價(jià)最小的寬度優(yōu)先搜索。二、路徑代價(jià)C(i,j)-i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)的路徑代價(jià)；G(i)-起始節(jié)點(diǎn)到i節(jié)點(diǎn)的路徑代價(jià)。等代價(jià)搜索中，OPEN排序策略按G(i)遞增，即從小到大的順序搜索。三、算法建立一個(gè)只含起始節(jié)點(diǎn)S的搜索圖G,建立一個(gè)OPEN表，用來(lái)存放未擴(kuò)展節(jié)點(diǎn)，將S放入OPEN表中，G(s)=0；建立一個(gè)CLOSE表，用來(lái)存放已擴(kuò)展節(jié)點(diǎn)，初始為空；LOOP:若OPEN為空，則失敗、退出；選擇OPEN表中G(i)值最小節(jié)點(diǎn)，將其移到CLOSE表中

59、，稱此節(jié)點(diǎn)為i節(jié)點(diǎn)；若n為目標(biāo)節(jié)點(diǎn)，則成功、退出；此解是追蹤圖G沿著指針從i到s這條路徑得到的。擴(kuò)展i節(jié)點(diǎn)，生成i的后繼節(jié)點(diǎn)集合J，在J中除去i的祖先節(jié)點(diǎn)，將J中剩下的后繼節(jié)點(diǎn)加入到圖G中；(1)對(duì)那些未曾在G中出現(xiàn)過(guò)的節(jié)點(diǎn)，既未在OPEN表，也未在CLOSE表出現(xiàn)，M成員設(shè)置一個(gè)通向i節(jié)點(diǎn)的指針，把J的這些成員加入OPEN表中；計(jì)算G(j)=G(i)+C(i,j)(2)對(duì)已經(jīng)在OPEN，或CLOSE表中的J成員，重新計(jì)算G(j)，如果新計(jì)算的值比原先的值?。阂孕掠?jì)算的值代替原來(lái)的值，修改節(jié)點(diǎn)返回指針為j到i；對(duì)已經(jīng)在CLOSE表中的J成員，將其移回到OPEN表。按G(i)值從小到大，重新排序

60、OPEN表；Gotoloop通用問(wèn)題求解系統(tǒng)(GPS)Generalproblemsolver1957年開(kāi)始，Newell、Shaw、Simon通過(guò)心理學(xué)實(shí)驗(yàn)，根據(jù)人在解題時(shí)的過(guò)程，提出一種不依賴具體應(yīng)用領(lǐng)域的通用問(wèn)題求解系統(tǒng)(GPS)，持續(xù)了十年。一、人解題的大致過(guò)程(1)制訂大致的解題計(jì)劃；(2)根據(jù)記憶中的公理、定理、解題規(guī)則，按計(jì)劃實(shí)施解題過(guò)程；解題過(guò)程中，不斷進(jìn)行方法和目的的分析，修正解題計(jì)劃。二、通用問(wèn)題求解原理中間一結(jié)局分析(MeansEndsAnalysis)根據(jù)現(xiàn)有狀態(tài)(中間)與希望目標(biāo)(結(jié)局)的差別，確定操作符以減少這種差別；選擇的操作符一般不能直接導(dǎo)致最終目標(biāo)，但必須產(chǎn)生