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

1、 第1章 人工智能概述 1.1 什么是人工智能 1.2 人工智能的研究意义、目标和策略 1.3 人工智能的学科范畴 1.4 人工智能的研究内容 1.5 人工智能的研究途径与方法 1.6 人工智能的基本技术 1.7 人工智能的应用 1.8 人工智能的分支领域与研究方向 1.9 人工智能的发展概况 1.1 什么是人工智能 人工智能（Artificial Intelligence”，AI）1.1.1 人工智能概念的一般描述 部分学者对人工智能概念的描述：人工智能是那些与人的思维相关的活动，诸如决策、问题求解和学习等的自动化（Bellman,1978）；人工智能是一种计算机能够思维，使机器具有智力的激

2、动人心的新尝试（Haugeland,1985）；人工智能是研究如何让计算机做现阶段只有人才能做得好的事情（Rich Knight,1991）；人工智能是那些使知觉、推理和行为成为可能的计算的研究（Winston,1992）；广义地讲，人工智能是关于人造物的智能行为，而智能行为包括知觉、推理、学习、交流和在复杂环境中的行为（Nilsson，1998）。Stuart Russell和Peter Norvig则把已有的一些人工智能定义分为4类：像人一样思考的系统、像人一样行动的系统、理性地思考的系统、理性地行动的系统（2003）。1.1.2 图灵测试和中文屋子 图灵测试”（Turing Test）约

3、翰.西尔勒(John Searle)的“中文屋子中文屋子”1.1.3 脑智能和群智能 脑（主要指人脑）的宏观心理层次的智能表现称为脑智能脑智能（Brain Intelligence,BI）。由群体行为所表现出的智能称为群智能群智能（Swarm Intelligence,SI）。脑智能和群智能是属于不同层次的智能：脑智能是一种个体智能个体智能（Individual Intelligence,II）；群智能是一种社会智能社会智能（Social Intelligence,SI），或者说系统智能系统智能（System Intelligence,SI）。1.1.4 符号智能和计算智能 1.符号智能符号智

4、能 符号智能就是符号人工智能，它是模拟脑智能的人工智能，也就是所说的传统人工智能或经典人工智能。符号智能以符号形式的知识和信息为基础，主要通过逻辑推理，运用知识进行问题求解。符号智能的主要内容包括知识获取（knowledge acquisition）、知识表示（knowledge representation）、知识组织与管理和知识运用等技术（这些构成了所谓的知识工程（Knowledge Engineering,KE）以及基于知识的智能系统等。2.计算智能计算智能 计算智能就是计算人工智能，它是模拟群智能的人工智能。计算智能以数值数据为基础，主要通过数值计算，运用算法进行问题求解。计算智能的主

5、要内容包括：神经计算（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）以及人工生命（Artif

6、icial Life，AL）等。1.2 人工智能的研究意义、目标和策略1.2.1 为什么要研究人工智能 使当前的电脑更好用，更有用，以扩大和延伸人类智能；信息化社会的迫切要求；自动化发展的必然趋势；有益于探索人类自身智能的奥秘。1.2.2 人工智能的研究目标和策略 研究目标就是制造智能机器和智能系统，实现智能化社会。具体来讲，就是要使计算机不仅具有脑智能和群智能，还要具有看、听、说、写等感知和交流能力。研究策略则是先部分地或某种程度地实现机器的智能，并运用智能技术解决各种实际问题特别是工程问题，从而使现有的计算机更灵活、更好用和更有用，成为人类的智能化信息处理工具，而逐步扩展和不断延伸人的智能

7、，逐步实现智能化。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 应用与工程

8、 1.5 人工智能的研究途径与方法1.5.1 心理模拟，符号推演1.5.2 生理模拟，神经计算1.5.3 行为模拟，控制进化1.5.4 群体模拟，仿生计算1.5.5 博采广鉴，自然计算1.5.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.11 智能CAD1.7.12 智能制造1.7.13 智能CAI1.7.14 智能人机接

