配套課件-人工智能技術導論(第三版)

人工智能導論人工智能導論

第1章人工智能概述

1.1什么是人工智能

1.2人工智能的研究意義、目標和策略

1.3人工智能的學科范疇

1.4人工智能的研究內容

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

1.6人工智能的基本技術

1.7人工智能的應用

1.8人工智能的分支領域與研究方向

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

1.1什么是人工智能

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

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

——

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

——

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

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

1.1什么是人工智能——

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

廣義地講，人工智能是關于人造物的智能行為，而智能行為包括知覺、推理、學習、交流和在復雜環(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)典人工智能。符號智能以符號形式的知識和信息為基礎，主要通過邏輯推理，運用知識進行問題求解。符號智能的主要內容包括知識獲取（knowledgeacquisition）、知識表示（knowledgerepresentation）、知識組織與管理和知識運用等技術（這些構成了所謂的知識工程（KnowledgeEngineering,KE））以及基于知識的智能系統(tǒng)等。

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

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

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

■

使當前的電腦更好用，更有用，以擴大和延伸人類智能；

■

信息化社會的迫切要求；

■

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

■

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

1.3人工智能的學科范疇

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

1.4人工智能的研究內容1.5.1搜索與求解1.5.2學習與發(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應用與工程1.4人工智能的研究內容1.5人工智能的研究途徑與方法1.5.1心理模擬，符號推演1.5.2生理模擬，神經(jīng)計算1.5.3行為模擬，控制進化1.5.4群體模擬，仿生計算1.5.5博采廣鑒，自然計算1.5.6原理分析，數(shù)學建模1.5人工智能的研究途徑與方法

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

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

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

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

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

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

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

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

■理論研究更加深入，應用研究愈加廣泛。

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

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

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

配套課件-人工智能技術導論(第三版)

智能交通智能交通

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

云松

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

云松

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

（無題）

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

背叛

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

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

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

第2章邏輯程序設計語言PROLOG

2.1基本PROLOG

2.2TurboPROLOG程序設計

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

1.事實(fact)

格式

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

like(mary,music).abc.repeat.

功能一般表示對象的性質或關系。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.

功能

一般表示對象間的因果關系、蘊含關系或對應關系。

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

格式

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

?

-student(john).?

-like(mary,X).

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

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

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程序的運行機理

1.自由變量與約束變量

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

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

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

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

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

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.回溯所謂回溯,就是在程序運行期間,當某一個子目標不能滿足(即謂詞匹配失敗)時,控制就返回到前一個已經(jīng)滿足的子目標(如果存在的話),并撤消其有關變量的約束值,然后再使其重新滿足。成功后,再繼續(xù)滿足原子目標。如果失敗的子目標前再無子目標,則控制就返回到該子目標的上一級目標(即該子目標謂詞所在規(guī)則的頭部)使它重新匹配?；厮菀彩荘ROLOG的一個重要機制。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).則求解目標為

friend(john,Y).

新目標

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

2.2TurboPROLOG程序設計2.2.1程序結構

/*〈注釋〉*/

〈編譯指令〉constants

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

2.2TurboPROLOG程序設計例

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

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程序,

領域段

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

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

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

1.領域

1)標準領域整數(shù)、實數(shù)、字符、串和符號

2)結構結構也稱復合對象,一般形式為

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

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

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

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

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

［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ù)、字符、串、符號、結構、表和文件這八種數(shù)據(jù)類型。同理,TurboPROLOG的變量也就有這八種取值。另外,變量名要求必須是以大寫字母或下劃線開頭的字母、數(shù)字和下劃線序列,或者只有一個下劃線。這后一種變量稱為無名變量。

2.常量與變量3.算術表達式

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

數(shù)學中的算術表達式PROLOG中的算術表達式

x+yz

X+Y*Zab-c/d

A*B-C/DumodvUmodV

Y=X+5 √X=X+1×3.算術表達式4.關系表達式

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

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

