新書推薦：
《
更好的行为：给教师的指南（教师成长系列）
》
售價：HK$
78.2
《
闽南佛教寺庙建筑艺术与景观研究
》
售價：HK$
181.7
《
烧掉你的船：将焦虑转化为积极行动的9个策略
》
售價：HK$
68.8
《
虚无主义与崇高的后现代：从浪漫主义到后现代主义一段艰难关系的历史（故事）
》
售價：HK$
90.9
《
图解昆虫学
》
售價：HK$
572.7
《
银幕艳史：都市文化与上海电影（1896-1937）（典藏本）
》
售價：HK$
147.2
《
淮南子的思想世界
》
售價：HK$
78.2
《
汉阙漫漫隐官道 ： 东汉二百年政争与兵事
》
售價：HK$
227.7
|
| 編輯推薦： |
|
人工智能是一门涉及内容广泛、发展迅速的交叉学科，近年来新理论和新方法不断涌现。本教材作为人工智能科学技术基础教育的课程内容，主要介绍人工智能的经典理论和方法，讨论该学科的*技术和发展动向，反映相关领域的应用成果，为相关学科学生提供人工智能的经典理论、方法和新技术。
|
| 內容簡介： |
本书系统介绍人工智能的基本原理、方法和应用技术，全面地反映了国内外人工智能研究领域的进展和热点。全书共11章，主要包括人工智能的基本概念、知识表示技术、搜索策略、逻辑推理技术、不确定性推理方法、专家系统、机器学习、模式识别、Agent和多Agent系统、人工智能程序设计语言以及人工智能在电力系统中的应用。内容由浅入深、循序渐进，条理清晰，各章均有大量的例题和习题，便于读者掌握和巩固所学知识，使其具备应用人工智能技术解决实际问题的能力。
本书可用作高等学校计算机类和电气信息类相关专业高年级本科生和研究生的教材或教学参考书，也可供其他教学、研究、设计和技术开发人员参考。
|
| 關於作者： |
|
鲁斌，博士，副教授，硕士生导师，中国人工智能学会委员，河北省机器学习学会理事，研究方向主要是人工智能及其在电力系统中的应用、分布式能源系统等。
|
| 目錄：
|
目录
第1章绪论1
1.1人工智能的基本概念1
1.1.1智能的概念1
1.1.2现代人工智能的兴起3
1.1.3人工智能的定义3
1.1.4其他相关的概念4
1.1.5图灵测试和中文房间问题5
1.2人工智能的发展历程9
1.2.1孕育期1956年之前9
1.2.2形成期19561969年10
1.2.3发展期1970年之后11
1.3人工智能的研究目标13
1.4人工智能的学术流派14
1.4.1符号主义、连接主义与行为主义14
1.4.2传统人工智能与现场人工智能15
1.4.3弱人工智能与强人工智能16
1.4.4简约与粗陋16
1.5人工智能的研究和应用领域17
1.5.1专家系统18
1.5.2自然语言理解19
1.5.3机器学习20
1.5.4分布式人工智能20
1.5.5人工神经网络21
1.5.6自动定理证明22
1.5.7博弈23
1.5.8机器人学23
1.5.9模式识别24
1.5.10自动程序设计24
1.5.11智能控制25
1.5.12智能决策支持系统25
1.5.13智能电网26
本章小结26
习题27第2章知识表示28
2.1概述28
2.1.1知识概述28
2.1.2知识的性质29
2.1.3知识的分类30
2.1.4知识表示32
2.1.5知识表示观33
2.2一阶谓词逻辑表示法36
2.2.1一阶谓词逻辑表示法的逻辑基础36
2.2.2一阶谓词逻辑表示知识的步骤38
2.2.3一阶谓词逻辑表示法的特点40
2.3产生式表示法41
2.3.1产生式表示的方法42
2.3.2产生式系统的基本结构43
2.3.3产生式系统的推理方式45
2.3.4产生式表示法的特点48
2.4语义网络表示法48
2.4.1语义基元48
2.4.2基本语义关系49
2.4.3关系的表示51
2.4.4情况、动作和事件的表示53
2.4.5谓词连接词的表示53
2.4.6量词的表示54
2.4.7基于语义网络的推理55
2.4.8语义网络表示法的特点57
2.5框架表示法57
2.5.1框架的一般结构58
2.5.2框架系统61
2.5.3基于框架的推理61
2.5.4框架表示法的特点63
2.6脚本表示法63
2.6.1概念依赖理论63
2.6.2脚本表示方法64
2.6.3脚本表示法的特点66
2.7过程表示法66
2.7.1陈述性知识表示与过程性知识表示66
2.7.2过程知识表示方法67
2.7.3过程表示的问题求解过程67
2.7.4过程表示的特点68
2.8Petri网表示法69
2.8.1表示知识的方法69
2.8.2Petri网表示法的特点71
本章小结72
习题72第3章搜索策略74
3.1概述74
3.1.1搜索概述74
3.1.2搜索的主要过程75
3.1.3搜索策略的分类75
3.1.4搜索的方向75
3.1.5主要的搜索策略76
3.2状态空间知识表示方法76
3.2.1状态空间表示法77
3.2.2状态空间图79
3.3状态空间的盲目搜索81
3.3.1回溯策略82
3.3.2一般的图搜索策略88
3.3.3深度优先搜索策略92
3.3.4宽度优先搜索策略95
3.4状态空间的启发式搜索98
3.4.1启发性信息与评价函数99
3.4.2A算法101
3.4.3分支界限法104
3.4.4动态规划法107
3.4.5爬山法108
3.4.6A算法109
3.5与或图搜索117
3.5.1与或图表示法117
3.5.2与或图的搜索策略121
3.5.3与或树的搜索策略125
3.6博弈树搜索131
3.6.1博弈概述131
3.6.2Grundy博弈132
3.6.3极大极小搜索法133
3.6.4-剪枝方法134
本章小结136
习题137第4章逻辑推理140
4.1概述140
4.1.1推理和推理方法140
4.1.2推理控制策略140
4.1.3经典逻辑推理141
4.2命题逻辑142
4.2.1命题公式的解释143
4.2.2等价式143
4.2.3范式144
4.2.4命题逻辑的推理规则145
4.2.5命题逻辑的归结方法147
4.3谓词逻辑151
4.3.1谓词公式的解释151
4.3.2谓词等价公式与范式152
4.3.3谓词逻辑的推理规则155
4.3.4谓词逻辑的归结方法156
4.4非单调逻辑164
4.4.1非单调推理164
4.4.2封闭世界假设、限制和最小模型165
4.4.3默认逻辑167
4.4.4溯因推理168
4.4.5真值维护系统169
4.5多值逻辑和模糊逻辑170
本章小结172
习题172第5章不确定性推理175
5.1概述175
5.1.1不确定性推理概述175
5.1.2不确定性的表现176
5.1.3不确定性推理要解决的基本问题177
5.1.4不确定性推理方法的分类179
5.2确定性理论179
5.2.1可信度的基本概念180
5.2.2表示问题180
5.2.3计算问题183
5.2.4带有阈值限度的不确定性推理185
5.2.5带有权重的不确定性推理187
5.2.6确定性理论的特点188
5.3主观Bayes方法188
5.3.1证据不确定性的表示188
5.3.2知识不确定性的表示189
5.3.3组合证据的不确定性191
5.3.4结论不确定性的更新192
5.3.5结论不确定性的合成193
5.3.6主观Bayes方法的特点195
5.4证据理论195
5.4.1D\|S理论195
5.4.2一个特殊的概率分配函数200
5.4.3表示问题203
5.4.4计算问题203
5.4.5证据理论的特点206
5.5贝叶斯网络206
5.5.1贝叶斯网络概述207
5.5.2基于贝叶斯网络的不确定性知识表示208
5.5.3基于贝叶斯网络的推理模式209
5.5.4基于贝叶斯网络的不确定性推理的特点211
5.6模糊推理211
5.6.1模糊理论的基本概念212
5.6.2表示问题218
5.6.3计算问题219
5.6.4模糊推理的特点226
本章小结226
习题227第6章专家系统229
6.1概述229
6.1.1专家系统发展历程229
6.1.2专家系统特点230
6.1.3专家系统的类型231
6.1.4新型专家系统233
6.2专家系统结构234
6.3专家系统设计237
6.3.1专家系统的设计步骤237
6.3.2知识获取239
6.3.3知识库设计和知识管理241
6.3.4推理机设计243
6.3.5解释功能设计244
6.3.6系统结构设计245
6.3.7专家系统的评价245
6.4专家系统应用案例246
6.4.1动物识别专家系统246
6.4.2PROSPECTOR系统249
6.5开发工具与环境251
6.5.1程序设计语言252
6.5.2骨架系统252
6.5.3知识表示语言253
6.5.4辅助型工具254
6.5.5专家系统开发环境254
本章小结255
习题255第7章机器学习256
7.1概述256
7.1.1机器学习的定义256
7.1.2机器学习的发展257
7.1.3机器学习分类259
7.1.4归纳学习260
7.2决策树学习261
7.2.1决策树261
7.2.2决策树构造算法263
7.2.3决策树的归纳偏置264
7.3变型空间学习266
7.3.1泛化和特化266
7.3.2候选删除算法268
7.4基于解释的学习271
7.4.1基本概念271
7.4.2基于解释的学习方法272
7.5人工神经网络274
7.5.1基本概念275
7.5.2感知器280
7.5.3多层神经网络282
7.5.4Hopfield神经网络287
7.5.5双向相关记忆290
7.5.6自组织神经网络293
7.6进化计算298
7.6.1模拟自然进化298
7.6.2遗传算法299
7.6.3进化策略304
7.6.4遗传编程305
本章小结307
习题308第8章模式识别310
8.1概述310
8.1.1模式识别的发展与应用310
8.1.2模式识别系统311
8.1.3模式识别方法314
8.1.4模式识别实例317
8.2线性分类器319
8.2.1感知器准则320
8.2.2最小均方误差320
8.2.3Fisher准则321
8.2.4支持向量机323
8.3贝叶斯决策理论327
8.3.1最小错误贝叶斯决策规则327
8.3.2最小风险贝叶斯决策规则328
8.3.3正态分布的贝叶斯分类329
8.3.4密度估计的参数法330
8.3.5密度估计的非参数法331
8.4聚类分析333
8.4.1动态聚类法333
8.4.2层次聚类法334
本章小结335
习题336第9章Agent和多Agent系统337
9.1概述337
9.2Agent理论 339
9.2.1Agent的基本概念339
9.2.2Agent的特性340
9.2.3Agent的内部结构341
9.2.4Agent类型344
9.2.5Agent的实现工具345
9.3多Agent系统346
9.3.1多Agent的结构模型346
9.3.2通信方式348
9.3.3通信语言349
9.3.4协调与协作350
9.4MAS的应用案例354
9.5Agent技术应用355
本章小结357
习题357第10章人工智能程序设计语言358
10.1概述358
10.1.1LISP语言简介358
10.1.2PROLOG语言简介359
10.2表处理语言LISP359
10.2.1LISP的基本元素360
10.2.2LISP的运行机制360
10.2.3LISP的基本函数361
10.2.4LISP的表处理364
10.2.5LISP的应用实例369
10.3逻辑程序设计语言PROLOG373
10.3.1Horn子句373
10.3.2PROLOG程序的语句374
10.3.3PROLOG的推理机制374
10.3.4PROLOG的表结构376
10.3.5PROLOG的应用实例378
本章小结382
习题383第11章人工智能在电力系统中的应用384
11.1概述384
11.2人工智能在电力系统故障诊断中的应用385
11.2.1电网故障诊断原理386
11.2.2贝叶斯网络建模388
11.2.3贝叶斯网络故障诊断推理388
11.2.4改进的贝叶斯网络故障诊断模型389
11.2.5其他智能故障诊断技术的应用390
11.3人工智能在电力巡检中的应用391
11.3.1电力设备巡检391
11.3.2巡检机器人392
11.3.3系统实时监控后台393
11.3.4路径规划管理395
11.3.5设备状态识别396
11.3.6Agent技术397
11.4人工智能在电力大数据分析中的应用400
11.4.1大数据基本概念400
11.4.2电力大数据的来源401
11.4.3大数据分析与人工智能402
11.4.4电力大数据分析典型应用场景403
本章小结406参考文献407
|
| 內容試閱：
|
第3章搜 索 策 略在进行问题的智能求解时，一般会涉及两个部分。第一部分是问题的表示，也就是把待求解的问题表示出来。如果一个问题找不到一种合适的表示方法，对它的求解也就无从谈起。在第2章中已经讨论过各种知识表示技术，可以基于这些技术表示待求解的问题。第二部分是问题的具体求解，即针对问题，分析其特征，选择一种相对合适的方法进行求解。目前问题求解的基本方法有搜索法、归约法、归结法、推理法、约束满足法、规划和产生式、模拟退火法、遗传算法等。本章主要讨论问题的搜索求解策略，即采用搜索法求解问题时怎样表示问题、怎样基于具体的搜索策略解决问题。3.1概述搜索是人工智能的经典问题之一，它与推理密切相关，搜索策略的优劣直接影响智能系统的性能。以下给出搜索的概念，并对搜索的基本过程、控制策略以及搜索策略的分类等做一个简单的介绍。3.1.1搜索概述人工智能所要解决的问题大多数是结构不良或非结构化的问题。对于这样的问题，一般很难获得其全部信息，也没有成熟的求解算法可供利用，问题求解只能依靠经验，利用已有的知识一步步地摸索着前进。例如，对于医疗诊断的智能系统，基于已知的初始症状，需要在规则库中寻找可以使用的医疗知识，逐步诊断出患者的疾病，这就存在按照何种线路进行诊断的问题。另外，从初始的症状到最后疾病的判断可能存在多条诊断路线，这就存在按照哪条路线进行诊断可以获得较高求解效率的问题。像这种根据问题的实际情况，不断寻找可以利用的知识，从而构造出一条代价较少的推理路线，使得问题得到圆满解决的过程称为搜索。人工智能进行问题求解时，即使对于结构性能较好，理论上也有算法可依的问题，如果问题本身或算法的复杂性较高如按照指数级增长，同时受计算机在时间和空间上的限制，会产生人们常说的组合爆炸问题。例如，64阶汉诺塔问题有364种状态，仅从空间上看，这是任何计算机都无法存储的问题。再如，在实现一个能进行人机对弈的智能系统时，计算机为了取得胜利，需要考虑所有的可能性，然后选择最佳的走步方式，设计这样的算法并不困难，但却需要计算机惊人的时间和空间代价。对于这种虽然理论上有算法但却无法付诸实现的问题，有时也需要通过搜索策略来解决。搜索中需要解决的基本问题有以下几个。1 搜索过程是否一定能找到一个解？2 搜索过程是否能终止运行？或是否会陷入一个死循环？3 当搜索过程找到一个解时，找到的是否是最佳解？4 搜索过程的时间和空间复杂性如何？我们曾经遇到过的走迷宫问题、旅行商问题、八数码问题等，都是很经典的搜索问题，后文会基于这些典型问题的求解，探讨不同的搜索策略及其特征。3.1.2搜索的主要过程不同的搜索策略，搜索的具体步骤并不一样，但它们都具有以下主要过程。1 从初始状态或目标状态出发，并把它们作为当前状态。2 扫描操作算子集操作算子用于实现状态的转换，将适用于当前状态的一些操作算子作用于当前状态得到新的状态，并建立指向其父结点的指针。3 检查所生成的新状态是否满足结束状态？如果满足，则得到问题的一个解，并可以沿着有关指针从结束状态逆向到达开始状态，给出这一解的路径；否则，将新状态作为当前状态，返回第2步再进行搜索。3.1.3搜索策略的分类可以根据搜索过程中是否使用了启发性的信息将搜索分为盲目搜索和启发式搜索两种类型。盲目搜索，也称无信息引导的搜索，是指没有利用和问题相关的知识，按照预定的控制策略进行搜索，在搜索过程中获得的中间信息也不用来改进控制策略。由于搜索总是按照预先设定的路线进行，没有考虑待求解问题本身的特性，因此这种搜索具有盲目性，效率不高，不擅长解决复杂问题。但盲目搜索具有通用性，当一时难以找到待求解问题的有效知识时，是一种不得不采用的方法。启发式搜索，也称有信息引导的搜索，它与盲目搜索正好相反，在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速了问题求解的过程，以尽快找到最佳解。启发式搜索由于利用了问题的有关知识，一般来说，问题的搜索范围会有所缩小，搜索效率会有所提高。但如何找到对问题求解有帮助的知识，以及如何利用这些知识，是启发式搜索的关键和难点。根据问题的表示方式，也可以将搜索分为状态空间搜索和与或图搜索。由于涉及的细节较多，这里不做过多阐述，状态空间搜索策略将在3.2节～3.4节详细讨论，与或图搜索策略则放在3.5节、3.6节说明。3.1.4搜索的方向搜索可以沿着两个方向进行，即正向搜索和逆向搜索。1. 正向搜索正向搜索指从初始状态出发的搜索，也称为数据驱动的搜索。它从问题给出的条件和一个用于状态转换的操作算子集出发，不断应用操作算子从给定的条件中产生新的条件，再用操作算子从新条件中产生更多的新条件，直到有满足目标要求的解产生为止。2. 逆向搜索逆向搜索指从目标状态出发的搜索，也称为目标驱动的搜索。它从想要达到的目标入手，看哪些操作算子能产生该目标，以及应用这些操作算子产生该目标时需要哪些条件，这些条件就成为想要达到的新目标，即子目标。通过反向搜索不断寻找子目标，直到找到问题给定的条件为止，这样就找到了从初始状态到目标状态的解，尽管搜索方向和解正好相反。究竟采用正向搜索还是逆向搜索，一般应该考虑以下3个因素。1 初始状态和目标状态中，哪个状态多？一般从小的状态集合出发朝大的状态集合搜索，这样问题求解更容易一些。2 正向搜索和逆向搜索哪个分支因素低？一般朝着分支因素低的方向进行搜索。分支因素是指从一个结点出发可以直接到达的平均结点数。3 选择搜索方向时还可以考虑操作算子的数目和复杂性、状态空间的形状和人们的思考方法等。当然，也可以将正向搜索和逆向搜索结合起来构成双向搜索，即两个方向同时进行，直到在中间的某处汇合为止。3.1.5主要的搜索策略到目前为止，人工智能领域已经出现了很多具体的搜索方法，概括起来有以下几种。1. 求任一解的搜索策略1 回溯法BackTracking。2 爬山法Hill Climbing。3 宽度优先法Breadthfirst。4 深度优先法Depthfirst。5 限定范围搜索法Beam Search。6 最佳优先法Bestfirst。2. 求最佳解的搜索策略1 大英博物馆法British Museum。2 分支界限法Branch and Bound。3 动态规划法Dynamic Programming。4 最佳图搜索法A。3. 求与或关系解图的搜索法1 一般与或图搜索法AO。2 极小极大法Minimax。3 \|剪枝法Alpha\|beta Pruning。4 启发式剪枝法Heuristic Pruning。本章将对其中几个基本的搜索策略做进一步讨论。3.2状态空间知识表示方法人工智能虽然有很多研究领域，而且每个研究领域又有自己的特点和规律，但从它们解决实际问题的过程来看，都可以归纳抽象成一个问题求解的过程。采用搜索法进行问题求解时，首先必须采用某种知识表示技术将待求解的问题表示出来，其表示方法是否恰当将直接影响问题求解的效率。本节介绍的状态空间表示法和后文将要介绍的与或图表示法是两种基本的知识表示方法，可以用来表示问题及其求解过程。考虑到它们和搜索问题的密切关系，以及搜索问题在人工智能研究中的核心地位，将这两种知识表示技术放在本章详细讨论，而没有将它们同谓词逻辑、产生式、语义网络等知识表示技术一起放在第2章 知识表示中单独说明。3.2.1状态空间表示法状态空间表示法是用状态和操作来表示和求解问题的一种方法。其中，状态用来描述问题求解过程中的各种情况，操作用来实现状态之间的转换。1. 状态状态State是描述问题求解过程中每一步问题状况的数据结构，一般采用以下形式表示，即Sk=Sk0,Sk1,其中，当对每一个分量Ski赋予一个确定的值时，就得到了一个具体的状态。在实际问题求解时，可以采用任何恰当类型的数据结构来描述状态，如符号、字符串、向量、多维数组、树和表格等，使之有利于问题的解决。2. 操作操作Operator，也称为算符，是将问题从一个状态转换为另一个状态的手段。当对一个状态使用某个可用的操作时，会引起该状态中某些分量的值的变化，导致问题从这个状态转换为另一个状态。简单地说，操作可以看成是状态集合上的一个函数，它描述了状态之间的关系。操作可以是一个运算、一条规则、一个过程或一个机械步骤。例如，在产生式系统中，操作实际就是一条条的产生式规则。3. 状态空间状态空间State Space是由问题的全部状态和全部可用操作构成的集合，它描述了问题的所有状态和它们之间的相互关系，一般用一个四元组表示，即S,O,S0,G其中，S是状态集合，S中的每一个元素表示一个状态； O是操作的集合，O 中的每一个元素表示一个操作； S0 是问题的初始状态集合，是 S 的非空子集，S0S ； G 是问题的目标状态集合，是 S 的非空子集，GS，G 可以是若干具体的状态，也可是满足某些性质的路径信息描述。从S0结点到G结点的路径被称为求解路径。图31八数码问题的一个状态状态空间的一个解是一个有限操作算子序列，它使初始状态转化为目标状态，即S0O1S1O2S2O3OkG其中，Oi为操作算子，O1,O2,O3,,Ok是状态空间的一个解。解也可以用对应的状态序列来表示。当然，解往往不是唯一的。例31八数码问题的状态空间表示。八数码问题重排九宫问题是在图31所示的33的方格棋盘上，放置8张标记为1～8的将牌，还有一个空格，空格四周上下左右的将牌可以移动到空格中。需要找到一种将牌移动的方式，使8张将牌的排列由某种情况转换为另一种情况。用状态空间表示法表示八数码问题。【解】现对八数码问题的状态空间表示中状态、操作和状态空间的形式进行说明。1 8张将牌的任何一种排列方式都是一种状态，所有的排列方式构成了状态集合S，其大小为9!个。2 操作是进行状态变换的手段，可以从两个角度进行设计。从将牌的角度看，操作可以是对将牌的移动，每张将牌可以有上、下、左、右4个移动方向，一共有8张将牌，因此操作算子共有48=32个；从空格的角度看，操作也可以看成是对空格的移动，空格可以有上、下、左、右4个移动方向，而且只有1个空格，因此操作算子共有41=4个，即空格上移Up、空格下移Down、空格左移Left和空格右移Right。显然后一种操作的设计方式更为简单。值得注意的是，并不是任何状态都可以使用这4个操作，对某个状态实施操作时还要确保空格不会被移出方格棋盘之外。例如，当空格在左下角时，只有两个操作可以使用，它们是空格上移Up和空格右移Right。同理，如果从将牌移动的角度设计操作，也并不是任何状态都可以使用32个操作，毕竟只有和空格相邻的将牌才能移动。3 状态空间描述了问题所有的状态和它们之间的关系，在四元组S,O,S0,G中，状态集合与操作集合都已在上面说明，问题的初始状态集合S0和目标状态集合G可以是需要的任何布局，如图32就是其中的一种。在搜索问题中，其实就是要寻找到一个将牌移动的序列操作序列，使得问题由初始状态变换为目标状态。图32八数码问题的初始状态和目标状态例32二阶汉诺塔问题的状态空间表示。假设有编号为1号、2号和3号的3个钢针，初始情况下，1号钢针上穿有A和B两个金片，A比B小，A位于B的上面。要求通过金片的移动将A和B移动到另外一根钢针上，规定每次只能移动一个金片，而且任何时刻都不能使大的金片位于小的金片上方。问题的初始状态和目标状态如图33所示。图33二阶汉诺塔问题的初始状态和目标状态【解】现对汉诺塔问题用状态空间表示法表示时，状态、操作和状态空间的形式进行说明。1 两个金片任意一种合法的放置方式都是一种状态，假设状态用二元组Sk=Sk0,Sk1表示，其中Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。如S0=1,1表示A片在1号钢针上，B片也在1号钢针上，且A片在B片上面。2 问题全部可能的状态一共有9种，即S0=1,1S1=1,2S2=1,3S3=2,1S4=2,2S5=2,3S6=3,1S7=3,2S8=3,3如图34所示。它们构成了状态集合 S，其大小为9个。图34二阶汉诺塔问题的所有状态3 初始状态集合为{S0}，目标状态集合为{S4,S8}。4 操作是进行状态变换的手段，分别用Ai,j和Bi,j表示，其中Ai,j表示把A片从第i号钢针移动到第j号钢针上，Bi,j表示把B片从第i号钢针移动到第j号钢针上。操作共有12种，它们分别是：A1,2A1,3A2,1A2,3A3,1A3,2B1,2B1,3B2,1B2,3B3,1B3,2在进行问题求解时，应当注意保证状态的合法性，即保证操作算子使用后不会使大的金片位于小的金片上方。5 状态空间描述了问题所有的状态和它们之间的关系，状态集合、操作集合、初始状态集，目标状态集在上面都已说明。在搜索问题中，其实就是要寻找到一个移动金片的操作序列，使得问题由初始状态变换为目标状态。3.2.2状态空间图状态空间可以用有向图来描述，因为图是最直观的。图中的结点表示问题的状态，图中的有向弧表示状态之间的关系，也就是操作。进行问题求解时，初始状态对应实际问题的已知信息，是图的根结点。问题求解就是寻找从初始状态转换为目标状态的某个操作算子序列，也就是寻找从初始状态到目标状态的一条路径。因此，问题的解又可以很形象地称为解路径。和操作算子序列对应的，问题的解也可以是一个合法状态的序列，其中序列的第一个状态是问题的初始状态，最后一个状态是问题的结束状态。介于初始状态和结束状态之间的则是中间状态。除了第一个状态外，该序列中任何一个状态，都可以通过一个操作，由与它相邻的前一个状态转换得到。在图35所示的状态空间图中，初始状态集合为{S0}，目标状态集合为{S12}，有向弧上的标识说明了相应的操作算子。通过利用操作算子对状态进行转换，可以找到从初始状态到目标状态的一个解，即O2、O6、O12，或者用状态的序列表示为S0、S2、S6、S12。图35状态空间的有向图示例在某些问题中，各操作算子的执行代价不同，这时只需要在图中给各弧线标注代价即可。一般来说，实际待求解问题的规模是比较大的，即问题所有可能出现的状态数是比较多的。当问题有解时，如何缩小搜索范围，快速有效地找到问题的解，甚至是问题的最佳解，正是搜索问题所要研究和探讨的。不难想象，对同一个问题来说，采用不同的搜索策略，找到解的搜索空间是有区别的。一般来说，对大空间问题，搜索策略就是要解决组合爆炸的问题。例33旅行商问题Traveling Salesman Problem，TSP的状态空间图。假设一个推销员从图36所示的A城市出发，到其他所有城市去推销产品，最终再回到出发地A城市，需要找到一条路径，能使推销员访问每个城市后回到出发地经过的路径最短或费用较少。各个城市之间的距离或费用标注在弧线上。图36旅行商问题图37描述了旅行商问题的部分状态空间图。最下方的表格里列出了各条路径及其耗散代价。图37旅行商问题的部分状态空间图在前面的例子中，都可以画出问题的全部状态空间图，即使对于例33的五城市旅行商问题而言，虽然只画出了状态空间图的一部分，但将其补充完整是可能的。但是，如果是80个城市的旅行商问题，要在有限时间画出问题的全部状态空间图难度却很大，因此，这类显示的描述对于复杂问题来说是不切实际的，而对于包含无限结点的问题更是不可能的，此时，一个问题的状态空间是客观存在的，只不过是用n元组之类的隐式描述而已。3.3状态空间的盲目搜索盲目搜索的过程中由于没有利用与问题有关的启发性知识，其搜索效率可能不如启发式搜索，但由于启发式搜索需要启发性信息，而启发性信息的获取和利用一般比较困难，因此在难以获取启发性信息的情况下，盲目搜索不失为一种比较好的选择。本节主要讨论状态空间的盲目搜索策略。3.3.1回溯策略前面已经分析过，寻找从初始状态到目标状态的解路径实际就是在状态空间中寻找从初始状态到目标状态的一个操作序列，如果在寻找这个操作序列时，系统能给出一个绝对可靠或绝对正确的选择策略，那就不需要搜索了，求解会一次性成功穿过状态空间到达目标状态，得到解路径。但对于实际问题来说，不可能存在这样一个绝对可靠的预测，求解必须通过不断地尝试，直到找到目标状态为止。回溯策略就是一种系统地尝试状态空间中不同路径的搜索技术。以下将给出回溯策略的算法描述和基于此策略的搜索实例。1. 一个基本的回溯策略回溯策略是一种用于状态空间搜索的盲目搜索策略。其主要思想简单来说是： 首先将问题所有的规则即操作、操作算子给出一个固定的排序，在搜索时对当前状态刚开始搜索时，当前状态就是初始状态依次检测规则集中的每一条规则，在当前状态未使用过的规则集中找到第一条可以触发的规则，应用于当前状态，得到一个新的状态，新状态重新设置为当前状态，并重复以上搜索。如果对当前状态而言，没有规则可用，或者所有的规则都已经被试探过但仍然没有找到问题的解，则将当前状态的前一个状态即当前状态的父状态设置为当前状态，重复以上搜索。如此进行下去，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。基于回溯策略进行搜索的过程明显呈现出递归的性质，其主要过程如下面的StepTrack。其返回值有两种情况： 如果从当前状态Data到目标状态有路径存在，则返回以规则序列操作序列表示的从Data到目标状态的解路径；如果从当前状态Data到目标状态没有路径存在，则返回Fail。递归过程StepTrackData如下。1 If GoalData Then Return Nil;GoalData返回值为真,表示Data是目标状态,即找到目标,过程返回空表Nil2 If DeadendData Then Return Fail;DeadendData返回值为真,表示Data是非法状态,过程返回Fail,即需要回溯3 Rules ：=ApprulesData;如果DeadendData返回值为假,执行Apprules函数,计算Data所有可应用的规则,再按照某种原则排列后赋给Rules4 Loop： If NullRules Then Return Fail;NullRules返回值为真,表示规则用完未找到目标或根本没有可应用的规则,过程返回Fail,即需要回溯5 R ：=FirstRules;取头条可应用的规则6 Rules ：=TailRules;删去头条规则,更新未被使用的规则集7 Newdata ：=GenR,Data;调用规则R作用于当前状态,生成新状态8 Path ：=StepTrackNewdata;对新状态递归调用本过程9 If Path=Fail Then Go Loop Else Return ConsR,Path;当Path=Fail时,表示递归调用失败,没有找到从Newdata到目标的解路径,转移到Loop处调用下一条规则进行测试;否则过程返回解路径递归过程StepTrackData将递归和循环结合在一起，实现了解路径的纵向和横向搜索。如图38所示，如果当前状态A不是目标状态，则对它第一个子状态B调用回溯过程StepTrackB，在StepTrackB中，又首先对B的第一个子状态E调用回溯过程StepTrackE，，这是一种纵向的搜索，依靠递归来实现。如果在以B为根的子图中没有找到目标状态，就对B的兄弟状态C调用回溯过程StepTrackC，如果在以C为根的子图中没有找到目标状态，就对B和C的兄弟状态D调用回溯过程StepTrackD，，这是一种横向的搜索，依靠循环来实现。图38给出了一个状态空间中搜索A到D的解路径的回溯搜索过程，图中虚线箭头指出了搜索的轨迹，结点旁边的数字说明了该结点被搜索到的次序。图38回溯搜索示意图算法StepTrackData有以下几点需要注意。1 当某一个状态t满足结束条件时，算法在第1步结束并返回Nil，此时StepTrackt的返回值为Nil，即t到目标状态的解路径是一张空的规则表。2 算法返回Fail发生在第2和第4步，第2步由于不合法状态返回Fail，第4步由于所有规则都试探失败返回Fail。一旦返回Fail，意味着过程会回溯到上一层继续运行，而在最高层返回Fail则整个过程失败退出。3 如果找到解路径，算法在第9步通过Cons函数构造出解路径。例34N皇后问题的回溯实现。在一个NN的国际象棋棋盘上，依次摆放N个皇后棋子，摆好后要求满足每行、每列和每个对角线上只允许出现一个皇后，即皇后之间不许相互俘获。图39给出4皇后问题的几种摆放方式，其中a和b满足摆放要求，皇后在行、列和对角线上均没有冲突，而c、d、e和f为非法状态，c中有列的冲突，d中有行的冲突，e中是44棋盘的主对角线冲突，f则是一个较短对角线33的棋盘上的冲突。图39皇后问题的合法状态和非法状态对于4皇后问题，求解前首先给所有规则排序，这里的规则就是操作算子，是摆放皇后的方法。假设皇后摆放的次序为棋盘上从左到右，从上到下，依次为r11、r12、r13、r14、r21、r22、r23、r24、r31、r32、、r44，其中rij表示将一个皇后放置在第i行第j列。问题的状态用一个表来表示，如图39中的a图为12 24 31 43，每个分量表示一个皇后所在的行列编号，由于4皇后问题中最多有4个皇后，所以表中最多有4个分量。根据StepTrack的基本流程，可以得到图310所示的搜索图。其中，为简单起见，每个状态只写出其增量部分。由图中向上的箭头可知，为了解决问题，共进行了22次回溯。图3104皇后问题的回溯搜索2. 一个改进的回溯策略在递归过程StepTrackData中，第2步和第4步设置了两个回溯点，一个是非法状态回溯，一个是试探了一个状态的所有子状态后，仍然找不到解时回溯。然而，对于某些问题还可能会遇到其他一些情况，StepTrackData无法解决。例如，如果问题的状态空间图中有某个分支可以向纵深无限深入进去，即这个分支是一个无限深渊，StepTrackData可能会落入这个深渊中永远回溯不回来，这样，即使问题在旁边的分支上有解，算法一旦落入这个无限深渊中就不能找到这个解。又如，问题的状态空间图的某一个分支上具有环路，搜索一旦进入这个环路就会陷入无限循环，在这个环路中一直搜索，同样也回溯不回来，这样，即使问题在旁边的分支上有解，也不可能找到这个解。为了解决这两个问题，可以对StepTrackData做一些改进，通过增加回溯点的方法解决无限深渊与环路的问题。下面给出的算法StepTrack1，它将StepTrack增加了两个回溯点： 一个是超过深度限制Bound的回溯点，一旦发现当前结点的深度超过深度限制，强制回溯；另一个是出现环路的回溯点，算法记录了从初始结点到当前结点的搜索路径，一旦发现当前结点已经在搜索路径上出现过，就说明有环路存在，强制回溯。StepTrack1的返回值和StepTrack一样，有两种情况： 如果从当前状态Data到目标状态有路径存在，则返回以规则序列表示的从Data到目标状态的解路径；如果从当前状态Data到目标状态没有路径存在，则返回Fail。而且，为了处理环路的问题，StepTrack1的形参由原先StepTrack的当前状态Data换为从初始状态到当前状态的逆序表Datalist，即初始状态排在表的最后，而当前状态排在表的最前面。递归过程StepTrack1Datalist如下。1 Data：=FirstDatalist;设置Data为当前状态2 If MemberData,TailDatalist Then Return Fail;函数Tail是取尾操作,TailDatalist表示取Datalist中除了第一个元素以外的所有元素。MemberData,TailDatalist取值为真,表示Data在TailDatalist中存在,即有环路出现,过程返回Fail,需要回溯3 If GoalData Then Return Nil;GoalData返回值为真,表示Data是目标状态,即找到目标,过程返回空表Nil4 If DeadendData Then Return Fail; Data是非法状态,过程返回Fail,即需要回溯5 If LengthDatalistBound Then Return Fail;函数Length计算Datalist的长度,即搜索的深度,当搜索深度大于给定常数Bound时,返回Fail,即需要回溯6 Rules：=ApprulesData;执行Apprules函数,计算Data所有可应用的规则,再按照某种原则排列后赋给Rules7 Loop： If NullRules Then Return Fail;NullRules返回值为真,表示规则用完未找到目标或根本没有可应用的规则,返回Fail,即需要回溯8 R：=FirstRules;取头条可应用的规则9 Rules：=TailRules;删去头条规则,更新未被使用的规则集10 Newdata：=GenR,Data;调用规则R作用于当前状态,生成新状态11 Newdatalist：=ConsNewdata,Datalist;将新状态加入到表Datalist前面,构成新的状态列表12 Path：=StepTrack1Newdatalist;递归调用本过程13 If Path=Fail Then Go Loop Else Return ConsR,Path;当Path=Fail时,表示递归调用失败,没有找到从Newdata到目标的解路径,转移到Loop处调用下一条规则进行测试;否则过程返回解路径StepTrack1比StepTrack增加了两个回溯点，即第2步的环路回溯和第5步的深度超限回溯。当然，在StepTrack1中也可能存在深度限制不合理的问题，如问题的解的深度为Bound 1，但由于设定的深度界限为Bound不太合理，导致找不到问题的解。此时，可以做可变深度限制的处理，即在遍历过深度Bound之内的结点后仍然没有找到问题的解，适当增加Bound的值接着搜索。3. 避免多次试探同一个结点的回溯策略上面介绍的StepTrack和StepTrack1尽管已经能处理非法状态的回溯、试探过所有子结点的回溯、无限深渊回溯和环路回溯，但还是有可能出现多次试探同一个结点的问题。对于什么是多次试探同一个结点，可以通过几个例子说明。在图38中的StepTrack或StepTrack1的搜索轨迹，如果增加一条从C结点到F结点的路径，如图311所示，即F结点可以由B结点生成，也可以由C结点生成，搜索的情况就会稍稍发生变化。此时由于StepTrack和StepTrack1只保留了从初始结点到当前结点的一条路径，而没有其他的数据结构记录那些试探过的、但不在从初始结点到当前结点的路径上的结点，导致F结点被试探两次，试探其是否能通向目标结点。其中，第一次试探来自B结点，B的第一个子结点E无法通向目标，因此试探E的兄弟F，此时算法记录的结点序列是ABF，发现F也无法通向目标，由于E和F没有其他兄弟结点，回溯至B结点，回溯至A结点。接着试探B的兄弟C是否能通向目标，C有两个孩子结点，第一个是F，此时算法记录的结点序列为ACF，由于没有数据结构记录刚刚F的试探结果，此时会对F进行第二次向纵深进行的试探，而这次试探来自C结点。试探后发现F无法通向目标，再去试探C的另一个孩子、F的兄弟G结点。与F结点类似，K结点也会被试探两次。图中虚线箭头指出了搜索的轨迹，结点旁边的数字说明了该结点被搜索到的次序。再来看图312所示的一个更极端的例子，初始结点有若干个子结点，每个子结点都链接到3条很深的路径中，且其中两条是最左边的A路径和B路径，而目标结点t位于最右边路径的最深处。图311回溯搜索示意图图312回溯搜索示意图
当采用StepTrack或StepTrack1时，由于它们只保留了从初始结点S0到当前结点的一条路径，所以从S1进入A路径搜索，回溯后，又进入B路径、第三条路径。由于没有找到解，又从S2往下搜索。对S2而言，同样要搜索A和B路径。对S0的其他孩子也是同样。这样，A和B路径将被多次搜索，影响了搜索的效率。为了处理某个结点被多次试探的问题，可以通过增加3张保存不同类型结点的表对前面的算法进一步改进。这3张表分别如下。1 PSPath State表，路径状态表，保存当前搜索路径上的状态。如果找到了目标状态，PS就是以状态序列表示的解路径。2 NPSNew Path State表，新路径状态表，保存了等待搜索的状态，其后裔状态还没有被搜索到，即还没有被生成扩展。3 NSSNo Solvable State表，不可解状态表，保存了不可解的结点，即找不到解路径的状态，如果在搜索中扩展出的结点属于NSS表，则可立刻将其排除，不必沿着该结点往下搜索试探。每次生成一个新状态后，都判断其是否在PS、NPS或NSS中出现过，如果出现过，说明它已经被搜索到而不必再考虑。对于当前正在被检测的状态即前面提到的当前状态，记做CSCurrent State。CS总是最近加入PS中的状态，对CS应用各种规则后得到一些新状态，即CS的子状态的有序集合，再将该集合中的第一个子状态作为CS，加入到PS中，其余子状态则按顺序放入NPS中，用于以后的搜索。如果CS没有子状态，则要从PS和NPS中删除它，同时将它加入NSS中，之后回溯查找NPS中的首元素。具体的算法描述如下。Function BackTrack：BeginPS：=\[Start\];NPS：=\[Start\];NSS：=\[ \];CS：=Start;初始化While NPS\[\] DoBeginIf CS=目标状态 Then ReturnPS;搜索成功,返回解路径If CS没有子状态不包括PS、NPS和NSS中已有的状态ThenBeginWhilePS非空 and CS=PS中第一个元素 DoBegin将CS加入NSS;标明此状态不可解从PS中删除第一个元素CS;回溯从NPS中删除第一个元素CS;CS：=NPS中第一个元素;End;将CS加入PS;End;ElseBegin将CS的子状态不包括PS、NPS和NSS中已有的加入NPS;CS：=NPS中第一个元素;将CS加入到PS;End;End;Return Fail；整个空间搜索完End例35用BackTrack搜索算法求解图313中A到G的解路径。图313回溯搜索示例【解】算法的搜索轨迹图313中的数字编号如表31所示。初始化： PS∶=［A］;NPS∶=［A］;NSS=［ ］;CS∶=A表31例35的搜索过程循环次数CSPSNPSNSS0A\[A\]\[A\]\[ \]1B\[BA\]\[BCDA\]\[ \]2E\[EBA\]\[EFBCDA\]\[ \]3I\[IEBA\]\[IJEFBCDA\]\[ \]4J\[JEBA\]\[JEFBCDA\]\[I\]5F\[FBA\]\[FBCDA\]\[EJI\]6K\[KFBA\]\[KFBCDA\]\[EJI\]7C\[CA\]\[CDA\]\[BFKEJI\]8G\[GCA\]\[GHCDA\]\[BFKEJI\]算法返回值为PS，即解路径为ACG。BackTrack是状态空间搜索的一个比较基本的盲目搜索策略，各种状态空间图的搜索算法，如深度优先搜索、广度优先搜索、最好优先搜索等都有回溯的思想。BackTrack有以下几个要注意的地方。1 用NPS表使算法回溯到任一状态。2 用NSS表来避免算法重复探索无解的路径。3 用PS表记录当前搜索的路径，一旦找到目标，就将PS作为解路径返回。4 为避免陷入死循环，每次新状态生成后都检查其是否在这3张表中，如果在其中，就不做任何处理。3.3.2一般的图搜索策略首先简要给出后面各搜索策略可能用到的一些术语。1. 一些术语1 路径设一结点序列为n0,n1,n2,,nk，对 i=1,2,,k，若任一结点 ni－1 都具有一个后继结点 ni，则该结点序列称为从结点 n0 到结点 nk 的长度为k的一条路径。2 路径耗散值令cni,nj为结点ni到结点nj的有向弧或路径的耗散值，一条路径的耗散值等于连接这条路径各结点间所有有向弧耗散值的总和。路径耗散值可按式31递归计算，即 cni,t=cni,nj cnj,t 31式中，cni,t为结点ni到t的路径的耗散值；cnj,t为结点nj到t的路径的耗散值。3 扩展一个结点扩展一个结点是指对结点使用规则操作算子，生成出其所有后继结点，并给出连接弧线的耗散值相当于使用规则的代价。2. 一般的图搜索算法下面将要给出的一般的图搜索算法实际是状态空间图搜索策略的一个总框架，后面讨论的深度优先搜索策略、宽度优先搜索策略、各种启发式搜索策略等都是基于此框架进行修改得到的。在给出这个算法的具体描述之前，先对算法中使用的一些数据结构做简要说明。1 一般将初始结点记为S或S0，目标结点记为t或g或Sg。2 图是通过规则或操作产生的结点状态之间的连接关系，一般记为G。3 为了记录搜索过程中探索过的结点信息，设计了两个重要的数据结构，即OPEN表和CLOSED表，它们的大致形式如表32和表33所示。
表32OPEN表状 态 结 点父结点表33CLOSED表编号状 态 结 点父结点4 OPEN表记录搜索过程中所有生成的但还未被扩展的结点，也就是在状态空间图中出现的。但还没有孩子的结点。CLOSED表记录搜索过程中所有被扩展过的结点，也就是在状态空间图中出现的、有孩子的结点。很显然，OPEN表和CLOSED表没有交集，它们的合集为扩展出的所有结点，也就是状态空间图中的所有结点。5 搜索主要是对OPEN表和CLOSED表这两个表的交替处理。首先判断OPEN表是否为空，如果是空那么搜索失败，结束，这是因为只有通过扩展结点才能逐渐到达目标结点，而能被扩展的结点是那些未被扩展过的结点，也就是OPEN表中的结点，如果OPEN表为空，意味着没有结点可被扩展，也就无法到达目标结点；否则，OPEN表不空，取出其中第一个结点，判断是否为目标，如果是目标，算法成功结束；如果不是目标，对它进行扩展，同时修改OPEN表和CLOSED表的状态，对OPEN表排序，继续判断。具体的算法描述如下。1 G：=G0G0=S,OPEN：=S;G为图,S为初始结点,设置OPEN表,OPEN表中最初只包含初始结点2 CLOSED ：=;设置CLOSED表,初始情况下CLOSED表为空表3 Loop： If OPEN＝ Then ExitFail;OPEN表为空,算法失败退出4 n：=FirstOPEN,Removen,OPEN,Addn,CLOSED;称OPEN表的第一个结点为n,将其移出OPEN表,放入CLOSED表5 If Goaln Then ExitSuccess;如果n是目标结点,算法成功退出,此时通过查找CLOSED表,得到由n返回S的路径,即逆向的解路径6 Expandn,生成一组子结点M={m1,m2,m3,},M中不包含n的父辈结点,G：=AddM,G;扩展结点n,将其子结点加入图中7 根据M中结点的不同性质,标记和修改它们到父结点的指针① 对于未在OPEN表和CLOSED表中出现过的子结点,即刚刚由n扩展出来的子结点而言,将其加入OPEN表,并标记其到父结点n的指针② 对于已经在OPEN表中出现的子结点,即图中已经由其他结点扩展出来并且未被扩展的、这次又由结点n扩展出来的子结点而言,计算是否要修改其父结点的指针③ 对于已经在CLOSED表中出现的子结点,即图中已经由其他结点扩展出来并且已经被扩展的、这次又由结点n扩展出来的子结点而言,计算是否要修改其父结点的指针,以及计算是否要修改其后继结点指向父结点的指针8 对OPEN中的结点按某种原则重新排序9 Go Loop;跳转到Loop标号处接着搜索一般的图搜索策略有以下几点需要特别说明。1 一般的图搜索算法是后面所有要讨论的状态空间图搜索算法的总框架，各种状态空间图搜索算法都是在这个框架的基础上做修改得到的，它们最主要的区别在于对OPEN表中结点的排序方式不同。2 当OPEN表为空但仍然没有找到解路径时，算法失败退出。3 当目标结点位于OPEN表最前面的时候，算法才成功结束，而仅仅是目标结点在OPEN表中出现但不在OPEN表最前面时，算法还需要继续进行。4 算法一旦成功结束，可以根据目标结点指向父结点的指针逆向地追溯至初始结点，从而获得问题的解路径。图314结点n的不同类型的子结点
5 算法的难点和重点是第7步，即标记和修改指针，此时要对结点n的不同类型的子结点做分别处理。结点n的子结点的类型如图314所示。在对结点n进行扩展后，生成了一组子结点M={m1,m2,m3,}，M中不包含n的父辈结点。M中的结点分为以下3种类型。① 第一种是以前没有在图中出现过的结点，即没有在OPEN表和CLOSED表中出现过的结点，如图314中的mj结点，它们刚刚由结点n扩展出来，这种结点直接加到OPEN表中因为它们还没有孩子，没有被扩展过，并且要标记指向父结点n的指针。② 第二种结点是已经在图中出现但还没有被扩展过的、这次又由结点n扩展出来的结点，即OPEN表中已有的结点，如图314中的mk结点。对mk结点要计算是否修改其到父结点的指针。如果从初始结点经过原先的父结点a到达mk的路径的耗散值大于从初始结点经过结点n到达mk的路径的耗散值，也就是新路径比旧路径耗散小，那么修改mk的父结点的指针，由原先的a改为n；否则，父结点的指针不变，仍然指向a。③ 第三种结点是已经在图中出现而且已经被扩展过的、这次又由结点n扩展出来的结点，即CLOSED表中已有的结点，如图314中的ml结点。对ml结点要处理两件事情。首先要计算是否修改其到父结点的指针，如果从初始结点经过原先的父结点b到达ml的路径的耗散值大于从初始结点经过结点n到达ml的路径的耗散值，也就是新路径比旧路径耗散小，那么修改ml的父结点的指针，由原先的b改为n；否则，父结点的指针不变，仍然指向b。其次要计算是否修改ml的后继结点指向其父结点的指针，修改的原则仍然是保证从初始结点到ml的后继结点的路径的耗散值最小，哪条路径的耗散值小，ml的后继结点的父指针就存在于该路径上。事实上，如果要搜索的状态空间图是树状结构，则n的子结点只有一种形式，即第一种mj结点，不存在mk和ml这两种类型的子结点，因此不必进行修改指针的操作。然而，如果要搜索的状态空间图不是树状结构，情况就比较复杂，可能这3种类型的子结点都会存在，这样就要比较不同路径的耗散值，保证指向父结点的指针在具有较小耗散值的路径上。6 在搜索图中，除了初始结点外，任何结点都有且只有一个指向父结点的指针。因此，由所有结点及其指向父结点的指针所构成的集合是一个树，称为搜索树。例36图315是一个状态空间图搜索过程中的一种情形，其中实心的结点表示已经被扩展过的结点，即CLOSED表中的结点，图315扩展结点6之前的情况空心的结点表示未被扩展的结点，即OPEN表中的结点，父结点的指针在有向弧旁边标注，每条有向弧的耗散值为单位耗散值，现在假设先要扩展结点6，接着扩展结点1，基于一般的图搜索算法，分析扩展后各结点的情况。【解】首先扩展结点6，生成了两个子结点，即结点7和结点4。结点7是刚刚在图中由结点6扩展出来的新结点，直接加到OPEN表中，并标记指向结点6的指针，如图316所示。结点4已经由结点2扩展，这次又由结点6扩展出来，而且结点4还未被扩展，所以结点4是OPEN表中的已有结点。现在有两条从初始结点S到结点4的路径，一条是老路径S324，耗散值是5个单位，一条是新路径S64，耗散值是4个单位，因此结点4的父结点指针从原先的结点2修改为结点6，如图316所示。接着扩展结点1，结点1只有一个子结点，即结点2。结点2已经在图中出现，原先是由结点3扩展而来的，而且结点2还有两个子结点，即结点4和结点5，说明结点2是CLOSED表中的结点。现在有两条从初始结点S到结点2的路径，一条是老路径S32，耗散值是4个单位，一条是新路径S12，耗散值是2个单位，因此结点2的父结点指针从原先的结点3修改为结点1，如图317所示。同时，结点2的子结点中，结点4要继续考虑，因为现在可以有两条从初始结点S到结点4的路径，一条是老路径S64，耗散值是4个单位，一条是新路径S124，耗散值是3个单位，因此结点4的父结点指针从原先的结点6又修改为结点2，如图317所示。图316扩展结点6之后的情况图317扩展结点1之后的情况
3.3.3深度优先搜索策略深度优先搜索没有利用与问题有关的知识，是一种盲目的搜索策略。深度优先是指在每次扩展结点时，优先选择到目前为止深度最深的结点扩展。深度优先搜索的过程如下。1 G：=G0G0=S,OPEN：=S,CLOSED：=2 Loop： If OPEN= Then ExitFail3 n：=FirstOPEN,Removen, OPEN,Addn, CLOSED4 If Goaln Then Exit Success5 Expandn,生成一组子结点M={m1,m2,m3,},M中不包含n的父辈结点,G：=AddM,G6 将n的子结点中没有在OPEN表和CLOSED表中出现过的结点,按照生成的次序加入OPEN表的前端,并标记它们到结点n的指针;把刚刚由结点n扩展出来的、以前没有出现过的结点放在OPEN表的最前面,使深度大的结点优先扩展7 Go Loop从深度优先搜索策略的算法描述中不难发现，它是在一般的图搜索框架基础上变换得到的，更具体地说，深度优先搜索的特色体现在标记和修改指针上，它只对结点n的第一种子结点即那些以前没有在图中出现过的，刚刚由结点n扩展而来的子结点，亦即那些没有在OPEN表和CLOSED表中出现过的结点进行处理，按照生成的顺序将它们放在OPEN表的最前端。由于子结点的深度大于父辈结点的深度，导致深度深的结点在OPEN表的前面，深度浅的结点在OPEN表的后面，也就是说，OPEN表是按照结点的深度由大到小进行排序的。这样，当下一个循环再次取出OPEN表的第一个元素时，实际上选择的就是到目前为止深度最深的结点，从而保证了搜索的深度优先。很明显，深度优先搜索策略不一定能找到最佳解。由于是盲目的搜索策略，在最糟糕的情况下，深度优先搜索等同于遍历穷举，这时的搜索空间就是问题的全部状态空间。而且，如果状态空间中有无限深渊时，深度优先搜索有可能找不到解。为了处理无限深渊的问题，可以将其改进为有界深度优先搜索。当然，这个深度限制应该设置得合适，深度过深影响搜索的效率，而深度过浅，有可能找不到解，这时可以进一步将算法改进为可变深度限制的深度优先搜索。有界深度优先搜索策略的算法描述如下。1 G：=G0G0=S,OPEN：=S,CLOSED：= 2 Loop： If OPEN= Then ExitFail3 n：=FirstOPEN,Removen, OPEN,Addn, CLOSED4 If Goaln Then ExitSuccess5 If DepthnBound Then Go Loop;Bound是一个事先设置好的常数,表示深度界限,如果n的深度超过了Bound,跳转至Loop标号处,进行下一轮搜索6 Expandn,生成一组子结点M={m1,m2,m3,},M中不包含n的父辈结点,G：=AddM,G7 将n的子结点中没有在OPEN表和CLOSED表中出现过的结点,按照生成的次序加入OPEN表的前端,并标记它们到结点n的指针8 Go Loop例37八数码问题的深度为4的有界深度优先搜索，问题的初始状态和目标状态如图32所示。画出搜索图，写出OPEN表和CLOSED表的变化情况。【解】可用的规则为空格的上、下、左、右移动，每次对状态使用规则时，也按照空格的上移、下移、左移、右移来依次使用规则。搜索图如图318所示，OPEN表和CLOSED表的变化情况如表34所示，其中略去了父结点指针情况。图318八数码问题的深度优先搜索图表34八数码问题深度优先搜索的OPEN表和CLOSED表的变化情况循环次数OPEN表CLOSED表0S0 1S1 S2 S3S02S4 S5 S6 S2 S3S0 S13S7 S8 S5 S6 S2 S3S0 S1 S44S9 S8 S5 S6 S2 S3S0 S1 S4 S75S8 S5 S6 S2 S3S0 S1 S4 S7S96S10 S5 S6 S2 S3S0 S1 S4 S7 S9 S87S5 S6 S2 S3S0 S1 S4 S7 S9 S8 S108S11 S12 S6 S2 S3S0 S1 S4 S7 S9 S8 S10 S59S13 S12 S6 S2 S3S0 S1 S4 S7 S9 S8 S10 S5 S1110S12 S6 S2 S3S0 S1 S4 S7 S9 S8 S10 S5 S11 S1311S14 S6 S2 S3S0 S1 S4 S7S9 S8 S10 S5 S11 S13 S12
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