9、口1.7.15 模式识别1.7.16 数据挖掘与数据库中的知识发现1.7.17 计算机辅助创新1.7.18 计算机文艺创作1.7.19 机器博弈1.7.20 智能机器人 1.8 人工智能的分支领域与研究方向 从模拟的层次和所用的方法来看，人工智能可分为符号智能和计算智能两大主要分支领域。而这两大领域各自又有一些子领域和研究方向。如符号智能中又有图搜索、自动推理、不确定性推理、知识工程、符号学习等。计算智能中又有神经计算、进化计算、免疫计算、蚁群计算、粒群计算、自然计算等。另外，智能Agent也是人工智能的一个新兴的重要领域。智能Agent或者说Agent智能则是以符号智能和计算智能为基础的更高

10、一级的人工智能。从模拟的脑智能或脑功能来看，AI中有机器学习、机器感知、机器联想、机器推理、机器行为等分支领域。而机器学习又可分为符号学习、连接学习、统计学习等许多研究领域和方向。机器感知又可分为计算机视觉、计算机听觉、模式识别、图像识别与理解、语音识别、自然语言处理等领域和方向。从应用角度看，如1.7节所述，AI中有难题求解等数十种分支领域和研究方向。从系统角度看，有智能计算机系统和智能应用系统两大类。智能计算机系统又可分为：智能硬件平台、智能操作系统、智能网络系统等。智能应用系统又可分为：基于知识的智能系统、基于算法的智能系统和兼有知识和算法的智能系统等。另外，还有分布式人工智能系统。从基

11、础理论看，AI中有数理逻辑和多种非标准逻辑、图论、人工神经网络、模糊集、粗糙集、概率统计（贝叶斯统计决策理论）和贝叶斯网络、统计学习理论与支持向量机、形式语言与自动机等领域和方向。1.9 人工智能学科的发展概况1.9.1 人工智能学科的产生1.9.2 符号主义途径发展概况1.9.3 连接主义途径发展概况1.9.4 计算智能异军突起1.9.5 智能Agent方兴未艾1.9.6 现状与发展趋势 多种途径齐头并进，多种方法协作互补。新思想、新技术不断涌现，新领域、新方向 不断开拓。理论研究更加深入，应用研究愈加广泛。研究队伍日益壮大，社会影响越来越大。虽然在通向人工智能最终目标的道路上，还有不少困难

12、、问题和挑战，但前进和发展毕竟是大势所趋。智能交通 图像识别系统 云松 銮仙玉骨寒，松虬雪友繁。大千收眼底，斯调不同凡。（无题）白沙平舟夜涛声，春日晓露路相逢。朱楼寒雨离歌泪，不堪肠断雨乘风。Betrayal Dave Striver loved the university.He loved its ivy-covered clocktowers,its ancient and sturdy brick,and its sun-splashed verdant greens and eager youth.He also loved the fact that the university

13、is free of the stark unforgiving trials of the business world-only this isnt a fact:Academia has its own tests,and some are as merciless as any in the marketplace.A prime example is the dissertation defense:To earn the PhD,to become a doctor,one must pass an oral examination on ones dissertation.Thi

14、s was a test Professor Edward Hart enjoyed giving.Dave wanted desperately to be a doctor.But he needed the signatures of three people on the first page of his dissertation,the priceless inscriptions that,together,would certify that he had passed his defense.One of the signatures had to come from Pro

15、fessor Hart,and Hart had often said-to others and to himself-that he was honored to help Dave secure his well-earned dream.Well before the defense,Striver gave Hart a penultimate copy of his thesis.Hart read it and told Dave that it was absolutely first rate,and that he would gladly sign it at the d

16、efense.They even shook hands in Harts book-lined office.Dave noticed that Harts eyes were bright and trustful,and his bearing paternal.At the defense,Dave thought that he eloquently summarized chapter 3 of his dissertation.There were two questions,one from Professor Rodman and one from Dr.Teer;Dave

