配套課件-人工智能技術(shù)導(dǎo)論(第三版)

人工智能導(dǎo)論人工智能導(dǎo)論

第1章人工智能概述

1.1什么是人工智能

1.2人工智能的研究意義、目標(biāo)和策略

1.3人工智能的學(xué)科范疇

1.4人工智能的研究內(nèi)容

1.5人工智能的研究途徑與方法

1.6人工智能的基本技術(shù)

1.7人工智能的應(yīng)用

1.8人工智能的分支領(lǐng)域與研究方向

1.9人工智能的發(fā)展概況第1章人工智能概述

1.1什么是人工智能

◆人工智能（ArtificialIntelligence”，AI）1.1.1人工智能概念的一般描述

◆部分學(xué)者對人工智能概念的描述：

——

人工智能是那些與人的思維相關(guān)的活動，諸如決策、問題求解和學(xué)習(xí)等的自動化（Bellman,1978）；

——

人工智能是一種計算機(jī)能夠思維，使機(jī)器具有智力的激動人心的新嘗試（Haugeland,1985）；

——人工智能是研究如何讓計算機(jī)做現(xiàn)階段只有人才能做得好的事情（RichKnight,1991）；

1.1什么是人工智能——

人工智能是那些使知覺、推理和行為成為可能的計算的研究（Winston,1992）；——

廣義地講，人工智能是關(guān)于人造物的智能行為，而智能行為包括知覺、推理、學(xué)習(xí)、交流和在復(fù)雜環(huán)境中的行為（Nilsson，1998）?！猄tuartRussell和PeterNorvig則把已有的一些人工智能定義分為4類：像人一樣思考的系統(tǒng)、像人一樣行動的系統(tǒng)、理性地思考的系統(tǒng)、理性地行動的系統(tǒng)（2003）?！斯ぶ悄苁悄切┦怪X、推理和行為成為可能的計算的研究（1.1.2圖靈測試和中文屋子

◆圖靈測試”（TuringTest）1.1.2圖靈測試和中文屋子◆約翰.西爾勒(JohnSearle)的“中文屋子”◆約翰.西爾勒(JohnSearle)的“中文屋子”1.1.3腦智能和群智能腦（主要指人腦）的宏觀心理層次的智能表現(xiàn)稱為腦智能（BrainIntelligence,BI）。由群體行為所表現(xiàn)出的智能稱為群智能（SwarmIntelligence,SI）。腦智能和群智能是屬于不同層次的智能：

腦智能是一種個體智能（IndividualIntelligence,II）；群智能是一種社會智能（SocialIntelligence,SI），或者說系統(tǒng)智能（SystemIntelligence,SI）。1.1.3腦智能和群智能1.1.4符號智能和計算智能

1.符號智能

符號智能就是符號人工智能，它是模擬腦智能的人工智能，也就是所說的傳統(tǒng)人工智能或經(jīng)典人工智能。符號智能以符號形式的知識和信息為基礎(chǔ)，主要通過邏輯推理，運用知識進(jìn)行問題求解。符號智能的主要內(nèi)容包括知識獲?。╧nowledgeacquisition）、知識表示（knowledgerepresentation）、知識組織與管理和知識運用等技術(shù)（這些構(gòu)成了所謂的知識工程（KnowledgeEngineering,KE））以及基于知識的智能系統(tǒng)等。

1.1.4符號智能和計算智能2.計算智能

計算智能就是計算人工智能，它是模擬群智能的人工智能。計算智能以數(shù)值數(shù)據(jù)為基礎(chǔ)，主要通過數(shù)值計算，運用算法進(jìn)行問題求解。計算智能的主要內(nèi)容包括：神經(jīng)計算（NeuralComputation，NC）、進(jìn)化計算（亦稱演化計算，EvolutionaryComputation，EC，包括遺傳算法（GeneticAlgorithm，GA）、進(jìn)化規(guī)劃（EvolutionaryPlanning，EP）、進(jìn)化策略（EvolutionaryStrategies，ES）等）、免疫計算（immunecomputation）、粒群計算（ParticleSwarmAlgorithm，PSA）、蟻群算法（AntColonyAlgorithm，ACA）、自然計算（NaturalComputation，NC）以及人工生命（ArtificialLife，AL）等。2.計算智能

1.2人工智能的研究意義、目標(biāo)和策略1.2.1為什么要研究人工智能

■

使當(dāng)前的電腦更好用，更有用，以擴(kuò)大和延伸人類智能；

■

信息化社會的迫切要求；

■

自動化發(fā)展的必然趨勢；

■

有益于探索人類自身智能的奧秘。1.2人工智能的研究意義、目標(biāo)和策略1.2.2人工智能的研究目標(biāo)和策略研究目標(biāo)就是制造智能機(jī)器和智能系統(tǒng)，實現(xiàn)智能化社會。具體來講，就是要使計算機(jī)不僅具有腦智能和群智能，還要具有看、聽、說、寫等感知和交流能力。研究策略則是先部分地或某種程度地實現(xiàn)機(jī)器的智能，并運用智能技術(shù)解決各種實際問題特別是工程問題，從而使現(xiàn)有的計算機(jī)更靈活、更好用和更有用，成為人類的智能化信息處理工具，而逐步擴(kuò)展和不斷延伸人的智能，逐步實現(xiàn)智能化。1.2.2人工智能的研究目標(biāo)和策略

1.3人工智能的學(xué)科范疇

