本文摘自《人工智能 （第2版）》公民邮电出版社出版

在本文中，我们从在人工智能中常常碰着的最主要的问题之一 ——搜索开始学习。
我们的目标是先容在AI中用于求解问题的最盛行方法：搜索、知识表示和学习。
我们开始学习基本的搜索算法——所谓的“无信息搜索”或“盲目搜索”的方法。
这些算法不依赖任何问题领域的特定知识。
正如我们将看到的，这些算法常日须要大量的空间和韶光。

2.0　简介：智能系统中的搜索

搜索是大多数人生活中的自然组成部分。
我们都放错过屋子钥匙或电视遥控器，然后检讨口袋，翻箱倒柜。
有时候，搜索可能更多是在大脑中进行。
你可能有时溘然不记得自己到访过的地方的名字、真正喜好的电影中演员的名字，或者不记得曾经谙熟于心的歌词。
要想起来这些事，可能须要几秒钟（影象力衰退时或许更长）。

许多算法专门通过列表进行搜索和排序。
当然，人们赞许，如果数据按照逻辑顺序组织，那么搜索就会比较方便一些。
想象一下，如果姓名和电话号码随机排列，那么搜索相对较大城市的电话簿会有多麻烦。
因此，搜索和信息组织在智能系统的设计中发挥了主要浸染，这并不奇怪。
大概我们要搜索曾经到访过地方的名字或序列中的下一个数字（见第1章），抑或是井字游戏或跳棋游戏中下一步最佳移动（见第4章和第16章）。
人们认为，可以非常快地办理此类问题的人，常日比其他人更聪明。
软件系统也常日利用相同的术语，例如，人们也认为，性能更好的国际象棋博弈程序比同类型的程序更加智能。

本章先容了几种基本搜索算法。
2.1节首先先容一个有助于形式化搜索过程的数学构造——状态空间图。
在众所周知的***问题（False Coin Problem）中，人们必须通过对两个或更多个***进行称重来识别***，个中就展示了这种构造。
接下来，本章先容和解释了天生和测试（generate-and-test）搜索范式。
天生器模块系统地提出了问题的可能解，而测试器模块验证理解的精确性。

本章还引入了两种经典的搜索方法：贪婪算法和回溯。
这两种方法都是先将问题分成多少步骤。
例如，如果你要将8个皇后放在棋盘上，任何两个皇后都不会相互攻击，也便是说，任何两个皇后都没有霸占同一行、同一列或同一对角线。
第 1 步便是将第一个皇后放在棋盘上，第2步便是将第二个皇后放在安全的方格中，以此类推。
正如你在2.2节中所看到的，在选用何种标准做出详细选择方面，这两种方法互不相同。

2.3节阐明了盲目搜索算法。
盲目或无信息搜索算法是一种不须要利用问题领域知识的方法。
例如，假设你正在迷宫中找出路。
在盲目搜索中，你可能总是选择最左边的路线，而不考虑任何其他可替代的选择。
两种范例的盲目搜索算法是宽度优先搜索（BFS）和深度优先搜索（DFS）——在第1章中已经做了简要先容。
回忆一下，在连续提高之前，BFS在离开始位置的指定间隔处仔细查看所有替代选项。
BFS的优点是，如果一个问题存在解，那么BFS就会找到它。

但是，如果在每个节点的可替代选项很多，那么BFS可能会因须要花费太多的内存而变得不切实际。
DFS采取了不同的策略来达到目标：在探求可替代路径之前，它追求探求单一的路径来实现目标。
DFS内存需求合理，但是它可能会因偏离开始位置无限远而错过了相对靠近搜索起始位置的解。
具有迭代加深的DFS是介于BFS和DFS之间的折上钩划，它将DFS中等空间需求与BFS供应能找到解的确定性结合到了一起。

2.1　状态空间图

状态空间图（state-space graph）是对一个问题的表示，通过问题表示，人们可以探索和剖析通往解的可能的可替代路径。
特定问题的解将对应状态空间图中的一条路径。
有时候，我们要搜索一个问题的任意解；而有时候，我们希望得到一个最短（最优）的解。
本章将紧张关注所谓的盲目搜索方法，即探求创造任意解。
第 3 章将重点关注知情搜索算法，这些算法常日可以创造问题的最佳解。