17、answered both,apparently to everyones satisfaction.There were no further objections.Professor Rodman signed.He slid the tome to Teer;she too signed,and then slid it in front of Hart.Hart didnt move.Ed?Rodman said.Hart still sat motionless.Dave felt slightly dizzy.Edward,are you going to sign?Later,H

18、art sat alone in his office in his big leather chair,saddened by Daves failure.He tried to think of ways he could help Dave achieve his dream.背叛 戴夫斯特赖维尔喜爱这所大学。他喜爱校园里爬满常青藤的钟楼，那古色古香而又坚固的砖块，还有那洒满阳光的碧绿草坪和热情的年轻人。使他感到欣慰的还有这样一件事，即大学里完全没有商场上那些冷酷无情的考验但事实恰恰并非如此：做学问也要通过考试，而且有的考试与市场上的考验一样不留情面。最好的例子就是论文答辩：为了取得博士

19、学位，为了成为博士，博士生必须通过论文的口试，爱德华哈特教授就喜欢主持这样的答辩考试。戴夫迫切希望成为一名博士。但他需要让个人在他论文的第一页上签上他们的名字，这个千金难买的签名能够证明他通过了答辩。其中一个签名是哈特教授的。哈特常常对戴夫本人和其他人说，对于帮助戴夫实现他应该有的梦想，他感到很荣幸。答辩之前，斯特赖维尔早早给哈特送去了他论文的倒数第二稿。哈特阅读后告诉戴夫，论文水平绝对一流，答辩时他会很高兴地在论文上签名。在哈特那四壁摆满书橱的办公室里，两人甚至还握了手。戴夫注意到，哈特两眼放光，充满信任，神情宛如慈父一般。在答辩时，戴夫觉得自己流利地概括了论文的第三章。评审者提了两个问题，

20、一个是罗德曼教授提的，另一个是蒂尔博士提的。戴夫分别做了回答，并且显然让每个人都心悦诚服，再没有人提出异议。罗德曼教授签了名。他把论文推给蒂尔，她也签上了名字，接着便把本子推到了哈特跟前。哈特没有动。“爱德华？”罗德曼问道。哈特仍然坐在那儿，毫无表情。戴夫感到有点眩晕。“爱德华，你打算签名吗？”过后，哈特一个人呆在办公室里，坐在那张宽大的皮椅里，他为戴夫未能通过答辩感到难过。他试图想出帮助戴夫实现他梦想的办法。第2章 逻辑程序设计语言PROLOG 2.1 基本PROLOG 2.2 Turbo PROLOG程序设计 2.1 基本PROLOG 2.1.1 PROLOG的语句 1.1.事实事实(fa

21、ct)(fact)格式 谓词名(项表).student(john).like(mary,music).abc.repeat.功能 一般表示对象的性质或关系。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.功能 一般表示对象间的因果关系、蕴含关系或对应关系。3.问题(question)格式?-谓词名(项表),谓词名(项表).?-stu

22、dent(john).?-like(mary,X).功能问题表示用户的询问,它就是程序运行的目标。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).?-like

23、s(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)至少有一个是

24、自由变量。考虑下面的各组谓词是否可匹配合一？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的一个重要机制。likes(be

25、ll,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).2.2 Turbo PROLOG程序设计2.2.1 程序结构 /*注 释 */编译指令 constants 常量说明 domai

26、ns 域说明 database 数据库说明 predicates 谓词说明 goal 目标语句 clauses 子句集 例例 如果把上节的例子程序作为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,s

27、ports),likes(X,music).friend(john,X):-likes(X,reading),likes(X,music).领域段该段说明程序谓词中所有参量项所属的领域。Turbo PROLOG的标准领域包括整数、实数、符号、串和符号等,其具体说明如下表所示。谓词段 该段说明程序中用到的谓词的名和参量项的名(但Turbo PROLOG 的内部谓词无须说明)子句段 该段是Turbo PROLOG程序的核心,程序中的所有事实和规则就放在这里,系统在试图满足程序的目标时就对它们进行操作。目标段 该段是放置程序目标的地方。目标段可以只有一个目标谓词,例如上面的例子中就只有一个目标谓词；