人工智能已構(gòu)成信息技術(shù)領(lǐng)域的一個重要學(xué)科。當(dāng)前的人工智能既屬于計算機(jī)科學(xué)技術(shù)的一個前沿領(lǐng)域，也屬于信息處理和自動化技術(shù)的一個前沿領(lǐng)域。還涉及到智能科學(xué)、認(rèn)知科學(xué)、心理科學(xué)、腦及神經(jīng)科學(xué)、生命科學(xué)、語言學(xué)、邏輯學(xué)、行為科學(xué)、教育科學(xué)、系統(tǒng)科學(xué)、數(shù)理科學(xué)以及控制論、科學(xué)方法論、哲學(xué)甚至經(jīng)濟(jì)學(xué)等眾多學(xué)科領(lǐng)域。人工智能實際上是一門綜合性的交叉學(xué)科和邊緣學(xué)科。1.3人工智能的學(xué)科范疇

1.4人工智能的研究內(nèi)容1.5.1搜索與求解1.5.2學(xué)習(xí)與發(fā)現(xiàn)1.5.3知識與推理1.5.4發(fā)明與創(chuàng)造1.5.5感知與交流1.5.6記憶與聯(lián)想1.5.7系統(tǒng)與建造1.5.8應(yīng)用與工程1.4人工智能的研究內(nèi)容1.5人工智能的研究途徑與方法1.5.1心理模擬，符號推演1.5.2生理模擬，神經(jīng)計算1.5.3行為模擬，控制進(jìn)化1.5.4群體模擬，仿生計算1.5.5博采廣鑒，自然計算1.5.6原理分析，數(shù)學(xué)建模1.5人工智能的研究途徑與方法

1.6人工智能的基本技術(shù)表示運算搜索1.6人工智能的基本技術(shù)1.7人工智能的應(yīng)用1.7.1難題求解1.7.2自動規(guī)劃、調(diào)度與配置1.7.3機(jī)器定理證明1.7.4自動程序設(shè)計1.7.5機(jī)器翻譯1.7.6智能控制1.7.7智能管理1.7.8智能決策1.7.9智能通信1.7.10智能仿真1.7人工智能的應(yīng)用1.7.11智能CAD1.7.12智能制造1.7.13智能CAI1.7.14智能人機(jī)接口1.7.15模式識別1.7.16數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)現(xiàn)1.7.17計算機(jī)輔助創(chuàng)新1.7.18計算機(jī)文藝創(chuàng)作1.7.19機(jī)器博弈1.7.20智能機(jī)器人1.7.11智能CAD

1.8人工智能的分支領(lǐng)域與研究方向從模擬的層次和所用的方法來看，人工智能可分為符號智能和計算智能兩大主要分支領(lǐng)域。而這兩大領(lǐng)域各自又有一些子領(lǐng)域和研究方向。如符號智能中又有圖搜索、自動推理、不確定性推理、知識工程、符號學(xué)習(xí)等。計算智能中又有神經(jīng)計算、進(jìn)化計算、免疫計算、蟻群計算、粒群計算、自然計算等。另外，智能Agent也是人工智能的一個新興的重要領(lǐng)域。智能Agent或者說Agent智能則是以符號智能和計算智能為基礎(chǔ)的更高一級的人工智能。

從模擬的腦智能或腦功能來看，AI中有機(jī)器學(xué)習(xí)、機(jī)器感知、機(jī)器聯(lián)想、機(jī)器推理、機(jī)器行為等分支領(lǐng)域。而機(jī)器學(xué)習(xí)又可分為符號學(xué)習(xí)、連接學(xué)習(xí)、統(tǒng)計學(xué)習(xí)等許多研究領(lǐng)域和方向。機(jī)器感知又可分為計算機(jī)視覺、計算機(jī)聽覺、模式識別、圖像識別與理解、語音識別、自然語言處理等領(lǐng)域和方向。

1.8人工智能的分支領(lǐng)域與研究方向從應(yīng)用角度看，如1.7節(jié)所述，AI中有難題求解等數(shù)十種分支領(lǐng)域和研究方向。

從系統(tǒng)角度看，有智能計算機(jī)系統(tǒng)和智能應(yīng)用系統(tǒng)兩大類。智能計算機(jī)系統(tǒng)又可分為：智能硬件平臺、智能操作系統(tǒng)、智能網(wǎng)絡(luò)系統(tǒng)等。智能應(yīng)用系統(tǒng)又可分為：基于知識的智能系統(tǒng)、基于算法的智能系統(tǒng)和兼有知識和算法的智能系統(tǒng)等。另外，還有分布式人工智能系統(tǒng)。從基礎(chǔ)理論看，AI中有數(shù)理邏輯和多種非標(biāo)準(zhǔn)邏輯、圖論、人工神經(jīng)網(wǎng)絡(luò)、模糊集、粗糙集、概率統(tǒng)計（貝葉斯統(tǒng)計決策理論）和貝葉斯網(wǎng)絡(luò)、統(tǒng)計學(xué)習(xí)理論與支持向量機(jī)、形式語言與自動機(jī)等領(lǐng)域和方向。從應(yīng)用角度看，如1.7節(jié)所述，AI中有難題求解等數(shù)十種分支領(lǐng)

1.9人工智能學(xué)科的發(fā)展概況1.9.1人工智能學(xué)科的產(chǎn)生1.9.2符號主義途徑發(fā)展概況1.9.3連接主義途徑發(fā)展概況1.9.4計算智能異軍突起1.9.5智能Agent方興未艾1.9人工智能學(xué)科的發(fā)展概況1.9.6現(xiàn)狀與發(fā)展趨勢

■多種途徑齊頭并進(jìn)，多種方法協(xié)作互補(bǔ)。

■新思想、新技術(shù)不斷涌現(xiàn)，新領(lǐng)域、新方向不斷開拓。

■理論研究更加深入，應(yīng)用研究愈加廣泛。

■研究隊伍日益壯大，社會影響越來越大。

1.9.6現(xiàn)狀與發(fā)展趨勢

雖然在通向人工智能最終目標(biāo)的道路上，還有不少困難、問題和挑戰(zhàn)，但前進(jìn)和發(fā)展畢竟是大勢所趨。

配套課件-人工智能技術(shù)導(dǎo)論(第三版)