數(shù)學中的關系式TurboPROLOG中的關系式

X+1≥Y

X+1>=YX≠Y

X<>Y4.關系表達式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.當變量X、Y、Z全部被實例化時,“=”就是比較符。如：對于問題

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

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

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

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(″對不起,找不到這個學生!″).例用輸入輸出謂詞編寫一個簡單的成績數(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.表的匹配合一————————————————————例設計一個能判斷對象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例設計一個能判斷對象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)若將“!”插在子句體內作為一個子目標,它總是立即成功。

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

(3)若“!”位于其他位置,則當其后發(fā)生回溯且回溯到“!”處時,就在此處失敗,并且“!”還使它所在子句的頭謂詞(子目標)整個失敗(即阻止再去訪問頭謂詞的其余子句(如果有的話),即迫使系統(tǒng)直接回溯到該頭謂詞(子目標)的前一個子目標(如果有的話))。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).

對于目標:r(Y).

可有一個解

Y=b

但當把式(2-4)改為

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

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

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

…

…

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

g12:-g21,g23,!.(2-9)例設有程序：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若目標節(jié)點Sg=N,則搜索成功,結束。步5若N不可擴展,則轉步2。步6擴展N,生成一組子節(jié)點,對這組子節(jié)點做如下處理：樹式搜索算法：步1把初始節(jié)點So放入OPEN表中。

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

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

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

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

3-5修改返回指針示例

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

說明：

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

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

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

說明：線式搜索算法：·

不回溯的線式搜索

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

·

可回溯的線式搜索

步1把初始節(jié)點So放入CLOSED表中。步2令N＝So。步3若N是目標節(jié)點,則搜索成功,結束。步4若N不可擴展,則移出CLOSED表的末端節(jié)點Ne,若Ne＝So,則搜索失敗,退出。否則,以CLOSED表新的末端節(jié)點Ne作為N,即令N＝Ne,轉步4。步5擴展N,選取其一個未在CLOSED表用出現(xiàn)過的子節(jié)點N1放入CLOSED表中,令N＝N1,轉步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若目標節(jié)點Sg=N,則搜索成功,結束。步5若N不可擴展,則轉步2。步6擴展N,將其所有子節(jié)點配上指向N的指針依次放入OPEN表尾部,轉步2。廣度優(yōu)先搜索算法：

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

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

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

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

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

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

1.問題的提出

2.啟發(fā)性信息

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

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

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

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

啟發(fā)函數(shù)是用來估計搜索樹上節(jié)點x與目標節(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若目標節(jié)點Sg=N,則搜索成功,結束。步5若N不可擴展,則轉步2。步6擴展N,計算每個子節(jié)點x的函數(shù)值h(x),并將所有子節(jié)點配以指向N的返回指針后放入OPEN表中,再對OPEN表中的所有子節(jié)點按其函數(shù)值大小以升序排序,轉步2。全局擇優(yōu)搜索算法：步1把初始節(jié)點So放入OPEN表圖

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

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

例3.5

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

解

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

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

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

例3.6

圖3-9(a)是一個交通圖,設A城是出發(fā)地,E城是目的地,邊上的數(shù)字代表兩城之間的交通費。試求從A到E最小費用的旅行路線。3.1.5加權狀態(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é)點進行考察,而不管這個節(jié)點在搜索樹的什么位置上。

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

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

●但注意：代價值g(x)是從初始節(jié)點So方向計算而來的,而啟發(fā)函數(shù)值h(x)則是朝目標節(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)的一種加權狀態(tài)圖啟發(fā)式搜索算法。其具體步驟如下：

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

步6擴展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)值以升序排序,轉步2。步6擴展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到目標節(jié)點的最小代價,即最佳路徑上的實際代價(若有多個目標節(jié)點則為其中最小的一個),則它就稱為A*算法。3.A*算法3.1.7狀態(tài)圖搜索策略小結3.1.7狀態(tài)圖搜