28、也可以含有多个目标谓词,如 goal readint(X),Y=X+3,write(Y=,Y).就有三个目标谓词。这种目标称为复合目标。2.2.2 数据与表达式1.1.领域领域 1)标准领域 整数、实数、字符、串和符号 2)结构 结构也称复合对象,一般形式为 函子(参量表)likes(Tom,sports(football,basketball,table_tennis).reading(王宏,book(人工智能技术导论,西安电子科技大学出版社).friend(father(Li),father(Zhao).复合对象在程序中的说明,需分层进行。例如,对于上面的谓词 likes(Tom,spor

29、ts(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(

30、male),addr(xian)表的说明方法是在其组成元素的说明符后加一个星号*。如：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的变量也就有这八种取值。另外,变量名要求必须是以大写字母或下划线开头的字母、数字和下划线

31、序列,或者只有一个下划线。这后一种变量称为无名变量。3.3.算术表达式算术表达式 Turbo PROLOG提供了五种最基本的算术运算：加、减、乘、除和取模,相应运算符号为+、-、*、/、mod。这五种运算的顺序为：*、/、mod优先于+、-。数学中的算术表达式 PROLOG中的算术表达式 x+yz X+Y*Z ab-c/d A*B-C/D u mod v U mod V Y=X+5 X=X+1 4.4.关系表达式关系表达式 Turbo PROLOG提供了六种常用的关系运算,即小于、小于或等于、等于、大于、大于或等于和不等于,其运算符依次为 ,=,数学中的关系式 Turbo PROLOG中的关系

32、式 X+1Y X+1=Y XY XY brother(Name1,Name2):-person(Name1,man,Age1),person(Name2,man,Age2),mother(Z,Name1),mother(Z,Name2),Age1Age2.“=”的用法：比较符和约束符 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

33、实例化为X+Y的结果。2.2.3 输入与输出 (1)readln(X)(2)readint(X)(3)readreal(X)(4)readchar(X)(5)write(X1,X2,Xn)(6)nl 例 用输入输出谓词编写一个简单的成绩 数据库查询程序。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,Sco

34、re),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.循环循环 程序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：student(1,张三,90.2)

35、.student(2,李四,95.5).student(3,王五,96.4).print:-student(Number,Name,Score),write(Number,Name,Score),nl,fail.print:-.2.2.5 动态数据库 动态数据库操作谓词:asserta(fact).assertz(fact).retract(fact).例 asserta(student(20,李明,90.5).retract(student(20,_,_).2.2.6 表处理与递归 1.表头与表尾 表头是表中的第一个元素；表尾是表中除第一个元素外的其余元素按原来顺序组成的表。表头与表尾示例

36、表 表头 表尾 2.表的匹配合一 表的匹配合一示例 表1 表2 合一后的变量值 X=a,Y=X=a,Y=X=a,Y=X=a,Y=a X X=a,Y=例 设计一个能判断对象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 例

37、表的拼接程序,即把两个表连接成一个表。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

38、,Y=2,3,4,5 X=1,2,Y=3,4,5 X=1,2,3,Y=4,5 例 表的输出。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)若“!”位于其他位置,则当

39、其后发生回溯且回溯到“!”处时,就在此处失败,并且“!”还使它所在子句的头谓词(子目标)整个失败(即阻止再去访问头谓词的其余子句(如果有的话),即迫使系统直接回溯到该头谓词(子目标)的前一个子目标(如果有的话)。例 考虑下面的程序：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)g

40、12:-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).Goal:path(a,e).yesyesGoal:path(e,a).nonoGoal：run.ru

41、n:-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=e 例 下面是一个求阶乘程序,程序中使用了递归。domains n,f=integer predicates factorial(n,f)goal readint(I),factorial(I,F),write(I,!=,F).clauses factorial(1,1).factorial(N,Res):-N0,N1=N-1,factorial(N1,FacN1),Res=N*FacN1.第 3 章 图搜索与问题求解 3.1

42、状态图搜索状态图搜索 3.2 状态图搜索问题求解状态图搜索问题求解 3.3 与或图搜索与或图搜索 3.4 与或图搜索问题求解与或图搜索问题求解 3.1 状态图搜索 3.1.1 状态图例例3.1 迷宫问题。图 3-2 迷宫的有向图表示 图 3-3 八数码问题示例 例例 3.2 3.2 八数码问题。3.1.2 状态图搜索1.1.搜索方式搜索方式树式搜索 线式搜索 2.2.搜索策略搜索策略 盲目搜索 启发式(heuristic)搜索 图 3-4 OPEN表与CLOSED表示例 3.3.搜索算法搜索算法树式搜索算法：树式搜索算法：步1 把初始节点So放入OPEN表中。步2 若OPEN表为空,则搜索失败

43、,退出。步3 移出OPEN表中第一个节点N放入CLOSED表中,并冠以顺序编号n。步4 若目标节点Sg=N,则搜索成功,结束。步5 若N不可扩展,则转步2。步6 扩展N,生成一组子节点,对这组子节点做如下处理：(1)删除N的先辈节点(如果有的话)。(2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示)。(3)对已存在于CLOSED表的节点(如果有的话),做与(2)同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展(为了重新计算代价)。(4)

44、对其余子节点配上指向N的返回指针后放入OPEN表中某处,或对OPEN表进行重新排序,转步2。图 3-5 修改返回指针示例 说明：(1)这里的返回指针也就是父节点在CLOSED表中的编号。(2)步6中修改返回指针的原因是,因为这些节点又被第二次生成,所以它们返回初始节点的路径已有两条,但这两条路径的“长度”可能不同。那么,当新路短时自然要走新路。(3)这里对路径的长短是按路径上的节点数来衡量的,后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量,则在需修改返回指针的同时还要修改相应的代价值,或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。线式搜索

45、算法：不回溯的线式搜索不回溯的线式搜索 步1 把初始节点So放入CLOSED表中。步2 令NSo。步3 若N是目标节点,则搜索成功,结束。步4 若N不可扩展,则搜索失败,退出。步5 扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中,令NN1,转步3。可回溯的线式搜索可回溯的线式搜索 步1 把初始节点So放入CLOSED表中。步2令NSo。步3若N是目标节点,则搜索成功,结束。步4 若N不可扩展,则移出CLOSED表的末端节点Ne,若NeSo,则搜索失败,退出。否则,以CLOSED表新的末端节点Ne作为N,即令NNe,转步4。步5扩展N,选取其一个未在CLOSED表用

46、出现过的子节点N1放入CLOSED表中,令NN1,转步3。3.1.3 穷举式搜索1.1.广度优先搜索广度优先搜索图 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.深度优先搜索深度优先搜索 深度优先搜索算法：深度优先搜索算法：步1 把初始节点So放入OPEN表中。

47、步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。步

48、6 扩展N,将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表中前部,置d(Ni)=d(N)+1,转步2。3.1.4 启发式搜索1.1.问题的提出问题的提出 2.2.启发性信息启发性信息按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。(3)用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。3.3.启发函数启发函数启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)。4.4.启发式搜索算法

49、启发式搜索算法1)全局择优搜索2)局部择优搜索 全局择优搜索算法：步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。图 3-8 八数码问题的全局择优搜索 例例 3.53.5 用全局择优搜索法解八数码难题。初始棋局和目标棋局同例3。解解设启发函数h

50、(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图3-8所示。此八数问题的解为：So,S1,S2,S3,Sg。3.1.5 加权状态图搜索1.1.加权状态图与代价树加权状态图与代价树例例3.63.6 图3-9(a)是一个交通图,设A城是出发地,E城是目的地,边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。图 3-9 交通图及其代价树 代价树的搜索。所谓代价,可以是两点之间的距离、交通费用或所需时间等等。通常用g(x)表示从初始节点So到节点x的代价,用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有 g(xj)g(x