智能交通智能交通

圖像識別系統(tǒng)圖像識別系統(tǒng)

云松

鑾仙玉骨寒，松虬雪友繁。大千收眼底，斯調(diào)不同凡。

云松

（無題）白沙平舟夜?jié)?，春日曉露路相逢。朱樓寒雨離歌淚，不堪腸斷雨乘風(fēng)。

（無題）

BetrayalDaveStriverlovedtheuniversity.Heloveditsivy-coveredclocktowers,itsancientandsturdybrick,anditssun-splashedverdantgreensandeageryouth.Healsolovedthefactthattheuniversityisfreeofthestarkunforgivingtrialsofthebusinessworld-onlythisisn'tafact:Academiahasitsowntests,andsomeareasmercilessasanyinthemarketplace.Aprimeexampleisthedissertationdefense:ToearnthePhD,tobecomeadoctor,onemustpassanoralexaminationonone'sdissertation.ThiswasatestProfessorEdwardHartenjoyedgiving.Davewanteddesperatelytobeadoctor.Butheneededthesignaturesofthreepeopleonthefirstpageofhisdissertation,thepricelessinscriptionsthat,together,wouldcertifythathehadpassedhisdefense.OneofthesignatureshadtocomefromProfessorHart,andHarthadoftensaid-toothersandtohimself-thathewashonoredtohelpDavesecurehiswell-earneddream.

Wellbeforethedefense,StrivergaveHartapenultimatecopyofhisthesis.HartreaditandtoldDavethatitwasabsolutelyfirstrate,andthathewouldgladlysignitatthedefense.TheyevenshookhandsinHart'sbook-linedoffice.DavenoticedthatHart'seyeswerebrightandtrustful,andhisbearingpaternal.Atthedefense,Davethoughtthatheeloquentlysummarizedchapter3ofhisdissertation.Thereweretwoquestions,onefromProfessorRodmanandonefromDr.Teer;Daveansweredboth,apparentlytoeveryone'ssatisfaction.Therewerenofurtherobjections.

Wellbeforethedefense,St

ProfessorRodmansigned.HeslidthetometoTeer;shetoosigned,andthensliditinfrontofHart.Hartdidn'tmove."Ed?"Rodmansaid.Hartstillsatmotionless.Davefeltslightlydizzy."Edward,areyougoingtosign?"Later,Hartsataloneinhisofficeinhisbigleatherchair,saddenedbyDave'sfailure.HetriedtothinkofwayshecouldhelpDaveachievehisdream.

ProfessorRodmansigned.He

背叛

戴夫·斯特賴維爾喜愛這所大學(xué)。他喜愛校園里爬滿常青藤的鐘樓，那古色古香而又堅固的磚塊，還有那灑滿陽光的碧綠草坪和熱情的年輕人。使他感到欣慰的還有這樣一件事，即大學(xué)里完全沒有商場上那些冷酷無情的考驗——但事實恰恰并非如此：做學(xué)問也要通過考試，而且有的考試與市場上的考驗一樣不留情面。最好的例子就是論文答辯：為了取得博士學(xué)位，為了成為博士，博士生必須通過論文的口試，愛德華·哈特教授就喜歡主持這樣的答辯考試。背叛

戴夫迫切希望成為一名博士。但他需要讓３個人在他論文的第一頁上簽上他們的名字，這３個千金難買的簽名能夠證明他通過了答辯。其中一個簽名是哈特教授的。哈特常常對戴夫本人和其他人說，對于幫助戴夫?qū)崿F(xiàn)他應(yīng)該有的夢想，他感到很榮幸。答辯之前，斯特賴維爾早早給哈特送去了他論文的倒數(shù)第二稿。哈特閱讀后告訴戴夫，論文水平絕對一流，答辯時他會很高興地在論文上簽名。在哈特那四壁擺滿書櫥的辦公室里，兩人甚至還握了手。戴夫注意到，哈特兩眼放光，充滿信任，神情宛如慈父一般。戴夫迫切希望成為一名博士。但他需要讓３個人在

在答辯時，戴夫覺得自己流利地概括了論文的第三章。評審者提了兩個問題，一個是羅德曼教授提的，另一個是蒂爾博士提的。戴夫分別做了回答，并且顯然讓每個人都心悅誠服，再沒有人提出異議。羅德曼教授簽了名。他把論文推給蒂爾，她也簽上了名字，接著便把本子推到了哈特跟前。哈特沒有動。“愛德華？”羅德曼問道。哈特仍然坐在那兒，毫無表情。戴夫感到有點眩暈?！皭鄣氯A，你打算簽名嗎？”過后，哈特一個人呆在辦公室里，坐在那張寬大的皮椅里，他為戴夫未能通過答辯感到難過。他試圖想出幫助戴夫?qū)崿F(xiàn)他夢想的辦法。在答辯時，戴夫覺得自己流利地概括了論文的第三配套課件-人工智能技術(shù)導(dǎo)論(第三版)配套課件-人工智能技術(shù)導(dǎo)論(第三版)配套課件-人工智能技術(shù)導(dǎo)論(第三版)配套課件-人工智能技術(shù)導(dǎo)論(第三版)

第2章邏輯程序設(shè)計語言PROLOG

2.1基本PROLOG

2.2TurboPROLOG程序設(shè)計

第2章邏輯程序設(shè)計語言PROLOG2.1基本PROLOG2.1.1PROLOG的語句

1.事實(fact)

格式

〈謂詞名〉(〈項表〉).student(john).

like(mary,music).abc.repeat.

功能一般表示對象的性質(zhì)或關(guān)系。2.1基本PROLOG2.規(guī)則(rule)

格式〈謂詞名〉(〈項表〉):-〈謂詞名〉(〈項表〉){,〈謂詞名〉(〈項表〉)}.