***问题

在打算机科学中，一个众所周知的问题是***问题。
有12枚***，已知个中一枚是假的或是假造的，但是不知道***是比其他币更轻还是更重。
普通的秤可以用于确定任何两组***的质量，即一组***比另一组***更轻或更重。
为理解决这个问题，你该当创建一个程序，通过称量三组***的组合，来识别***。

在这一章中，我们将办理一个相对大略的问题实例，这只涉及6枚***；与上述的原始问题一样，它也须要比较三组***，但是在这种情形下，任何一组***的***枚数相对较少，我们称之为最小***问题。
我们利用符号Ci1 Ci2…Cir：Cj1 Cj2…Cjr来指示r枚***，比较Ci1 Ci2…Cir与另r枚***Cj1 Cj2…Cjr的质量大小。
结果是，要么这两组***同样重，要么不一样重。
我们不须要进一步知道左边盘子的***是否比右边盘子的***更重或是更轻（如果要办理这个问题的12枚***的版本，就须要知道其他知识）。
末了，我们采取暗号[Ck1 Ck2…Ckm]来指示具有m枚***的子集是所知道的包含了***的最小***凑集。
图2.1给出了这个最小***问题的一个解。

如图2.1所示，状态空间树由节点和分支组成。
一个椭圆是一个节点，代表问题的一个状态。
节点之间的弧表示将状态空间树移动到新节点的算符（或所运用的算符）。
请参考图2.1中标有（）的节点。
这个节点[C1 C2 C3 C4]表示***可能是C1、C2、C3或C4中的任何一个。
我们决定对C1和C2以及C5和C6之间的质量大小（运用算符）进行比较。
如果结果是这两个凑集中的***质量相等，那么就知道***一定是C3或C4中的一个；如果这两个凑集中的***质量不相等，那么我们确定C1或C2是***。
为什么呢？状态空间树中有两种分外类型的节点。
第一个是表示问题起始状态的起始节点。
在图2.1中，起始节点是[C1 C2 C3 C4 C5 C6]，这表明起始状态时，***可以是6枚***中的任何一个。
另一种分外类型的节点对应于问题的终点或终极状态。
图2.1中的状态空间树有6个终端节点，每个标记为[Ci]（i = 1,…, 6），个中i的值指定了哪枚是***。

图2.1　最小***问题的解

问题的状态空间树包含了问题可能涌现的所有状态以及这些状态之间所有可能的转换。
事实上，由于回路常常涌现，这样的构造常日称为状态空间图。
问题的解常日须要在这个构造中搜索（无论它是树还是图），这个构造始于起始节点，终于终点或终极状态（goal state）。
有时候，我们关心的是找到一个解（不论代价）；但有时候，我们可能希望找到最低代价的解。

说到解的代价，我们指的是到达目标状态所需的算符的数量，而不是实际找到此解所需的事情量。
比较打算机科学，解的代价等同于运行韶光，而不是软件开拓韶光。

到目前为止，我们不加差异地利用了节点（node）和状态（state）这两个术语。
但是，这是两个不同的观点。
常日情形下，状态空间图可以包含代表相同问题状态的多个节点，如图2.2所示。
回顾最小***问题可知，通过对两个不同凑集的***进行称重，可以到达表示相同状态的不同节点。

图2.2　状态空间图中的不同节点可以表示相同的状态

如图2.1所示，这是最小***问题的解。
办理这个问题的人穿着一件蓝色的衬衫，或者在处理12***版本的问题时，其他人须要一大杯咖啡，这些可能都是真的。
但是，这些细节该当与解无关。
抽象许可你抛开这样的细节。

在求解过程中，可以故意忽略系统的某些细节，这样就可以许可在合理的层面与系统进行交互，这便是在第1章中定义的抽象。
例如，如果你想玩棒球，那么抽象就可以更好地让你练习如何打弧线球，而不是让你花6年韶光成为研究物体如何移动的力学方面的博士。