簡(jiǎn)介:人工智能與專(zhuān)家系統(tǒng),研究生課程,第一章緒論,11人工智能的定義和發(fā)展12人類(lèi)智能和人工智能13人工智能的各種認(rèn)知觀14人工智能的研究與應(yīng)用領(lǐng)域15課程概要,111人工智能的定義,幾種定義智能機(jī)器(INTELLIGENTMACHINE)人工智能(學(xué)科)人工智能(能力)人工智能(擬人思維、行為)人工智能(理性思維、行為),11定義和發(fā)展,112人工智能的起源與發(fā)展,孕育期(1956年前)數(shù)理邏輯學(xué)科(弗雷治、維納等)計(jì)算的新思想(丘奇、圖靈等)形成期(19561970年)1956年,第一次人工智能的研討會(huì)1969年,第一屆國(guó)際人工智能聯(lián)合會(huì)議1970年,人工智能?chē)?guó)際雜志創(chuàng)刊,11定義和發(fā)展,112人工智能的起源與發(fā)展,發(fā)展期(1970年)進(jìn)一步研究AI基本原理方法和技術(shù)進(jìn)行實(shí)用化研究專(zhuān)家系統(tǒng)與知識(shí)工程機(jī)器定理證明智能機(jī)器人智能控制等從“一枝獨(dú)秀”到“百花齊放”,11定義和發(fā)展,12人類(lèi)智能和人工智能,121智能信息處理系統(tǒng)的假設(shè)人是一種智能信息處理系統(tǒng)物理符號(hào)系統(tǒng)的六種基本功能物理符號(hào)系統(tǒng)的假設(shè)推論一推論二推論三,121智能信息處理系統(tǒng)的假設(shè),人類(lèi)的認(rèn)知行為具有不同層次認(rèn)知生理學(xué)認(rèn)知心理學(xué)認(rèn)知信息學(xué)認(rèn)知工程學(xué),12人類(lèi)智能和人工智能,122人類(lèi)智能的計(jì)算機(jī)模擬,機(jī)器智能可以模擬人類(lèi)智能智能計(jì)算機(jī)下棋定理證明語(yǔ)言翻譯新型智能計(jì)算機(jī)神經(jīng)計(jì)算機(jī)量子計(jì)算機(jī),12人類(lèi)智能和人工智能,123人工智能的研究目標(biāo),近期目標(biāo)建造智能計(jì)算機(jī)代替人類(lèi)的部分智力勞動(dòng)遠(yuǎn)期目標(biāo)用自動(dòng)機(jī)模仿人類(lèi)的思維過(guò)程和智能行為,12人類(lèi)智能和人工智能,13人工智能的各種認(rèn)知觀,符號(hào)主義(SYMBOLICISM)基于物理符號(hào)系統(tǒng)假設(shè)和有限合理性原理連接主義(CONNECTIONISM)基于神經(jīng)網(wǎng)絡(luò)及其間的連接機(jī)制與學(xué)習(xí)算法行為主義(ACTIONISM)基于控制論及感知?jiǎng)幼餍涂刂葡到y(tǒng),14人工智能的研究及應(yīng)用領(lǐng)域,人工智能的基本技術(shù)知識(shí)表示(KNOWLEDGEREPRESENTATION)狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法推理搜索(SEARCHINGREASONING)啟發(fā)式搜索、消解原理、不確定性推理計(jì)算智能(COMPUTATIONALINTELLIGENCE)模糊計(jì)算、神經(jīng)計(jì)算、進(jìn)化計(jì)算構(gòu)成技術(shù)(系統(tǒng)與語(yǔ)言)產(chǎn)生式系統(tǒng)、LISP語(yǔ)言、PROLOG語(yǔ)言,141問(wèn)題求解,問(wèn)題的表示、分解、搜索、歸約等進(jìn)行復(fù)雜的數(shù)學(xué)公式符號(hào)運(yùn)算求解142邏輯推理與定理證明通過(guò)對(duì)事實(shí)數(shù)據(jù)庫(kù)的操作來(lái)證明定理多種證明方法幾何定理證明的“吳氏方法”,14研究及應(yīng)用,143自然語(yǔ)言理解,語(yǔ)言自然語(yǔ)言、人造語(yǔ)言、機(jī)器語(yǔ)言“理解”的標(biāo)準(zhǔn)144自動(dòng)程序設(shè)計(jì)根據(jù)不同目的描述來(lái)編寫(xiě)的計(jì)算機(jī)程序促進(jìn)人工智能系統(tǒng)的發(fā)展,14研究及應(yīng)用,145專(zhuān)家系統(tǒng),是一個(gè)智能化的計(jì)算機(jī)程序系統(tǒng)和傳統(tǒng)的計(jì)算機(jī)程序之間有本質(zhì)區(qū)別146機(jī)器學(xué)習(xí)是機(jī)器獲取智能的途徑學(xué)習(xí)是一個(gè)有特定目的的知識(shí)獲取過(guò)程學(xué)習(xí)的本質(zhì)是對(duì)信息的理解與應(yīng)用有多種學(xué)習(xí)方法,14研究及應(yīng)用,147神經(jīng)網(wǎng)絡(luò),神經(jīng)計(jì)算機(jī)在其它領(lǐng)域中的廣泛應(yīng)用148機(jī)器人學(xué)操作機(jī)器人智能機(jī)器人機(jī)器人的廣泛應(yīng)用促進(jìn)人工智能的發(fā)展,14研究及應(yīng)用,149模式識(shí)別,是計(jì)算機(jī)對(duì)環(huán)境識(shí)別的需要是對(duì)人類(lèi)環(huán)境的感知模擬1410機(jī)器視覺(jué)人類(lèi)80%以上的外部信息來(lái)自視覺(jué)低層視覺(jué)與高層視覺(jué)前沿研究領(lǐng)域廣泛應(yīng)用,14研究及應(yīng)用,1411智能控制,驅(qū)動(dòng)智能機(jī)器自主地實(shí)現(xiàn)其目標(biāo)的過(guò)程是一個(gè)定性和定量的混合控制過(guò)程是當(dāng)今自動(dòng)控制的最高水平1412智能檢索是信息時(shí)代來(lái)臨的需要智能檢索系統(tǒng)所面臨的三大問(wèn)題,14研究及應(yīng)用,1413智能調(diào)度與指揮,尋找最佳調(diào)度和組合NP完全類(lèi)問(wèn)題的求解軍事指揮系統(tǒng)等領(lǐng)域1414分布式人工智能與AGENT是傳統(tǒng)人工智能的延伸和擴(kuò)展研究目標(biāo)是創(chuàng)建一種能描述自然系統(tǒng)和社會(huì)系統(tǒng)的精確概念模型,14研究及應(yīng)用,1415計(jì)算智能與進(jìn)化計(jì)算,計(jì)算智能包括神經(jīng)計(jì)算、模糊計(jì)算、進(jìn)化計(jì)算等進(jìn)化計(jì)算的理論基礎(chǔ)是生物進(jìn)化論1416數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)知識(shí)獲取數(shù)據(jù)庫(kù)知識(shí)挖掘數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)的四個(gè)特征,14研究及應(yīng)用,1417人工生命,人工生命概念的提出理論基礎(chǔ)與研究方法研究?jī)?nèi)容1418系統(tǒng)與語(yǔ)言工具計(jì)算機(jī)系統(tǒng)的一些概念得到發(fā)展新的編程語(yǔ)言與專(zhuān)用開(kāi)發(fā)工具,14研究及應(yīng)用,15課程概要,簡(jiǎn)述人工智能的起源與發(fā)展概括地論述知識(shí)表示的各種主要方法討論常用的搜索原理和推理求解技術(shù)介紹近期人工智能技術(shù)和方法的熱點(diǎn)詳細(xì)地分析人工智能的主要應(yīng)用領(lǐng)域敘述人工智能的爭(zhēng)議與展望,第二章知識(shí)表示方法,21狀態(tài)空間法22問(wèn)題歸約法23謂詞邏輯法24語(yǔ)義網(wǎng)絡(luò)法25其他方法26小結(jié),21狀態(tài)空間法(STATESPACEREPRESENTATION),問(wèn)題求解技術(shù)主要是兩個(gè)方面問(wèn)題的表示求解的方法狀態(tài)空間法狀態(tài)(STATE)算符(OPERATOR)狀態(tài)空間方法,211問(wèn)題狀態(tài)描述,定義狀態(tài)描述某類(lèi)不同事物間的差別而引入的一組最少變量Q0,Q1,,QN的有序集合。算符使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。問(wèn)題的狀態(tài)空間是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖,它包含三種說(shuō)明的集合,即三元狀態(tài)(S,F(xiàn),G)。,21狀態(tài)空間法,2狀態(tài)空間表示概念詳釋,例如下棋、迷宮及各種游戲。,MIDDLESTATE,GOALSTATE,,,21狀態(tài)空間法,例三數(shù)碼難題(3PUZZLEPROBLEM),,,,,,,初始棋局,目標(biāo)棋局,21狀態(tài)空間法,有向圖路徑代價(jià)圖的顯示說(shuō)明圖的隱示說(shuō)明,212狀態(tài)圖示法,A,,B,21狀態(tài)空間法,213狀態(tài)空間表示舉例,產(chǎn)生式系統(tǒng)(PRODUCTIONSYSTEM)一個(gè)總數(shù)據(jù)庫(kù)它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同,這些數(shù)據(jù)庫(kù)可能簡(jiǎn)單,或許復(fù)雜。一套規(guī)則它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。一個(gè)控制策略它確定應(yīng)該采用哪一條適用規(guī)則,而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí),就停止計(jì)算。,21狀態(tài)空間法,狀態(tài)空間表示舉例,例猴子和香蕉問(wèn)題,21狀態(tài)空間法,解題過(guò)程,用一個(gè)四元表列(W,X,Y,Z)來(lái)表示這個(gè)問(wèn)題狀態(tài),這個(gè)問(wèn)題的操作(算符)如下2GOTO(U)表示猴子走到水平位置U或者用產(chǎn)生式規(guī)則表示為(W,0,Y,Z)GOTO(U)(U,0,Y,Z),,21狀態(tài)空間法,PUSHBOX(V)猴子把箱子推到水平位置V,即有(W,0,W,Z)PUSHBOX(V)(V,0,V,Z),CLIMBBOX猴子爬上箱頂,即有(W,0,W,Z)CLIMBBOX(W,1,W,Z),,,21狀態(tài)空間法,GRASP猴子摘到香蕉,即有(C,1,C,0)GRASP(C,1,C,1),該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為{GOTOB,PUSHBOXC,CLIMBBOX,GRASP},,21狀態(tài)空間法,21狀態(tài)空間法,猴子和香蕉問(wèn)題自動(dòng)演示,21狀態(tài)空間法,22問(wèn)題歸約法(PROBLEMREDUCTIONREPRESENTATION),問(wèn)題歸約表示的組成部分一個(gè)初始問(wèn)題描述;一套把問(wèn)題變換為子問(wèn)題的操作符;一套本原問(wèn)題描述。,問(wèn)題歸約的實(shí)質(zhì)從目標(biāo)要解決的問(wèn)題出發(fā)逆向推理,建立子問(wèn)題以及子問(wèn)題的子問(wèn)題,直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。,22問(wèn)題規(guī)約法,221問(wèn)題歸約描述(PROBLEMREDUCTIONDESCRIPTION),梵塔難題,22問(wèn)題規(guī)約法,解題過(guò)程(3個(gè)圓盤(pán)問(wèn)題),22問(wèn)題規(guī)約法,多圓盤(pán)梵塔難題演示,22問(wèn)題規(guī)約法,222與或圖表示,1與圖、或圖、與或圖,22問(wèn)題規(guī)約法,,22問(wèn)題規(guī)約法,2一些關(guān)于與或圖的術(shù)語(yǔ),22問(wèn)題規(guī)約法,3定義,22問(wèn)題規(guī)約法,不可解節(jié)點(diǎn)的一般定義沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。全部后裔為不可解的非終葉節(jié)點(diǎn)且含有或后繼節(jié)點(diǎn),此非終葉節(jié)點(diǎn)才是不可解的。后裔至少有一個(gè)為不可解的非終葉節(jié)點(diǎn)且含有與后繼節(jié)點(diǎn),此非終葉節(jié)點(diǎn)才是不可解的。與或圖構(gòu)成規(guī)則,22問(wèn)題規(guī)約法,梵塔問(wèn)題歸約圖,,(322)(333),,,,,,,,,,,,,,22問(wèn)題規(guī)約法,23謂詞邏輯法,邏輯語(yǔ)句形式語(yǔ)言,231謂詞演算1語(yǔ)法和語(yǔ)義基本符號(hào)謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)、常量符號(hào)、括號(hào)和逗號(hào)原子公式,連詞和量詞CONNECTIVEQUANTIFIERS連詞與及合?。–ONJUNCTION或及析?。―ISJUNCTION)蘊(yùn)涵(IMPLICATION)非(NOT)量詞全稱量詞(UNIVERSALQUANTIFIERS存在量詞EXISTENTIALQUANTIFIERS,23謂詞邏輯法,232謂詞公式原子公式的的定義用PX1,X2,,XN表示一個(gè)N元謂詞公式,其中P為N元謂詞,X1,X2,,XN為客體變量或變?cè)?。通常把PX1,X2,,XN叫做謂詞演算的原子公式,或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復(fù)合謂詞公式,并把它叫做分子謂詞公式。,23謂詞邏輯法,合適公式(WFF,WELLFORMEDFORMULAS)合適公式的遞歸定義合適公式的性質(zhì)合適公式的真值等價(jià)(EQUIVALENCE,23謂詞邏輯法,233置換與合一,置換概念假元推理全稱化推理綜合推理定義就是在該表達(dá)式中用置換項(xiàng)置換變量性質(zhì)可結(jié)合的不可交換的,23謂詞邏輯法,合一(UNIFICATION合一尋找項(xiàng)對(duì)變量的置換,以使兩表達(dá)式一致??珊弦蝗绻粋€(gè)置換S作用于表達(dá)式集{EI}的每個(gè)元素,則我們用{EI}S來(lái)表示置換例的集。我們稱表達(dá)式集{EI}是可合一的。,23謂詞邏輯法,24語(yǔ)義網(wǎng)絡(luò)法(SEMANTICNETWORKREPRESENTATION),語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu)定義組成部分詞法結(jié)構(gòu)過(guò)程語(yǔ)義,表示占有關(guān)系和其它情況例小燕是一只燕子,燕子是鳥(niǎo);巢1是小燕的巢,巢1是巢中的一個(gè)。,選擇語(yǔ)義基元試圖用一組基元來(lái)表示知識(shí),以便簡(jiǎn)化表示,并可用簡(jiǎn)單的知識(shí)來(lái)表示更復(fù)雜的知識(shí)。,24語(yǔ)義網(wǎng)絡(luò)法,241二元語(yǔ)義網(wǎng)絡(luò)的表示,242多元語(yǔ)義網(wǎng)絡(luò)的表示,謂詞邏輯與語(yǔ)義網(wǎng)絡(luò)等效,24語(yǔ)義網(wǎng)絡(luò)法,多元語(yǔ)義網(wǎng)絡(luò)表示的實(shí)質(zhì)把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合,或二元關(guān)系的合取。,24語(yǔ)義網(wǎng)絡(luò)法,243連接詞和量化的表示,合取三元變?yōu)槎M合析取加注析取界限,并標(biāo)記DIS,以免引起混淆。否定兩種表示方式~或標(biāo)注NEG界限。,24語(yǔ)義網(wǎng)絡(luò)法,蘊(yùn)涵在語(yǔ)義網(wǎng)絡(luò)中可用標(biāo)注ANTE和CONSE界限來(lái)表示蘊(yùn)涵關(guān)系。ANTE和CONSE界限分別用來(lái)把與先決條件ANTECEDENT及與結(jié)果CONSEQUENCE相關(guān)的鏈聯(lián)系在一起。量化存在量化ISA鏈全稱量化分割法,24語(yǔ)義網(wǎng)絡(luò)法,25其他方法(OTHERS,框架(FRAME)表示框架是一種結(jié)構(gòu)化表示法,通常采用語(yǔ)義網(wǎng)絡(luò)中的節(jié)點(diǎn)槽值表示結(jié)構(gòu)。劇本(SCRIPT)表示劇本是框架的一種特殊形式,它用一組槽來(lái)描述某些事件的發(fā)生序列。過(guò)程(PROCEDURE)表示過(guò)程式表示就是將有關(guān)某一問(wèn)題領(lǐng)域的知識(shí),連同如何使用這些知識(shí)的方法,均隱式地表達(dá)為一個(gè)求解問(wèn)題的過(guò)程。,26小結(jié)(SUMMARY),本章所討論的知識(shí)表示問(wèn)題是人工智能研究的核心問(wèn)題之一。知識(shí)表示方法很多,本章介紹了其中的7種,有圖示法和公式法,陳述式表示和過(guò)程式表示等。,第三章搜索推理技術(shù),36產(chǎn)生式系統(tǒng)37系統(tǒng)組織技術(shù)38不確定性推理39非單調(diào)推理310小結(jié),31圖搜索策略32盲目搜索33啟發(fā)式搜索34消解原理35規(guī)則演繹系統(tǒng),31圖搜索策略,圖搜索控制策略一種在圖中尋找路徑的方法。圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)狀態(tài),每條連線對(duì)應(yīng)一個(gè)操作符。這些節(jié)點(diǎn)和連線即狀態(tài)與操作符又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫(kù)和規(guī)則來(lái)標(biāo)記。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。圖搜索過(guò)程圖,開(kāi)始,把S放入OPEN表,OPEN表為空表,把第一個(gè)節(jié)點(diǎn)N從OPEN表移至CLOSED表,N為目標(biāo)節(jié)點(diǎn)嗎,把N的后繼節(jié)點(diǎn)放入OPEN表的末端,提供返回節(jié)點(diǎn)N的指針,修改指針?lè)较?重排OPEN表,失敗,成功,,,,,,,,,圖31圖搜索過(guò)程框圖,是,是,否,否,,31圖搜索策略,32盲目搜索,特點(diǎn)不需重排OPEN表種類(lèi)寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。,開(kāi)始,把S放入OPEN表,OPEN表為空表,把第一個(gè)節(jié)點(diǎn)N從OPEN表移至CLOSED表,是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn),擴(kuò)展N,把N的后繼節(jié)點(diǎn)放入OPEN表的末端,提供返回節(jié)點(diǎn)N的指針,失敗,成功,,,,,,,,圖32寬度優(yōu)先算法框圖,是,否,是,否,32盲目搜索,例子八數(shù)碼難題(8PUZZLEPROBLEM),(初始狀態(tài)),規(guī)定將牌移入空格的順序?yàn)閺目崭褡筮呴_(kāi)始順時(shí)針旋轉(zhuǎn)。不許斜向移動(dòng),也不返回先輩節(jié)點(diǎn)。從圖可見(jiàn),要擴(kuò)展26個(gè)節(jié)點(diǎn),共生成46個(gè)節(jié)點(diǎn)之后才求得解(目標(biāo)節(jié)點(diǎn))。,32盲目搜索,1,圖34八數(shù)碼難題的寬度優(yōu)先搜索樹(shù),32盲目搜索,322深度優(yōu)先搜索,定義,首先擴(kuò)展最新產(chǎn)生的即最深的節(jié)點(diǎn)。,算法,防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去,往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限。與寬度優(yōu)先搜索算法最根本的不同在于將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。(算法框圖見(jiàn)教材),32盲目搜索,323等代價(jià)搜索,定義,是寬度優(yōu)先搜索的一種推廣,不是沿著等長(zhǎng)度路徑斷層進(jìn)行擴(kuò)展,而是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展。搜索樹(shù)中每條連接弧線上的有關(guān)代價(jià),表示時(shí)間、距離等花費(fèi)。,算法,若所有連接弧線具有相等代價(jià),則簡(jiǎn)化為寬度優(yōu)先搜索算法。,32盲目搜索,開(kāi)始,把S放入OPEN表,OPEN表為空表,把具有最小GI值的節(jié)點(diǎn)I從OPEN表移至CLOSED表,是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn),失敗,成功,,,,,,,圖32等代價(jià)搜索算法框圖,是,否,是,否,令GS0,S是否目標(biāo)節(jié)點(diǎn),,,是,成功,擴(kuò)展I,計(jì)算其后繼節(jié)點(diǎn)J的GJ,并把后繼節(jié)點(diǎn)放入OPEN表,,,否,32盲目搜索,33啟發(fā)式搜索,特點(diǎn)重排OPEN表,選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展種類(lèi)有序搜索、A算法等,331啟發(fā)式搜索策略和估價(jià)函數(shù),盲目搜索可能帶來(lái)組合爆炸啟發(fā)式信息用來(lái)加速搜索過(guò)程的有關(guān)問(wèn)題領(lǐng)域的特征信息。,估價(jià)函數(shù)為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息,提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法,以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上。FN表示節(jié)點(diǎn)N的估價(jià)函數(shù)值應(yīng)用節(jié)點(diǎn)“希望”程度(估價(jià)函數(shù)值)重排OPEN表,332有序搜索,實(shí)質(zhì),選擇OPEN表上具有最小F值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。,33啟發(fā)式搜索,開(kāi)始,把S放入OPEN表,計(jì)算估價(jià)函數(shù)FS,OPEN表為空表,選取OPEN表中F值最小的節(jié)點(diǎn)I放入CLOSED表,I為目標(biāo)節(jié)點(diǎn)嗎,擴(kuò)展I,得后繼節(jié)點(diǎn)J,計(jì)算FJ,提供返回節(jié)點(diǎn)I的指針,利用FJ對(duì)OPEN表重新排序,調(diào)整親子關(guān)系及指針,失敗,成功,,,,,,,,圖39有序搜索算法框圖,是,否,是,否,33啟發(fā)式搜索,算法,例子,八數(shù)碼難題(8PUZZLEPROBLEM),八數(shù)碼難題的有序搜索樹(shù)見(jiàn)下圖,33啟發(fā)式搜索,5,7,1,4,5,6,3,2,圖310八數(shù)碼難題的有序搜索樹(shù),33啟發(fā)式搜索,333A算法,估價(jià)函數(shù)的定義對(duì)節(jié)點(diǎn)N定義FNGNHN,表示從S開(kāi)始約束通過(guò)節(jié)點(diǎn)N的一條最佳路徑的代價(jià)。希望估價(jià)函數(shù)F定義為FNGNHNG是G的估計(jì),H是H的估計(jì)A算法的定義定義1在GRAPHSEARCH過(guò)程中,如果第8步的重排OPEN表是依據(jù)FXGXHX進(jìn)行的,則稱該過(guò)程為A算法。定義2在A算法中,如果對(duì)所有的X存在HX≤HX,則稱HX為HX的下界,它表示某種偏于保守的估計(jì)。定義3采用HX的下界HX為啟發(fā)函數(shù)的A算法,稱為A算法。當(dāng)H0時(shí),A算法就變?yōu)橛行蛩阉魉惴ā?33啟發(fā)式搜索,34消解原理,回顧原子公式(ATOMICFORMULAS)文字一個(gè)原子公式及其否定。子句由文字的析取組成的合適公式。消解對(duì)謂詞演算公式進(jìn)行分解和化簡(jiǎn),消去一些符號(hào),以求得導(dǎo)出子句。,例子,將下列謂詞演算公式化為一個(gè)子句集?X{PX?{?Y[PY?PFX,Y]∧~?Y[QX,Y?PY]}},,,開(kāi)始消去蘊(yùn)涵符號(hào)只應(yīng)用∨和~符號(hào),以~A∨B替換A?B。,1?X{~PX∨{?Y[PY∨PFX,Y]∧~?Y[QX,Y∨PY]}},34消解原理,2減少否定符號(hào)的轄域每個(gè)否定符號(hào)~最多只用到一個(gè)謂詞符號(hào)上,并反復(fù)應(yīng)用狄摩根定律。3對(duì)變量標(biāo)準(zhǔn)化對(duì)啞元(虛構(gòu)變量)改名,以保證每個(gè)量詞有其自己唯一的啞元。,34消解原理,2?X{~PX∨{?Y[~PY∨PFX,Y]∧?Y[QX,Y∧~PY]}},3?X{~PX∨{?Y[~PY∨PFX,Y]∧?W[QX,W∧~PW]}},4消去存在量詞以SKOLEM函數(shù)代替存在量詞內(nèi)的約束變量,然后消去存在量詞化為前束形把所有全稱量詞移到公式的左邊,并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。前束形{前綴}{母式}全稱量詞串無(wú)量詞公式,4?X{~PX∨{?YPY∨PFX,Y]∧[QX,GX)∧~PGX]}}式中,WGX為一SKOLEM函數(shù)。,5?X?Y{~PX∨{[~PY∨PFX,Y]∧[QX,GX∧~PGX]}},34消解原理,把母式化為合取范式任何母式都可寫(xiě)成由一些謂詞公式和或謂詞公式的否定的析取的有限集組成的合取。7消去全稱量詞所有余下的量詞均被全稱量詞量化了。消去前綴,即消去明顯出現(xiàn)的全稱量詞。,34消解原理,6?X?Y{[~PX∨~PY∨PFX,Y]∧[~PX∨QX,GX]∧[~PX∨~PGX]},7{[~PX∨~PY∨PFX,Y]∧[~PX∨QX,GX]∧[~PX∨~PGX]},8消去連詞符號(hào)∧用{A,B}代替A∧B,消去符號(hào)∧。最后得到一個(gè)有限集,其中每個(gè)公式是文字的析取。9更換變量名稱可以更換變量符號(hào)的名稱,使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。,34消解原理,8~PX∨~PY∨PFX,Y~PX∨QX,GX~PX∨~PGX,9~PX1∨~PY∨P[FX1,Y]~PX2∨Q[X2,GX2]~PX3∨~P[GX3],342消解推理規(guī)則,消解式的定義令L1,L2為兩任意原子公式;L1和L2具有相同的謂詞符號(hào),但一般具有不同的變量。已知兩子句L1∨Α和~L2∨Β,如果L1和L2具有最一般合一Σ,那么通過(guò)消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句Α∨ΒΣ。這個(gè)新子句叫做消解式。,消解式求法,取各子句的析取,然后消去互補(bǔ)對(duì)。,34消解原理,343含有變量的消解式,34消解原理,344消解反演求解過(guò)程,消解反演給出{S},L否定L,得~L;把~L添加到S中去;把新產(chǎn)生的集合{~L,S}化成子句集;應(yīng)用消解原理,力圖推導(dǎo)出一個(gè)表示矛盾的空子句,例子儲(chǔ)蓄問(wèn)題前提每個(gè)儲(chǔ)蓄錢(qián)的人都獲得利息。結(jié)論如果沒(méi)有利息,那么就沒(méi)有人去儲(chǔ)蓄錢(qián),34消解原理,1)規(guī)定原子公式SX,Y表示“X儲(chǔ)蓄Y”MX表示“X是錢(qián)”IX表示“X是利息”EX,Y表示“X獲得Y”,2)用謂詞公式表示前提和結(jié)論前提?X?YSX,Y∧MY??YIY∧EX,Y結(jié)論~?XIX??X?YMY→~SX,Y,3化為子句形,證明,34消解原理,把前提化為子句形1~SX,Y∨~MY∨IFX2~SX,Y∨~MY∨EX,FX,把結(jié)論化為子句形3~I(xiàn)Z4SA,B5MB,4消解反演求NIL,圖312儲(chǔ)蓄問(wèn)題反演樹(shù),34消解原理,反演求解過(guò)程從反演樹(shù)求取答案步驟把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。按照反演樹(shù),執(zhí)行和以前相同的消解,直至在根部得到某個(gè)子句止。用根部的子句作為一個(gè)回答語(yǔ)句。實(shí)質(zhì)把一棵根部有NIL的反演樹(shù)變換為根部帶有回答語(yǔ)句的一棵證明樹(shù)。,34消解原理,35規(guī)則演繹系統(tǒng),定義基于規(guī)則的問(wèn)題求解系統(tǒng)運(yùn)用IF→THEN規(guī)則來(lái)建立,每個(gè)IF可能與某斷言ASSERTION集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱為工作內(nèi)存,THEN部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)。在這種系統(tǒng)中,通常稱每個(gè)IF部分為前項(xiàng),稱每個(gè)THEN部分為后項(xiàng)。,351規(guī)則正向演繹系統(tǒng),定義正向規(guī)則演繹系統(tǒng)是從事實(shí)到目標(biāo)進(jìn)行操作的,即從狀況條件到動(dòng)作進(jìn)行推理的,也就是從IF到THEN的方向進(jìn)行推理的。求解過(guò)程事實(shí)表達(dá)式的與或形變換在基于規(guī)則的正向演繹系統(tǒng)中,我們把事實(shí)表示為非蘊(yùn)涵形式的與或形,作為系統(tǒng)的總數(shù)據(jù)庫(kù)。,35規(guī)則演繹系統(tǒng),事實(shí)表達(dá)式的與或圖表示,QW,A∧{~RV∧~PV∨~SA,V},QW,A,~RV∧~PV∨~SA,V,,,~RV∧~PV,~SA,V,~RV,~PV,,,圖315一個(gè)事實(shí)表達(dá)式的與或樹(shù)表示,35規(guī)則演繹系統(tǒng),與或圖的F規(guī)則變換這些規(guī)則是建立在某個(gè)問(wèn)題轄域中普通陳述性知識(shí)的蘊(yùn)涵公式基礎(chǔ)上的。我們把允許用作規(guī)則的公式類(lèi)型限制為下列形式L?W式中L是單文字;W為與或形的唯一公式。,35規(guī)則演繹系統(tǒng),352規(guī)則逆向演繹系統(tǒng),定義逆向規(guī)則演繹系統(tǒng)是從THEN向IF進(jìn)行推理的,即從目標(biāo)或動(dòng)作向事實(shí)或狀況條件進(jìn)行推理的。求解過(guò)程目標(biāo)表達(dá)式的與或形式與或圖的B規(guī)則變換作為終止條件的事實(shí)節(jié)點(diǎn)的一致解圖,35規(guī)則演繹系統(tǒng),正向和逆向組合系統(tǒng)是建立在兩個(gè)系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫(kù)由表示目標(biāo)和表示事實(shí)的兩個(gè)與或圖結(jié)構(gòu)組成。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來(lái)修正。,353規(guī)則雙向演繹系統(tǒng),35規(guī)則演繹系統(tǒng),36產(chǎn)生式系統(tǒng),定義用來(lái)描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的系統(tǒng)。這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對(duì)的概念。實(shí)質(zhì)在產(chǎn)生式系統(tǒng)中,論域的知識(shí)分為兩部分用事實(shí)表示靜態(tài)知識(shí),如事物、事件和它們之間的關(guān)系;用產(chǎn)生式規(guī)則表示推理過(guò)程和行為。由于這類(lèi)系統(tǒng)的知識(shí)庫(kù)主要用于存儲(chǔ)規(guī)則,因此又把此類(lèi)系統(tǒng)稱為基于規(guī)則的系統(tǒng)。,361產(chǎn)生式系統(tǒng)的組成,控制策略,,,,圖322產(chǎn)生式系統(tǒng)的主要組成,總數(shù)據(jù)庫(kù),產(chǎn)生式規(guī)則,36產(chǎn)生式系統(tǒng),選擇規(guī)則到執(zhí)行操作的步驟1匹配把當(dāng)前數(shù)據(jù)庫(kù)與規(guī)則的條件部分相匹配。2沖突當(dāng)有一條以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫(kù)相匹配時(shí),就需要決定首先使用哪一條規(guī)則,這稱為沖突解決。3操作操作就是執(zhí)行規(guī)則的操作部分。,36產(chǎn)生式系統(tǒng),362產(chǎn)生式系統(tǒng)的推理,正向推理從一組表示事實(shí)的謂詞或命題出發(fā),使用一組產(chǎn)生式規(guī)則,用以證明該謂詞公式或命題是否成立。逆向推理從表示目標(biāo)的謂詞或命題出發(fā),使用一組產(chǎn)生式規(guī)則證明事實(shí)謂詞或命題成立,即首先提出一批假設(shè)目標(biāo),然后逐一驗(yàn)證這些假設(shè)。雙向推理雙向推理的推理策略是同時(shí)從目標(biāo)向事實(shí)推理和從事實(shí)向目標(biāo)推理,并在推理過(guò)程中的某個(gè)步驟,實(shí)現(xiàn)事實(shí)與目標(biāo)的匹配。,36產(chǎn)生式系統(tǒng),37系統(tǒng)組織技術(shù),371議程表,系統(tǒng)組織技術(shù)首先將一個(gè)大系統(tǒng)或復(fù)雜系統(tǒng)中的知識(shí)劃分為一組相對(duì)獨(dú)立的模塊,然后考慮各子模塊間在求解時(shí)的合作問(wèn)題。,議程表是一個(gè)系統(tǒng)能夠執(zhí)行的任務(wù)表列。與每個(gè)任務(wù)有關(guān)的有兩件事,即提出該任務(wù)的理由和表示對(duì)該任務(wù)是有用的證據(jù)總權(quán)的評(píng)價(jià)。,372黑板法,黑板法由一組稱為知識(shí)資源KS的獨(dú)立模塊和一塊黑板組成求解系統(tǒng)。知識(shí)資源含有系統(tǒng)中專(zhuān)門(mén)領(lǐng)域的知識(shí),而黑板則是一切KS可以訪問(wèn)的公用數(shù)據(jù)結(jié)構(gòu)。,37系統(tǒng)組織技術(shù),373Δ極小搜索法,提供了一種選擇最有希望假設(shè)的技術(shù)。,38不確定性推理,以模糊集理論為基礎(chǔ)的方法以概率為基礎(chǔ)的方法,381關(guān)于證據(jù)的不確定性,不確定性推理是研究復(fù)雜系統(tǒng)不完全性和不確定性的有力工具。有兩種不確定性,即關(guān)于證據(jù)的不確定性和關(guān)于結(jié)論的不確定性。,382關(guān)于結(jié)論的不確定性,關(guān)于結(jié)論的不確定性也叫做規(guī)則的不確定性,它表示當(dāng)規(guī)則的條件被完全滿足時(shí),產(chǎn)生某種結(jié)論的不確定程度。,383多個(gè)規(guī)則支持同一事實(shí)時(shí)的不確定性,基于模糊集理論的方法基于概率論的方法,38不確定性推理,39非單調(diào)推理,定義非單調(diào)推理用來(lái)處理那些不適合用謂詞邏輯表示的知識(shí)。它能夠較好地處理不完全信息、不斷變化的情況以及求解復(fù)雜問(wèn)題過(guò)程中生成的假設(shè),具有較為有效的求解效率。,391缺省推理,定義1如果X不知道,那么得結(jié)論Y。定義2如果X不能被證明,那么得結(jié)論Y。定義3如果X不能在某個(gè)給定的時(shí)間內(nèi)被證明,那么得結(jié)論Y。,39非單調(diào)推理,392非單調(diào)推理系統(tǒng)正確性維持系統(tǒng)用以保持其它程序所產(chǎn)生的命題之間的相容性。一旦發(fā)現(xiàn)某個(gè)不相容,它就調(diào)出自己的推理機(jī)制,面向從屬關(guān)系的回溯,并通過(guò)修改最小的信念集來(lái)消除不相容。,310小結(jié),經(jīng)典搜索推理技術(shù)圖搜索技術(shù)消解反演高級(jí)搜索推理技術(shù)規(guī)則演繹系統(tǒng)產(chǎn)生式系統(tǒng)系統(tǒng)組織
下載積分: 4 賞幣
上傳時(shí)間:2024-01-06
頁(yè)數(shù): 298
大小: 1.93(MB)
子文件數(shù):