bird(X):-animal(X),has(X,feather).grandfather(X,Y):-father(X,Z),father(Z,Y).run:-start,step1(X),step2(X),end.

功能

一般表示對象間的因果關(guān)系、蘊含關(guān)系或?qū)?yīng)關(guān)系。

2.規(guī)則(rule)3.問題(question)

格式

?-〈謂詞名〉(〈項表〉){,〈謂詞名〉(〈項表〉)}.

?

-student(john).?

-like(mary,X).

功能問題表示用戶的詢問,它就是程序運行的目標(biāo)。3.問題(question)2.1.2PROLOG的程序

PROLOG程序一般由一組事實、規(guī)則和問題組成。問題是程序執(zhí)行的起點,稱為程序的目標(biāo)。

likes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,reading),likes(X,music).friend(john,X):-likes(X,sports),likes(X,music).?-friend(john,Y).

2.1.2PROLOG的程序

?-likes(mary,X).或

?-likes(mary,music).或

?-friend(X,Y).或

?-likes(bell,sports),likes(mary,music),friend(john,X).

2.1.3PROLOG程序的運行機(jī)理

1.自由變量與約束變量

2.匹配合一兩個謂詞可匹配合一,是指兩個謂詞的名相同,參量項的個數(shù)相同,參量類型對應(yīng)相同,并且對應(yīng)參量項還滿足下列條件之一：

(1)如果兩個都是常量,則必須完全相同。

(2)如果兩個都是約束變量,則兩個約束值必須相同。

(3)如果其中一個是常量,一個是約束變量,則約束值與常量必須相同。(4)至少有一個是自由變量。2.1.3PROLOG程序的運行機(jī)理

考慮下面的各組謂詞是否可匹配合一？

pre1(″ob1″,″ob2″,Z)pre1(″ob1″,″ob3″,Y)

pre1(″ob1″,″ob2″,Z)pre1(″ob1″,X,″ob3″)pre1(″ob1″,″ob2″,Z)pre1(″ob1″,X,Y)考慮下面的各組謂詞是否可匹配合一？3.回溯所謂回溯,就是在程序運行期間,當(dāng)某一個子目標(biāo)不能滿足(即謂詞匹配失敗)時,控制就返回到前一個已經(jīng)滿足的子目標(biāo)(如果存在的話),并撤消其有關(guān)變量的約束值,然后再使其重新滿足。成功后,再繼續(xù)滿足原子目標(biāo)。如果失敗的子目標(biāo)前再無子目標(biāo),則控制就返回到該子目標(biāo)的上一級目標(biāo)(即該子目標(biāo)謂詞所在規(guī)則的頭部)使它重新匹配?；厮菀彩荘ROLOG的一個重要機(jī)制。3.回溯

likes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,reading),likes(X,music).friend(john,X):-likes(X,sports),likes(X,music).?-friend(john,Y).則求解目標(biāo)為

friend(john,Y).

新目標(biāo)

likes(X,reading),likes(X,music).likes(bell,sports).配套課件-人工智能技術(shù)導(dǎo)論(第三版)

2.2TurboPROLOG程序設(shè)計2.2.1程序結(jié)構(gòu)

/*〈注釋〉*/

〈編譯指令〉constants

〈常量說明〉domains〈域說明〉database〈數(shù)據(jù)庫說明〉predicates〈謂詞說明〉goal〈目標(biāo)語句〉clauses〈子句集〉

2.2TurboPROLOG程序設(shè)計例

如果把上節(jié)的例子程序作為TurboPROLOG程序,則應(yīng)改寫為：

DOMAINSname=symbolPREDICATESlikes(name,name).friend(name,name)GOALfriend(john,Y),write(″Y=″,Y).CLAUSESlikes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,sports),likes(X,music).friend(john,X):-likes(X,reading),likes(X,music).

例如果把上節(jié)的例子程序作為TurboPROLOG程序,

領(lǐng)域段

該段說明程序謂詞中所有參量項所屬的領(lǐng)域。TurboPROLOG的標(biāo)準(zhǔn)領(lǐng)域包括整數(shù)、實數(shù)、符號、串和符號等,其具體說明如下表所示。領(lǐng)域段該段說明程序謂詞中所有參量項所屬的領(lǐng)域。Tu謂詞段該段說明程序中用到的謂詞的名和參量項的名(但TurboPROLOG的內(nèi)部謂詞無須說明)子句段該段是TurboPROLOG程序的核心,程序中的所有事實和規(guī)則就放在這里,系統(tǒng)在試圖滿足程序的目標(biāo)時就對它們進(jìn)行操作。目標(biāo)段該段是放置程序目標(biāo)的地方。目標(biāo)段可以只有一個目標(biāo)謂詞,例如上面的例子中就只有一個目標(biāo)謂詞；也可以含有多個目標(biāo)謂詞,如

goalreadint(X),Y=X+3,write(″Y=″,Y).就有三個目標(biāo)謂詞。這種目標(biāo)稱為復(fù)合目標(biāo)。

謂詞段該段說明程序中用到的謂詞的名和參量項的名(但Turb2.2.2數(shù)據(jù)與表達(dá)式

1.領(lǐng)域

1)標(biāo)準(zhǔn)領(lǐng)域整數(shù)、實數(shù)、字符、串和符號

2)結(jié)構(gòu)結(jié)構(gòu)也稱復(fù)合對象,一般形式為

〈函子〉(〈參量表〉)likes(″Tom″,sports(football,basketball,table_tennis)).reading(″王宏″,book(″人工智能技術(shù)導(dǎo)論″,″西安電子科技大學(xué)出版社″)).

friend(father(″Li″),father(″Zhao″)).

2.2.2數(shù)據(jù)與表達(dá)式復(fù)合對象在程序中的說明,需分層進(jìn)行。例如,對于上面的謂詞

likes(″Tom″,sports(football,basketball,table_tennis)).在程序中可說明如下：

