配套ppt课件-人工智能技术导论(第三版)

人工智能导论人工智能导论 第1章 人工智能概述 1.1 什么是人工智能 1.2 人工智能的研究意义、目标和策略 1.3 人工智能的学科范畴 1.4 人工智能的研究内容 1.5 人工智能的研究途径与方法 1.6 人工智能的基本技术 1.7 人工智能的应用 1.8 人工智能的分支领域与研究方向 1.9 人工智能的发展概况 第1章人工智能概述 1.1 什么是人工智能人工智能（Artificial Intelligence”，AI）1.1.1 人工智能概念的一般描述 部分学者对人工智能概念的描述：人工智能是那些与人的思维相关的活动，诸如决策、问题求解和学习等的自动化（Bellman,1978）；人工智能是一种计算机能够思维，使机器具有智力的激动人心的新尝试（Haugeland,1985）；人工智能是研究如何让计算机做现阶段只有人才能做得好的事情（Rich Knight,1991）；1.1什么是人工智能 人工智能是那些使知觉、推理和行为成为可能的计算的研究（Winston,1992）；广义地讲，人工智能是关于人造物的智能行为，而智能行为包括知觉、推理、学习、交流和在复杂环境中的行为（Nilsson，1998）。Stuart Russell和Peter Norvig则把已有的一些人工智能定义分为4类：像人一样思考的系统、像人一样行动的系统、理性地思考的系统、理性地行动的系统（2003）。人工智能是那些使知觉、推理和行为成为可能的计算的研究（1.1.2 图灵测试和中文屋子图灵测试”（TuringTest）1.1.2图灵测试和中文屋子约翰.西尔勒(JohnSearle)的“中文屋子中文屋子”约翰.西尔勒(JohnSearle)的“中文屋子”1.1.3 脑智能和群智能脑（主要指人脑）的宏观心理层次的智能表现称为脑智能脑智能（Brain Intelligence,BI）。由群体行为所表现出的智能称为群智能群智能（Swarm Intelligence,SI）。脑智能和群智能是属于不同层次的智能：脑智能是一种个体智能个体智能（Individual Intelligence,II）；群智能是一种社会智能社会智能（Social Intelligence,SI），或者说系统智能系统智能（System Intelligence,SI）。1.1.3脑智能和群智能1.1.4 符号智能和计算智能1.符号智能符号智能符号智能就是符号人工智能，它是模拟脑智能的人工智能，也就是所说的传统人工智能或经典人工智能。符号智能以符号形式的知识和信息为基础，主要通过逻辑推理，运用知识进行问题求解。符号智能的主要内容包括知识获取（knowledge acquisition）、知识表示（knowledge representation）、知识组织与管理和知识运用等技术（这些构成了所谓的知识工程（Knowledge Engineering,KE）以及基于知识的智能系统等。1.1.4符号智能和计算智能 2.计算智能计算智能计算智能就是计算人工智能，它是模拟群智能的人工智能。计算智能以数值数据为基础，主要通过数值计算，运用算法进行问题求解。计算智能的主要内容包括：神经计算（Neural Computation，NC）、进化计算（亦称演化计算，Evolutionary Computation，EC，包括遗传算法（Genetic Algorithm，GA）、进化规划（Evolutionary Planning，EP）、进化策略（Evolutionary Strategies，ES）等）、免疫计算（immune computation）、粒群计算（Particle Swarm Algorithm，PSA）、蚁群算法（Ant Colony Algorithm，ACA）、自然计算（Natural Computation，NC）以及人工生命（Artificial Life，AL）等。2.计算智能1.2 人工智能的研究意义、目标和策略1.2.1 为什么要研究人工智能使当前的电脑更好用，更有用，以扩大和延伸人类智能；信息化社会的迫切要求；自动化发展的必然趋势；有益于探索人类自身智能的奥秘。1.2人工智能的研究意义、目标和策略1.2.2 人工智能的研究目标和策略研究目标就是制造智能机器和智能系统，实现智能化社会。具体来讲，就是要使计算机不仅具有脑智能和群智能，还要具有看、听、说、写等感知和交流能力。研究策略则是先部分地或某种程度地实现机器的智能，并运用智能技术解决各种实际问题特别是工程问题，从而使现有的计算机更灵活、更好用和更有用，成为人类的智能化信息处理工具，而逐步扩展和不断延伸人的智能，逐步实现智能化。1.2.2人工智能的研究目标和策略 1.3 人工智能的学科范畴人工智能已构成信息技术领域的一个重要学科。当前的人工智能既属于计算机科学技术的一个前沿领域，也属于信息处理和自动化技术的一个前沿领域。还涉及到智能科学、认知科学、心理科学、脑及神经科学、生命科学、语言学、逻辑学、行为科学、教育科学、系统科学、数理科学以及控制论、科学方法论、哲学甚至经济学等众多学科领域。人工智能实际上是一门综合性的交叉学科和边缘学科。1.3人工智能的学科范畴 1.4 人工智能的研究内容1.5.1 搜索与求解1.5.2 学习与发现1.5.3 知识与推理1.5.4 发明与创造1.5.5 感知与交流1.5.6 记忆与联想1.5.7 系统与建造1.5.8 应用与工程1.4人工智能的研究内容 1.5 人工智能的研究途径与方法1.5.1 心理模拟，符号推演1.5.2 生理模拟，神经计算1.5.3 行为模拟，控制进化1.5.4 群体模拟，仿生计算1.5.5 博采广鉴，自然计算1.5.6 原理分析，数学建模1.5人工智能的研究途径与方法 1.6 人工智能的基本技术表示运算搜索1.6人工智能的基本技术 1.7 人工智能的应用1.7.1 难题求解1.7.2 自动规划、调度与配置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 数据挖掘与数据库中的知识发现1.7.17 计算机辅助创新1.7.18 计算机文艺创作1.7.19 机器博弈1.7.20 智能机器人1.7.11智能CAD 1.8 人工智能的分支领域与研究方向从模拟的层次和所用的方法来看，人工智能可分为符号智能和计算智能两大主要分支领域。而这两大领域各自又有一些子领域和研究方向。如符号智能中又有图搜索、自动推理、不确定性推理、知识工程、符号学习等。计算智能中又有神经计算、进化计算、免疫计算、蚁群计算、粒群计算、自然计算等。另外，智能Agent也是人工智能的一个新兴的重要领域。智能Agent或者说Agent智能则是以符号智能和计算智能为基础的更高一级的人工智能。从模拟的脑智能或脑功能来看，AI中有机器学习、机器感知、机器联想、机器推理、机器行为等分支领域。而机器学习又可分为符号学习、连接学习、统计学习等许多研究领域和方向。机器感知又可分为计算机视觉、计算机听觉、模式识别、图像识别与理解、语音识别、自然语言处理等领域和方向。1.8人工智能的分支领域与研究方向从应用角度看，如1.7节所述，AI中有难题求解等数十种分支领域和研究方向。从系统角度看，有智能计算机系统和智能应用系统两大类。智能计算机系统又可分为：智能硬件平台、智能操作系统、智能网络系统等。智能应用系统又可分为：基于知识的智能系统、基于算法的智能系统和兼有知识和算法的智能系统等。另外，还有分布式人工智能系统。从基础理论看，AI中有数理逻辑和多种非标准逻辑、图论、人工神经网络、模糊集、粗糙集、概率统计（贝叶斯统计决策理论）和贝叶斯网络、统计学习理论与支持向量机、形式语言与自动机等领域和方向。从应用角度看，如1.7节所述，AI中有难题求解等数十种分支领 1.9 人工智能学科的发展概况1.9.1 人工智能学科的产生1.9.2 符号主义途径发展概况1.9.3 连接主义途径发展概况1.9.4 计算智能异军突起1.9.5 智能Agent方兴未艾1.9人工智能学科的发展概况1.9.6 现状与发展趋势多种途径齐头并进，多种方法协作互补。新思想、新技术不断涌现，新领域、新方向不断开拓。理论研究更加深入，应用研究愈加广泛。研究队伍日益壮大，社会影响越来越大。1.9.6现状与发展趋势虽然在通向人工智能最终目标的道路上，还有不少困难、问题和挑战，但前进和发展毕竟是大势所趋。配套ppt课件-人工智能技术导论(第三版)智能交通智能交通 图像识别系统图像识别系统 云松 銮仙玉骨寒，松虬雪友繁。大千收眼底，斯调不同凡。云松 （无题）白沙平舟夜涛声，春日晓露路相逢。朱楼寒雨离歌泪，不堪肠断雨乘风。（无题）BetrayalDaveStriverlovedtheuniversity.Heloveditsivy-coveredclocktowers,itsancientandsturdybrick,anditssun-splashedverdantgreensandeageryouth.Healsolovedthefactthattheuniversityisfreeofthestarkunforgivingtrialsofthebusinessworld-onlythisisntafact:Academiahasitsowntests,andsomeareasmercilessasanyinthemarketplace.Aprimeexampleisthedissertationdefense:ToearnthePhD,tobecomeadoctor,onemustpassanoralexaminationononesdissertation.ThiswasatestProfessorEdwardHartenjoyedgiving.Davewanteddesperatelytobeadoctor.Butheneededthesignaturesofthreepeopleonthefirstpageofhisdissertation,thepricelessinscriptionsthat,together,wouldcertifythathehadpassedhisdefense.OneofthesignatureshadtocomefromProfessorHart,andHarthadoftensaid-toothersandtohimself-thathewashonoredtohelpDavesecurehiswell-earneddream.Wellbeforethedefense,StrivergaveHartapenultimatecopyofhisthesis.HartreaditandtoldDavethatitwasabsolutelyfirstrate,andthathewouldgladlysignitatthedefense.TheyevenshookhandsinHartsbook-linedoffice.DavenoticedthatHartseyeswerebrightandtrustful,andhisbearingpaternal.Atthedefense,Davethoughtthatheeloquentlysummarizedchapter3ofhisdissertation.Thereweretwoquestions,onefromProfessorRodmanandonefromDr.Teer;Daveansweredboth,apparentlytoeveryonessatisfaction.Therewerenofurtherobjections.Wellbeforethedefense,StProfessorRodmansigned.HeslidthetometoTeer;shetoosigned,andthensliditinfrontofHart.Hartdidntmove.Ed?Rodmansaid.Hartstillsatmotionless.Davefeltslightlydizzy.Edward,areyougoingtosign?Later,Hartsataloneinhisofficeinhisbigleatherchair,saddenedbyDavesfailure.HetriedtothinkofwayshecouldhelpDaveachievehisdream.ProfessorRodmansigned.He背叛戴夫斯特赖维尔喜爱这所大学。他喜爱校园里爬满常青藤的钟楼，那古色古香而又坚固的砖块，还有那洒满阳光的碧绿草坪和热情的年轻人。使他感到欣慰的还有这样一件事，即大学里完全没有商场上那些冷酷无情的考验但事实恰恰并非如此：做学问也要通过考试，而且有的考试与市场上的考验一样不留情面。最好的例子就是论文答辩：为了取得博士学位，为了成为博士，博士生必须通过论文的口试，爱德华哈特教授就喜欢主持这样的答辩考试。背叛戴夫迫切希望成为一名博士。但他需要让个人在他论文的第一页上签上他们的名字，这个千金难买的签名能够证明他通过了答辩。其中一个签名是哈特教授的。哈特常常对戴夫本人和其他人说，对于帮助戴夫实现他应该有的梦想，他感到很荣幸。答辩之前，斯特赖维尔早早给哈特送去了他论文的倒数第二稿。哈特阅读后告诉戴夫，论文水平绝对一流，答辩时他会很高兴地在论文上签名。在哈特那四壁摆满书橱的办公室里，两人甚至还握了手。戴夫注意到，哈特两眼放光，充满信任，神情宛如慈父一般。戴夫迫切希望成为一名博士。但他需要让个人在在答辩时，戴夫觉得自己流利地概括了论文的第三章。评审者提了两个问题，一个是罗德曼教授提的，另一个是蒂尔博士提的。戴夫分别做了回答，并且显然让每个人都心悦诚服，再没有人提出异议。罗德曼教授签了名。他把论文推给蒂尔，她也签上了名字，接着便把本子推到了哈特跟前。哈特没有动。“爱德华？”罗德曼问道。哈特仍然坐在那儿，毫无表情。戴夫感到有点眩晕。“爱德华，你打算签名吗？”过后，哈特一个人呆在办公室里，坐在那张宽大的皮椅里，他为戴夫未能通过答辩感到难过。他试图想出帮助戴夫实现他梦想的办法。在答辩时，戴夫觉得自己流利地概括了论文的第三配套ppt课件-人工智能技术导论(第三版)配套ppt课件-人工智能技术导论(第三版)配套ppt课件-人工智能技术导论(第三版)配套ppt课件-人工智能技术导论(第三版)第2章 逻辑程序设计语言PROLOG 2.1 基本PROLOG 2.2 Turbo PROLOG程序设计 第2章逻辑程序设计语言PROLOG 2.1 基本PROLOG 2.1.1 PROLOG的语句 1.1.事实事实(fact)(fact)格式 谓词名(项表).student(john).like(mary,music).abc.repeat.功能 一般表示对象的性质或关系。2.1基本PROLOG 2.2.规则规则(rule)(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.规则(rule)3.问题(question)格式?-谓词名(项表),谓词名(项表).?-student(john).?-like(mary,X).功能问题表示用户的询问,它就是程序运行的目标。3.问题(question)2.1.2 PROLOG的程序 PROLOG程序一般由一组事实、规则和问题组成。问题是程序执行的起点,称为程序的目标。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.3 PROLOG程序的运行机理 1.1.自由变量与约束变量自由变量与约束变量 2.2.匹配合一匹配合一 两个谓词可匹配合一,是指两个谓词的名相同,参量项的个数相同,参量类型对应相同,并且对应参量项还满足下列条件之一：(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.3.回溯回溯 所谓回溯,就是在程序运行期间,当某一个子目标不能满足(即谓词匹配失败)时,控制就返回到前一个已经满足的子目标(如果存在的话),并撤消其有关变量的约束值,然后再使其重新满足。成功后,再继续满足原子目标。如果失败的子目标前再无子目标,则控制就返回到该子目标的上一级目标(即该子目标谓词所在规则的头部)使它重新匹配。回溯也是PROLOG的一个重要机制。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).配套ppt课件-人工智能技术导论(第三版)2.2 Turbo PROLOG程序设计2.2.1 程序结构 /*注 释 */编译指令 constants 常量说明 domains 域说明 database 数据库说明 predicates 谓词说明 goal 目标语句 clauses 子句集2.2TurboPROLOG程序设计例例 如果把上节的例子程序作为Turbo PROLOG程序,则应改写为：DOMAINS name=symbol PREDICATES likes(name,name).friend(name,name)GOAL friend(john,Y),write(Y=,Y).CLAUSES likes(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).例如果把上节的例子程序作为TurboPROLOG程序,领域段该段说明程序谓词中所有参量项所属的领域。Turbo PROLOG的标准领域包括整数、实数、符号、串和符号等,其具体说明如下表所示。领域段该段说明程序谓词中所有参量项所属的领域。Tu谓词段 该段说明程序中用到的谓词的名和参量项的名(但Turbo PROLOG 的内部谓词无须说明)子句段 该段是Turbo PROLOG程序的核心,程序中的所有事实和规则就放在这里,系统在试图满足程序的目标时就对它们进行操作。目标段 该段是放置程序目标的地方。目标段可以只有一个目标谓词,例如上面的例子中就只有一个目标谓词；也可以含有多个目标谓词,如 goal readint(X),Y=X+3,write(Y=,Y).就有三个目标谓词。这种目标称为复合目标。谓词段该段说明程序中用到的谓词的名和参量项的名(但Turb2.2.2 数据与表达式1.1.领域领域 1)标准领域 整数、实数、字符、串和符号 2)结构 结构也称复合对象,一般形式为 函子(参量表)likes(Tom,sports(football,basketball,table_tennis).reading(王宏,book(人工智能技术导论,西安电子科技大学出版社).friend(father(Li),father(Zhao).2.2.2数据与表达式复合对象在程序中的说明,需分层进行。例如,对于上面的谓词 likes(Tom,sports(football,basketball,table_tennis).在程序中可说明如下：domains name=symbol sy=symbol sp=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,in logic a,b,c,d,e name(LiMing),age(20),sex(male),addr(xian)3)表表的说明方法是在其组成元素的说明符后加一个星号*。如：domains lists=string*predicates pl(lists)例如，谓词 p(name(Liming),age(20)则需这样说明:domains rec=seg*seg=name(string);age(integer)predicates p(rec)表的说明方法是在其组成元素的说明符后加一个星号*。如：2.2.常量与变量常量与变量 Turbo PROLOG的常量有整数、实数、字符、串、符号、结构、表和文件这八种数据类型。同理,Turbo PROLOG的变量也就有这八种取值。另外,变量名要求必须是以大写字母或下划线开头的字母、数字和下划线序列,或者只有一个下划线。这后一种变量称为无名变量。2.常量与变量3.3.算术表达式算术表达式 Turbo PROLOG提供了五种最基本的算术运算：加、减、乘、除和取模,相应运算符号为+、-、*、/、mod。这五种运算的顺序为：*、/、mod优先于+、-。数学中的算术表达式 PROLOG中的算术表达式 x+yz X+Y*Z ab-c/d A*B-C/D u mod v U mod VY=X+5X=X+13.算术表达式4.4.关系表达式关系表达式 Turbo PROLOG提供了六种常用的关系运算,即小于、小于或等于、等于、大于、大于或等于和不等于,其运算符依次为 ,=,数学中的关系式 Turbo PROLOG中的关系式 X+1Y X+1=Y XY XY 4.关系表达式brother(Name1,Name2):-person(Name1,man,Age1),person(Name2,man,Age2),mother(Z,Name1),mother(Z,Name2),Age1Age2.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)nl2.2.3输入与输出例 用输入输出谓词编写一个简单的成绩 数据库查询程序。PREDICATES student(integer,string,real)grade GOAL grade.CLAUSES student(1,张三,90.2).student(2,李四,95.5).student(3,王五,96.4).grade:-write(请输入姓名:),readln(Name),student(_,Name,Score),nl,write(Name,的成绩是,Score).grade:-write(对不起,找不到这个学生!).例用输入输出谓词编写一个简单的成绩数据库查询程序。2.2.4 分支与循环1.1.分支分支 将 IF x0 THEN x:=1 ELSE x:=0用PROLOG实现则可以是 br:-x0,x=1.br:-x=0.2.2.4分支与循环2.2.循环循环 程序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.循环 程序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 动态数据库 动态数据库操作谓词:asserta(fact).assertz(fact).retract(fact).例 asserta(student(20,李明,90.5).retract(student(20,_,_).2.2.5动态数据库2.2.6 表处理与递归 1.表头与表尾 表头是表中的第一个元素；表尾是表中除第一个元素外的其余元素按原来顺序组成的表。表头与表尾示例表表头表尾1,2,3,4,51,2,3,4,5112,3,4,52,3,4,5apple,orange,bananaapple,orange,bananaappleappleorange,bananaorange,bananaa,ba,b,c c,d,ed,ea,ba,bc c,d,ed,ePROLOGPROLOGPROLOGPROLOG 无定义无定义无定义无定义2.2.6表处理与递归 2.表的匹配合一 表的匹配合一示例表1表2合一后的变量值X XY Y a,b,ca,b,cX=a,Y=b,cb,cX XY Y a aX=a,Y=a aY YX,bX,bX=a,Y=bbX,Y,ZX,Y,Za,b,ca,b,cX=a,Y=b,Z=cb,Z=c a,Y,YZ ZX,b,b,c cX=a,Y=b,Z=b,Z=c c2.表的匹配合一例 设计一个能判断对象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).yes Goal:member(e,a,b,c,d).no Goal: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).yes Goal: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)若“!”位于其他位置,则当其后发生回溯且回溯到“!”处时,就在此处失败,并且“!”还使它所在子句的头谓词(子目标)整个失败(即阻止再去访问头谓词的其余子句(如果有的话),即迫使系统直接回溯到该头谓词(子目标)的前一个子目标(如果有的话)。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 程序举例例 一个简单的路径查询程序。predicates road(symbol,symbol)path(symbol,symbol)clauses road(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).yesyesGoal:path(e,a).nonoGoal：run.run:-path(a,X),write(X=,X),nl,fail.run.X=bX=b X=cX=c X=dX=d X=eX=e X=dX=d X=eX=e X=eX=eGoal:path(a,e).例 下面是一个求阶乘程序,程序中使用了递归。domainsn,f=integerpredicatesfactorial(n,f)goalreadint(I),factorial(I,F),write(I,!=,F).clausesfactorial(1,1).factorial(N,Res):-N0,N1=N-1,factorial(N1,FacN1),Res=N*FacN1.例下面是一个求阶乘程序,程序中使用了递归。第3章图搜索与问题求解3.1 状态图搜索状态图搜索 3.2 状态图搜索问题求解状态图搜索问题求解 3.3 与或图搜索与或图搜索 3.4 与或图搜索问题求解与或图搜索问题求解 第3章图搜索与问题求解3.1状态图搜索3.1 状态图搜索 3.1.1 状态图例例3.1 迷宫问题。3.1状态图搜索3.1.1状态图图3-2迷宫的有向图表示图3-2迷宫的有向图表示图3-3八数码问题示例例例 3.2 3.2 八数码问题。图3-3八数码问题示例例3.2八数码问题。3.1.2 状态图搜索1.1.搜索方式搜索方式树式搜索 线式搜索 2.2.搜索策略搜索策略盲目搜索启发式(heuristic)搜索 3.1.2状态图搜索图3-4OPEN表与CLOSED表示例3.3.搜索算法搜索算法图3-4OPEN表与CLOSED表示例3.搜索算法树式搜索算法：树式搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,生成一组子节点,对这组子节点做如下处理：树式搜索算法：步1把初始节点So放入OPEN表中。(1)删除N的先辈节点(如果有的话)。(2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示)。(3)对已存在于CLOSED表的节点(如果有的话),做与(2)同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展(为了重新计算代价)。(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处,或对OPEN表进行重新排序,转步2。(1)删除N的先辈节点(如果有的话)。图3-5修改返回指针示例图3-5修改返回指针示例说明：(1)这里的返回指针也就是父节点在CLOSED表中的编号。(2)步6中修改返回指针的原因是,因为这些节点又被第二次生成,所以它们返回初始节点的路径已有两条,但这两条路径的“长度”可能不同。那么,当新路短时自然要走新路。(3)这里对路径的长短是按路径上的节点数来衡量的,后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量,则在需修改返回指针的同时还要修改相应的代价值,或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。说明：线式搜索算法：不回溯的线式搜索不回溯的线式搜索 步1把初始节点So放入CLOSED表中。步2令NSo。步3若N是目标节点,则搜索成功,结束。步4若N不可扩展,则搜索失败,退出。步5扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中,令NN1,转步3。线式搜索算法：步1把初始节点So放入CLOSED表中 可回溯的线式搜索可回溯的线式搜索 步1把初始节点So放入CLOSED表中。步2令NSo。步3若N是目标节点,则搜索成功,结束。步4若N不可扩展,则移出CLOSED表的末端节点Ne,若NeSo,则搜索失败,退出。否则,以CLOSED表新的末端节点Ne作为N,即令NNe,转步4。步5扩展N,选取其一个未在CLOSED表用出现过的子节点N1放入CLOSED表中,令NN1,转步3。可回溯的线式搜索3.1.3 穷举式搜索1.1.广度优先搜索广度优先搜索图 3-6 八数码问题的广度优先搜索3.1.3穷举式搜索图3-6八数码问题的广度优先搜索 广度优先搜索算法：广度优先搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的指针依次放入OPEN表尾部,转步2。广度优先搜索算法：2.2.深度优先搜索深度优先搜索2.深度优先搜索 深度优先搜索算法：深度优先搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的返回指针依次放入OPEN表的首部,转步2。深度优先搜索算法：3.有界深度优先搜索有界深度优先搜索步1把So放入OPEN表中,置So的深度d(So)=0。步2若OPEN表为空,则失败,退出。步3取OPEN表中前面第一个节点N,放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则成功,结束。步5若N的深度d(N)=dm(深度限制值),或者若N无子节点,则转步2。步6扩展N,将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表中前部,置d(Ni)=d(N)+1,转步2。3.有界深度优先搜索3.1.4 启发式搜索1.1.问题的提出问题的提出 2.2.启发性信息启发性信息按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。(3)用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。3.1.4启发式搜索3.3.启发函数启发函数启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)。4.4.启发式搜索算法启发式搜索算法1)全局择优搜索2)局部择优搜索3.启发函数全局择优搜索算法：步1把初始节点So放入OPEN表中,计算h(So)。步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以序号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,计算每个子节点x的函数值h(x),并将所有子节点配以指向N的返回指针后放入OPEN表中,再对OPEN表中的所有子节点按其函数值大小以升序排序,转步2。全局择优搜索算法：步1把初始节点So放入OPEN表图3-8八数码问题的全局择优搜索图3-8八数码问题的全局择优搜索例例 3.53.5 用全局择优搜索法解八数码难题。初始棋局和目标棋局同例3。解解设启发函数h(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图3-8所示。此八数问题的解为：So,S1,S2,S3,Sg。例3.5用全局择优搜索法解八数码难题。初始棋局和目标3.1.5 加权状态图搜索1.1.加权状态图与代价树加权状态图与代价树例例3.63.6 图3-9(a)是一个交通图,设A城是出发地,E城是目的地,边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。3.1.5加权状态图搜索图3-9交通图及其代价树图3-9交通图及其代价树代价树的搜索。所谓代价,可以是两点之间的距离、交通费用或所需时间等等。通常用g(x)表示从初始节点So到节点x的代价,用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有g(xj)g(xi)c(xi,xj)而g(So)0代价树的搜索。所谓代价,可以是两点之间的距离、交通费用或2.2.分支界限法分支界限法(最小代价优先法最小代价优先法)基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察,而不管这个节点在搜索树的什么位置上。算法与前面的“全局择优法”仅有引导搜索的函数不同，前者为启发函数h(x)，后者为代价g(x)。但注意：代价值g(x)是从初始节点So方向计算而来的,而启发函数值h(x)则是朝目标节点方向计算的。2.分支界限法(最小代价优先法)3.3.最近择优法最近择优法(瞎子爬山法瞎子爬山法)把局部择优法算法中的h(x)换成g(x)就可得最近择优法的算法。例：例：用代价树搜索求解例3.6中给出的问题。用分支界限法得到的路径为ACDE这是一条最小费用路径(费用为8)。3.最近择优法(瞎子爬山法)3.1.6 A算法和A*算法1.1.估价函数估价函数 f(x)g(x)h(x)3.1.6A算法和A*算法2.A算法算法 A 算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。其具体步骤如下：步1把附有f(So)的初始节点So放入OPEN表。步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。2.A算法步1把附有f(So)的初始节点So步6扩展N,生成一组附有f(x)的子节点,对这组子节点做如下处理：(1)考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点,若有则删除之；对于其余节点,也删除之,但由于它们又被第二次生成,因而需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f(x)值,修改原则是“抄f(x)值小的路走”。(2)对其余子节点配上指向N的返回指针后放入OPEN表中,并对OPEN表按f(x)值以升序排序,转步2。步6扩展N,生成一组附有f(x)的子节点,对这组子节点算法中节点x的估价函数f(x)的计算方法是f(xj)g(xj)h(xj)g(xi)c(xi,xj)h(xj)(xj是xi的子节点)至于h(x)的计算公式则需由具体问题而定。可以看出,A算法其实就是对于本节开始给出的图搜索一般算法中的树式搜索算法,再增加了估价函数f(x)的一种启发式搜索算法。算法中节点x的估价函数f(x)的计算方法是f(xj)g(3.A*算法算法如果对上述A算法再限制其估价函数中的启发函数h(x)满足：对所有的节点x均有 h(x)h*(x)其中h*(x)是从节点x到目标节点的最小代价,即最佳路径上的实际代价(若有多个目标节点则为其中最小的一个),则它就称为A*算法。3.A*算法3.1.7 状态图搜索策略小结 3.1.7状态图搜索策略小结3.2 状态图搜索问题求解 3.2.1 问题的状态图表示1.1.状态状态 状态就是问题在任一确定时刻的状况,它表征了问题特征和结构等。状态在状态图中表示为节点。状态一般用一组数据表示。在程序中用字符、数字、记录、数组、结构、对象等表示。3.2状态图搜索问题求解3.2.1问题的状态图表示2.2.状态转换规则状态转换规则状态转换规则就是能使问题状态改变的某种操作、规则、行为、变换、关系、函数、算子、过程等等。状态转换规则也称为操作,问题的状态也只能经定义在其上的这种操作而改变。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。2.状态转换规则3.3.状态图表示状态图表示一个问题的状态图是一个三元组 (S,F,G)其中S是问题的初始状态集合,F是问题的状态转换规则集合,G是问题的目标状态集合。一个问题的全体状态及其关系就构成一个空间,称为状态空间。所以,状态图也称为状态空间图。3.状态图表示一个问题的状态图是一个三元组例例 3.73.7 迷宫问题的状态图表示。S：SoF：(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)G：Sg 例3.7迷宫问题的状态图表示。S：SoX1X2X3XX0X4X7X6X5例例 3.83.8八数码难题的状态图表示。用向量 A(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi为变量,Xi的值就是所在方格内的数字。于是,向量A就是该问题的状态表达式。我们将棋局X1X2X3XX0X4X7X6X5例3.8八数码难题的 设初始状态和目标状态分别为 So(0,2,8,3,4,5,6,7,1)Sg(0,1,2,3,4,5,6,7,8)设初始状态和目标状态分别为0组规则:1组规则:0组规则:1组规则:2组规则组规则:8组规则:于是,八数码问题的状态图可表示为(So,r1,r2,r24,Sg)2组规则:8组规则:于是,八数码问题的状态图可表示例例3.93.9 梵塔问题。传说在印度的贝那勒斯的圣庙中,主神梵天做了一个由64个大小不同的金盘组成的“梵塔”,并把它穿在一个宝石杆上。另外,旁边再插上两个宝石杆。然后,他要求僧侣们把穿在第一个宝石杆上的64个金盘全部搬到第三个宝石杆上。搬动金盘的规则是：一次只能搬一个；不允许将较大的盘子放在较小的盘子上。于是,梵天预言：一旦64个盘子都搬到了3号杆上,世界将在一声霹雳中毁灭。盘子的搬动次数：264-118446744073709511615例3.9梵塔问题。传说在印度的贝那勒斯的圣庙中,主神梵二阶梵塔问题设有三根宝石杆,在1号杆上穿有A、B两个金盘,A小于B,A位于B的上面。用二元组(SA,SB)表示问题的状态,SA表示金盘A所在的杆号,SB表示金盘B所在的杆号,这样,全部可能的状态有9种,可表示如下：(1,1),(1,2),(1,3)(2,1),(2,2),(2,3)(3,1),(3,2),(3,3)如图3-10所示。二阶梵塔问题(1,1),(1,2),(1,3)图3-10二阶梵塔的全部状态图3-10二阶梵塔的全部状态这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)及B(i,j)表示：A(i,j)表示把A盘从第i号杆移到第j号杆上;B(i,j)表示把B盘从第i号杆移到第j号杆上。经分析，共有12个操作，它们分别是：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)规则的具体形式应是：IF条件THENA(i,j)IF条件THENB(i,j)这里的状态转换规则就是金盘的搬动规则，分别用A(i,j)这样由题意,问题的初始状态为(1,1),目标状态为(3,3),则二阶梵塔问题可用状态图表示为(1,1),A(1,2),B(3,2),(3,3)由这9种可能的状态和12种操作,二阶梵塔问题的状态空间图如图3-11所示。这样由题意,问题的初始状态为(1,1),目标状态为(3图3-11二阶梵塔状态空间图图3-11二阶梵塔状态空间图 例例3.10 旅行商问题(Traveling-SalesmanProblem,TSP)。设有n个互相可直达的城市,某推销商准备从其中的A城出发,周游各城市一遍,最后又回到A城。要求为该推销商规划一条最短的旅行路线。该问题的状态为以A打头的已访问过的城市序列:ASo:A。Sg:A,A。其中“”为其余n-1个城市的一个序列。例3.10旅行商问题(Traveling-Salesm状态转换规则：状态转换规则：规规则则1 1 如果当前城市的下一个城市还未去过,则去该城市,并把该城市名排在已去过的城市名序列后端。规规则则2 2 如果所有城市都去过一次,则从当前城市返回A城,把A也添在去过的城市名序列后端。状态转换规则：3.2.2 状态图问题求解程序举例例例3.113.11 下面是一个通用的状态图搜索程序。对于求解的具体问题，只需将其状态图的程序表示并入该程序即可。3.2.2状态图问题求解程序举例/*状态图搜索通用程序*/DOMAINS state=%例如:state=symbol DATABASE-mydatabase open(state,integer)%用动态数据库实现OPEN表 closed(integer,state,integer)%和CLOSED表 res(state)open1(state,integer)min(state,integer)mark(s