第二部分 问题求解
第3章 通过搜索进行问题求解
在本章中，我们讨论一个智能体是如何向前搜索，找到一个动作序列来实现它的最终目标。
当要采取的正确动作不是很明显时，智能体可能需要提前规划：考虑一个形成通往目标状态路径的动作序列。这样的智能体被称为问题求解智能体（problem-solving agent），它所进行的计算过程被称为搜索（search）。
如2.4.7节所述，问题求解智能体使用原子（atomic）表示，也就是说，世界状态被视为一个整体，其内部结构对问题求解算法来说是不可见的。使用状态的因子化（factored）表示或结构化（structured）表示的智能体称为规划智能体（planning agent），第7章和第11章中将会讨论。
我们将在本书中介绍若干搜索算法。在本章中，我们将只考虑最简单的环境，即回合式的、单智能体的、完全可观测的、确定性的、静态的、离散的和已知的环境，并对有信息（informed）算法和无信息（uninformed）算法进行区分。在有信息算法中，智能体可以估计自己到目标的距离，而在无信息算法中不能进行这样的估计。第4章会讨论更一般的环境中的问题，第5章则考虑了多智能体的情形。
本章使用了渐近复杂性的概念（即O(n)表示法）。不熟悉这些概念的读者可以参阅附录A。
3.1 问题求解智能体
想象一下，一个智能体正在罗马尼亚度假。它想参观景点，想学习罗马尼亚语，想享受罗马尼亚的夜生活但又不想宿醉，等等。这一决策问题是复杂的。现在，假设智能体目前位于Arad，并且买了一张第二天从Bucharest起飞且不能退款的机票。智能体观察路牌后发现，从Arad出发有3条路：一条通往Sibiu，一条通往Timisoara，还有一条通往Zerind。但这都不是它的目的地，所以除非智能体熟悉罗马尼亚的地理环境，不然它不知道该走哪条路。[1]
[1] 我们假设大多数读者都处于同样的处境，并且很容易想象自己和智能体一样毫无头绪。我们向不能利用这一教学安排的罗马尼亚读者道歉，因为他们清楚地知晓哪条路更易到达Bucharest。
如果智能体没有额外信息，也就是说，如果环境是未知的（unknown），那么智能体只能随机执行一个动作。这种情况将在第4章讨论。在本章中，我们假设智能体总是能够访问与世界相关的信息，例如图3-1中的地图。有了这些信息，智能体可以执行以下4个阶段的问题求解过程。
● 目标形式化（goal formulation）：智能体的目标为到达Bucharest。目标通过限制智能体的目的和需要考虑的动作来组织其行为。
图3-1 罗马尼亚部分地区的简化道路图，道路距离单位为英里（1英里 = 1.61千米）
● 问题形式化（problem formulation）：智能体刻画实现目标所必需的状态和动作——进而得到这个世界中与实现目标相关的部分所构成的抽象模型。对智能体来说，一个好的模型应该考虑从一个城市到其相邻城市的动作，这时，状态中只有“当前所在城市”会由于动作而改变。
● 搜索（search）：在真实世界中采取任何动作之前，智能体会在其模型中模拟一系列动作，并进行搜索，直到找到一个能到达目标的动作序列。这样的序列称为解（solution）。智能体可能不得不模拟多个无法到达目标的序列，但最终它要么找到一个解（例如从Arad到Sibiu到Fagaras再到Bucharest），要么发现问题是无解的。
● 执行（execution）：现在智能体可以执行解中的动作，一次执行一个动作。
一个重要的性质是，在一个完全可观测的、确定性的、已知的环境中，任何问题的解都是一个固定的动作序列：开车到Sibiu，然后到Fagaras，最后到达Bucharest。如果模型是正确的，那么一旦智能体找到了一个解，它就可以在执行动作时忽略它的感知（“闭上眼睛”），因为解一定会到达目标。控制理论家称之为开环（open-loop）系统，因为忽略感知打破了智能体和环境之间的环路。如果模型有可能是不正确的，或者环境是非确定性的，那么监控感知的闭环（closed-loop）方法会更安全（见4.4节）。
在部分可观测或非确定性环境中，问题的解将是一个根据感知推荐不同的未来动作的分支策略。例如，智能体可能规划从Arad开车到Sibiu，但还需要一个应变规划，以防它不小心到了Zerind或者发现了“Drum Închis”（道路封闭）的标志。
3.1.1 搜索问题和解
搜索问题（problem）的形式化定义如下。
● 可能的环境状态（state）的集合，我们称之为状态空间（state space）。
● 智能体启动时的初始状态（initial state），例如Arad。
● 一个或多个目标状态（goal state）的集合。有时问题只有一个目标状态（如Bucharest），有时存在若干个可供选择的目标状态，也有时目标是由一个适用于许多状态（可能是无限多个状态）的属性所定义的。例如，在一个真空吸尘器世界里，目标可能是让任何位置都没有灰尘，而无论该状态的其他情况如何。我们通过给问题指定一个Is-Goal方法来将这3种可能性都考虑在内。在本章中，为了简单起见，我们有时会直接用“目标”一词，它表示“任一可能的目标状态”。
● 智能体可以采取的行动（action）。给定一个状态s，Actions(s)将返回在s中可以执行的有限[2]动作集合。我们称集合中的任一动作在s中都是适用的（applicable）。例如：
[2] 对于具有无限多个动作的问题，我们需要本章之外的其他技巧。
● 转移模型（transition model）用于描述每个动作所起到的作用。Result(s, a)将返回在状态s中执行动作a所产生的状态。例如：
● 动作代价函数（action cost function），在编程中记作Action-Cost(s, a, s' )，在数学运算中记作c(s, a, s' )。它给出了在状态s中执行动作a从而转移到状态s'的数值代价。问题求解智能体应该使用反映其自身性能指标的代价函数；例如，对于寻径智能体，动作代价可能是以英里为单位的长度（如图3-1所示），也可能是完成动作所花费的时间。
一个动作序列形成一条路径（path），而解（solution）是一条从初始状态到某个目标状态的路径。我们假设动作代价是可累加的；也就是说，一条路径的总代价是各个动作代价的总和。最优解（optimal solution）是所有解中路径代价最小的解。在本章中，我们假设所有的动作代价都为正，以减少复杂性。[3]
[3] 在任何存在负代价环的问题中，代价最优解为在这个环中循环无限次。不存在负代价环时，Bellman-Ford算法和Floyd-Warshall算法（本章暂未涉及）可以处理负代价动作。只要连续的零代价动作的数量是有限的，处理零代价动作就很容易。例如，假设有一个机器人，其移动的代价为正，但旋转90°的代价为0；只要连续旋转90°动作的数量不超过3个，本章的算法就可以处理这个问题。存在无限多个任意小的动作代价的问题也很复杂。考虑Zeno悖论的情况，存在一个动作，它每次向目标移动剩余距离的二分之一，代价为上一次移动代价的二分之一。这个问题不存在动作数量有限的解，但为了防止搜索在没有完全到达目标的情况下采取无限数量的动作，我们可以要求所有动作的代价至少为
，为某个较小的正值。
状态空间可以用图（graph）来表示，图中的顶点表示状态，顶点之间的有向边表示动作。图3-1所示的罗马尼亚地图就是这样一个图，每条道路表示两种动作，即两个方向各表示一种。
3.1.2 问题形式化
我们将前文中去往Bucharest的问题形式化为一个模型（model）——一种抽象的数学描述，而不是真实存在的实物。与简单的原子状态描述Arad相比，实际的旅行的世界状态包括很多内容：旅行伙伴、当时的广播节目、窗外的风景、附近是否有执法人员、到下一个休息站的距离、道路状况、天气、交通等。所有这些因素都被排除在我们的模型之外，因为它们与寻找前往Bucharest的路线问题无关。
从表示中剔除细节的过程称为抽象（abstraction）。一个良好的问题形式化应该具有适度的细节层次。如果智能体的动作细化到“右脚向前移动1厘米”或“方向盘向左转动1度”的层次上，那它可能永远都找不到走出停车场的路，更不用说去Bucharest了。
我们能更精确地定义合适的抽象层级（level of abstraction）吗？我们所选择的抽象状态和动作对应于大量具体的世界状态和动作序列。现在考虑抽象问题的解，例如，从Arad到Sibiu，到Rimnicu Vilcea，到Pitesti，再到Bucharest的路径。这个抽象解对应于大量更详细的路径。例如，从Sibiu开往Rimnicu Vilcea的途中，我们可以打开收音机，而在其他的旅程中关掉收音机。
如果我们能够将任何抽象解细化为更详细的世界中的解，那么这种抽象就是合理的；一个充分条件是，对于“in Arad”的每个详细状态，都有一条到达“in Sibiu”状态的详细路径，以此类推。[4]如果执行解中的每个动作都比原始问题更容易，那么抽象是有用的；在我们的示例中，“从Arad开车到Sibiu”的动作，任何一个一般水平的司机都可以在不进一步搜索或规划的情况下完成。因此，选择一个好的抽象需要删除尽可能多的细节，同时保留合理性，并确保抽象动作易于执行。如果没有构造有用的抽象的能力，智能体将被真实世界完全淹没。
[4] 参见11.4节。
3.2 问题示例
问题求解的方法已被应用于大量任务环境中。我们在这里列出一些典型问题，区分为标准化问题和真实世界问题。标准化问题（standardized problem）常用于说明或训练各种问题求解方法。它具有简洁、准确的描述，因此适合作为研究人员比较算法性能的基准。真实世界问题（real-world problem），如机器人导航，则意味着这一问题的解是人们实际使用的，且问题的形式化是独特的而非标准化的，因为例如在机器人导航问题中，每个机器人具有不同的传感器，产生不同的数据。
3.2.1 标准化问题
网格世界（grid world）问题是一个由正方形单元格组成的二维矩形阵列，在这个阵列中，智能体可以从一个单元格移动到另一个单元格。一般来说，智能体可以水平或垂直地移动到任何无障碍的相邻单元格，在某些问题中还可以沿对角线移动。单元格中可以包含智能体能拿起、推开或施加其他动作的物体，也可以存在阻止智能体进入单元格内的墙壁或其他不可逾越的障碍。2.1节中的真空吸尘器世界（vacuum world）可以表示为一个网格世界问题。
● 状态：即哪些对象在哪些单元格中。在真空吸尘器世界中，对象就是智能体和灰尘。对于只有两个单元格的简单情形，智能体可以位于这两个单元格中的任何一个，每个单元格都可能存在灰尘，所以共有2×2×2 = 8个状态（见图3-2）。一般来说，存在n个单元格的真空吸尘器环境有n×2n 个状态。
● 初始状态：任一状态都可以被指定为初始状态。
● 动作：在只有两个单元格的情形中，我们可以定义3种动作，即吸尘（Suck）、向左（Left）移动和向右（Right）移动。在二维多单元格世界中，我们则需要更多种移动动作。我们可以增加向上（Upward）和向下（Downward）的动作，从而得到4种绝对的（absolute）移动动作，或者可以将其转换为以自我为中心的动作，即从相对于智能体的角度来定义，例如，向前（Forward）、向后（Backward）、右转（TurnRight）和左转（TurnLeft）。
● 转移模型：Suck将去除单元格内的任何灰尘；Forward将智能体朝它所面对的方向向前移动一个单元格，除非它撞到墙（在这种情况下，这个行动不起作用）。Backward让智能体朝相反的方向移动一个单元格，而TurnRight和TurnLeft则将智能体的朝向旋转90°。
● 目标状态： 每个单元格都保持干净的状态。
● 动作代价： 每个动作的代价都是1。
图3-2 两个单元格的真空吸尘器世界的状态空间图。共有8个状态，每个状态有3种动作：L = Left（向左）、R = Right（向右）、S = Suck（吸尘）
另一种类型的网格世界是推箱子问题（sokoban puzzle），在这个问题中，智能体的目标是将一些散落在网格中的箱子推到指定的存储位置。每个单元格最多容纳一个箱子。当智能体向前移动到放有一个箱子的单元格，而箱子另一侧的单元格为空时，箱子和智能体都向前移动一格。智能体不能把一个箱子推到另一个箱子上或墙上。对于存在n个无障碍单元格和b个箱子的世界，共有
个状态；例如，在一个存在12个箱子的8×8网格中，有超过200万亿个状态。
在滑块问题（sliding-tile puzzle）中，若干滑块（有时称为块或片）排列在一个有若干空白区域的网格中，其中滑块可以滑进空白区域。它的一个变体是汽车华容道问题（Rush Hour puzzle），在这个问题中，我们需要在6×6的网格中滑动汽车和卡车，目标是将一辆汽车从交通堵塞中解救出来。滑块问题中最著名的变体是8数码问题（8-puzzle）（见图3-3），它由一个3×3的网格、8个带编号的滑块和一个空格组成，目标是达到指定的状态，如图3-3中右侧所示。类似的还有由4×4的网格组成的15数码问题（15-puzzle）。对8数码问题做如下形式化处理。
● 状态：指定每个滑块位置的状态描述。
● 初始状态：任何状态都可以被指定为初始状态。注意，可以根据奇偶性划分状态空间——任何给定目标都可以从恰好一半的可能初始状态到达（见习题 3.PART）。
● 动作：虽然在真实世界中是滑块在移动，但描述动作的最简单方法是假设空格执行Left、Right、Up或Down动作。如果空格位于边缘或角落，则不是所有的动作都可用。
● 转移模型：将状态和动作映射为一个结果状态；例如，图3-3中，对于初始状态，我们采取Left动作，那么结果状态中滑块5和空格将交换位置。
● 目标状态：尽管任何状态都可以作为目标状态，但我们通常用有序编号指定目标状态，如图3-3所示。
● 动作代价：每个动作的代价都为1。
注意，每个问题的形式化都涉及抽象。8数码问题中的动作被抽象为它们的开始状态和结束状态，忽略滑块滑动的中间位置。我们已经通过抽象除去了一些动作，例如，当滑块被卡住时需要晃动木板，并排除了用刀取出滑块然后再放回去的可能性。最终只剩下对规则的描述，避免了实际操作的所有细节。
图3-3 8数码问题的一个典型实例
我们介绍的最后一个标准化问题是由高德纳（Knuth, 1964）设计的，它说明了无限状态空间是如何产生的。高德纳推测，通过只由平方根、向下取整和阶乘操作组成的序列可以从数字4得到任何正整数。例如，我们可以这样从4得到5：
问题定义很简单，如下所述。
● 状态：正实数。
● 初始状态：4。
● 动作：应用平方根、向下取整或阶乘操作（阶乘仅用于整数）。
● 转移模型：根据运算的数学定义给出。
● 目标状态：所求的正整数。
● 动作代价：每个动作的代价都是1。
这一问题的状态空间是无限的：对于任意大于2的整数，阶乘操作总是产生一个更大的整数。这个问题很有趣，因为它探索了非常大的数字：从4到5的最短路径生成了数字(4!)! = 620 448 401 733 239 439 360 000。无限状态空间经常出现在涉及数学表达式生成、电路、证明、程序和其他递归定义对象的任务中。
3.2.2 真实世界问题
我们已经了解了如何根据指定的位置和沿着它们之间的边进行的位置转移来定义寻径问题（route-finding problem）。寻径算法有许多应用场景。其中一些是上文中罗马尼亚例子的直接扩展，例如提供导航的网站和车载系统等。（需要考虑的主要复杂因素是因与交通相关的延迟而导致的代价变化，以及因道路封闭而导致的路线变更。）另一些例如计算机网络中的视频流路由、军事行动规划和飞机航线规划系统等，则更加复杂。下面介绍旅行规划网站必须解决的航空旅行问题。
● 状态：每个状态显然包括当前位置（例如，某个机场）和当前时间。此外，由于每个动作（一个航段）的代价可能依赖于之前的航段、票价基础以及它们是国内航班还是国际航班，状态必须记录这些额外的“历史”信息。
● 初始状态：用户家所在的机场。
● 动作：在当前时间之后，从当前位置乘坐任意航班任意舱位起飞，如果需要，还要留出足够的时间在机场中转。
● 转移模型：乘坐航班产生的结果状态将航班的目的地作为新的当前位置，将航班的到达时间作为新的当前时间。
● 目标状态：目的地城市。有时目标可能更复杂一点，例如“乘坐直达航班到达目的地”。
● 动作代价：金钱成本、等待时间、飞行时间、海关和入境手续、舱位质量、当日时间、飞机类型、常旅客奖励积分等的组合。
商业旅行咨询系统使用的就是上述问题的形式化。不过，在处理航空公司错综复杂的票价结构时，还会有许多额外的复杂因素。例如，任何有经验的旅行者都知道，并不是所有的航空旅行都能按计划进行。因此，一个真正好的系统应该包括应变规划——如航班延误或者错过转机时的应对方案。
旅行问题（touring problem）描述的是一组必须访问的地点，而非单一目的地。旅行商问题（traveling salesperson problem，TSP），就是一个旅行问题，即地图上每个城市都必须被访问。其目标是找到代价小于C的旅行路线（在优化版本中，目标是找到代价最低的旅行路线）。为了提高TSP算法的性能，科研人员付出了大量的努力。该算法也可以扩展到处理车队问题。例如，规划波士顿校车路线的搜索优化算法为人们节约了500万美元，减少了交通拥堵和空气污染，同时还为司机和学生节省了时间（Bertsimas et al., 2019）。除了规划行程，搜索算法还被用于规划自动电路板钻孔机钻头的运动和装料机在车间内的移动等任务。
超大规模集成电路布图（VLSI layout）问题需要在一个芯片上定位数百万个元件和连接点，以最小化芯片面积、电路延迟和杂散电容，并最大化成品率。布图问题在逻辑设计阶段之后，通常分为两个部分：单元布图（cell layout）和通道布线（channel routing）。在单元布图中，电路的基本元件分组为若干单元，每个单元执行一些特定功能。每个单元都有固定的占用区域（大小和形状），并且需要与其他每个单元建立一定数量的连接。单元布图的目的是将单元彼此不重叠地放置在芯片上，并且单元之间有足够的空间布置连线。通道布线的目的则是通过单元之间的间隙为每条导线寻找特定的路线。这些搜索问题极其复杂，但绝对值得研究。
机器人导航（robot navigation）是寻径问题的一个推广。机器人不必沿着明确的路径（如罗马尼亚的道路）行走，而是可以四处游走，实际上是自己走自己的路。对于在平面上移动的圆形机器人，空间本质上是二维的。当机器人的手臂和腿也必须受到控制时，搜索空间就变成了多维的——每个关节角都是一个维度。为了使基本上连续的搜索空间变成有限空间，需要一些更先进的技术（见第26章）。除了问题的复杂性外，真正的机器人还必须处理传感器读取错误、电动机控制中的错误、部分可观测性以及可能改变环境的其他智能体等问题。
自20世纪70年代以来，由机器人对复杂物体（例如电动机）进行自动装配排序（automatic assembly sequencing）已成为标准的工业实践。算法首先找到一个可行的装配序列，然后对装配过程进行优化。将装配线上的人工劳动减少到最低限度可以节省大量时间和成本。装配问题的目标是找到某个对象的各个零件的组装顺序。如果顺序错误，那么只能撤消某些已完成的工序，否则无法在序列的后面添加其他部分。检查序列中动作的可行性是与机器人导航问题密切相关的几何搜索难题。因此，合法动作的生成是装配排序问题中代价较高的部分。任何实用算法都必须尽量避免探索全部的状态空间，而应只探索状态空间中的很小一部分。一类重要的装配问题是蛋白质设计（protein design），其目的是找到一种氨基酸序列，该序列能够折叠成具有正确特性的三维蛋白质结构，以治疗某些疾病。
3.3 搜索算法
搜索算法（search algorithm）将搜索问题作为输入并返回问题的解或报告failure（当解不存在时）。在本章中，我们考虑在状态空间图上叠加一棵搜索树（search tree）的算法，该算法从初始状态形成各条路径，并试图找到一条可以达到某个目标状态的路径。搜索树中的每个节点（node）对应于状态空间中的一个状态，搜索树中的边对应于动作。树的根对应于问题的初始状态。
理解状态空间和搜索树之间的区别非常重要。状态空间描述了世界的（可能无限的）状态集，以及允许从一个状态转移到另一个状态的动作。搜索树描述了这些状态之间通向目标的路径。搜索树可以有多条路径（因此可以有多个节点）到达任何给定状态，但树中的每个节点都只有唯一一条返回根的路径（与所有树一样）。
图3-4展示了寻找从Arad到Bucharest的路径的前几步。搜索树的根节点位于初始状态，Arad。我们可以按如下方式扩展（expand）节点：考虑该状态的可用动作Actions，使用Result函数查看这些动作指向何处，并为每个结果状态生成（generating）一个新节点，称为子节点（child node）或后继节点（successor node）。每个子节点的父节点（parent node）都是Arad。
图3-4 3棵部分搜索树，用于寻找从Arad到Bucharest的路线。已扩展节点用淡紫色和粗体字母表示；边界上已生成但未被扩展的节点用绿色表示；对应于这两种类型节点的状态集被称为已达。接下来可能生成的节点用虚线表示。注意，在最下面的树中，有一个从Arad到Sibiu再到Arad的环，这不可能是最优路径，因此搜索不应该从那里继续
现在我们必须从这3个子节点中选择一个考虑下一步扩展。这就是搜索的本质——先跟踪一个选项，之后再考虑其他选项。假定我们选择先扩展Sibiu。结果如图3-4中最下面的搜索树所示，我们得到了6个未被扩展的节点（以绿色节点显示）。我们称之为搜索树的边界（frontier）。任何已经生成过节点的状态都称为已达（reached）状态（无论该节点是否被扩展）。[5]图3-5为叠加在状态空间图上的搜索树。
[5] 一些作者将边界称为开节点表，这在地理学上不太容易引起共鸣，在计算上也不太合适，因为在这里，队列比表更有效。这些作者还使用闭节点表一词来指代之前已扩展的节点的集合，在我们的术语中，这些节点为已达节点去掉边界节点后的剩余节点。
图3-5 由图3-1中的罗马尼亚问题的图搜索生成的搜索树序列。在每一阶段，我们扩展边界上的每个节点，使用所有不指向已达状态的可用动作延伸每条路径。需要注意的是，在第三阶段，最高位置的城市（Oradea）有两个后继城市，这两个城市都已经有其他路径到达，所以没有路径可以从Oradea延伸
注意，边界分离（separate）了状态空间图的两个区域，即内部区域（其中每个状态都已被扩展）和外部区域（尚未到达的状态）。该属性如图3-6所示。
图3-6 以矩形网格问题为例说明图搜索的分离性质。边界（绿色）分离了内部（淡紫色）和外部（虚线）。边界是已达但尚未扩展的节点（及相应的状态）的集合；内部是已被扩展的节点（及相应的状态）的集合；外部是尚未到达的状态的集合。在（a）中，只有根节点被扩展。在（b）中，上面的边界节点被扩展。在（c）中，按顺时针顺序扩展根节点的其他后继节点
3.3.1 最佳优先搜索
我们如何决定下一步从边界扩展哪个节点？最佳优先搜索（best-first search）是一种非常通用的方法，在这种方法中，我们选择使得某个评价函数（evaluation function）f(n)的值最小的节点n。算法如图3-7所示。在每次迭代中，选择边界上具有最小f(n)值的一个节点，如果它的状态是目标状态，则返回这个节点，否则调用Expand生成子节点。对于每个子节点，如果之前未到达过该子节点，则将其添加到边界；如果到达该子节点的当前路径的代价比之前任何路径都要小，则将其重新添加到边界。该算法要么返回failure，要么返回一个节点（表示一条通往目标的路径）。通过使用不同的f(n)函数，可以得到不同的具体算法，本章将介绍这些算法。
图3-7 最佳优先搜索算法以及扩展节点的函数。这里使用的数据结构将在3.3.2节中介绍。yield的说明见附录B
3.3.2 搜索数据结构
搜索算法需要一个数据结构来跟踪搜索树。树中的节点（node）由一个包含4个组成部分的数据结构表示。
● node.State：节点对应的状态。
● node.Parent：父节点，即树中生成该节点的节点。
● node.Action：父节点生成该节点时采取的动作。
● node.Path-Cost：从初始状态到此节点的路径总代价。在数学公式中，一般使用g(node)表示Path-Cost。
通过从一个节点返回的Parent指针，我们可以复原到达该节点的路径上的状态和动作。从一个目标节点开始复原，我们就可以得到问题的解。
我们需要一个数据结构来存储边界。一个恰当的选择是某种队列（queue），因为边界上的操作有以下几个。
● Is-Empty( frontier)：返回true当且仅当边界中没有节点。
● Pop( frontier)：返回边界中的第一个节点并将它从边界中删除。
● Top( frontier)：返回（但不删除）边界中的第一个节点。
● Add(node, frontier)：将节点插入队列中的适当位置。
搜索算法使用了3种不同类型的队列。
● 优先队列（priority queue）首先弹出根据评价函数f计算得到的代价最小的节点。它被用于最佳优先搜索。
● FIFO队列（FIFO queue），即先进先出队列（first-in-first-out queue），首先弹出最先添加到队列中的节点；它被用于广度优先搜索。
● LIFO队列（LIFO queue），即后进先出队列（last-in-first-out queue），也称为栈（stack），首先弹出最近添加的节点；它被用于深度优先搜索。
已达状态可以存储为一个查找表（例如，哈希表），其中每个键是一个状态，对应的值是该状态的节点。
3.3.3 冗余路径
图3-4（最下面一排）所示的搜索树包含了一条从Arad到Sibiu再回到Arad的路径。这时我们称Arad为搜索树中的一个重复状态（repeated state），在本例中该重复状态是由循环（cycle）［也称为环路（loopy path）］生成的。因此，即使状态空间只有20种状态，完整的搜索树也是无限的，因为遍历循环的频率没有限制。
循环是冗余路径（redundant path）的一种特殊情况。例如，我们可以通过路径Arad—Sibiu（总长140英里）或路径Arad—Zerind—Oradea—Sibiu（总长297英里）到达Sibiu。第二条路径是冗余的——是到达相同状态的一种比较差的方式——在我们寻找最优路径时不需要考虑它。
考虑一个10×10网格世界中的智能体，它能够移动到8个相邻方格中的任何一个。如果没有障碍，智能体可以在9步或更少的移动内到达100个方格中的任何一个。但是长度为9的路径的数量几乎是89（由于网格边缘的存在，路径数稍微少了一点），超过了1亿条。也就是说，平均意义下，有超过100万条长度为9的冗余路径到达同一个单元格，如果我们消除了冗余路径，搜索完成的速度可以快大约100万倍。俗话说，不记得历史的算法注定要重复历史。有3种方法可以解决这一问题。
第一，我们可以记住之前到达的所有状态（就像最佳优先搜索一样），这样能够检测到所有冗余路径，并只保留每个状态的最优路径。这适用于存在大量冗余路径的状态空间，当内存可以容纳下已达状态表时，它是首选方法。
第二，我们不必担心对过去的重复。在一些问题形式化中，很少或不可能出现两条路径到达相同状态。以装配问题为例，每个动作都会将一个零件添加到一个不断发展的装配中，零件是有序的，因此可以先添加A，然后再添加B，但不能先添加B，然后再添加A。对于这些问题, 如果我们不记录已达状态也不检查冗余路径，则可以节省内存空间。如果搜索算法会检查冗余路径，我们称之为图搜索（graph search）；否则，称之为树状搜索（tree-like search）[6]。图3-7中的Best-First-Search算法是一种图搜索算法；如果删除所有对reached的引用，即为树状搜索，它使用更少的内存，但会出现到达相同状态的冗余路径，因此运行速度会更慢。
[6] 我们称之为“树状搜索”，是因为无论如何搜索，状态空间仍然是相同的图；我们只是把它当作一棵树，从每个节点返回根只有一条路径。
第三，我们可以选择折中方法，检查循环，但通常不检查冗余路径。由于每个节点都有一个父指针链，因此可以通过跟踪父指针链来查看路径末端的状态之前是否在路径中出现过，从而不需要额外内存即可检查是否存在循环。某些算法实现一直沿着这个链向上移动，从而消除了所有循环。另一些算法实现仅跟踪少数几个链接（例如，到父节点、祖父节点和曾祖父节点），因此仅需花费固定的时间就可以消除所有短循环（并依靠其他机制来处理长循环）。
3.3.4 问题求解性能评估
在开始设计各种搜索算法之前，需要考虑在这些算法中进行选择时所使用的标准。我们可以从以下4个方面评价算法的性能。
● 完备性（completeness）：当存在解时，算法是否能保证找到解，当不存在解时，是否能保证报告失败？
● 代价最优性（cost optimality）：它是否找到了所有解中路径代价最小的解？[7]
[7] 一些作者使用“可容许性”这一术语表示寻找最小代价解的性质，还有一些作者仅使用“最优性”，但这可能与其他类型的最优性相混淆。
● 时间复杂性（time complexity）：找到解需要多长时间？可以用秒数来衡量，或者更抽象地用状态和动作的数量来衡量。
● 空间复杂性（space complexity）：执行搜索需要多少内存？
为了理解完备性，考虑一个具有单一目标的搜索问题。这个目标可能是状态空间的任何地方；因此，一个完备的算法必须能够系统地探索从初始状态可以到达的每一个状态。在有限状态空间中，这是很容易实现的：只要我们跟踪路径并切断循环（例如，Arad到Sibiu再到Arad），最终我们将到达每一个可到达的状态。
在无限状态空间中，则需要更加小心。例如，在高德纳的“4”问题中反复应用“阶乘”操作的算法将沿着从4到4!到(4!)!……的无限路径行进。同样地，在一个没有障碍的无限网格上，沿着直线不停前进也会形成由新状态组成的无限路径。在这两种情况下，算法永远不会返回它之前到达的状态，但它是不完备的，因为状态空间中的大部分状态永远都不会到达。
完备的搜索算法探索无限状态空间的方式必须是系统的（systematic），以确保它最终能够到达与初始状态相关的任何状态。例如，在无限网格上，一种系统搜索方法是螺旋路径，它覆盖了距离原点s步远的所有单元格，然后移动到s + 1步远的单元格。遗憾的是，在一个不存在解的无限状态空间中，一个合理的算法会一直搜索，它不会终止，因为它不知道下一个状态是否是目标状态。
时间复杂性和空间复杂性与问题的困难程度相关。在理论计算机科学中，一种典型的度量方式是状态空间图的大小，
，其中
是图中顶点（状态节点）的数量，
是边（不同的状态/动作对）的数量。当状态空间图是显式的数据结构（如罗马尼亚地图）时，这种度量是合适的。但在许多人工智能问题中，状态空间图只是由初始状态、动作和转移模型隐式地表示。对于隐式的状态空间，复杂性可以用3个量来衡量：d，最优解的深度（depth）或动作数；m，任意路径的最大动作数；b，需要考虑的节点的分支因子（branching factor）或后继节点数。
3.4 无信息搜索策略
无信息搜索算法不提供有关某个状态与目标状态的接近程度的任何线索。例如，考虑一个位于Arad且目标为Bucharest的智能体。一个对罗马尼亚地理一无所知的无信息智能体无法判断第一步应该前往Zerind还是Sibiu。相比之下，了解每个城市位置的有信息智能体（3.5节）则知道Sibiu距离Bucharest更近，因此Sibiu更有可能在最短路线上。
3.4.1 广度优先搜索
当所有动作的代价相同时，正确的策略是采用广度优先搜索（breadth-first search），即先扩展根节点，然后扩展根节点的所有后继节点，再扩展后继节点的后继，以此类推。这是一种系统的搜索策略，因此即使在无限状态空间上也是完备的。我们可以通过调用Best-First-Search实现广度优先搜索，其中评价函数f(n)是节点的深度，即到达该节点所需的动作数。
然而，我们可以通过一些技巧来提高算法效率。先进先出队列比优先队列速度更快，并且能提供正确的节点顺序：新节点（总是比其父节点更深）进入队列的队尾，而旧节点，即比新节点浅的节点，首先被扩展。此外，reached可以是一组状态，而不是状态到节点的映射，因为一旦到达某个状态，我们就再也找不到到达该状态的更好路径了。这也意味着我们可以进行早期目标测试（early goal test），即在生成节点后立即检查该节点是否为一个解，而不是像最佳优先搜索使用的后期目标测试（late goal test）那样，等节点弹出队列后再检查该节点是否为一个解。图3-8展示了在二叉树上进行广度优先搜索的过程，图3-9展示了使用早期目标测试来提高效率的算法。
图3-8 简单二叉树上的广度优先搜索。每个阶段接下来要扩展的节点用三角形标记表示
图3-9 广度优先搜索和一致代价搜索算法
广度优先搜索总是能找到一个动作最少的解，因为当它生成深度为d的节点时，说明它已经生成了深度为d - 1的所有节点，如果其中一个节点是解，它应该已经被找到了。这意味着，对于所有动作都具有相同代价的问题，它是代价最优的，但对于不具有该特性的问题，则不一定是最优的。这两种情况都是完备的。在时间和空间方面，想象我们在搜索一棵均衡树，其中每个状态都有b个后继。搜索树的根生成b个节点，每个节点又生成b个节点，第二层总共是b2个节点。每个节点又生成b个节点，从而在第三层产生b3个节点，以此类推。现在假设解的深度为d，那么生成的节点总数为
所有节点都存储在内存中，所以时间复杂性和空间复杂性都是O(bd)。这样的指数级上界是可怕的。举一个典型的真实世界中的例子，考虑一个分支因子b = 10、处理速度为每秒100万节点、内存需求为1 KB/节点的问题。深度d = 10的搜索将花费不到3小时的时间，但需要10 TB的内存。对广度优先搜索来说，内存需求是一个比执行时间更严重的问题。但时间仍然是一个重要因素。深度d = 14时，即使有无限内存，搜索也需要3.5年。一般来说，除了最小的问题实例，指数级复杂性的搜索问题无法通过无信息搜索求解。
3.4.2 Dijkstra算法或一致代价搜索
当动作具有不同的代价时，一个显而易见的选择是使用最佳优先搜索，评价函数为从根到当前节点的路径的代价。理论计算机科学界称之为Dijkstra算法，人工智能界则称之为一致代价搜索（uniform-cost search）。不同于广度优先搜索在深度一致的波（首先是深度1，然后是深度2，以此类推）中展开，一致代价搜索算法的思想是在路径代价一致的波中展开。该算法可以通过调用Best-First-Search实现，评价函数为Path-Cost，如图3-9所示。
考虑图3-10，问题是从Sibiu到达Bucharest。Sibiu的后继是Rimnicu Vilcea和Fagaras，代价分别为80和99。然后扩展代价最小的节点Rimnicu Vilcea，加入节点Pitesti，其代价为80 + 97 = 177。此时代价最小的节点是Fagaras，所以接着扩展Fagaras，加入节点Bucharest，代价为99 + 211 = 310。目标节点是Bucharest，但算法只在扩展节点时测试其是否为目标节点，而不是在生成节点时测试，因此它还没有检测到这是一条通往目标的路径。
图3-10 罗马尼亚问题状态空间的一部分，选择这部分来说明一致代价搜索
算法继续进行，接下来选择Pitesti进行扩展，添加到Bucharest的第二条路径，代价为80 + 97 + 101 = 278。它的代价更低，因此用它取代reached中之前的路径，并添加到frontier中。结果证明，这个节点目前具有最小代价，因此它被认为是下一个要扩展的节点，此时我们发现它是一个目标节点，从而返回该节点。注意，如果我们在生成节点时检查目标，而不是在扩展代价最小的节点时检查，那么我们将返回一个代价更高的路径（即经过Fagaras的路径）。
一致代价搜索的复杂性用C*和
表示，C*是最优解的代价[8]，是每个动作代价的下界，
。那么算法在最坏情况下的时间复杂性和空间复杂性是
，比bd大得多。这是因为一致代价搜索在探索包含一个可能有用的高代价动作的路径之前，可能会先探索具有低代价动作的大型树。当所有动作代价相同时，
等于bd+1，这时一致代价搜索类似于广度优先搜索。
[8] 在这里，以及整本书中，C*中的“*”表示C的最优值。
一致代价搜索是完备的，也是代价最优的，因为它找到的第一个解的代价至少与边界上的任何其他节点的代价一样小。一致代价搜索会按照代价递增的顺序系统地考虑所有路径，而不会陷入一直沿单一无限路径探索的困境（假设所有动作的代价 
）。
3.4.3 深度优先搜索与内存问题
深度优先搜索（depth-first search）总是优先扩展边界中最深的节点。它可以通过调用Best-First-Search来实现，其中评价函数f为深度的负数。然而，它通常不是以图搜索的形式实现而是以树状搜索（不维护已达状态表）的形式实现。搜索的过程如图3-11所示，搜索先直接到达搜索树的最深层，这里的节点不存在后继节点。然后，搜索将“回退”到下一个仍存在未扩展后继节点的最深的节点。深度优先搜索不是代价最优的，它会返回它找到的第一个解，即使这个解不是路径代价最小的。
图3-11 二叉树的深度优先搜索过程中，从开始状态A到目标M，共12步（从左到右，从上到下）。边界节点为绿色，用三角形表示下一步要扩展的节点。已扩展的节点为淡紫色，潜在的未来节点用模糊的虚线表示。边界中没有后继的已扩展节点（用非常模糊的线表示）可以丢弃
对于树型的有限状态空间，算法是有效且完备的。对于无环状态空间，算法可能会通过不同路径多次扩展同一状态，但是（最终）将系统地探索整个空间。
在有环状态空间中，深度优先搜索算法可能陷入无限循环；因此，一些深度优先搜索算法的实现会检查每个新节点是否存在循环。在无限状态空间中，深度优先搜索不是系统性的：即使没有循环，它也可能陷入无限路径。因此，深度优先搜索是不完备的。
那么，为什么还会有人选择使用深度优先搜索而不是广度优先搜索或最佳优先搜索呢？答案是，对于使用树状搜索可以处理的问题，深度优先搜索对内存的需求要小得多。深度优先搜索根本不保留reached表，并且边界集很小：如果将广度优先搜索中的边界集视为不断扩展的球体的表面，那么深度优先搜索中的边界集只是球体的半径。
对于图3-11所示的有限树状状态空间，深度优先的树状搜索所花费的时间与状态数成正比，其空间复杂性仅为O(bm)，其中b是分支因子，m是树的最大深度。有些问题在广度优先搜索时需要EB量级的内存，而在深度优先搜索时仅需要KB量级。由于其对内存的节约使用，深度优先树状搜索已经成为许多人工智能领域的基本工具，例如，约束满足（第6章）、命题可满足性（第7章）和逻辑编程（第9章）。
回溯搜索（backtracking search）是深度优先搜索的一种变体，它使用的内存更少。（详见第6章。）在回溯搜索中，一次只生成一个后继，而不是所有后继节点；每个部分扩展的节点会记住下一个要生成的后继节点。此外，回溯通过直接修改当前状态描述而不是为一个全新的状态分配内存来生成后继状态。这将内存需求减少到只有一个状态描述和一条具有O(m)个动作的路径；与深度优先搜索的O(bm)个状态相比，节省了大量资源。通过回溯，我们还可以为当前路径上的状态维护一个有效的集合数据结构，从而使检查循环的时间从O(m)减少到O(1)。为了使回溯起作用，我们必须能够在回溯时撤销每个动作。回溯对许多具有大型状态描述的问题（例如机器人组装）的成功求解至关重要。
3.4.4 深度受限和迭代加深搜索
为了避免深度优先搜索陷入无限路径，我们可以使用深度受限搜索（depth-limited search）。这是一个深度优先搜索的改进版本，在深度受限搜索中，我们设置深度界限
，将深度上的所有节点视为其不存在后继节点（见图3-12）。深度受限搜索算法的时间复杂性为O(b
)，空间复杂性为O(b)。遗憾的是，如果我们对的选择不当，算法将无法得到解，成为不完备的算法。
由于深度优先搜索是一种树状搜索，通常无法避免在冗余路径上浪费时间，但我们可以以一定的计算时间为代价来消除循环。沿着父节点向上查看几个节点，就能检测出大多数循环；更长的循环则由深度界限处理。
有时可以根据对问题的了解选择一个较好的深度界限。例如，罗马尼亚地图上有20个城市。因此，
= 19是一个有效的界限。但是如果仔细研究地图，我们会发现，从任何一个城市到达另一个城市最多需要9步。这个数值称为状态空间图的直径（diameter），它为我们提供了更好的深度界限，从而可以更有效地进行深度受限搜索。然而，对于大多数问题，在求解问题之前，我们无法知道什么深度界限是好的。
迭代加深搜索（iterative deepening search）解决了如何选择一个合适的的问题，方法是尝试所有值：首先是0，然后是1，然后是2，依次类推——直到找到一个解，或者深度受限搜索返回failure值（而不是cutoff值）。算法如图3-12所示。迭代加深搜索结合了深度优先和广度优先搜索的许多优点。和深度优先搜索一样，它对内存的需求也不大：当问题存在解时，是O(bd)，在不存在解的有限状态空间上，是O(bm)。与广度优先搜索一样，迭代加深搜索对于所有动作都具有相同代价的问题是最优的，并且在有限无环状态空间上是完备的，或者说在任何有限状态空间上，当我们检查路径节点上所有的循环时，它都是完备的。
图3-12 迭代加深和深度受限树状搜索。迭代加深搜索反复调用界限递增的深度受限搜索。它返回以下3种类型的值中的一种：一个解节点；当它搜索了所有节点，证明在任何深度都不存在解时，返回failure；当在比
更深的层上可能存在解时，返回cutoff。这是一种树状搜索算法，它不记录reached状态，因此比最佳优先搜索使用的内存要少得多，但存在通过不同路径多次访问相同状态的风险。另外，如果Is-Cycle检验函数不检查所有环，那么算法可能会陷入一个无限循环
存在解时，时间复杂性为O(bd)，不存在解时，时间复杂性为O(bm)。与广度优先搜索相同，迭代加深搜索的每次迭代也会生成一个新层级，但是广度优先搜索将所有节点都存储在内存中，而迭代加深搜索则会重复之前的层级，从而以花费更多的时间为代价节省了内存。图3-13展示了二叉搜索树上的迭代加深搜索的4次迭代，在第4次迭代时找到了解。
迭代加深搜索可能看起来很浪费，因为搜索树顶端附近的状态被多次重复生成。但是对于许多状态空间，大多数节点位于底层，所以上层是否重复并不重要。在迭代加深搜索中，底层（深度d）的节点被生成一次，倒数第二层的节点被生成两次，以此类推，直到根节点的子节点（生成d次）。所以在最坏情况下生成的节点总数是
时间复杂性为O(bd)——与广度优先搜索相近。例如，当b = 10、d = 5时，生成的节点数分别为
如果你确实很在意重复的问题，可以使用一种混合方法，即先运行广度优先搜索，直到几乎消耗掉所有可用内存，然后对边界集中的所有节点应用迭代加深搜索。通常，当搜索状态空间大于内存容量而且解的深度未知时，迭代加深搜索是首选的无信息搜索方法。
图3-13 二叉搜索树上的迭代加深搜索的4次迭代（目标为M），深度界限从0到3。注意，内部节点形成了一条路径。三角形标记下一步要扩展的节点，边界为加粗轮廓的绿色节点，非常模糊的节点可被证明不可能是这种深度界限下的解的一部分
3.4.5 双向搜索
到目前为止，我们介绍的算法都是从一个初始状态开始，最终到达多个可能目标状态中的任意一个。另一种称为双向搜索（bidirectional search）的方法则同时从初始状态正向搜索和从目标状态反向搜索，直到这两个搜索相遇。算法的动机是，
要比bd小得多（例如，当b = d = 10时，复杂性不到之前算法的五万分之一）。
为此，我们需要维护两个边界集和两个已达状态表，并且要能反向推理：如果状态s'是s的正向后继，那么我们需要知道s是s'的反向后继。当两个边界触碰到一起时，我们就找到了一个解。[9]
[9] 在我们的实现中，reached数据结构支持查询给定状态是否为其成员，而边界数据结构（一个优先队列）不支持，因此我们使用reached检查是否互相触碰；但从概念上讲，我们查询的是这两个边界是否已经相遇。通过将每个目标状态的节点加载到反向边界和反向已达表中，可以将实现扩展为处理多个目标状态。
双向搜索有很多不同版本，就像有很多不同的单向搜索算法一样。在这一节中，我们将介绍双向最佳优先搜索。尽管存在两个独立的边界，但接下来要扩展的节点始终是两个边界中的评价函数值最小的节点。当函数为路径代价时，我们得到双向一致代价搜索，如果最优路径的代价是C*，则不扩展代价大于
的节点。这将使得速度大大提高。
一般的最佳优先双向搜索算法如图3-14所示。我们传入问题和评价函数的两个版本，一个是正向的（下标F），另一个是反向的（下标B）。当评价函数是路径代价时，找到的第一个解将是最优解，但是对于不同的评价函数，这一结论不一定是正确的。因此，我们会记录迄今为止找到的最优解，并且可能不得不多次更新最优解，直到Terminated测试证明不可能再有更好的解。
图3-14 双向最佳优先搜索维护两个边界集和两个已达状态表。当一个边界中的路径到达另一半搜索已达状态时，这两条路径（通过Join-Nodes函数）被连起来构成一个解。我们得到的第一个解不一定是最优的；函数Terminated决定了什么时候停止寻找新的解
3.4.6 无信息搜索算法对比
图3-15根据3.3.4节中列出的4个评价标准对无信息搜索算法进行了比较。这种比较适用于不检查重复状态的树状搜索版本。对于检查重复状态的图搜索，主要区别在于，对于有限状态空间，深度优先搜索是完备的，并且空间复杂性和时间复杂性受到状态空间大小（顶点和边的数量，
）的限制。
图3-15 搜索算法比较。b是分支因子；m是搜索树的最大深度；d是最浅层解的深度，当不存在解时为m；
是深度界限
3.5 有信息（启发式）搜索策略
本节将展示有信息搜索（informed search）策略——使用关于目标位置的特定领域线索——如何比无信息搜索策略更有效地找到解。线索以启发式函数（heuristic function）的形式出现，记为h(n)：[10]
[10] 这看起来可能很奇怪，启发式函数真正需要的只是节点的状态，但作用对象却是节点。一般使用h(n)而不是h(s)，是为了与评价函数f (n)和路径代价g(n)保持一致。
h(n) = 从节点n的状态到目标状态的最小代价路径的代价估计值
例如，在寻径问题中，我们可以通过计算地图上两点之间的直线距离来估计从当前状态到目标的距离。我们将在3.6节中详细研究启发式函数及其来源。
3.5.1 贪心最佳优先搜索
贪心最佳优先搜索（greedy best-first search）是最佳优先搜索的一种形式，它首先扩展h(n)值最小的节点——看起来最接近目标的节点——因为这样可能可以更快找到解。因此，评价函数f(n) = h(n)。
让我们看看这种算法如何求解罗马尼亚寻径问题；我们使用直线距离（straight-line distance）作为启发式函数，记为hSLD。如果目标是Bucharest，我们需要知道到Bucharest的直线距离，如图3-16所示。例如，hSLD(Arad) = 366。注意，无法从问题描述本身（即Actions和Result函数）来计算hSLD的值。此外，根据经验可知，hSLD与实际道路距离相关，因此是一个有用的启发式函数。
图3-17展示了使用hSLD搜索从Arad到Bucharest的路径的贪心最佳优先搜索的过程。从Arad扩展的第一个节点是Sibiu，因为启发式函数认为它比Zerind或Timisoara更接近Bucharest。下一个要扩展的节点是Fagaras，因为根据启发式函数，它现在最接近Bucharest。Fagaras接着生成了Bucharest，即目标节点。对于这一特定问题，使用hSLD的贪心最佳优先搜索无须扩展不在解路径上的节点就找到了解。但是，它找到的解并不是代价最优的：经由Sibiu和Fagaras到达Bucharest的路径比经过Rimnicu Vilcea和Pitesti的路径长32英里。这就是为什么这种算法会被称为“贪心的”——在每次迭代中，它都会做出在当前看来最优的（即可以最接近目标的）选择，但这也会导致贪心法在全局意义上可能产生比谨慎的算法更糟糕的结果。
图3-16 hSLD（到Bucharest的直线距离）的值
图3-17 基于直线距离启发式函数hSLD的贪心最佳优先树状搜索的各个阶段（目标为Bucharest）。节点上标有h值
贪心最佳优先图搜索在有限状态空间中是完备的，但在无限状态空间中是不完备的。最坏情况下的时间复杂性和空间复杂性是
。然而，使用一个好的启发式函数，复杂性可以大大降低，对于某些问题可以达到O(bm)。
3.5.2 A*搜索
最常见的有信息搜索算法是A*搜索（A* search）（读为“A星搜索”），这是一种最佳优先搜索，评价函数为
其中g(n)是从初始状态到节点n的路径代价，h(n)是从节点n到一个目标状态的最短路径的代价估计值，因此我们有
f(n) = 经过n到一个目标状态的最优路径的代价估计值
在图3-18中，我们展示了目标为Bucharest的A*搜索过程。g的值由图3-1中的动作代价计算得到，hSLD的值在图3-16中给出。注意，Bucharest首先出现在图3-18的步骤e的边界中，但算法并没有选择它来进行扩展（因此它没有被检测为一个解），因为此时它不是边界中代价最小的节点（f = 450）——代价最小的节点是Pitesti（f = 417）。换句话说，可能存在一个经过Pitesti的解，代价低至417，所以算法不会满足于一个代价为450的解。在图3-18的步骤f中，另一条到Bucharest的路径此时代价最小（f = 418），因此它被选中并被检测为最优解。
A*搜索是完备的。[11]它是否是代价最优则取决于启发式函数的某些性质。一个关键性质是可容许性（admissibility）：一个可容许的启发式（admissible heuristic）函数永远不会高估到达某个目标的代价。（因此，一个可容许的启发式函数是乐观的。）
[11] 再强调一次，假设所有动作的代价都 
，状态空间要么有解，要么有限。
对于可容许的启发式函数，A*是代价最优的，我们可以通过反证法来证明这一点。假设最优路径的代价为C*，但是该算法返回的路径代价为C 
C*，那么最优路径上一定存在某个未扩展的节点n（因为如果最优路径上的所有节点都已被扩展，那么算法返回的将是这个最优解）。因此，使用符号g*(n)表示从起点到n的最优路径的代价，h*(n)表示从n到最近目标的最优路径的代价，我们将得到
第一行和最后一行矛盾，所以“算法可能返回次优路径”的假设一定是错误的——A*一定只返回代价最优路径。
另一个稍强的性质为一致性（consistency）。如果对于每个节点n以及由动作a生成的n的每个后继节点n' 有以下条件，则启发式函数h(n)是一致的：
这是三角不等式（triangle inequality）的一种形式，它规定三角形的一条边不能大于其他两条边之和（见图3-19）。一致的启发式函数的一个实例是上文中的直线距离hSLD。
图3-18 A*搜索的各个阶段（目标为Bucharest）。节点上标有f = g + h，h值为图3-16中得到的到Bucharest的直线距离
图3-19 三角不等式：如果启发式函数h是一致的，那么单个数值h(n)小于从n到n'的动作代价值c(n, a, n')加上启发式函数的估计值h(n')的和
一致的启发式函数都是可容许的（反过来不成立），因此，使用一致的启发式函数的A*搜索都是代价最优的。此外，如果使用一致的启发式函数，算法第一次到达某个状态时，它就在一条最优路径上，因此我们永远不需要将某个状态重复添加到边界中，也不必更改reached中的条目。但是，如果使用不一致的启发式函数，最终可能导致多个路径到达相同状态，而且如果每条新路径的路径代价都小于前一条路径，最终在边界中该状态会有多个节点，这会耗费时间和空间。因此，有些A*搜索算法的实现会注意让一个状态只进入边界一次，如果找到了到达该状态的更优路径，那么该状态的所有后继都会更新（这要求节点除了父指针外还要有子指针）。这些复杂性使得许多研究人员在实现A*搜索时避免使用不一致的启发式函数，但费尔纳等人（Felner et al., 2011）认为，最坏的结果在实践中很少发生，因此不应该害怕不一致的启发式函数。
如果采用不可容许的启发式函数，那么A*搜索可能是代价最优的，也可能不是。存在两种情况使得A*搜索是代价最优的：第一，如果存在一条代价最优路径，对于该路径上的所有节点n，h(n)都是可容许的，那么无论启发式函数在路径外状态上的值如何，算法都能找到这条路径。第二，假设最优解的代价为C*，次优解的代价为C2，如果h(n)高估了部分代价但又没有高估太多，都不超过C2 − C*，那么也可以保证A*返回的解是代价最优的。
3.5.3 搜索等值线
一种对搜索进行可视化的方法是在状态空间中绘制等值线（contour），就像在地形图中绘制等高线一样。如图3-20所示，在标记为400的等值线内，所有节点都有
，以此类推。因为A*扩展的是f代价最小的边界节点，所以它是从初始节点扇形地向外扩展，以f 值递增的同心带状方式添加节点。
一致代价搜索中也存在等值线，但是等值线表示g代价，而不是g + h。一致代价搜索中，等值线将以初始状态为圆心呈“圆形”向各个方向均匀扩展，而不是偏向于目标状态。对于具有好的启发式函数的A*搜索，g + h带将朝一个目标状态延伸（如图3-20所示），并且在最优路径周围收敛变窄。
需要清楚的是，扩展路径时，g代价是单调的（monotonic）：路径代价始终随着路径的延伸而不断增加，因为动作代价始终为正。[12]因此，所得到的同心等值线彼此不会交叉，如果希望画出的等值线足够精细，则可以在任何路径上的任意两个节点之间画一条线。
[12] 从技术上讲，始终保持增加的代价称为“严格单调的”；永远不会减少但可能保持不变的代价称为“单调的”。
但
代价是否单调递增则并不显然。当你将一条路径从n扩展到n'时，代价从
变为
。消去g(n)项，我们可以看到，当且仅当
时，路径代价单调递增。换句话说，当且仅当启发式函数是一致的时，路径代价单调递增。[13]但需要注意的是，一条路径可能会在一行中贡献若干个具有相同g(n) + h(n)得分的节点；当h的减少量恰好等于刚刚采取的动作代价时，就会发生这种情况（例如，在一个网格问题中，当n与目标在同一行然后向目标迈进一步时，g增加1，h减少1）。如果C*是最优解路径的代价，那么以下说法成立。
[13] 事实上，“单调启发式函数”这一术语是“一致的启发式函数”的同义词。这两种观点是独立发展的，但是之后被证明是等价的（Pearl, 1984）。
● A*搜索将扩展从初始状态可以到达并且路径上的每个节点都满足
的所有节点。我们称这些节点为必然扩展节点（surely expanded node）。
● A*搜索可能会在选出目标节点之前扩展某些恰好在“目标等值线”（即f (n) = C*）上的节点。
● A*搜索不扩展
的节点。
图3-20 罗马尼亚地图，其中等值线为f = 380、f = 400和f = 420，初始状态为Arad。给定等值线内的节点的代价f = g + h小于或等于等值线值
我们认为具有一致启发式函数的A*搜索是效率最优（optimally efficient）的，因为任何从初始状态扩展搜索路径并使用相同启发式信息的算法都必须扩展A*的所有必然扩展节点（因为任何一个必然扩展节点都可能是某个最优解的一部分）。对于f(n)=C*的节点，某个算法可能运气好，首先选择了最优节点，而另一个算法就没这么幸运。我们在定义最优效率时不考虑这种差异。
A*之所以高效，是因为它会对那些对于寻找最优解没有帮助的搜索树节点进行剪枝（pruning）。在图3-18b中，我们看到，对于Timisoara，f = 447；对于Zerind，f = 449。即使它们是根的子节点并且是采用一致代价搜索或广度优先搜索时首先扩展的节点，它们也永远不会被A*搜索扩展，因为A*会首先找到f = 418的解。对许多人工智能领域来说，剪枝（不必进行检查就可以排除不正确的答案）非常重要。
在所有这些算法中，A*搜索都是完备的、代价最优的和效率最优的，这是相当令人满意的结果。遗憾的是，这并不意味着A*适用于所有搜索需求。问题在于，对于许多问题，所扩展的节点数可能是解路径长度的指数级。例如，考虑一个具有超强吸力的真空吸尘器世界，它可以以单位代价清理任一方格却不需要访问该方格。在这种情况下，可以按任何顺序清理方格。如果开始时有N个脏的方格，则有2N种状态，其中某个子集已被清理；所有这些状态都在最优解路径上，因此满足
，所以所有这些状态都会被A*搜索访问。
3.5.4 满意搜索：不可容许的启发式函数与加权A*搜索
A*搜索有很多好的性质，但它扩展了大量节点。如果我们愿意接受次优但“足够好”的解——我们称之为满意（satisficing）解，则可以探索更少的节点（花费更少的时间和空间）。如果我们允许A*搜索使用不可容许的启发式函数（inadmissible heuristic）（它可能会高估到达某个目标的代价），那么我们就有可能错过最优解，但是该启发式函数可能更准确，从而减少了需要扩展的节点数。例如，道路工程师知道弯道指数（detour index）的概念，它是应用于直线距离的乘数，用来说明道路的典型曲率。弯道指数1.3意味着如果两个城市的直线距离相距10千米，那么它们之间的最优路径的一个恰当的估计值是13千米。对于大多数地区，弯道指数的范围是1.2到1.6。
不仅仅是与道路相关的问题，我们还可以将这一思想应用于任何问题，我们采用一种称为加权A*搜索（weighted A* search）的方法，对启发式函数的值进行更重的加权，评价函数为
，其中
。
图3-21为一个网格世界中的搜索问题。在图3-21a中，A*搜索必须探索大部分状态空间才能找到最优解。在图3-21b中，加权A*搜索找到一个代价稍高的解，但搜索时间要快得多。我们看到，加权搜索使得已达状态的等值线专注于趋向某个目标。这意味着需要探索的状态变少，但如果最优路径偏离加权搜索的等值线（就像在这种情况下一样），则无法找到最优路径。一般来说，如果最优解的代价是C*，那么加权A*搜索将找到一个代价介于C*和W×C*之间的解；但在实践中，通常结果更接近于C*而不是W×C*。
图3-21 同一网格上的两种搜索：（a）A*搜索，（b）加权A*搜索，权重W = 2。灰色线条表示障碍，紫色线是一条从绿色起始点到红色目标点的路径，较小的点是每次搜索到达的状态。在这个特定问题上，加权A*搜索探索的状态数不到A*搜索探索的状态数的七分之一，找到的路径的代价只比最优代价大了5%
我们已经考虑过以各种方式组合g和h来评价状态的搜索方法；加权A*搜索可以看作是其他方法的一般化。
A*搜索：
一致代价搜索：
贪心最佳优先搜索：
加权A*搜索：
你可以称加权A*搜索为“有点贪心的搜索”：就像贪心最佳优先搜索一样，它使得搜索专注于趋向一个目标；但是，它不会完全忽略路径代价，并且会暂停代价高昂但进展甚微的路径。
次优的搜索算法有很多，其区别在于“足够好”的标准。在有界次优搜索（bounded suboptimal search）中，我们寻找一个能保证代价在最优代价的常数因子W倍内的解。加权A*搜索提供了这一保证。在有界代价搜索（bounded-cost search）中，我们寻找一个代价小于某个常数C的解。在无界代价搜索（unbounded-cost search）中，我们接受任何代价的解，只要能快速找到它。
无界代价搜索算法的一个例子是快速搜索（speedy search），它是一种贪心最佳优先搜索，使用到达目标所需动作个数的估计值作为启发式函数，不考虑这些动作的代价。因此，对于所有动作都具有相同代价的问题，它等于贪心最佳优先搜索，但当动作具有不同代价时，它往往会导致搜索快速找到一个代价可能很高的解。
3.5.5 内存受限搜索
A*搜索的主要问题是它对内存的使用较多。在本节中，我们将介绍一些可以节省空间的实现技巧和一些能够更好地利用可用空间的全新算法。
内存被分为frontier状态和reached状态。在我们所实现的最佳优先搜索中，边界上的状态存储在两个位置：边界中的一个节点（因此我们可以决定下一步扩展哪个节点）和已达状态表中的一个表项（因此我们知道之前是否访问过该状态）。对于许多问题（例如探索网格），这种重复不是关注点，因为frontier要比reached小得多，所以复制边界中的状态所需内存相对较少。但是有些算法实现只保留这两个位置中的其中一个，从而节省了一点空间，其代价是算法变得更复杂（可能会减慢速度）。
另一种可能性是，当我们能够证明不再需要某些状态时，就将它们从reached中删除。对于某些问题，我们可以利用分离性质（图3-6），同时禁止掉头行动，以确保所有行动要么是从边界向外移动，要么是移动到另一个边界状态。在这种情况下，我们只需检查边界就能判断是否有冗余路径，并且可以删除reached状态表。
对于其他问题，我们可以维护引用计数（reference count）——到达某一状态的次数，并且在再也没有路径可以到达该状态时将其从reached表中删除。例如，在网格世界中，每个状态只能从它的4个邻居状态到达，一旦我们已经到达了一个状态4次，就可以将它从表中删除。
现在，我们考虑旨在节省内存使用的新算法。
束搜索（beam search）对边界的大小进行了限制。最简单的方法是只保留具有最优f值的k个节点，放弃其他已扩展节点。这当然会导致搜索变成不完备的和次优的算法，但我们可以选取合适的k以充分利用可用内存，算法执行速度也会更快，因为它只扩展了较少的节点。对于许多问题，它可以找到很好的近似最优解。你可以将一致代价搜索或A*搜索看作在同心等值线的各个方向扩展，而将束搜索看作只探索这些等值线的主要部分，即包含k个最佳候选的部分。
另一种形式的束搜索并不严格限制边界的大小，而是保留f值在最优f值的
范围内的所有节点。这样的话，当存在几个强得分节点时，只会保留几个节点，但如果不存在强节点，则会保留更多节点，直到出现一个强节点。
迭代加深A*搜索（iterative-deepening A* search，IDA*）之于A*搜索，就像迭代加深搜索之于深度优先搜索一样：IDA*既拥有A*的优点，又不要求在内存中保留所有已达状态，这样做的代价是需要多次访问某些状态。它是一种非常重要且常用的用于解决内存不足问题的算法。
在标准的迭代加深搜索中，截断值为深度，每次迭代深度增加1。而在IDA*中，截断值是f代价（g + h）；在每次迭代中，新的截断值为超过上一次迭代截断值的节点中最小的f代价。换句话说，每次迭代都会彻底地搜索一个f等值线，找到一个刚好超出该等值线的节点，并使用该节点的f代价作为下一个等值线。像8数码这样的问题，每条路径的f代价都是整数，这非常有效地使得每次迭代都朝着目标稳步前进。如果最优解的代价是C*，那么迭代的次数不可能超过C*（例如，最难的8数码问题的迭代次数不超过31）。但对于每个节点的f代价都不相同的问题，每一个新的等值线可能只包含一个新节点，并且迭代次数可能等于状态数。
递归最佳优先搜索（recursive best-first search，RBFS）（见图3-22）试图模拟标准的最佳优先搜索的操作，但仅仅使用线性空间。RBFS类似于递归深度优先搜索，但它不是沿着当前路径无限地向下搜索，而是使用f_limit变量跟踪从当前节点的任意祖先节点可得到的最优备选路径的f值。如果当前节点超过了这个限制，那么递归将回到备选路径上。随着递归的展开，RBFS将路径上每个节点的f值替换为一个倒推值（backed-up value）——其子节点的最优f值。通过这种方式，RBFS可以记住被它遗忘的子树中最优叶节点的f值，因此，在之后的某个时刻，RBFS可以决定是否要重新扩展该子树。图3-23展示了RBFS是如何到达Bucharest的。
图3-22 递归最佳优先搜索算法
在一定程度上，RBFS比IDA*更高效，但仍然存在重复生成大量节点的问题。在图3-23的示例中，RBFS沿着经过Rimnicu Vilcea的路径，然后“改变主意”去尝试经过Fagaras，然后又“回心转意”。之所以会发生这些改变，是因为每次扩展当前的最优路径时，它的f值很可能增加——对于靠近目标的节点，h值通常不那么乐观。当这种情况发生时，次优路径可能会成为最优路径，因此搜索必须回溯。每一次改变对应于IDA*的一次迭代，并且可能需要多次重新扩展已经遗忘的节点，以重建最优路径，并对该路径再扩展一个节点。
图3-23 使用RBFS搜索到Bucharest的最短路线的各个阶段。每次递归调用的f_limit值标注在每个当前节点的上方，每个节点上都标有它的f代价。（a）沿着经过Rimnicu Vilcea的路径前进，直到当前最优叶节点（Pitesti）的值比最优备选路径（Fagaras）差。（b）递归回溯，被遗忘子树的最优叶节点值（417）被备份到Rimnicu Vilcea；接着扩展Fagaras，得到最优叶节点值450。（c）递归回溯，被遗忘子树的最优叶节点值（450）被备份到Fagaras；然后扩展Rimnicu Vilcea。这一次，因为最优备选路径（经由Timisoara）的代价至少为447，所以继续扩展Bucharest
如果启发式函数h(n)是可容许的，那么RBFS是最优的。它的空间复杂性在最深的最优解的深度上是线性的，但时间复杂性很难刻画：既取决于启发式函数的准确性，也取决于最优路径随节点扩展变化的频率。它按照f得分递增的顺序来扩展节点，即使f是非单调的。
IDA*和RBFS使用内存太少，它们的时间复杂性会受到影响。在两次迭代之间，IDA*只保留一个数值：当前的f代价限制。RBFS在内存中保留了更多的信息，但它只使用线性空间：即使有更多的内存可用，RBFS也无法利用。因为它们会遗忘它们所做的大部分事情，这两种算法都可能会多次重复探索相同状态。
因此，确定我们有多少可用内存并允许算法使用所有内存似乎是明智的。执行这样操作的两种算法是MA*（memory-bounded A*，内存受限的A*）和SMA*（simplified MA*，简化的MA*）。SMA*更简单一些，所以我们介绍SMA*。SMA*很像A*算法，不断扩展最优叶节点，直到内存被填满。此时，它不能再为搜索树添加新节点，除非删除旧节点。SMA*总是丢弃最差的叶节点，即f值最大的叶节点。和RBFS一样，SMA*将被遗忘节点的值备份到其父节点。这样，被遗忘子树的祖先知道该子树中最优路径的质量。有了这一信息，只有在所有其他路径看起来都比它已经遗忘的路径更差时，SMA*才会重新生成该子树。这意味着如果节点n的所有后代都被遗忘了，那么尽管我们不知道从n开始应该走哪条路径，但我们仍知道是否应该从n开始走。
本书附带的在线代码库中描述了完整的SMA*算法。有一点值得注意，我们之前提到SMA*将扩展最优叶节点，删除最差叶节点。如果所有叶节点的f值都相同呢？为了避免算法选择同一个节点进行删除和扩展操作，SMA*扩展最新的最优叶节点并删除最老的最差叶节点。当只有一个叶节点时，这两者是同一个节点，但在这种情况下，当前的搜索树一定是一条从根节点到叶节点的占满所有内存的单一路径。如果叶节点不是目标节点，那么即使它在最优解路径上，也无法在可用内存范围内得到这个解。因此，完全可以丢弃该节点，就好像它没有后继节点一样。
如果存在任意可达解，也就是说，如果最浅的目标节点的深度d小于内存大小（用节点数表示），那么SMA*就是完备的。如果存在可达的最优解，那么SMA*就是最优的；否则，就返回当前最优的可达解。在实践中，SMA*是寻找最优解的一个相当稳健的选择，特别是当状态空间是一个图、行动代价不一致，并且生成节点的总开销相比维护边界集和已达集的总开销更大时。
然而，在非常困难的问题上，常常会出现SMA*被迫在许多候选解路径之间来回不断切换的情况，只有一小部分路径可以存入内存。［这类似于磁盘分页系统中的抖动（thrashing）问题。］那么，重复生成相同节点就需要额外的时间，这意味着，在给定无限内存的情况下可以用A*实际求解的问题，对于SMA*将变得难以处理。也就是说，从计算时间的角度，内存限制会使问题变得难以处理。虽然还没有现有理论解释如何在时间和内存之间权衡，但这似乎是一个不可避免的问题。唯一的出路是放弃最优性要求。
3.5.6 双向启发式搜索
我们发现，在单向最佳优先搜索中，使用f(n) = g(n) + h(n)作为评价函数可以得到A*搜索，保证找到代价最优的解（假设h是可容许的），同时在所扩展的节点数上效率最优。
在双向最佳优先搜索中，我们也可以尝试使用f(n) = g(n) + h(n)，但遗憾的是，即使使用可容许的启发式函数，算法也不能保证可以找到代价最优的解，更不能保证效率最优。可以证明的是，在双向搜索中一定会被扩展的并不是单个的节点，而是节点对（分别来自两个边界），因此任何效率证明都必须考虑节点对（Eckerle et al., 2017）。
我们先介绍一些新的符号。对于正向搜索（以初始状态作为根节点）中的节点，我们用fF(n) = gF(n) + hF(n)作为评价函数；对于反向搜索（以某个目标状态作为根节点）中的节点，我们用fB(n) = gB(n) + hB(n)作为评价函数。尽管正向搜索和反向搜索求解的是同一个问题，但它们具有不同的评价函数，这是因为，启发式函数依据其努力方向是目标状态还是初始状态而有所不同。我们假设启发式函数是可容许的。
考虑从初始状态到节点m的正向路径和从目标到节点n的反向路径。我们可以如下定义一个解代价的下界（这个解先沿着前向路径从初始状态到达m，然后以某种方式到达n，最后再沿着后向路径从n到达目标）。
换句话说，这样一条路径的代价一定不小于两部分路径代价之和（因为它们之间的剩余连接一定具有非负代价），而且也一定不小于任一部分的f代价估计值（因为启发式的估计是乐观的）。因此，有如下的定理：对于任意一对节点m和n，若lb(m, n)小于最优代价C*，那么算法必须扩展m或n，因为经过这两个节点的路径是一个潜在的最优解。然而，一个难题是我们无法确定扩展这两者中的哪个节点才是最优的，因此，没有一个双向搜索算法可以保证效率最优——如果算法总是首先选择一对节点中错误的那个进行扩展，那么任何算法都可能需要扩展到最小节点数两倍的节点。一些双向启发式搜索算法显式地管理一个(m, n)节点对队列，但我们将坚持双向最佳优先搜索（图3-14），它有两个边界优先队列，并使用模拟lb准则的评价函数：
接下来要扩展的节点将是f2值最小的节点；它可以来自任何一个边界。这个f2函数保证算法永远不会扩展（来自任一边界的）
的节点。当两个边界相交时，任一边界内的节点都不存在超过C*/2的路径代价，在这种意义上，我们可以说搜索的两部分“在中间相遇”。图3-24为一个双向搜索的示例。
图3-24 双向搜索维护两个边界：左半部分，节点A和B是开始状态的后继；右半部分，节点F是目标状态的逆向后继。每个节点都标有f = g + h值和f2 = max(2g, g + h)值。（g值是每个箭头上所显示的动作代价的总和；h值是任意的，而且不能从图中的任何内容推出。）最优解“开始-A-F-目标”的代价C* = 4 + 2 + 4 = 10，这意味着一个在中间相遇的双向算法不应该扩展任何
的节点；实际上，下一个要扩展的节点是A或F（g = 4），这将引导我们找到一个最优解。如果我们首先扩展f代价最低的节点，那么下一个扩展的将是B和C，D和E将与A并列，但它们的
，因此当f2是评价函数时它们永远不会被扩展
我们已经介绍了一种方法，即用hF估计到目标的距离（或者说，当问题有多个目标状态时，估计到最近目标的距离），用hB估计到开始状态的距离。这就是所谓的front-to-end搜索。另一种方法是front-to-front搜索，它试图估计到另一个边界的距离。显然，如果边界内有数百万个节点，那么对每个节点应用启发式函数然后取最小值是非常低效的。但它可以从边界中抽样几个节点。在某些特定问题域中，可以对边界进行总结，例如，在网格搜索问题中，我们可以递增地计算边界的界限框，并使用到界限框的距离作为启发式函数。
双向搜索有时比单向搜索更有效，有时则不然。一般来说，如果我们有一个很好的启发式函数，那么A*搜索会生成专注于目标的搜索等值线，使用双向搜索则增益不大。使用一般的启发式函数时，在中间相遇的双向搜索往往会扩展较少的节点，因此双向搜索是首选方法。在启发式函数较差的最坏情况下，搜索算法将不再专注于目标，并且双向搜索具有与A*相同的渐近复杂性。使用f2评价函数和可容许的启发式函数h的双向搜索算法是完备且最优的。
3.6 启发式函数
在本节中，我们将研究启发式函数的准确性是如何影响搜索性能的，并考虑如何构造启发式函数。我们将8数码问题作为主要示例。如3.2节所述，它的目标是将滑块水平或竖直地滑动到空格中，直到棋盘布局与目标布局一致（图3-25）。
图3-25 8数码问题的典型实例。最短的解需要26步动作
在一个8数码问题中，存在9!/2 = 181 400个可达状态，所以搜索算法可以轻松地将它们全部保存在内存中。但是对于15数码问题，存在16!/2个状态（超过10万亿个），因此，为了搜索这个空间，我们需要借助一个较好的可容许的启发式函数。对于15数码问题，这样的启发式函数有着悠久的历史。下面介绍两个常用的选择。
● h1 = 错位滑块的数量（不包括空格）。图3-25中，所有的8个滑块都不在原位，所以开始状态的h1 = 8。h1是一个可容许的启发式函数，因为任何错位滑块都至少需要一次移动才能回到正确的位置。
● h2 = 滑块到其目标位置距离的总和。因为滑块不能沿对角线移动，所以距离是水平距离和垂直距离之和——有时称为城市街区距离或曼哈顿距离（Manhattan distance）。h2也是可容许的，因为任何移动操作所能做的就是将一个滑块向目标移近一步。图3-25中开始状态的滑块1到滑块8得到的曼哈顿距离为
正如我们希望的那样，这两种方法都没有高估实际的解代价26。
3.6.1 启发式函数的准确性对性能的影响
一种描述启发式函数质量的方法是有效分支因子（effective branching factor）b*。如果针对一个特定问题，A*搜索所生成的总节点数是n，而解的深度是d，那么b*就是深度为d的均衡树要包含n + 1个节点所必需的分支因子。因此有
例如，如果A*用52个节点在第5层上找到了一个解，那么有效分支因子是1.92。在不同的问题实例中，有效分支因子可能会发生变化，但通常对于特定领域（如8数码问题），在所有复杂的问题实例中它都是相当恒定的。因此，对一小部分问题的b*进行实验测量可以为启发式函数的总体有用性提供良好的指导。设计良好的启发式函数的b*接近1，使得我们能以合理的计算代价求解相当大的问题。
科尔夫和里德（Korf and Reid, 1998）认为，对于一个使用给定启发式函数h的A*剪枝，刻画其效果的一个更好方式是：有效深度（effective depth）相比于真实深度的减少量kh（一个常数）。这意味着相较于无信息搜索的代价O(bd)，上述方法的总搜索代价为
。他们在魔方和n数码问题上的实验结果表明，这一公式可以准确地预测各种解长度范围内（至少对于大于kh的解长度）的抽样问题实例的总搜索代价。
在图3-26中，我们生成了随机8数码问题，并使用无信息广度优先搜索和使用h1或h2的A*搜索求解该问题，报告了每种搜索策略和每种解长度所生成的平均节点数及相应的有效分支因子。结果表明，h2优于h1，两者都优于无启发式算法。
图3-26 使用广度优先搜索、使用h1（错位滑块）的A*搜索或使用h2（曼哈顿距离）的A*搜索求解8数码问题的搜索代价和有效分支因子的比较。每个解长度d（6～28）的数据为100多个实例的平均结果
有人可能会问，h2是否总是优于h1。答案是“基本上，是的”。从这两种启发式函数的定义可以看出，对于任意节点n，都有
。因此我们说h2占优于（dominate）h1。优势可以直接转化为效率：使用h2的A*永远不会比使用h1的A*扩展更多的节点（除了
的节点）。证明很简单。回想一下3.5.3节观察到的，每个的节点都一定会被扩展。也就是说，当h一致时，每个
的节点都一定会被扩展。但是，因为对于所有节点，h2至少和h1一样大，每个在h2下一定会被扩展的节点在h1下也一定会被扩展，而h1还可能导致其他的节点也被扩展。因此，通常情况下，只要启发式函数是一致的并且其计算时间不太长，使用具有较高值的启发式函数效果都会更好。
3.6.2 从松弛问题出发生成启发式函数
我们已经看到，对于8数码问题，h1（错位滑块）和h2（曼哈顿距离）都是相当好的启发式函数，其中h2更好。人们是怎么想出h2这样的启发式函数的？计算机是否有可能自动地设计出这种启发式函数？
h1和h2是对8数码问题剩余路径长度的估计，但对简化版本的问题来说，它们也是非常精确的路径长度。如果改变游戏规则，即滑块可以移动到任何地方，而不是只能移动到相邻的空格，那么h1将给出最短解的准确长度。类似地，如果一个滑块可以向任意方向移动一个方格，甚至移动到一个被占用的方格上，那么h2将给出最短解的准确长度。减少了对动作的限制条件的问题称为松弛问题（relaxed problem）。松弛问题的状态空间图是原始状态空间的一个超图，因为删除限制条件会导致原图中边的增加。
因为松弛问题向状态空间图中添加了一些边，根据定义，原问题的任一最优解也是松弛问题的一个解；但是，如果增加的边提供了捷径，松弛问题可能有更好的解。因此，松弛问题中最优解的代价可以作为原问题的一个可容许的启发式函数。此外，因为得到的启发式函数是松弛问题的准确代价，所以它一定满足三角不等式，因此它是一致的（见3.5.2节）。
如果用形式语言定义一个问题，则可以自动构造它的松弛问题。[14]例如，如果将8数码问题的行动描述为
[14] 在第8章和第11章中，我们将介绍适用于此任务的形式语言：有了可操纵的形式化描述，就可以自动化地构建松弛问题。现在，我们先使用自然语言。
如果方格X与方格Y相邻，且Y是空格，那么滑块可以从方格X移动到方格Y。
我们可以通过删除一个或两个条件来生成3种松弛问题。
（a）如果方格X与方格Y相邻，那么滑块可以从方格X移动到方格Y。
（b）如果方格Y是空格，那么滑块可以从方格X移动到方格Y。
（c）滑块可以从方格X移动到方格Y。
由（a）可以推导出h2（曼哈顿距离）。原因是，如果我们将每个滑块依次移动到其目标位置，那么h2就是准确的步数。由（b）推导出的启发式函数将在习题3.GASC中讨论。由（c）我们可以推导出h1（错位滑块），因为如果可以仅用一步就将滑块移动到其预期目标位置，那么h1就是准确的步数。需要注意的是，通过这种方法生成的松弛问题本质上不需要搜索就能求解，因为松弛规则将问题分解为8个独立的子问题。如果松弛问题本身很难求解，那么获取相应的启发式函数值的代价将非常高。
Absolver程序可以通过“松弛问题”方法及各种其他技术从问题定义中自动生成启发式函数（Prieditis, 1993）。Absolver为8数码问题生成了一种新的启发式函数，它优于任何已有的启发式函数。此外，Absolver为著名的魔方问题找到了第一种有效的启发式函数。
如果一个可容许的启发式函数集合h1, …, hm可以求解同一个问题，但没有一个函数明显优于其他函数，那么我们应该选择哪个函数？事实证明，我们可以通过如下定义，得到最优的启发式函数：
这种复合启发式函数将选择对于所讨论节点最准确的函数。因为hi都是可容许的，所以h也是可容许的（如果hi都是一致的，则h也是一致的）。此外，h优于所有组成它的启发式函数。唯一的缺点是h(n)的计算时间更长。如果考虑这一问题，另一种选择是在每次评价时随机选择一个启发式函数，或者使用机器学习算法来预测哪个启发式函数是最优的。这样做可能会导致启发式函数失去一致性（即使每个hi都是一致的），但在实践中，它通常能更快地求解问题。
3.6.3 从子问题出发生成启发式函数：模式数据库
可容许的启发式函数也可以由给定问题的子问题（subproblem）的解代价推导得到。例如，图3-27为图3-25中8数码问题实例的一个子问题。子问题涉及将滑块1、2、3、4和空格分别放置到正确位置。显然，这个子问题最优解的代价是完整问题代价的一个下界。在某些情况下，它比曼哈顿距离更准确。
图3-27 图3-25中所给出的8数码实例的子问题。任务是将滑块1、2、3、4和空格放置到正确位置，而不考虑其他滑块的情况
模式数据库（pattern database）的思想是为每个可能的子问题（在我们的示例中，为4个滑块和空格的所有可能排列）存储准确的解代价。（数据库中将有9×8×7×6×5 = 15 120种模式。其他4个滑块与子问题的求解无关，但移动这些滑块将计入子问题的解代价。）然后，通过在数据库中查找相应的子问题，为搜索过程中遇到的每个状态计算一个可容许的启发式函数hDB。数据库本身是从目标状态反向搜索并记录所遇到的每个新模式的代价来构建的[15]；这一搜索的开销将分摊到后续的问题实例中，因此如果我们需要求解很多问题，那么这种方法是有意义的。
[15] 通过从目标反向回溯，可以立即获得所遇到的每个实例的准确的解代价。这是动态规划的一个示例，我们将在第17章进一步讨论。
与空格搭配的滑块1-2-3-4的选择是相当随意的；我们还可以为5-6-7-8、2-4-6-8等建立数据库。每个数据库产生一种可容许的启发式函数，正如前文所述，可以通过取最大值对这些启发式函数进行组合。这种组合的启发式函数要比曼哈顿距离精确得多；求解随机15数码问题时所生成的节点数可以减少到千分之一。然而，每增加一个数据库，收益会随之减少，内存和计算成本也会增加。
你们可能想知道从1-2-3-4数据库和5-6-7-8数据库中得到的启发式函数是否可以相加，因为这两个子问题似乎没有重叠。这会是一个可容许的启发式函数吗？答案是否定的，因为对于一个给定的状态，1-2-3-4子问题和5-6-7-8子问题的解一定会有一些重复操作——1-2-3-4不可能在不接触5-6-7-8的情况下移动到位，反之亦然。但是，如果我们不计入这些操作，换句话说，如果我们让其他滑块直接消失呢？也就是说，我们不记录求解1-2-3-4子问题的总代价，而只记录与1-2-3-4有关的操作数。那么这两个代价的和仍然是求解完整问题代价的一个下界。这就是不相交模式数据库（disjoint pattern database）的思想。有了这样的数据库，可以在几毫秒内求解随机的15数码问题——与使用曼哈顿距离相比，生成的节点数不到原来的万分之一。对于24数码问题，则可以获得大约一百万倍的加速。不相交模式数据库适用于滑块数码问题，因为每次移动只涉及一个滑块，因而原问题可以被划分成若干个子问题使得每次移动只影响一个子问题。
3.6.4 使用地标生成启发式函数
一些在线服务可以托管含有数千万个顶点的地图，并在毫秒内找到代价最优的驾驶路线。即使是我们之前提到的最优的搜索算法，做到这一点也要比这些在线服务多耗费100万倍的时间。那在线服务是怎么做到这一点的呢？这里有很多技巧，但最重要的是对一些最优路径代价的预计算（precomputation）。虽然预计算可能相当耗时，但只需完成一次预计算，就可以摊销数十亿用户的搜索请求。
我们可以通过预计算并存储每对顶点之间的最优路径代价来生成完美的启发式函数。这需要
空间和
时间——对于含有1万个顶点的图很实用，但对于1000万个顶点，这样的复杂性不可接受。
更好的方法是从顶点中选择一些（也许10个或20个）地标点（landmark point）[16]。然后，对于图中每个地标L和每个其他顶点v，我们计算并存储C*(v, L)，即从v到L的最优路径的准确代价。（我们同样需要C*(L, v)；在无向图上，C*(L, v)与C*(v, L)相同；在有向图上，如单行道，我们则需要单独计算C*(L, v)。）给定存储的C*表，我们可以很容易地创建出一个高效的（尽管是不可容许的）启发式函数：在所有地标中，从当前节点到地标然后到目标节点代价的最小值为
[16] 地标点有时被称为“枢轴”或“锚点”。
如果最优路径刚好经过一个地标，这个启发式函数将是准确的；否则，这个启发式函数就是不可容许的——它高估了到目标的代价。在A*搜索中，如果启发式函数是准确的，那么一旦到达一个位于最优路径上的节点，此后所扩展的每个节点都将位于最优路径上。把等值线想象为沿着这条最优路径前进。搜索将沿着最优路径进行，在每次迭代中加入一个代价为c的动作，然后到达一个h值减少c的结果状态，这意味着在整条路径上总的f = g + h得分将保持在常量C*。
一些寻径算法通过在图中添加捷径（shortcut）——人工定义的对应于一条最优多行动路径的边——来节省更多的时间。例如，如果我们在美国最大的100个城市之间预先定义了捷径，并且尝试从位于加利福尼亚州的加利福尼亚大学伯克利分校校区导航到纽约的纽约大学，那么我们可以走萨克拉门托（Sacramento）到曼哈顿（Manhattan）之间的捷径，一次动作就能覆盖90%的路径。
hL(n)是高效的，但不是可容许的。只要稍加注意，我们就可以提出一种既高效又可容许的启发式函数：
这被称为差分启发式（differential heuristic）函数（因为包含减法）。可以把它理解为在比目标还要远的某个位置设置一个地标点。如果目标恰好在从n到该地标点的最优路径上，那么“考虑从n到L的完整路径，然后减去这条路径的最后一部分，即从goal到L，即可得到从n到goal的这段路径的准确代价”。如果目标稍微偏离到地标的最优路径，启发式函数将是不准确的，但仍然是可容许的。比目标近的地标是没有用的；例如，一个恰好位于n和goal正中间的地标将导致hDH = 0，这是没有用的。
下面我们介绍几种选择地标点的方法。随机选择速度较快，但如果我们多花些功夫将地标分散开来，使得它们彼此之间不太接近，我们将得到更好的结果。贪心方法是随机选择第一个地标，然后找到离它最远的点，将其添加到地标集合中，接着在每次迭代中添加离最近地标最远的点。如果你有用户过去的搜索请求日志，那么你可以选择搜索中经常请求的地点作为地标。对于差分启发式函数，地标分布在图的周界上更好。因此，一个比较好的技术是找到图的质心，围绕质心划分出k个楔形（就像饼状图一样），并在每个楔形中选择离中心最远的顶点。
地标在寻径问题上尤其有效，这是由世界上道路的布局方式导致的：许多交通运输实际上都是在地标之间穿行，所以土木工程师在这些路线上修建最宽、最快的道路；地标式搜索可以更轻松地复原这些路线。
3.6.5 学习以更好地搜索
我们介绍了几种固定的搜索策略（广度优先、A*等），这些都是计算机科学家精心设计和编程实现的。那么智能体能自己学习如何更好地搜索吗？答案是肯定的，这种方法基于一个重要的概念，元级状态空间（metalevel state space）。元级状态空间中的每个状态将捕捉在普通状态空间（例如罗马尼亚地图）进行搜索的程序的内部（计算）状态。［为了区分这两个概念，我们将罗马尼亚地图称为对象级状态空间（object-level state space）。］例如，A*算法的内部状态由当前搜索树组成。元级状态空间中的每个动作都是一个改变内部状态的计算步；例如，A*中的每一个计算步扩展一个叶节点，并将其后续节点添加到树中。因此，图3-18展示了一个逐渐增大的搜索树序列，它描述了元级状态空间中的一条路径，路径上的每个状态都是一棵对象级搜索树。
现在，图3-18中的路径共有5步，包括一个扩展Fagaras的步骤，这一步不是非常有用。对于更困难的问题，将存在很多这样的错误步骤，元级学习（metalevel learning）算法可以从这些经验中学习，以避免探索毫无希望的子树。这种学习算法将在第22章中介绍。学习的目标是对计算开销和路径代价进行权衡，以最小化求解问题的总代价。
3.6.6 从经验中学习启发式函数
我们已经看到，生成启发式函数的一种方法是设计一个容易找到最优解的松弛问题，另一种选择是从经验中学习。这里的“经验”意味着，例如，求解大量8数码问题。一个8数码问题的每个最优解都提供了一个“(目标,路径)”对作为示例。可以利用学习算法通过这些示例构造一个函数h，（幸运的话）它可以近似搜索过程中出现的其他状态的真实路径代价。这些方法中的大多数学习到的都是启发式函数的一个不完美的近似，因此存在启发式函数不可容许的风险。这必然导致算法需要在学习时间、搜索运行时间和解的代价之间进行权衡。机器学习技术将在第19章中介绍。第22章中介绍的强化学习方法也适用于搜索问题。
如果除了原始状态描述外，还提供与预测启发式函数值相关的状态特征（feature），那么一些机器学习技术将表现得更好。例如，“错位滑块数”这一特征可能有助于预测8数码问题中状态与目标的实际距离。我们将这一特征记作x1(n)。我们可以使用100个随机生成的8数码配置，并收集其真实解代价的统计数据。我们可能会发现，当x1(n) = 5时，平均的解代价大约是14，等等。当然，可以使用多种特征。例如，第二个特征x2(n)可能是“在当前状态相邻而在目标状态中不相邻的滑块对的数量”。如何对x1(n)和x2(n)进行组合来预测h(n)？一种常见的方法是线性组合：
可以调整常数c1和c2以适应随机生成的配置中实际数据的值。我们希望c1和c2都是正值，因为错位滑块和不正确的相邻对都会使得问题更难求解。注意，这个启发式函数满足目标状态h(n) = 0的条件，但它不一定是可容许的或一致的。
小结
本章对搜索算法进行了介绍，智能体可以用这些算法在各种环境中选择动作序列——只要环境是回合式的、单智能体的、完全可观测的、确定性的、静态的、离散的和已知的。算法需要在搜索所需时间、可用内存和解的质量之间进行权衡。如果我们对于启发式函数的形式拥有额外的领域相关知识来估计给定状态离目标有多远，或者我们预计算涉及模式或地标的部分解，算法会更高效。
● 在智能体开始搜索之前，必须形式化一个良定义的问题。
● 问题由5部分组成：初始状态、动作集合、描述这些动作结果的转移模型、目标状态集合和动作代价函数。
● 问题的环境用状态空间图表示。通过状态空间（一系列动作）从初始状态到达一个目标状态的路径是一个解。
● 搜索算法通常将状态和动作看作原子的，即没有任何内部结构（尽管我们在学习时引入了状态特征）。
● 根据完备性、代价最优性、时间复杂性和空间复杂性来评估搜索算法。
● 无信息搜索方法只能访问问题定义。算法构建一棵搜索树，试图找到一个解。算法会根据其首先扩展的节点而有所不同。
❏ 最佳优先搜索根据评价函数选择节点进行扩展。
❏ 广度优先搜索首先扩展深度最浅的节点；它是完备的，对于单位动作代价是最优的，但具有指数级空间复杂性。
❏ 一致代价搜索扩展路径代价g(n)最小的节点，对于一般的动作代价是最优的。
❏ 深度优先搜索首先扩展最深的未扩展节点。它既不是完备的也不是最优的，但具有线性级空间复杂性。深度受限搜索增加了一个深度限制。
❏ 迭代加深搜索在不断增加的深度限制上调用深度优先搜索，直到找到一个目标。当完成全部循环检查时，它是完备的，同时对于单位动作代价是最优的，且具有与广度优先搜索相当的时间复杂性和线性级空间复杂性。
❏ 双向搜索扩展两个边界，一个围绕初始状态，另一个围绕目标，当两个边界相遇时搜索停止。
● 有信息搜索方法可以访问启发式函数h(n)来估计从n到目标的解代价。它们可以访问一些附加信息，例如，存有解代价的模式数据库。
❏ 贪心最佳优先搜索扩展h(n)值最小的节点。它不是最优的，但通常效率很高。
❏ A*搜索扩展f(n) = g(n) + h(n)值最小的节点。在h(n)可容许的条件下，A*是完备的、最优的。对于许多问题，A*的空间复杂性仍然很高。
❏ 双向A*搜索有时比A*搜索本身更高效。
❏ IDA*（迭代加深A*搜索）是A*搜索的迭代加深版本，它解决了空间复杂性问题。
❏ RBFS（递归最佳优先搜索）和SMA*（简化的内存受限A*）搜索是健壮的最优搜索算法，它们仅使用有限的内存；如果时间充足，它们可以解决对A*来说内存不足的问题。
❏ 束搜索限制了边界的大小；因此它是非完备的、次优的，但束搜索通常能找到相当好的解，运行速度也比完备搜索更快。
❏ 加权A*搜索将搜索专注于一个目标，以扩展更少的节点，但它牺牲了最优性。
● 启发式搜索算法的性能取决于启发式函数的质量。我们有时可以通过松弛问题定义、在模式数据库中存储预计算的子问题的解代价、定义地标点，或者从问题类的经验中学习来构建良好的启发式函数。
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e59810”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。