domainsname=symbolsy=symbolsp=sports(sy,sy,sy)predicates likes(name,sp)復(fù)合對象在程序中的說明,需分層進(jìn)行。例如,對于上面的謂3)表表的一般形式［x1,x2,…,xn］其中xi(i=1,2,…,n)為PROLOG的項,一般要求同一個表的元素必須屬于同一領(lǐng)域。不含任何元素的表稱為空表,記為［］。

［1,2,3］［apple,orange,banana,grape,cane］［″PROLOG″,″PROGRAMMING″,″inlogic″］［［a,b］,［c,d］,［e］］［］［name(″LiMing″),age(20),sex(male),addr(xian)］3)表表的說明方法是在其組成元素的說明符后加一個星號*。如：domainslists=string*predicatespl(lists)例如，謂詞

p(［name(″Liming″),age(20)］)則需這樣說明:domainsrec=seg*seg=name(string);age(integer)predicatesp(rec)表的說明方法是在其組成元素的說明符后加一個星號*。如：2.常量與變量

TurboPROLOG的常量有整數(shù)、實數(shù)、字符、串、符號、結(jié)構(gòu)、表和文件這八種數(shù)據(jù)類型。同理,TurboPROLOG的變量也就有這八種取值。另外,變量名要求必須是以大寫字母或下劃線開頭的字母、數(shù)字和下劃線序列,或者只有一個下劃線。這后一種變量稱為無名變量。

2.常量與變量3.算術(shù)表達(dá)式

TurboPROLOG提供了五種最基本的算術(shù)運算：加、減、乘、除和取模,相應(yīng)運算符號為+、-、*、/、mod。這五種運算的順序為：*、/、mod優(yōu)先于+、-。

數(shù)學(xué)中的算術(shù)表達(dá)式PROLOG中的算術(shù)表達(dá)式

x+yz

X+Y*Zab-c/d

A*B-C/DumodvUmodV

Y=X+5 √X=X+1×3.算術(shù)表達(dá)式4.關(guān)系表達(dá)式

TurboPROLOG提供了六種常用的關(guān)系運算,即小于、小于或等于、等于、大于、大于或等于和不等于,其運算符依次為

<,<=,=,>,>=,<>

數(shù)學(xué)中的關(guān)系式TurboPROLOG中的關(guān)系式

X+1≥Y

X+1>=YX≠Y

X<>Y4.關(guān)系表達(dá)式brother(Name1,Name2):-person(Name1,man,Age1),person(Name2,man,Age2),mother(Z,Name1),mother(Z,Name2),Age1>Age2.

brother(Name1,Name2):-

◆

“=”的用法：比較符和約束符

p(X,Y,Z):-Z=X+Y.當(dāng)變量X、Y、Z全部被實例化時,“=”就是比較符。如：對于問題

Goal:p(3,5,8).機(jī)器回答：yes。而對于

Goal:p(3,5,7).機(jī)器回答：no。但當(dāng)X,Y被實例化,而Z未被實例化時,“=”號就是約束符。如：

Goal:p(3,5,Z).機(jī)器回答：Z=8這時,機(jī)器使Z實例化為X+Y的結(jié)果?！簟?”的用法：比較符和約束符

2.2.3輸入與輸出

(1)readln(X)(2)readint(X)(3)readreal(X)(4)readchar(X)(5)write(X1,X2,…,Xn)

(6)nl

2.2.3輸入與輸出例

用輸入輸出謂詞編寫一個簡單的成績數(shù)據(jù)庫查詢程序。

PREDICATESstudent(integer,string,real)gradeGOALgrade.CLAUSESstudent(1,″張三″,90.2).student(2,″李四″,95.5).student(3,″王五″,96.4).grade:-write(″請輸入姓名:″),readln(Name),student(_,Name,Score),nl,write(Name,″的成績是″,Score).grade:-write(″對不起,找不到這個學(xué)生!″).例用輸入輸出謂詞編寫一個簡單的成績數(shù)據(jù)庫查詢程序。2.2.4分支與循環(huán)

1.分支將

IFx>0THENx:=1ELSEx:=0用PROLOG實現(xiàn)則可以是

br:-x>0,x=1.br:-x=0.2.2.4分支與循環(huán)2.循環(huán)程序1：

student(1,″張三″,90.2).student(2,″李四″,95.5).student(3,″王五″,96.4).print:-student(Number,Name,Score),write(Number,Name,Score),nl,Number=3.

2.循環(huán)

程序2：

student(1,″張三″,90.2).student(2,″李四″,95.5).student(3,″王五″,96.4).print:-student(Number,Name,Score),write(Number,Name,Score),nl,fail.print:-.程序2：2.2.5動態(tài)數(shù)據(jù)庫動態(tài)數(shù)據(jù)庫操作謂詞:asserta(〈fact〉).assertz(〈fact〉).retract(〈fact〉).

例

asserta(student(20,″李明″,90.5)).retract(student(20,_,_)).2.2.5動態(tài)數(shù)據(jù)庫2.2.6表處理與遞歸

1.表頭與表尾

表頭是表中的第一個元素；表尾是表中除第一個元素外的其余元素按原來順序組成的表。

表頭與表尾示例———————————————————————————————————

表表頭表尾———————————————————————————————————［1,2,3,4,5］1［2,3,4,5］

［apple,orange,banana］apple［orange,banana］

［［a,b］,［c］,［d,e］］［a,b］［［c］,［d,e］］

［″PROLOG″］″PROLOG″［］

［］無定義無定義———————————————————————————————————2.2.6表處理與遞歸—————————————————2.表的匹配合一

表的匹配合一示例————————————————————————————————————

表1表2合一后的變量值————————————————————————————————————

［X︱Y］［a,b,c］

X=a,Y=［b,c］

［X︱Y］

［a］

X=a,Y=［］

［a︱Y］

［X,b］X=a,Y=［b］

［X,Y,Z］［a,b,c］X=a,Y=b,Z=c

［［

a,Y］︱Z］［［

X,b］,［c］］

X=a,Y=b,Z=［［c］］

————————————————————————————————————2.表的匹配合一————————————————————例設(shè)計一個能判斷對象X是表L的成員的程序。

分析：

(1)如果X與表L中的第一個元素(即表頭)是同一個對象,則X就是L的成員。

(2)如果X是L的尾部的成員,則X也就是L的成員。

程序：

member(X,［X|_］).

member(X,［Head|Tail］):-member(X,Tail).

Goal:member(a,［a,b,c,d］).yesGoal:member(e,［a,b,c,d］).noGoal:member(X,［a,b,c,d］).X=a例設(shè)計一個能判斷對象X是表L的成員的程序。

例表的拼接程序,即把兩個表連接成一個表。

append(［］,L,L).append(［H|T］,L2,［H|Tn］):-append(T,L2,Tn).Goal:append(［1,2,3］,［4,5］,L).L=［1,2,3,4,5］

Goal:append(［1,2,3］,［4,5］,［1,2,3,4,5］).yesGoal:append(［1,2,3］,［4,5］,［1,2,3,4,5,6］).no例表的拼接程序,即把兩個表連接成一個表。

Goal:append(［1,2,3］,Y,［1,2,3,4,5］).Y=［4,5］

Goal:append(X,［4,5］,［1,2,3,4,5］).X=［1,2,3］

Goal:append(X,Y,［1,2,3,4,5］).X=［］,Y=［1,2,3,4,5］

X=［1］,Y=［2,3,4,5］

X=［1,2］,Y=［3,4,5］

X=［1,2,3］,Y=［4,5］Goal:append(［1,2,3］,Y,［例表的輸出。

print(［］).print(［H|T］):-write(H),print(T).例表的倒置,即求一個表的逆序表。

reverse(［］,［］).reverse(［H|T］,L):-reverse(T,L1),append(L1,［H］,L).例表的輸出。

2.2.7回溯控制

截斷謂詞“!”的語義：

(1)若將“!”插在子句體內(nèi)作為一個子目標(biāo),它總是立即成功。

(2)若“!”位于子句體的最后,則它就阻止對它所在子句的頭謂詞的所有子句的回溯訪問,而讓回溯跳過該頭謂詞(子目標(biāo)),去訪問前一個子目標(biāo)(如果有的話)。

(3)若“!”位于其他位置,則當(dāng)其后發(fā)生回溯且回溯到“!”處時,就在此處失敗,并且“!”還使它所在子句的頭謂詞(子目標(biāo))整個失敗(即阻止再去訪問頭謂詞的其余子句(如果有的話),即迫使系統(tǒng)直接回溯到該頭謂詞(子目標(biāo))的前一個子目標(biāo)(如果有的話))。2.2.7回溯控制例考慮下面的程序：

p(a). (2-1)p(b).

(2-2)q(b). (2-3)r(X):-p(X),q(X).(2-4)r(c).

對于目標(biāo):r(Y).

可有一個解

Y=b

但當(dāng)把式(2-4)改為

r(X):-p(X),!,q(X).(2-4′)

時,卻無解。為什么呢？例考慮下面的程序：例設(shè)有程序：

g0:-g11,g12,g13. (2-5) g0:-g14. (2-6)g12:-g21,!,g23. (2-7) g12:-g24,g25.(2-8)

…

…

…給出目標(biāo):g0.把子句(2-7)改為

g12:-g21,g23,!.(2-9)例設(shè)有程序：2.2.8程序舉例例一個簡單的路徑查詢程序。

predicatesroad(symbol,symbol)path(symbol,symbol)clausesroad(a,b).road(a,c).road(b,d).road(c,d).road(d,e).road(b,e).path(X,Y):-road(X,Y).path(X,Y):-road(X,Z),path(Z,Y).

2.2.8程序舉例Goal:path(a,e).

yesGoal:path(e,a).

noGoal：

run.run:-path(a,X),write(″X=″,X),nl,fail.run.X=b

X=c

X=d

X=e

X=d

X=e

X=eGoal:path(a,e).

例下面是一個求階乘程序,程序中使用了遞歸。

domainsn,f=integerpredicatesfactorial(n,f)goalreadint(I),factorial(I,F),write(I,″!=″,F).clausesfactorial(1,1).factorial(N,Res):-N>0,N1=N-1,factorial(N1,FacN1),Res=N*FacN1.例下面是一個求階乘程序,程序中使用了遞歸。第3章圖搜索與問題求解

3.1狀態(tài)圖搜索

3.2狀態(tài)圖搜索問題求解

3.3與或圖搜索

3.4與或圖搜索問題求解

第3章圖搜索與問題求解3.1狀態(tài)圖搜索3.1狀態(tài)圖搜索

3.1.1狀態(tài)圖

例3.1

迷宮問題。3.1狀態(tài)圖搜索3.1.1狀態(tài)圖圖

3-2迷宮的有向圖表示

圖3-2迷宮的有向圖表示圖

3-3八數(shù)碼問題示例

例3.2八數(shù)碼問題。圖3-3八數(shù)碼問題示例例3.2八數(shù)碼問題。3.1.2狀態(tài)圖搜索

1.搜索方式

●樹式搜索

●線式搜索

2.搜索策略

●盲目搜索

●啟發(fā)式(heuristic)搜索

3.1.2狀態(tài)圖搜索圖

3-4OPEN表與CLOSED表示例

3.搜索算法圖3-4OPEN表與CLOSED表示例3.搜索算法樹式搜索算法：

步1把初始節(jié)點So放入OPEN表中。步2若OPEN表為空,則搜索失敗,退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中,并冠以順序編號n。步4若目標(biāo)節(jié)點Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。步6擴(kuò)展N,生成一組子節(jié)點,對這組子節(jié)點做如下處理：樹式搜索算法：步1把初始節(jié)點So放入OPEN表中。

(1)刪除N的先輩節(jié)點(如果有的話)。

(2)對已存在于OPEN表的節(jié)點(如果有的話)也刪除之；但刪除之前要比較其返回初始節(jié)點的新路徑與原路徑,如果新路徑“短”,則修改這些節(jié)點在OPEN表中的原返回指針,使其沿新路返回(如圖3-5所示)。

(3)對已存在于CLOSED表的節(jié)點(如果有的話),做與(2)同樣的處理,并且再將其移出CLOSED表,放入OPEN表重新擴(kuò)展(為了重新計算代價)。

(4)對其余子節(jié)點配上指向N的返回指針后放入OPEN表中某處,或?qū)PEN表進(jìn)行重新排序,轉(zhuǎn)步2。(1)刪除N的先輩節(jié)點(如果有的話)。圖

3-5修改返回指針示例

圖3-5修改返回指針示例

說明：

(1)這里的返回指針也就是父節(jié)點在CLOSED表中的編號。

(2)步6中修改返回指針的原因是,因為這些節(jié)點又被第二次生成,所以它們返回初始節(jié)點的路徑已有兩條,但這兩條路徑的“長度”可能不同。那么,當(dāng)新路短時自然要走新路。

(3)這里對路徑的長短是按路徑上的節(jié)點數(shù)來衡量的,后面我們將會看到路徑的長短也可以其“代價”(如距離、費用、時間等)衡量。若按其代價衡量,則在需修改返回指針的同時還要修改相應(yīng)的代價值,或者不修改返回指針也要修改代價值(為了實現(xiàn)代價小者優(yōu)先擴(kuò)展)。

說明：線式搜索算法：·

不回溯的線式搜索

步1把初始節(jié)點So放入CLOSED表中。步2令N＝So。步3若N是目標(biāo)節(jié)點,則搜索成功,結(jié)束。步4若N不可擴(kuò)展,則搜索失敗,退出。步5擴(kuò)展N,選取其一個未在CLOSED表中出現(xiàn)過的子節(jié)點N1放入CLOSED表中,令N＝N1,轉(zhuǎn)步3。線式搜索算法：步1把初始節(jié)點So放入CLOSED表中

·

可回溯的線式搜索

步1把初始節(jié)點So放入CLOSED表中。步2令N＝So。步3若N是目標(biāo)節(jié)點,則搜索成功,結(jié)束。步4若N不可擴(kuò)展,則移出CLOSED表的末端節(jié)點Ne,若Ne＝So,則搜索失敗,退出。否則,以CLOSED表新的末端節(jié)點Ne作為N,即令N＝Ne,轉(zhuǎn)步4。步5擴(kuò)展N,選取其一個未在CLOSED表用出現(xiàn)過的子節(jié)點N1放入CLOSED表中,令N＝N1,轉(zhuǎn)步3。

·可回溯的線式搜索3.1.3窮舉式搜索

1.廣度優(yōu)先搜索

圖3-6八數(shù)碼問題的廣度優(yōu)先搜索3.1.3窮舉式搜索圖3-6八數(shù)碼問題的廣度優(yōu)先搜索

廣度優(yōu)先搜索算法：

步1把初始節(jié)點So放入OPEN表中。步2若OPEN表為空,則搜索失敗,退出。步3取OPEN表中前面第一個節(jié)點N放在CLOSED表中,并冠以順序編號n。步4若目標(biāo)節(jié)點Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。步6擴(kuò)展N,將其所有子節(jié)點配上指向N的指針依次放入OPEN表尾部,轉(zhuǎn)步2。廣度優(yōu)先搜索算法：

2.深度優(yōu)先搜索2.深度優(yōu)先搜索

深度優(yōu)先搜索算法：

步1把初始節(jié)點So放入OPEN表中。步2若OPEN表為空,則搜索失敗,退出。步3取OPEN表中前面第一個節(jié)點N放入CLOSED表中,并冠以順序編號n。步4若目標(biāo)節(jié)點Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。步6擴(kuò)展N,將其所有子節(jié)點配上指向N的返回指針依次放入OPEN表的首部,轉(zhuǎn)步2。

深度優(yōu)先搜索算法：

3.有界深度優(yōu)先搜索

步1把So放入OPEN表中,置So的深度d(So)=0。步2若OPEN表為空,則失敗,退出。步3取OPEN表中前面第一個節(jié)點N,放入CLOSED表中,并冠以順序編號n。步4若目標(biāo)節(jié)點Sg=N,則成功,結(jié)束。步5若N的深度d(N)=dm(深度限制值),或者若N無子節(jié)點,則轉(zhuǎn)步2。步6擴(kuò)展N,將其所有子節(jié)點Ni配上指向N的返回指針后依次放入OPEN表中前部,置d(Ni)=d(N)+1,轉(zhuǎn)步2。3.有界深度優(yōu)先搜索3.1.4啟發(fā)式搜索

1.問題的提出

2.啟發(fā)性信息

按其用途劃分,啟發(fā)性信息可分為以下三類：

(1)用于擴(kuò)展節(jié)點的選擇,即用于決定應(yīng)先擴(kuò)展哪一個節(jié)點,以免盲目擴(kuò)展。

(2)用于生成節(jié)點的選擇,即用于決定應(yīng)生成哪些后續(xù)節(jié)點,以免盲目地生成過多無用節(jié)點。

(3)用于刪除節(jié)點的選擇,即用于決定應(yīng)刪除哪些無用節(jié)點,以免造成進(jìn)一步的時空浪費。3.1.4啟發(fā)式搜索3.啟發(fā)函數(shù)

啟發(fā)函數(shù)是用來估計搜索樹上節(jié)點x與目標(biāo)節(jié)點Sg接近程度的一種函數(shù),通常記為h(x)。4.啟發(fā)式搜索算法

1)全局擇優(yōu)搜索

2)局部擇優(yōu)搜索

3.啟發(fā)函數(shù)全局擇優(yōu)搜索算法：

步1把初始節(jié)點So放入OPEN表中,計算h(So)。步2若OPEN表為空,則搜索失敗,退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中,并冠以序號n。步4若目標(biāo)節(jié)點Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。步6擴(kuò)展N,計算每個子節(jié)點x的函數(shù)值h(x),并將所有子節(jié)點配以指向N的返回指針后放入OPEN表中,再對OPEN表中的所有子節(jié)點按其函數(shù)值大小以升序排序,轉(zhuǎn)步2。全局擇優(yōu)搜索算法：步1把初始節(jié)點So放入OPEN表圖

3-8八數(shù)碼問題的全局擇優(yōu)搜索

圖3-8八數(shù)碼問題的全局擇優(yōu)搜索

例3.5

用全局擇優(yōu)搜索法解八數(shù)碼難題。初始棋局和目標(biāo)棋局同例3。

解

設(shè)啟發(fā)函數(shù)h(x)為節(jié)點x的格局與目標(biāo)格局相比數(shù)碼不同的位置個數(shù)。以這個函數(shù)制導(dǎo)的搜索樹如圖3-8所示。此八數(shù)問題的解為：So,S1,S2,S3,Sg。

例3.5用全局擇優(yōu)搜索法解八數(shù)碼難題。初始棋局和目標(biāo)3.1.5加權(quán)狀態(tài)圖搜索

1.加權(quán)狀態(tài)圖與代價樹

例3.6

圖3-9(a)是一個交通圖,設(shè)A城是出發(fā)地,E城是目的地,邊上的數(shù)字代表兩城之間的交通費。試求從A到E最小費用的旅行路線。3.1.5加權(quán)狀態(tài)圖搜索圖

3-9交通圖及其代價樹

圖3-9交通圖及其代價樹

代價樹的搜索。所謂代價,可以是兩點之間的距離、交通費用或所需時間等等。通常用g(x)表示從初始節(jié)點So到節(jié)點x的代價,用c(xi,xj)表示父節(jié)點xi到子節(jié)點xj的代價,即邊(xi,xj)的代價。從而有

g(xj)＝g(xi)＋c(xi,xj)而

g(So)＝0代價樹的搜索。所謂代價,可以是兩點之間的距離、交通費用或

2.分支界限法(最小代價優(yōu)先法)

●基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點進(jìn)行考察,而不管這個節(jié)點在搜索樹的什么位置上。

●算法與前面的“全局擇優(yōu)法”

僅有引導(dǎo)搜索的函數(shù)不同，前者為啟發(fā)函數(shù)h(x)，后者為代價g(x)。

●但注意：代價值g(x)是從初始節(jié)點So方向計算而來的,而啟發(fā)函數(shù)值h(x)則是朝目標(biāo)節(jié)點方向計算的。

2.分支界限法(最小代價優(yōu)先法)

3.最近擇優(yōu)法(瞎子爬山法)

把局部擇優(yōu)法算法中的h(x)換成g(x)就可得最近擇優(yōu)法的算法。

例：用代價樹搜索求解例3.6中給出的問題。用分支界限法得到的路徑為A→C→D→E這是一條最小費用路徑(費用為8)。3.最近擇優(yōu)法(瞎子爬山法)3.1.6A算法和A*算法

1.估價函數(shù)

f(x)＝g(x)＋h(x)

3.1.6A算法和A*算法

2.A算法

A算法是基于估價函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。其具體步驟如下：

步1把附有f(So)的初始節(jié)點So放入OPEN表。步2若OPEN表為空,則搜索失敗,退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中,并冠以順序編號n。步4若目標(biāo)節(jié)點Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。2.A算法步1把附有f(So)的初始節(jié)點So

步6擴(kuò)展N,生成一組附有f(x)的子節(jié)點,對這組子節(jié)點做如下處理：

(1)考察是否有已在OPEN表或CLOSED表中存在的節(jié)點；若有則再考察其中有無N的先輩節(jié)點,若有則刪除之；對于其余節(jié)點,也刪除之,但由于它們又被第二次生成,因而需考慮是否修改已經(jīng)存在于OPEN表或CLOSED表中的這些節(jié)點及其后裔的返回指針和f(x)值,修改原則是“抄f(x)值小的路走”。

(2)對其余子節(jié)點配上指向N的返回指針后放入OPEN表中,并對OPEN表按f(x)值以升序排序,轉(zhuǎn)步2。步6擴(kuò)展N,生成一組附有f(x)的子節(jié)點,對這組子節(jié)點算法中節(jié)點x的估價函數(shù)f(x)的計算方法是

f(xj)＝g(xj)＋h(xj)

＝g(xi)＋c(xi,xj)＋h(xj)

(xj是xi的子節(jié)點)

至于h(x)的計算公式則需由具體問題而定?？梢钥闯?A算法其實就是對于本節(jié)開始給出的圖搜索一般算法中的樹式搜索算法,再增加了估價函數(shù)f(x)的一種啟發(fā)式搜索算法。算法中節(jié)點x的估價函數(shù)f(x)的計算方法是f(xj)＝g(

3.A*算法

如果對上述A算法再限制其估價函數(shù)中的啟發(fā)函數(shù)h(x)滿足：對所有的節(jié)點x均有

h(x)≤h*(x)其中h*(x)是從節(jié)點x到目標(biāo)節(jié)點的最小代價,即最佳路徑上的實際代價(若有多個目標(biāo)節(jié)點則為其中最小的一個),則它就稱為A*算法。3.A*算法3.1.7狀態(tài)圖搜索策略小結(jié)3.1.7狀態(tài)圖搜