第3章 通过搜索进行问题求解

第3章 通过搜索进行问题求解

本章讨论当问题求解不能通过单个行动一步完成时，Agent 如何找到一组行动序列达到目标。搜索即是指从问题出发寻找解的过程。

在第2章中讨论的最简单的 Agent 是反射 Agent，这类 Agent 存有在何种状态下可采取何种行动的直接映射表，它们的行为就取决于这种映射。有些环境中 Agent 的这种映射表可能非常大，导致占用很多存储空间或者查表消耗的时间太长而无法学习，Agent 在这样的环境中难以运转。另一方面，基于目标的 Agent 会考虑将要采取的行动及行动的可能后果，即与目标还有多远。

本章讨论基于目标的 Agent 中的一种，称为问题求解 Agent（problem-solving Agent）。问题求解 Agent 使用原子（atomic）表示（参见 2.4.7 节）：世界的状态被视为一个整体，对问题求解算法而言没有可见的内部结构。使用更先进的要素化（factored）或结构化（structured）表示的基于目标的 Agent，通常被称为规划 Agent（planning Agent），将在第 7 章和第 10 章讨论。

要进行问题求解，首先要讨论的是对问题及其解的精确定义，我们将通过一些实例来说明如何描述一个问题及其解。接着我们介绍一些求解此类问题的通用的搜索算法。首先讨论无信息的（uninformed）搜索算法——无信息是指算法除了问题定义本身没有任何其他信息。尽管这些算法有的可以用于求解任何问题，但此类算法效率都不好。另一方面，有信息（Informed）的搜索算法，利用给定的知识引导能够更有效地找到解。

这章中我们会把任务环境简化，限定问题的解是一组有固定顺序的行动。更一般的情况是 Agent 的行动决策将随着未来感知数据的改变而改变，这将在第4章讨论。

本章将使用渐进复杂度（即 O() 表示法）和 NP 完全性的概念。不熟悉这些概念的请参看附录 A。

3.1 问题求解 Agent

我们假设智能 Agent 要最大化其性能度量。如同我们在第 2 章中提到的，如果 Agent 能采纳一个目标（goal）并试图去满足它，最大化性能度量的问题就可能会简化。我们首先讨论 Agent 为何这样做及该如何做。

想象一个 Agent 正在罗马尼亚的 Arad 享受旅游假期。该 Agent 的性能度量包含很多方面：它想要晒黑些，想学习罗马尼亚语，欣赏风景，享受夜生活（诸如此类），还要避免宿醉，等等。这个 Agent 决策问题有些复杂，要权衡许多方面的因素，同时要阅读大量的旅游指南。现在假设该 Agent 有一张第二天飞离 Bucharest 的不能改签也不能退的机票。在这种情况下，Agent 建立合理目标：抵达 Bucharest。导致不能按时到达 Bucharest 的行动方案

将不再予以考虑，因此该 Agent 的决策问题被大幅度简化。Agent 的行动能力可能帮它达到各种目的，但是此时的目标限制了这些行动，帮助 Agent 组织行动序列，以达到最终目标。基于当前的情形和 Agent 的性能度量进行目标形式化（goal formulation）是问题求解的第一个步骤。

我们将目标考虑成是世界的一个状态集合——目标被满足的那些状态的集合。Agent的任务是找出现在和未来如何行动，以使它达到一个目标状态。在 Agent 能做这个之前，它（或是我们代表它）需要确定它能完成的行动种类和行动能带来的状态变化。如果 Agent 试图在诸如“左脚前移 1 英尺”或“将方向盘向左旋转 1 度”的层次上考虑行动，它将可能永远无法找到走出停车场的路，更别说去 Bucharest 了，因为在那样的细节水平上世界的不确定性因素太多，而问题的解也将包含过多的步骤。问题形式化（problem formulation）是在给定目标下确定需要考虑哪些行动和状态的过程。后面我们将详细地讨论这个过程。现在我们假设 Agent 将在开车从一个主要城镇到另一个城镇的层次上考虑行动。因此每个状态表示 Agent 在一个特定的城镇中。

Agent 现在的目标是开车去 Bucharest，正在考虑从 Arad 先开往哪里。从 Arad 开出有三条道路分别前往 Sibiu、Timisoara 和 Zerind。这三条路没有一条能直接到达最终目标，所以除非 Agent 对罗马尼亚非常熟悉，它无法知道应该走哪条路 $ ^{1} $。换句话说，Agent 不知道这三条路中哪条路或哪个可能的行动是最好的，因为它对由每个行动之后的状态知道得不够多。如果 Agent 没有额外的知识——如我们在 2.3 节中提到过未知的环境——那么它就只能随机选择一个行动。这种糟糕的情况我们在第 4 章中讨论。

但是假设 Agent 有罗马尼亚的地图。地图上的每个点都可以向 Agent 提供信息：Agent 可以到达哪些状态和它可以采取哪些行动。Agent 可以利用这些信息假想整个旅程，考虑途经上述 3 个城镇后的后继阶段，试图找出最终能到达 Bucharest 的路。一旦 Agent 在地图上发现从 Arad 到 Bucharest 的路，它就可以完成相应的驾驶行动来达到它的目标。一般来说，一个 Agent 在面临多种未知值的选择时，可以首先检查那些最终导出已知价值的状态的未来行动，然后做出决策。

下面我们解释何为“检查未来行动”，在此之前我们还应具体了解环境的性质，这点在2.3节中有定义。现在，我们假定环境是可观察的，所以Agent总是知道当前状态。Agent在罗马尼亚开车，假设在司机到达地图上的每个城市时都会发现有标识标明该城市。我们假设该任务环境是离散的，所以在任一给定状态，可以选择的行动是有限的。这是正确的，因为在罗马尼亚游玩时，每个城市只与其他一小部分城市相邻。我们假设环境是已知的，所以Agent知道每个行动达到哪个状态。（拥有一份足够精确的地图以满足游玩问题的要求。）最后，我们假设环境是确定的，每个行动的结果只有一个。在理想条件下，这对罗马尼亚的Agent是正确的——这意味着如果Agent选择了从Arad开车前往Sibiu，那么它一定会到达Sibiu。当然，条件并不总是理想化的，我们会在第4章讨论这一点。

在这些假设下，任何问题的解是一个行动的固定序列。“当然！”，有人会说，“还能是什么？”也许，一般来说，它也可能是分支策略，在感知到抵达城市时会建议不同的行动

选择。例如，在不够理想化的条件下，Agent 可能计划从 Arad 开往 Sibiu 接着前往 Rimnicu Vilcea，但也可能要做好本来要去 Sibiu 结果却意外抵达 Zerind 的计划。幸运的是，如果 Agent 知道初始状态并且环境是已知的和确定的，它清楚地知道行动之后的状态。因为行动之后只有一个后果，问题求解才有可能继续选择后继的行动。

为达到目标，寻找这样的行动序列的过程被称为搜索。搜索算法的输入是问题，输出是问题的解，以行动序列的形式返回问题的解。解一旦找到，它所建议的行动将会付诸实施。这被称为执行阶段。那么，我们就完成了对 Agent 的简单设计，即“形式化、搜索、执行”，如图 3.1 所示。在完成对目标和对待求解问题的形式化之后，Agent 调用搜索过程进行问题求解。然后 Agent 用得到的解来导引行动，按照问题求解给出的解步骤逐一实施——通常是执行序列中的第一个行动——从序列中删除已完成的步骤。一旦解被执行，Agent 将形式化新的目标。

function SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action

persistent: seq, an action sequence, initially empty

state, some description of the current world state

goal, a goal, initially null

problem, a problem formulation

state ← UPDATE-STATE(state, percept)

if seq is empty then

goal ← FORMULATE-GOAL(state)

problem ← FORMULATE-PROBLEM(state, goal)

seq ← SEARCH(problem)

if seq = failure then return a null action

action ← FIRST(seq)

seq ← REST(seq)

return action

需要注意的是，Agent 在执行解的行动序列时，它无视它的感知信息，每当它选择了行动它都知道它将到达什么状态。Agent 在执行计划时是闭上了眼睛的，就是说，它十分确定行动后果是什么。控制理论把这称为开环系统，因为无视感知信息打破了 Agent 和环境之间的环路。

我们首先描述如何对待求解问题进行形式化，然后用本章的大部分篇幅专门介绍SEARCH函数的各种不同算法。在本章中我们不会讨论UPDATE-STATE和FORMULATE-GOAL这两个函数。

3.1.1 良定义的问题及解

一个问题可以用5个组成部分形式化地描述：

Agent 的初始状态。例如，在罗马尼亚问题中 Agent 的初始状态可以描述为 $ In(Arad) $。

描述 Agent 的可能行动。给定一个特殊状态 s，ACTIONS(s) 返回在状态 s 下可以执行的动作集合。我们称这些行动对状态 s 是可应用的。例如，考虑状态 In(Arad)，可应用的行动为：

$$ \{G o(S i b i u),G o(T i m i s o a r a),G o(Z e r i n d)\} $$

对每个行动的描述；正式的名称是转移模型，用函数 RESULT(s,a) 描述：在状态 s 下执行行动 a 后达到的状态。我们也会使用术语后继状态来表示从一给定状态出发通过单步行动可以到达的状态集合 $ ^{1} $。例如，

$$ RESULT(In(Arad),Go(Zerind))=In(Zerind) $$

总之，初始状态、行动和转移模型无疑就定义了问题的状态空间——即从初始状态可以达到的所有状态的集合。状态空间形成一个有向网络或图，其中结点表示状态，结点之间的弧表示行动（图3.2中的罗马尼亚地图就可以被解释为一个状态空间图，每条连线视为双向驾驶行动即双向边）。状态空间中的一条路径指的是通过行动连接起来的一个状态序列。

目标测试，确定给定的状态是不是目标状态。有时候目标状态是一个显式集合，测试只需简单检查给定的状态是否在目标状态集合中。在罗马尼亚问题中，目标状态集是一个单元素集合 $ \{In(Bucharest)\} $。有些时候目标状态并不是一个显式可枚举的目标状态集合，而是具备某些特定抽象属性的状态。例如，在国际象棋中，目标状态是指被“将死”的状态，即对方的国王在己方的攻击下已经无路可逃必死无疑。

路径耗散函数为每条路径赋一个耗散值，即边加权。问题求解 Agent 选择能反映它自己的性能度量的耗散函数。对于试图前往 Bucharest 的 Agent，时间是基本要素，

所以它的路径耗散可以是用公里数表示的路径长度。在本章中，我们假设一条路径的耗散值为该路径上的每个行动（每条边）的耗散值总和 $ ^{1} $。采用行动 a 从状态 s 走到状态 s'所需要的单步耗散用 $ c(s, a, s') $ 表示。罗马尼亚问题中的单步耗散即单步路程距离，如图3.2所示，我们假设单步耗散值是非负的 $ ^{2} $。

由上述元素即可定义一个问题，通常把它们组织在一起成为一个数据结构，并以此作为问题求解算法的输入。问题的解就是从初始状态到目标状态的一组行动序列。解的质量由路径耗散函数度量，所有解里路径耗散值最小的解即为最优解。

3.1.2 问题的形式化

3.1.1 节我们给出了罗马尼亚问题的形式化，用初始状态、行动、转移模型、目标测试和路径耗散来描述。这种形式化看起来是合理的，不过它依然只是个模型——一种抽象的数学描述——不是真实的事情。比较我们选择的简单状态描述， $ \ln(Arad) $，和实际的越野旅行，现实世界状态包括太多事情：同行的旅伴，收音机播放的节目，窗外的景色，附近是否有执法人员，到下一个休息点的距离、路况、天气情况等。我们选择的状态描述中不包括这些信息，因为它们与找到前往 Bucharest 的路径问题不相关。在表示中去除细节的过程被称为抽象。

不仅是状态描述要抽象，我们还需要对行动进行抽象。一个驾驶行动会造成很多影响。驾驶行为不仅改变了车辆和它的乘客的位置，它还花费了时间，消耗了汽油，产生了污染，以及改变了 Agent 自身（就像他们所说的，旅行拓展了视野）。我们的形式化则只考虑了位置的变化。我们同时也忽略了许多其他行动：打开收音机，欣赏窗外的景色，遇到执法人员而减速，等等。我们当然更不会将行动细节到“把方向盘向左转1度”这种层次上。

我们是否能够精确地定义合适的抽象层次？考虑对应于现实的世界状态和现实的行动序列，我们在前面选择了抽象化的状态和行动。现在考虑罗马尼亚问题抽象后的一个解：例如，从 Arad 到 Sibiu 到 Rimnicu Vilcea 到 Pitesti 到 Bucharest 的解路径。这个抽象解可以对应大量的更细节的解路径。例如，我们在从 Sibiu 开往 Rimnicu Vilcea 的途中听收音机，然后在剩下的旅途中关掉收音机。如果我们能够把任何抽象解扩展成为更细节的世界中的解，这种抽象就是有效的；一个充分条件是对于每个抽象为“在 Arad”的细节状态都有一条详细路径到达一些如“在 Sibiu”的状态，等等 $ ^{3} $。如果执行解中的每个行动比原始问题中的容易，那么这种抽象是有用的；在这种情况下，解路径中的每个行动要足够容易，以至于对于平均水平的驾驶 Agent 而言不用更进一步地搜索或者规划就能实施了。因此，选择一个好的问题抽象，包括在保持有效抽象的前提下去除尽可能多的细节和确保抽象后的行动容易完成。如果缺乏能力去构建有用的问题抽象，智能 Agent 将会被现实世界完全淹没。

3.2 问题实例

问题求解方法已经应用于各种不同的任务环境。我们列出一些大家熟知的问题，分别讨论玩具问题和现实世界问题。玩具问题试图描述或练习各种问题求解方法。可以对玩具问题给出简洁精确的描述，因此研究人员可以用它来比较各自算法的性能。人们真正关心的是现实世界问题的解。虽然现实世界问题通常没有意见一致的描述，我们会尽量给出一般意义下的问题形式化。

3.2.1 玩具问题

第2章中我们介绍过真空吸尘器世界（参见图2.2）。这个问题可以形式化如下：

状态：状态由 Agent 位置和灰尘位置确定。Agent 的位置有两个，每个位置都可能有灰尘。因此，可能的世界状态有 $ 2 \times 2^{2} = 8 $ 个。对于具有 n 个位置的大型环境而言，状态数为 $ n \times 2^{n} $。

初始状态：任何状态都可能被设计成初始状态。

行动：这个任务环境相对简单，每个状态下可执行的行动只有3个：Left，Right 和 Suck。大型的任务环境中还可能包括 Up 和 Down。

转移模型：行动会产生它们所期待的后果，除了在最左边位置不能 Left 再向左移动，在最右边位置不能再 Right 向右移动，在干净的位置进行 Suck 也没有效果。完整的状态空间如图 3.3 所示。

目标测试：检测所有位置是否干净。

路径消耗：每一步耗散值为1，因此整个解路径的耗散值是路径中的步数。

与现实世界相比较，上述玩具问题中位置是离散的、灰尘是离散的、清洁过程是可靠的，而且在清洁过程中它从不会把环境搞得更脏。在第4章中，我们将不考虑这些假设。

八数码问题游戏，如图3.4所示，包括一个 $ 3\times3 $的棋盘，棋盘上有8个数字棋子和一个空格。与空格相邻的棋子可以滑动到空格中。游戏目标是要达到一个特定的状态，如图中右侧所给出的状态。该问题可形式化如下：

状态：状态描述指明8个棋子以及空格在棋盘9个方格上的分布。

初始状态：任何状态都可能是初始状态。注意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为开始（习题3.4）。

后继函数：用来产生通过四个行动（把空位向 Left、Right、Up 或 Down 移动）能够达到的合法状态。

目标测试：用来检测状态是否能匹配图3.4中所示的目标布局（其他目标布局也是可能的）。

路径耗散：每一步的耗散值为1，因此整个路径的耗散值是路径中的步数。

这个问题我们在哪些地方做了抽象呢？行动被抽象为它的起始和结果状态，忽略了当棋子滑动时所走过的中间过程。这个问题的抽象还包括不考虑如下行动：棋子粘住的时候晃动棋盘、或者用小刀把棋子抠出来再放回去。我们保留和游戏规则有关的描述，避免陷入所有物理操作的细节。

八数码问题属于滑块问题家族，这类问题经常被用作 AI 中新的搜索算法的测试用例。滑块问题为 NP 完全问题，因此不要期望能找到在最坏情况下明显好于本章和下一章所描述的搜索算法的方法。八数码问题共有 9!/2 = 181 440 个可达到的状态，并且很容易求解。15 数码问题（在 4×4 的棋盘上）有大约 1.3 万亿个状态，用最好的搜索算法求解一个随机的实例的最优解需要几毫秒。24 数码问题（在 5×5 的棋盘上）的状态数可达 $ 10^{25} $ 个，求解随机实例的最优解可能需要几个小时。

八皇后问题的目标是在国际象棋棋盘中放置8个皇后，使得任何一个皇后都不会攻击到其他任一皇后。（皇后可以攻击和它在同一行、同一列或者同一对角线的任何棋子。）图3.5给出了失败的尝试：最右下角的皇后与最左上角的皇后可能互相攻击。

Start State

Goal State

尽管求解 n 皇后问题存在一些有效的专用算法，但对于搜索算法而言此类问题仍然是

有用的测试用例。这类问题的形式化主要分为两类。增量形式化（incremental formulation）包括了算符来增加状态描述，从空状态开始；对于八皇后问题，即每次行动添加一个皇后到状态中去。另一类是完整状态形式化（complete-state formulation），8个皇后都在棋盘上并且不断移动。无论哪种情况，都无需考虑路径消耗，只需考虑最终状态。增量形式化可以如下考虑：

状态：棋盘上0到8个皇后的任一摆放都是一个状态。

初始状态：棋盘上没有皇后。

行动：在任一空格增加摆放1个皇后。

转移模型：将增加了皇后的棋盘返回。

目标测试：8个皇后都在棋盘上，并且无法互相攻击。

这种形式化我们需要考查 $ 64 \times 63 \times \cdots \times 57 \approx 1.8 \times 10^{14} $ 个可能序列。如果禁止把一个皇后放到可能被攻击的格子里，这样的形式化可能更好：

状态：n 皇后在棋盘上（ $ 0 \leq n \leq 8 $）的任意摆放，满足从最左边 n 列里每列一个皇后，保证没有皇后能攻击另一个。

行动：在最左侧的空列中选择一格摆放1皇后，要求该格子未受到其他皇后攻击。

这样的形式化把八皇后问题的状态空间从 $ 1.8 \times 10^{14} $ 降到了 2057，解就容易找到了。另一方面，对于 100 个皇后，状态空间从约 $ 10^{400} $ 个状态减少到约 $ 10^{52} $ 个状态（习题 3.5），这是很大的改进，但还不足以使得问题容易求解。4.1 节给出了完整状态的形式化，第 6 章给出了一个简单的算法，可以轻易地解决甚至百万个皇后问题。

最后要讨论的玩具问题由 Donald Knuth（1964）提出，从中可以看出无限的状态空间的生长。Knuth 推测，只用数字 4，一个由阶乘、平方根和取整构成的操作序列可以得到任意正整数。例如，我们可以这样从 4 得到 5：

$$ \left\lfloor\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{(4!)}}}}!}\right\rfloor=5 $$

这个问题的形式化简单：

状态：正整数。

初始状态：4。

行动：应用阶乘、求平方根或取整操作（阶乘只能应用于整数）。

转移模型：数学家们对这些操作给出了定义。

目标测试：状态是要求的正整数。

据我们现在所知，为了求得某个给定整数需要构造的数字可能大到没有界限——例如，为了求得数字5，我们生成了数字620448401733239439360000——所以这个问题的状态空间是无限的。诸如此类牵涉到数学表达式的状态空间扩展非常快，如电路、定理证明和其他递归定义的对象。

3.2.2 现实世界问题

我们前面已经定义了寻径问题，我们定义了位置和由边连接形成的位置之间的转移。

寻径算法已有很多应用。如，Web站点和车载系统的导航，可以看作是罗马尼亚问题的相对扩展。其他情况如，计算机网络中的流媒体路由、军事行动规划以及飞机航线规划系统，涉及到更复杂的形式化。考虑旅行规划Web网站必须面临的飞机航行问题，形式化如下：

状态：每个状态显然包括地点（如机场）和当前的时间。更进一步考虑，由于每个行动（单个飞行区间）的代价可能依赖于上一飞行区间、票价、状态如是国内航段还是国际航段，状态中应体现这些你航行的“历史”信息。

初始状态：用户在咨询时确定。

行动：在当前时刻之后，乘坐一航班任意舱位从现有地点起飞，如果需要的话还应留够抵达机场的时间。

转移模型：执行行动的结果状态包括到达飞行目的地作为当前地点和以飞机抵达时间作为当前时间。

目标测试：是否到达了用户描述的目的地？

路径耗散：这取决于金钱、等待时间、飞行时间、海关和入境过程、舱位等级、时差、飞机类型、飞行常客的里程奖，等等。

商业的旅行建议系统使用此类问题形式化方法，还要考虑很多因素以应付航空公司复杂的收费结构。经常坐飞机的旅客都知道并不是所有的航行都能按计划顺利进行。一个好的系统应该包括后备计划——如选择其他航班预留座位——旅客会因为票价因素和未能搭承原定航班调整行程。

旅行问题类似于寻径问题，但也有区别。考虑如下实例，“访问图3.2中的每个城市至少一次，起点和终点都是 Bucharest”。和寻径问题一样，行动还是对应于邻接城市间的旅行。然而状态空间就不一样了。每个状态不仅必须包括当前所在地点，还必须包括 Agent 已经访问过的城市集合。因此初始状态应该是 $ \ln(\text{Bucharest}) $, $ \text{Visited}(\{\text{Bucharest}\}) $，一个典型的中间状态可能是 $ \ln(\text{Vaslui}) $, $ \text{Visited}(\{\text{Bucharest}, \text{Urziceni}, \text{Vaslui}\}) $，目标测试则应该是检测 Agent 是否在 Bucharest 且是否访问过所有的 20 个城市。

旅行商问题（TSP）是旅行问题，要求每个城市都仅能被访问一次。它的目标是找最短路程。这个问题已知是 NP 难题，很多人做了大量的努力来提高 TSP 算法的能力。除了为旅行商规划行程，旅行商算法还被用于规划电路板上的自动钻孔机的运动和商店库房里的货物摆放机器的运动。

VLSI 布线问题要求在一个芯片上放置几百万个元器件和连线，追求较小的芯片面积、较少的电路延迟、较小的杂散电容和较大的产量。逻辑设计阶段之后就是布线阶段，布线一般分为两部分：单元布局和通道布线。在单元布局中，原始的电路元器件分组成单元，每个单元完成某个特定功能。每个单元占用固定的区域（大小和形状），和其他单元之间通过一定数量的连线连接。该问题的目标是把这些单元不重叠地放置在芯片上，并且单元之间留有足够的空间布设连线。通道布线是寻找单元之间的空隙来安放每条连线。这些搜索问题极复杂，但无疑是值得解决的。在这章后面几节，我们介绍求解此问题的算法。

机器人导航问题是前面所述的寻径问题的一般化。与找寻离散状态的路径不同，机器人导航可以在连续空间上运动，（原则上）可能的行动和状态是无限集合。对于在平面上运动的圆形机器人来说，空间实质上是二维的。如果机器人有需要控制的机器臂、机器腿或者轮子，搜索空间就变成多维的了。要求先进的技术来使它的搜索空间变得有限。第25

章中我们将讨论此问题。除了问题的复杂性之外，真实机器人还必须考虑如何处理传感器读入错误和发动机控制上的错误。

机器人完成复杂物体的自动装配序列问题最早是由 FREDDY（Michie，1972）展示的。这方面的研究进展缓慢，不过在装配诸如发动机这样的复杂对象已经在经济上可行。在装配问题中，目标是找到装配对象各个部件的次序。如果选择了错误的装配顺序，在后面就会遇到有些零件无法安装的情况，只能返工。检查装配序列中的某步骤的可行性是困难的几何搜索问题，与机器人导航问题类似。因此，自动装配序列中开销最大的部分是生成合法行动。任何实用算法都必须避免搜索全部状态空间，只能搜索状态空间中的很小一部分。蛋白质设计问题是另外一类装配问题，它的目标是寻找氨基酸序列，该序列叠放在三维的蛋白质结构里，具有能够治愈某些疾病的合适特性。

3.3 通过搜索求解

在对问题进行形式化之后，我们现在需要对问题求解。一个解是一个行动序列，所以搜索算法的工作就是考虑各种可能的行动序列。可能的行动序列从搜索树中根结点的初始状态出发；连线表示行动，结点对应问题的状态空间中的状态。图3.6给出了求解罗马尼亚问题画搜索树的最初几步。搜索树的根结点对应于初始状态 $ In(Arad) $。第一步检测该结点是否为目标状态。（显然它不是目标状态，但是这步检测很重要，因为这样可以解决如“从Arad出发，到达Arad”的问题。）下面我们就要考虑选择各种行动。这是通过扩展当前状态完成的；即，在当前状态下应用各种合法行动，由此生成了一个新的状态集。在这个问题中，从父结点 $ In(Arad) $出发得到三个新的子结点： $ In(Sibiu) $， $ In(Timisoara) $和 $ In(Zerind) $。现在我们需要从这三种可能性中选择其一继续考虑。

这就是搜索——选择一条路往下走，把其他的选择暂且放在一边，等以后发现第一个选择不能求出问题的解时再考虑。假设我们首先选择Sibiu。检查它是否为目标状态（不是），然后扩展它得到四个状态：In(Arad)，In(Fagaras)，In(Oradea)和In(RimnicuVilcea)。现在我们的选择包括这四个状态，以及Timisoara和Zerind。这六个结点都是叶结点，在当前的搜索树中没有子结点。在任一给定时间点，所有待扩展的叶结点的集合称为边缘。（很多作者称之为开结点表，这种说法不容易记忆也不精确，原因是其他的数据结构比表更合适。）在图3.6中，搜索树中的边缘包括那些粗实线的结点。

在边缘中选择结点并扩展的过程一直继续，直到找到了解或者已经没有状态可扩展。在图3.7中给出了一般的树搜索算法。搜索算法的基本结构大多如此；区别主要在如何选择将要扩展的状态——即搜索策略。

细心的读者可能已经发现图3.6中有些特别：它包括了从Arad到Sibiu然后又回到Arad的路径！这时 $ In(Arad) $是搜索树中的重复状态，生成了一个有环路的路径。考虑这样的有环路径，这意味着罗马尼亚问题的完整搜索树是无限的，因为环路是没有限制的。另一方面，状态空间——如图3.2中所示——只有20个状态。我们在3.4节会讨论，循环会导致算法失败，会导致有解的问题无法求得解。幸运的是，我们无须考虑有环的路径。我们可以依赖直觉这样做：由于路径代价是递增的并且每一步的代价都是非负数，通向某一给定

状态的有环路径都不会比去掉那个环路的好。

有环路径是冗余路径的一种特殊情况，在两个状态之间的迁移路径多于一条时这种情况可能就会发生。考虑路径 Arad-Sibiu（路径长度 140 公里）和 Arad-Zerind-Oradea-Sibiu（路径长度 297 公里）。显然，后一条路径是冗余的——是达到同一状态的较差方法。如果你关心最终目标，那么对到达任一给定状态都没有必要记录超过一条路径，因为通过一种途径如果可以到达目标状态，通过其他途径同样也可以。

有些情况下，通过定义问题本身可以减少冗余路径。例如，在我们形式化八皇后问题时每个皇后可以放在任一列中，那么到达n后问题的每个状态有n!个不同的路径；但是如果我们在形式化此问题时，定义每个皇后只能放在最左侧的空列中，那么每个状态就只能通过一条路径抵达。

有些问题中，冗余状态是不可避免的。这里指的是问题中的行动是可逆的，如交通找路问题和滑块问题，这样的情况下冗余状态不可避免。矩形网格中的寻径问题（后面的图3.9）在计算机游戏中极为重要。在这样的网格中，每个状态有四个后继状态，所以包括重复状态的深度为 d 的搜索树有 $ 4^d $ 个叶结点；但是事实上对任一给定状态 d 步内只有大概 $ 2d^2 $ 个确定的状态。设 d=20，这意味着搜索树会有几万亿个结点，但事实上我们只有大约800个确定的状态。所以，如果不处理冗余路径会使得可解问题变得不可解。即使算法知道如何避免死循环，处理冗余路径依然重要。

正如前面所说，遗忘历史的算法将会不幸的重复历史。避免探索冗余路径的方法是牢记曾经走过的路。为了做到这一点，我们给TREE-SEARCH算法增加一个参数——这个数据结构称为探索集（也被称为closed表），用它记录每个已扩展过的结点。新生成的结点若与已经生成的某个结点相匹配的话——即是在探索集中或是边缘集中——那么它将被丢弃而不是被加入边缘集中。新算法叫GRAPH-SEARCH，如图3.7所示。本章中的特定算法都具有这种一般结构。

清楚的是，GRAPH-SEARCH算法构造的搜索树中每个状态至多只包含一个副本，所以我们可以直接在状态空间图中生长一棵树，如图3.8所示。这个算法还有另一个好的特点：边缘将状态空间图分成了已探索区域和未被探索区域，因此从初始状态出发至任一未被探索状态的路径都不得不通过边缘中的结点。（如果这看起来很显然，请现在就做练习3.13。）这种特点如图3.9所示。每个步骤要么将一个状态从边缘变为已探索区域，要么将未探索区域变为边缘，我们看到算法系统地检查状态空间中的每一个状态，直到找到问题的解。

3.3.1 搜索算法基础

搜索算法需要一个数据结构来记录搜索树的构造过程。对树中的每个结点，我们定义的数据结构包含四个元素：

n.STATE：对应状态空间中的状态；

n.PARENT：搜索树中产生该结点的结点（即父结点）；

n.ACTION：父结点生成该结点时所采取的行动：

● n.PATH-COST：代价，一般用 $ g(n) $ 表示，指从初始状态到达该结点的路径消耗；

给出了父结点的组成后，可以容易地看出如何计算子结点的必要组成。函数 CHILD-NODE 以父结点和一个行动作为输入，输出的是生成的子结点：

function CHILD-NODE(problem, parent, action) returns a node

return a node with

STATE = problem.RESULT( parent.STATE, action),

PARENT = parent, ACTION = action,

PATH-COST=parent.PATH-COST+problem.STEP-COST(parent.STATE, action)

结点的数据结构如图3.10所示。要注意的是PARENT指针。通过这些指针在求得问题的解时可以找出解路径；我们用SOLUTION函数通过最终指向根结点的父结点指针返回获得的解路径。

到目前为止，我们并未严格区分结点与状态，但在写算法时区分这两个概念十分重要。结点是用来表示搜索树的数据结构。状态则对应于世界的一个配置情况。所以说，结点是一种由 PARENT 指针定义的特定路径，但状态不是。更进一步，如果同一状态可以通过两种不同的路径生成，那么两个不同的结点就包含同样的世界状态。

现在我们有了结点，就需要空间来存放。搜索算法希望可以根据喜欢的策略很容易地选择出下一个要扩展的结点，这是边缘存储需要考虑的。最合适的数据结构应该是队列。队列的一些操作如下：

EMPTY?(queue) 返回值为真当且仅当队列中没有元素。

POP(queue) 返回队列中的第一个元素并将它从队列中删除。

INSERT(element, queue) 在队列中插入一个元素并返回结果队列。

根据队列中新插入元素如何存放的不同，我们将队列分类。三种常见的队列包括先进先出队列或FIFO队列，总是最古老的元素出队；后进先出队列或LIFO队列（即栈），总是最新鲜的元素出队；优先级队列，队列中的元素具有根据函数计算出的优先级，总是具有最高优先级的队列出队。

已扩展结点表可以用哈希表实现，便于有效检查重复状态。实现得好的话，不论表中有多少状态，插入和查找操作的时间消耗是常数。实现中还需要考虑的是哈希表中状态的等价性。例如，在旅行商问题（见3.2.2节）中，哈希表需要知道{Bucharest，Urziceni，Vaslui}和{Urziceni，Vaslui，Bucharest}是相同的。有时候这很容易处理，可以要求数据结构中的状态组织成规范形式；就是说，逻辑上等价的状态只映射到同一个数据结构。如，考虑由集合所描述的状态，位向量表示或无重复的有序表就是规范的，而无序表则不是规范的。

3.3.2 问题求解算法的性能

在设计搜索算法之前，我们需要一些标准。我们评价一个算法的性能要考虑四个方面：

完备性：当问题有解时，这个算法是否能保证找到解？

最优性：搜索策略是否能找到3.1.1节定义的最优解？

时间复杂度：找到解需要花费多长时间？

空间复杂度：在执行搜索的过程中需要多少内存？

时间和空间复杂度通常要与问题的难度规模一起考虑。在理论计算机科学中，一种典型的度量方式是状态空间图的大小， $ |V| + |E| $，其中 $ V $ 是图中顶点（结点）的集合， $ E $ 是图中边（连接）的集合。状态空间图作为显式的数据结构是搜索算法的输入，上面的说法是合理的（罗马尼亚地图就是实例）。在 AI 领域，状态空间图大多由初始状态、行动和转移模型隐式表示，并且大多是无限的。因此，复杂度通常由下列三个量来表达： $ b $，分支因子，或者说任何结点的最多后继数； $ d $，目标结点所在的最浅的深度（如从根结点到目标状态的步数）； $ m $，状态空间中任何路径的最大长度。时间常常由搜索过程中产生的结点数目来度量，而空间则由在内存中储存的最多结点数来度量。大多数情况下，我们描述搜索树的时间和空间复杂度；对于图，这个答案依赖于状态空间中的路径有多冗余。

评价搜索算法的有效性，我们可以只考虑搜索代价——它通常取决于时间复杂度，有时也包括内存的使用——或者我们可以使用总代价，它包括求解的搜索代价和解路径的路径代

价。对于寻找从 Arad 到 Bucharest 的路径的问题，搜索代价是搜索花费的时间，而解代价是解路径总长度的公里数。因此，要计算总代价，我们不得不把公里数和毫秒数相加。这两者之间没有“官方兑换率”，在这种情况下利用对汽车平均速度的估计把公里数合理地转换为毫秒数（因为该 Agent 关心的是时间）。这使得 Agent 能够找到一个最优的折中点，寻找最短路径的进一步计算将适得其反。更一般的不同利益之间的折中问题将在第 16 章中讨论。

3.4 无信息搜索策略

这一节讨论几种无信息搜索（也称为盲目搜索）策略。无信息搜索指的是除了问题定义中提供的状态信息外没有任何附加信息。搜索算法要做的是生成后继并区分目标状态与非目标状态。这些搜索策略是以结点扩展的次序来分类的。知道一个非目标状态是否比其他状态“更有希望”接近目标的策略称为有信息搜索策略或者启发式搜索策略；它们将在3.5节中讨论。

3.4.1 宽度优先搜索

宽度优先搜索（breadth-first search）是简单搜索策略，先扩展根结点，接着扩展根结点的所有后继，然后再扩展它们的后继，依此类推。一般地，在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过。

宽度优先搜索是一般图搜索算法（图3.7）的一个实例，每次总是扩展深度最浅的结点。这可以通过将边缘组织成FIFO队列来实现。就是说，新结点（结点比其父结点深）加入到队列尾，这意味着浅层的老结点会在深层结点之前被扩展。对一般图搜索算法做简单修改，目标的测试是在结点被生成的时候，而不是结点被选择扩展的时候。我们会在讨论时间复杂度的时候解释这一点。要注意的是，算法具有一般的图搜索框架，忽视所有到边缘结点或已扩展结点的新路径；可以容易地看出，这样的路径至少和已经找到的一样深。所以，宽度优先搜索总是有到每一个边缘结点的最浅路径。

图 3.11 给出了伪代码。图 3.12 显示了一个简单二叉树的搜索过程。

function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure

node← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

frontier← a FIFO queue with node as the only element

explored ← an empty set

loop do

if EMPTY?(frontier) then return failure

node← POP(frontier) /* chooses the shallowest node in frontier */

add node.STATE to explored

for each action in problem.ACTIONS(node.STATE) do

child ← CHILD-NODE(problem, node, action)

if child.STATE is not in explored or frontier then

if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)

frontier ← INSERT(child, frontier)

根据上节提到的4个标准，宽度优先搜索的性能怎样呢？很容易知道宽度优先搜索是完备的——如果最浅的目标结点处于一个有限深度d，宽度优先搜索在扩展完比它浅的所有结点（假设分支因子b是有限的）之后最终一定能找到该目标结点。请注意目标结点一经生成，我们就知道它一定是最浅的目标结点，原因是所有比它的浅的结点在此之前已经生成并且肯定未能通过目标测试。最浅的目标结点不一定就是最优的目标结点；从技术上看，如果路径代价是基于结点深度的非递减函数，宽度优先搜索是最优的。最常见的情况就是当所有的行动要花费相同的代价。

到目前为止我们讨论的宽度优先搜索的性能都是好的方面。但是它在时间和空间耗费上却不好。假设搜索一致树（uniform tree）的状态空间中每个状态都有 $b$ 个后继。搜索树的根结点生成第一层的 $b$ 个子结点，每个子结点又生成 $b$ 个子结点，第二层则有 $b^{2}$ 个结点。这些结点的每一个再生成 $b$ 个子结点，在第三层则得到 $b^{3}$ 个结点，依此类推。现在假设解的深度为 $d$。在最坏的情况下，解是那一层最后生成的结点。这时的结点总数为：

$$ b+b^{2}+b^{3}+\cdots+b^{d}=O(b^{d}) $$

（如果算法是在选择要扩展的结点时而不是在结点生成时进行目标检测，那么在目标被检测到之前深度 d 上的其他结点已经被扩展，这时时间复杂度应为 $ O(b^{d+1}) $。）

空间复杂度：对任何类型的图搜索，每个已扩展的结点都保存在探索集中，空间复杂度总是在时间复杂度的 $b$ 分之一内。特别对于宽度优先图搜索，每个生成的结点都在内存中。那么将有 $O(b^{d-1})$ 个结点在探索集中，$O(b^d)$ 个结点在边缘结点集中。所以空间复杂度为 $O(b^d)$，即它由边缘结点集的大小所决定。即使转换为树的搜索问题也节省不了多大的存储空间，如果状态空间有重复路径的话，这种转换会耗费大量时间。

指数级的复杂度 $ O(b^{d}) $ 令人担忧。图3.13说明了原因。它列出了，当解的深度为 d，分支因子 b=10 时，宽度优先搜索算法所需要的时间和空间开销。表中假设计算速度为每秒钟生成一百万个结点，存储一个结点需要 1000 字节。许多搜索问题在现代个人计算机上运行都粗略符合这样的假设（可乘以或者除以因子 100）。

从图3.13中我们学到了两点。首先，内存需求是宽度优先搜索算法中比它的执行时间更令人头疼的问题。要求解一个重要问题，人们可以忍受等待13天搜索到第12层，但是很少有计算机能具备上P字节的内存支持其存储要求。幸运的是，我们还有其他需要内存较少的搜索策略。

第二点是时间需求依然是主要因素。如果你的问题在第16层有一个解，那么（按照我们给定的假设）宽度优先搜索（或者事实上任一无信息搜索算法）需要花费350年的时间来求解。一般来讲，指数级别复杂度的搜索问题不能用无信息的搜索算法求解，除非是规模很小的实例。

3.4.2 一致代价搜索

当每一步的行动代价都相等时宽度优先搜索是最优的，因为它总是先扩展深度最浅的未扩展结点。更进一步，我们可以找到一个对任何单步代价函数都是最优的算法。不再扩展深度最浅的结点，一致代价搜索（uniform-cost search）扩展的是路径消耗 $ g(n) $ 最小的结点 n。这可以通过将边缘结点集组织成按 g 值排序的队列来实现。算法如图 3.14 所示。

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure

node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0

frontier ← a priority queue ordered by PATH-COST, with node as the only element

explored ← an empty set

loop do

if EMPTY?(frontier) then return failure

node ← POP(frontier) /* chooses the lowest-cost node in frontier */

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

add node.STATE to explored

for each action in problem.ACTIONS(node.STATE) do

child ← CHILD-NODE(problem, node, action)

if child.STATE is not in explored or frontier then

frontier ← INSERT(child, frontier)

else if child.STATE is in frontier with higher PATH-COST then

replace that frontier node with child

图 3.14 图的一致代价搜索。算法与图 3.7 给出的一般图搜索算法有不同，它使用了优先级队列并在边缘中的状态发现更小代价的路径时引入了额外的检查。边缘的数据结构需要支持有效的成员检测，这样它就结合了优先级队列和哈希表的能力

除了按路径代价对队列进行排序外，一致代价搜索和宽度优先搜索有两个显著不同。第一点是目标检测应用于结点被选择扩展时（与图3.7给出的图搜索算法一样），而不是在结点生成的时候进行。理由是第一个生成的目标结点可能在次优路径上。第二个不同是如果边缘中的结点有更好的路径到达该结点那么会引入一个测试。

上述修改在图3.15的搜索中都起到了作用，图中的搜索是从Sibiu到Bucharest。Sibiu的后继包括Rimnicu Vilcea和Fagaras，代价分别为80和99。最小代价结点为Rimnicu Vilcea被选择扩展，此时加入了Pitesti代价为80+97=177。所以这时的最小代价结点为Fagaras，扩展它得到Bucharest代价为99+211=310。目标结点已经生成，但是一致代价搜索算法还在继续，选择Pitesti扩展得到到达Bucharest的第二条路代价为80+97+101=278。现在算法则需要检查新路径是不是要比老路径好；确实是新的好，于是老路径被丢弃。Bucharest，

g 代价为 278，被选择扩展算法返回。

显然一致代价搜索是最优的。首先，我们观察到当一致代价搜索选择结点 n 去扩展时，就已经找到到达结点 n 的最优路径（否则，在从开始结点到结点 n 的最优路径上就会存在另一边缘结点 $ n' $，见图3.9的图分离特点；根据定义， $ n' $ 的 g 代价就会比 n 小即应被选择扩展）。接着，由于每一步的代价是非负的，随着结点的增加路径绝不会变短。这两点说明了一致代价搜索按结点的最优路径顺序扩展结点。所以，第一个被选择扩展的目标结点一定是最优解。

一致代价搜索对解路径的步数并不关心，只关心路径总代价。所以，如果存在零代价行动就可能陷入死循环——例如 NoOp 行动 $ ^{1} $。如果每一步的代价都大于等于某个小的正值常数 $ \varepsilon $，那么一致代价搜索是完备的。

一致代价搜索由路径代价而不是深度来引导，所以算法复杂度不能简单地用 $b$ 和 $d$ 来表示。引入 $C^*$ 表示最优解的代价$^{2}$，假设每个行动的代价至少为 $\varepsilon$。那么最坏情况下，算法的时间和空间复杂度为 $O(b^{1+\left\lfloor C^{*}/\varepsilon\right\rfloor})$，要比 $b^d$ 大得多。这是因为一致代价搜索在探索包含代价大的行动之前，经常会先探索代价小的行动步骤所在的很大的搜索树。当所有的单步耗散都相等的时候，$b^{1+\left\lfloor C^{*}/\varepsilon\right\rfloor}$ 就是 $b^{d+1}$。此时，一致代价搜索与宽度优先搜索类似，除了算法终止条件，宽度优先搜索在找到解时终止，而一致代价搜索则会检查目标深度的所有结点看谁的代价最小；这样，在这种情况下一致代价搜索在深度 $d$ 无意义地做了更多的工作。

3.4.3 深度优先搜索

深度优先搜索（depth-first search）总是扩展搜索树的当前边缘结点集中最深的结点。搜索过程如图3.16所示。搜索很快推进到搜索树的最深层，那里的结点没有后继。当那些结点扩展完之后，就从边缘结点集中去掉，然后搜索算法回溯到下一个还有未扩展后继的深度稍浅的结点。

深度优先搜索算法是图3.7的图搜索算法的实例；宽度优先搜索使用FIFO队列，而深度优先搜索使用LIFO队列。LIFO队列指的是最新生成的结点最早被选择扩展。这一定是最深的未被扩展结点，因为它比它的父结点深1——上一次扩展的则是这个父结点因为当时它最深。

作为一个可行的 TREE-SEARCH 实现，通常使用调用自己的递归函数来实现深度优先搜索算法，可以依次对当前结点的子结点调用该算法（有深度界限的递归深度优先搜索算法如图 3.17 所示）。

function DEPTH-LIMITED-SEARCH(problem,limit) returns a solution, or failure/cutoff

return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE),problem,limit)

function RECURSIVE-DLS(node,problem,limit) returns a solution, or failure/cutoff

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

else if limit = 0 then return cutoff

else

cutoff_occurred? ← false

for each action in problem.ACTIONS(node.STATE) do

child ← CHILD-NODE(problem,node,action)

result ← RECURSIVE-DLS(child,problem,limit - 1)

if result = cutoff then cutoff_occurred? ← true

else if result ≠ failure then return result

if cutoff_occurred? then return cutoff else return failure

深度优先搜索算法的效率严重依赖于使用的是图搜索还是树搜索。避免重复状态和冗余路径的图搜索，在有限状态空间是完备的，因为它至多扩展所有结点。而树搜索，则不完备——如图3.6中，算法会陷入Arad-Sibiu-Arad-Sibiu的死循环。深度优先搜索可以改成无需额外内存耗费，它只检查从根结点到当前结点的新结点；这避免了有限状态空间的死循环，但无法避免冗余路径。在无限状态空间中，如果遭遇了无限的又无法到达目标结点的路径，无论是图搜索还是树搜索都会失败。例如，在Knuth提出的4问题中，深度优先搜索会一直申请阶乘操作。

同样的原因，无论是基于图搜索还是树搜索的深度优先搜索都不是最优的。例如图3.16中，深度优先搜索会探索整个左子树，尽管C就是目标结点。如果J是目标结点，那么深度优先搜索会返回J为解而不是C，而此时C是更好的解；所以深度优先搜索不是最优的。

深度优先搜索的时间复杂度受限于状态空间的规模（当然，也可能是无限的）。另一方面，深度优先的树搜索，可能在搜索树上生成所有 $ O(b^{m}) $ 个结点，其中 m 指的是任一结点的最大深度；这可能比状态空间大很多。要注意的是 m 可能比 d（最浅解的深度）大很多，并且如果树是无界限的，m 可能是无限的。

这样看来，深度优先搜索与宽度优先搜索相比似乎没有任何优势，那我们为什么要考虑它？原因就在于空间复杂度。对图搜索而言，优势在于，深度优先搜索只需要存储一条从根结点到叶结点的路径，以及该路径上每个结点的所有未被扩展的兄弟结点即可。一旦一个结点被扩展，当它的所有后代都被探索过后该结点就从内存中删除（见图3.16）。考虑状态空间分支因子为b最大深度为m，深度优先搜索只需要存储O(bm)个结点。使用与图3.13相同的假设，假设与目标结点在同一深度的结点没有后继，我们发现在深度d=16的时候深度优先搜索只需要156K字节而不是10E字节（1K约为 $ 10^{3} $，1E约为 $ 10^{18} $——译者注），节省了大约7000亿倍的空间。这使得深度优先搜索在AI的很多领域成为工作主力，其中包括约束满足问题（第6章），命题逻辑可满足性（第7章）和逻辑程序设计（第9章）。这一节的其余部分，我们将集中讨论树搜索版本的深度优先搜索。

深度优先搜索的一种变形称为回溯搜索（backtracking search），所用的内存空间更少。（详见第6章。）在回溯搜索中，每次只产生一个后继而不是生成所有后继；每个被部分扩展的结点要记住下一个要生成的结点。这样，内存只需要 $ O(m) $ 而不是 $ O(bm) $。回溯搜索催化了另一个节省内存（和节省时间）的技巧：通过直接修改当前的状态描述而不是先对它进行复制来生成后继。这可以把内存需求减少到只有一个状态描述以及 $ O(m) $ 个行动。为了达到这个目的，当我们回溯生成下一个后继时，必须能够撤销每次修改。对于状态描述相当复杂的问题，例如机器人组装问题，这些技术是成功的关键。

3.4.4 深度受限搜索

在无限状态空间深度优先搜索会令人尴尬地失败，而这个问题可以通过对深度优先搜索设置界限 $l$ 来避免。就是说，深度为 $l$ 的结点被当作没有后继对待。这种方法称为深度受限搜索（depth-limited search）。深度界限解决了无穷路径的问题。不幸的是，如果我们选择了 $l < d$，即是说，最浅的目标结点的深度超过了深度限制，那么这种搜索算法是不完备的。如果选择的 $l > d$，深度受限搜索同样也不是最优的。它的时间复杂度是 $O(b^l)$，空间复杂度是 $O(bl)$。深度优先搜索可以看作是特殊的深度受限搜索，其深度 $l = \infty$。

有时，深度界限的设定可以依据问题本身的知识。例如，罗马尼亚地图上有20个城市。所以，如果有解的话其路径长度至多为19，l=19是一个可能的选择。但是事实上，如果我们仔细研究地图，会发现从任何一个城市到达另外一个城市最多只需要9步。这个数值被称为状态空间的直径，是一个更好的深度界限，导致更有效的深度受限搜索。然而，对于大多数问题，不到问题找到解，我们是无法知道一个好的深度界限的。

深度受限搜索可以通过修改一般的树搜索算法或者图搜索算法来实现。或者，它可以

作为简单递归算法来实现，如图3.17。要注意的是深度受限搜索可能因为两种失败而终止：标准的failure返回值指示无解；cutoff值指示在深度界限内无解。

3.4.5 迭代加深的深度优先搜索

迭代加深的深度优先搜索（iterative deepening search）是一种常用策略，它经常和深度优先搜索结合使用来确定最好的深度界限。做法是不断地增大深度限制——首先为0，接着为1，然后为2，依此类推——直到找到目标。当深度界限达到d，即最浅的目标结点所在深度时，就能找到目标结点。算法参见图3.18。迭代加深的深度优先搜索算法结合了深度优先搜索和宽度优先搜索的优点，它的空间需求是合适的： $ O(bd) $。和宽度优先搜索一样，当分支因子有限时是该搜索算法是完备的，当路径代价是结点深度的非递减函数时该算法是最优的。图3.19给出了二叉搜索树上ITERATIVE-DEEPENING-SEARCH函数的4次迭代情况，在第4次迭代时找到了解。

function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure

for depth = 0 to ∞ do

result -- DEPTH-LIMITED-SEARCH(problem, depth)

if result ≠ cutoff then return result

也许迭代加深的深度优先搜索看起来比较浪费，因为状态被多次重复生成。但事实上代价并不是多大。原因是在分支因子相同（或者近似）的搜索树中，绝大多数的结点都在底层，所以上层的结点重复生成多次影响不大。在迭代加深的深度优先搜索中，底层（深度 d）结点只被生成一次，倒数第二层的结点被生成两次，依此类推，一直到根结点的子结点，它被生成 d 次。因此，生成结点的总数为

$$ N(IDS)=(d)b+(d-1)b^{2}+\cdots+(1)b^{d}, $$

时间复杂度为 $ O(b^{d}) $——与宽度优先搜索相近。重复生成上层结点需要付出额外代价，但不是很大。如，当 b=10, d=5 时，数目分别为：

$$ N(IDS)=50+400+3000+20000+100000=123450 $$

$$ N(BFS)=10+100+1000+10000+100000=111110 $$

如果你确实担忧状态的重复生成，可以混合使用两种搜索算法，先用宽度优先搜索直到有效内存耗尽，然后对边缘集中的所有结点应用迭代加深的深度优先搜索。一般来讲，当搜索空间较大并且不知道解所在深度时，迭代加深的深度优先搜索是首选的无信息搜索方法。

迭代加深的深度优先搜索和广度优先搜索相似，每次迭代要把当前层的新结点全都探索过。结合一致代价搜索的迭代搜索是有价值的，在一致代价搜索确保最优化的同时避免了大量的内存需求。它的主要思想是用不断增加的路径代价界限代替不断增加的深度界限。基于这种思想的算法被称为迭代加长搜索（iterative lengthening search），详见习题3.17。不幸的是，与一致代价搜索相比，事实上迭代加长搜索将导致实在的额外开销。

3.4.6 双向搜索

双向搜索（bidirectional search）的思想是同时运行两个搜索——一个从初始状态向前搜索同时另一个从目标状态向后搜索——希望它们在中间某点相遇，此时搜索终止（图3.20）。理由是 $ b^{d/2} + b^{d/2} $ 要比 $ b^{d} $ 小很多，或者可以看图，两个小圆的面积相比以起点为中心到达目标的大圆的面积要小很多。

双向搜索可以这样实现：目标测试替换为检查两个方向的搜索的边缘结点集是否相交；如果交集不为空就找到了一个解（重点要提到的是这样找到的解可能不是最优解，即使两个方向采用的都是宽度优先搜索；保证最短路径还需要额外搜索）。这种检查可以在结点生成或被选择扩展时进行，如果使用哈希表则需耗费常数时间。例如，如果问题在深度 d=6 时有解，双向都同时使用宽度优先搜索每次搜索一个结点，那么在最坏情况下，两个搜索会把所有深度为3的结点都扩展完才相遇。若 b=10，则总共生成2220个结点，而单向

宽度优先搜索则需要生成 1111110 个结点。那么，双向都使用宽度优先搜索的算法时间复杂度是 $ O(b^{d/2}) $。空间复杂度也是 $ O(b^{d/2}) $。如果一个方向的搜索改为迭代加深的深度优先搜索，复杂度大约可以减半，但至少一个边缘结点集一定要存放在内存中，这样才能检查是否有交集。

降低的时间复杂度使得双向搜索很诱人，但是如何向后搜索呢？这并不像听起来那么简单。定义结点x的祖先是所有以结点x为后继的结点集。双向搜索需要计算祖先的算法。如果状态空间中所有的行动都是可逆的，x的祖先正是它的后继。其他情况则需要具体情况具体分析。

让我们考虑一下“从目标开始的向后搜索”中的“目标”是什么。在八数码问题和罗马尼亚问题中，都只有一个目标状态，因此向后搜索与向前搜索类似。如果某问题有几个明确列出的目标状态——例如，图3.3中的两个无尘目标状态——那么我们可以构造一个虚拟的目标状态，它的直接祖先特点是所有真实的目标状态。但如果目标状态是一种抽象描述的话，如n后问题的目标是“没有皇后攻击另一个皇后”，就很难应用双向搜索。

3.4.7 无信息搜索策略对比

图 3.21 根据 3.3.2 节中提出的 4 项评价标准比较了各搜索策略。考虑图搜索，最大的区别在于有限状态空间的深度优先搜索是完备的，时间和空间复杂度都受限于状态空间的规模。

3.5 有信息（启发式）的搜索策略

这一节介绍有信息搜索（informed search）策略——使用问题本身的定义之外的特定知识——比无信息的搜索策略更有效地进行问题求解。

我们要考虑的一般算法称为最佳优先搜索（best-first search）。最佳优先搜索是一般TREE-SEARCH和GRAPH-SEARCH算法的一个实例，结点是基于评价函数 $ f(n) $值被选择扩展的。评估函数被看作是代价估计，因此评估值最低的结点被选择首先进行扩展。最佳优先图搜索的实现与一致代价搜索类似（图3.14），不过最佳优先是根据f值而不是g值对优先级队列排队。

对f的选择决定了搜索策略。（例如，如习题3.21所示，深度优先搜索是最佳优先树搜索的特殊情况。）大多数的最佳优先搜索算法的f由启发函数（heuristic function）构成：

$$ h(n)= 结点 n 到目标结点的最小代价路径的代价估计值 $$

（要注意的是 $h(n)$ 以结点为输入，但它与 $g(n)$ 不同，它只依赖于结点状态。）例如，在罗马尼亚问题中，可以用从 Arad 到 Bucharest 的直线距离来估计从 Arad 到 Bucharest 的最小代价路径的代价值。

启发式函数是在搜索算法中利用问题额外信息的最常见的形式。在 3.6 节中将深入地讨论启发式信息。目前，我们假设启发式信息是任一非负的由问题而定的函数，有一个约束：若 n 是目标结点，则 $ h(n)=0 $。本节余下部分讨论用启发式信息导引搜索的两种方式。

3.5.1 贪婪最佳优先搜索

贪婪最佳优先搜索 $ ^{1} $（greedy best-first search）试图扩展离目标最近的结点，理由是这样可能可以很快找到解。因此，它只用启发式信息，即 $ f(n) = h(n) $。

将此算法应用在罗马尼亚问题中；使用直线距离启发式，记为 $ h_{SLD} $。如果目的地是 Bucharest，我们需要知道到达 Bucharest 的直线距离，如图 3.22 所示。如 $ h_{SLD}(In(Arad)) = 366 $。要注意的是 $ h_{SLD} $ 不能由问题本身的描述计算得到。而且，由经验可知 $ h_{SLD} $ 和实际路程相关，因此这是一个有用的启发式。

图 3.23 给出了使用 $ h_{SLD} $ 的贪婪最佳优先搜索寻找从 Arad 到 Bucharest 的路的过程。从

Arad 出发最先扩展的结点为 Sibiu，因为与 Zerind 和 Timisoara 相比，它距离 Bucharest 最近。下一个扩展的结点是 Fagaras，因为它是离目标最近的。Fagaras 接下来生成了 Bucharest，也就是目标结点。对于这个特殊问题，使用 $ h_{SLD} $ 的贪婪最佳优先搜索在没有扩展任何不在解路径上的结点前就找到了问题的解；所以，它的搜索代价是最小的。然而却不是最优的：经过 Sibiu 到 Fagaras 到 Bucharest 的路径比经过 Rimnicu Vilcea 到 Pitesti 到 Bucharest 的路径要长 32 公里。这说明了为什么这个算法被称为“贪婪的”——在每一步它都要试图找到离目标最近的结点。

贪婪最佳优先搜索与深度优先搜索类似，即使是有限状态空间，它也是不完备的。考虑从Iasi到Fagaras。启发式建议先扩展Neamt，因为它离Fagaras最近，但是这是个死胡同。解法是先到Vaslui——根据启发式这是离目标较远的一步——然后继续前往Urziceni，Bucharest到Fagaras。然而，算法始终找不到这个解，因为扩展Neamt则将Iasi重新放回到了边缘结点集中，Iasi比Vaslui离Fagaras更近，所以又去扩展Iasi，从而导致死循环。（有限状态空间的图搜索版本是完备的，但无限的则不是）最坏情况下，算法的时间复杂度

和空间复杂度都是 $ O(b^{m}) $，其中 m 是搜索空间的最大深度。然而，如果有一个好的启发式函数，复杂度可以得到有效降低。下降的幅度取决于特定的问题和启发式函数的质量。

3.5.2 A*搜索：缩小总评估代价

最佳优先搜索的最广为人知的形式称为 A* 搜索（可以读为 “A 星搜索”）。它对结点的评估结合了 $ g(n) $，即到达此结点已经花费的代价，和 $ h(n) $，从该结点到目标结点所花代价：

$$ f(n)=g(n)+h(n) $$

由于 $ g(n) $ 是从开始结点到结点 n 的路径代价，而 $ h(n) $ 是从结点 n 到目标结点的最小代价路径的估计值，因此

$$ f(n)= 经过结点 n 的最小代价解的估计代价 $$

这样，如果我们想要找到最小代价的解，首先扩展 $ g(n) + h(n) $ 值最小的结点是合理的。可以发现这个策略不仅仅合理：假设启发式函数 $ h(n) $ 满足特定的条件，A* 搜索既是完备的也是最优的。算法与一致代价搜索类似，除了 A* 使用 $ g + h $ 而不是 g。

保证最优性的条件：可采纳性和一致性

保障最优性的第一个条件是 h(n) 是一个可采纳启发式。可采纳启发式是指它从不会过高估计到达目标的代价。因为 g(n) 是当前路径到达结点 n 的实际代价，而 $ f(n) = g(n) + h(n) $，我们可以得到直接结论： $ f(n) $ 永远不会超过经过结点 n 的解的实际代价。

可采纳的启发式自然是乐观的，因为它们认为解决问题所花代价比实际代价小。可采纳启发式的明显例子就是用来寻找到达 Bucharest 的路径的直线距离 $ h_{SLD} $。直线距离是可采纳的启发式，因为两点之间直线最短，所以用直线距离肯定不会高估。图 3.24 给出了通过 A* 树搜索求解到达 Bucharest 的过程。g 值从图 3.2 给出的单步代价计算得到， $ h_{SLD} $ 值在图 3.22 中给出。特别要注意的是，Bucharest 首次在步骤（e）的边缘结点集里出现，但是并没有被选中扩展，因为它的 f 值（450）比 Pitesti 的 f 值（417）高。换个说法就是可能有一个经过 Pitesti 的解的代价低至 417，所以算法将不会满足于代价为 450 的解。

第二个条件，略强于第一个的条件被称为一致性（有时也称为单调性），只作用于在图搜索中使用 A*算法 $ ^{1} $。我们称启发式 $ h(n) $ 是一致的，如果对于每个结点 n 和通过任一行动 a 生成的 n 的每个后继结点 $ n' $，从结点 n 到达目标的估计代价不大于从 n 到 $ n' $ 的单步代价与从 $ n' $ 到达目标的估计代价之和：

$$ h(n)\leqslant c(n,a,n^{\prime})+h(n^{\prime}) $$

这是一般的三角不等式，它保证了三角形中任何一条边的长度不大于另两条边之和。这里，三角形是由 n， $ n' $ 和离 n 最近的目标结点 $ G_{n} $ 构成的。对于可采纳的启发式，这种不等式有明确意义：如果从 n 经过 $ n' $ 到 $ G_{n} $ 比 h(n) 代价小，就违反了 h(n) 的性质：它是到达 $ G_{n} $ 的下界。

很容易证明（习题 3.29）一致的启发式都是可采纳的。虽然一致性的要求比可采纳性更严格，要找到满足可采纳性的但可能不一致的启发式仍然需要艰苦的工作。本章中我们讨论的可采纳的启发式都是一致的。例如，考虑 $ h_{SLD} $。我们知道当每边都用直线距离来度

(a) The initial state

(b) After expanding Arad

量时是满足一般的三角形不等式的，而且 n 和 $ n' $ 之间的直线距离不超过 $ c(n, a, n') $。因此， $ h_{SLD} $ 是一致的启发式。

A*算法的最优性

我们前面提到过， $ A^{*} $有如下性质：如果 $ h(n) $ 是可采纳的，那么 $ A^{*} $的树搜索版本是最优的；如果 $ h(n) $是一致的，那么图搜索的 $ A^{*} $算法是最优的。

我们讨论上述声明中的后半部分，因为这更有用。一致代价搜索中参数 g 被替换成 f——就像是 A*算法自身。

第一步是证明如下性质：如果 $ h(n) $ 是一致的，那么沿着任何路径的 $ f(n) $ 值是非递减的。证明可从一致性的定义直接得到。假设 $ n' $ 是结点 n 的后继；那么对于某行动 a，有 $ g(n') = g(n) + c(n, a, n') $，可得到

$$ f(n^{\prime})=g(n^{\prime})+h(n^{\prime})=g(n)+c(n,a,n^{\prime})+h(n^{\prime})\geqslant g(n)+h(n)=f(n) $$

下一步则需要证明：若 $ A^{*} $ 选择扩展结点 n 时，就已经找到到达结点 n 的最优路径。否则，在到达结点 n 的最优路径上就会存在另一边缘结点 $ n' $，这可由图 3.9 的图分离性质得到；因为 f 在任何路径上都是非递减的， $ n' $ 的 f 代价比 n 小，会先被选择。

从上面两个观察可以看出，GRAPH-SEARCH 的 A*算法以 $ f(n) $ 值的非递减序扩展结点。由于 f 是目标结点的实际代价（目标结点的 h=0），因此，第一个被选择扩展的目标结点一定是最优解，之后扩展的目标结点代价都不会低于它。

f 代价沿着任何路径都是非递减的事实也意味着我们可以在状态空间上绘制等值线。图3.25给出了实例。在400的等值线内，所有结点的 $ f(n) $值都小于等于400，其他依此类推。那么，由于A*算法扩展的是f值最小的边缘结点，可以看到A*搜索由起始结点发散，以f值增长同心带状的方式添加结点。

对于一致代价搜索（A*搜索中令 $ h(n)=0 $），同心带是以起始状态为圆心的“圆”。如果使用更精确的启发式，同心带将向目标结点方向拉伸，并且在最优解路径的周围收敛变窄。如果C*是最优解路径的代价值，可以得到：

$ A^* $算法扩展所有 $ f(n) < C^* $的结点。

A*算法在扩展目标结点前可能会扩展一些正好处于“目标等值线” $ (f(n)=C^{*}) $上

的结点。

完备性要求代价小于等于 $ C^{*} $ 的结点是有穷的，前提条件是每步代价都超过 $ \varepsilon $ 并且 b 是有穷的。

要注意的是 A*算法不会扩展 $f(n) > C^*$的结点——如图3.24中，Timisoara尽管是根结点的子结点，并没有被扩展。可以说Timisoara的子树被剪枝了；因为$h_{SLD}$是可采纳的，搜索算法可以在忽略这棵子树的同时确保最优性。剪枝——无需检验就直接把它们从考虑中排除——在AI的很多领域中都是很重要的。

最后一个观察到的事实是，在这类最优算法中——从根结点开始扩展搜索解路径的算法——A*算法对于任何给定的一致的启发式函数都是效率最优的。就是说，没有其他的最优算法能保证扩展的结点少于A*算法（除了在 $ f(n)=C^* $的结点上做文章）。这是因为如果算法不扩展所有 $ f(n)

令人满意的是，A*搜索在所有此类算法中是完备的、最优的也是效率最优的。然而，这并不意味着 A*算法是我们所需要的答案。难点在于，对于相当多的问题而言，在搜索空间中处于目标等值线内的结点数量仍然以解路径的长度呈指数级增长。对这个结论的分析超出了本书的范围，但仍有如下基本结论。对于那些每步骤代价为常量的问题，时间复杂度的增长是最优解所在深度 d 的函数，这可以通过启发式的绝对错误和相对错误来分析。绝对误差定义为 $ \Delta \equiv h^* - h $，其中 $ h^* $ 是从根结点到目标结点的实际代价，相对误差定义为 $ \varepsilon \equiv (h^* - h)/h^* $。

复杂度的结论严重依赖于对状态空间所做的假设。最简单的模型是只有一个目标状态的状态空间，本质上是树及行动是可逆的。（八数码问题满足第一、第三个假设。）在这种情况下， $ A^* $ 的时间复杂度在最大绝对误差下是指数级的，为 $ O(b^4) $。考虑每步骤代价均为常量，我们可以把这记为 $ O(b^{ed}) $，其中 $ d $ 是解所在深度。考虑绝大多数实用的启发式，绝对误差至少是路径代价 $ h^* $ 的一部分，所以 $ \varepsilon $ 是常量或者递增的并且时间复杂度随 $ d $ 呈指数级增长。我们还可以看到更精确的启发式的作用： $ O(b^{ed}) = O((b^6)^d) $，所以有效的分支因子（下节会给出形式化定义）为 $ b^E $。

如果状态空间中包含多个目标状态——特别是接近最佳目标状态时——搜索过程可能会误入歧途，带来的额外代价是目标状态的数目的一部分。最后，考虑图搜索，情况会更坏。即使绝对误差受限于常量，满足 $ f(n) < C^* $ 的结点也是指数级的。例如，吸尘器世界中 Agent 可以以单位代价打扫任一方格却不用访问它：在这样的情况下，方格可以以任何顺序打扫。如果开始时有 $ N $ 个脏的方格，则会有 $ 2^N $ 个状态，其中一些子集已被打扫并且这些都在最优解路径上——所以满足 $ f(n) < C^* $——尽管启发式的误差是 1。

A*的复杂度使得坚持找到最优解的做法变得不实用。可以使用 A*算法的各种变型快速地找到局部最优解，或者有时可以设计更精确却不是严格满足可采纳性的启发式。无论任何情况下，与无信息搜索相比，使用好的启发式可以节省大量的时间和空间。我们将在第3.6节讨论如何设计好的启发式。

然而计算时间还不是 A*算法的主要缺点。因为它在内存中保留了所有已生成的结点（跟算法 GRAPH-SEARCH 一样），A*算法常常在计算完之前就耗尽了它的内存。因此，A*算法对于很多大规模问题，A*算法并不实用。确实有算法通过花费一些执行时间来克服内存问题，同时又不牺牲最优性和完备性。我们将在以后讨论。

3.5.3 存储受限的启发式搜索

A*算法减少内存需求的简单办法就是将迭代加深的思想用在启发式搜索上，即迭代加深A*(IDA*)算法。IDA*和典型的迭代加深算法的主要区别是所用的截断值是f代价(g+h)而不是搜索深度；每次迭代，截断值取超过上一次迭代截断值的结点中最小的f代价值。IDA*算法对很多每步代价都是单位代价的问题是实用的，它可以避免结点队列排序的实际系统开销。不幸的是，对于每步代价都是某个实数的问题，它会遇到与习题3.17中描述的迭代的一致代价搜索相同的困难。本节简单介绍其他两种存储受限的算法，称为RBFS和MA*。

递归最佳优先搜索（RBFS）是一个简单的递归算法，它试图模仿标准的最佳优先搜索的操作，但只使用线性的存储空间。算法如图 3.26 所示。它的结构和递归深度优先搜索类似，但是它不会不确定地沿着当前路径继续，它用变量 $ f_{limit} $ 跟踪记录从当前结点的祖先可得到的最佳可选路径的 f 值。如果当前结点超过了这个限制，递归将回到可选路径上。如果递归回溯，对当前路径上的每个结点，RBFS 用其子结点的最佳 f 值替换其 f 值。这样，RBFS 能记住被它遗忘的子树中最佳叶结点的 f 值，以决定以后是否值得重新扩展该子树。图 3.27 可以看出 RBFS 是怎样到达 Bucharest 的。

function RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution, or failure

return RBFS(problem, MAKE-NODE(problem.INITIAL-STATE), \infty)

function RBFS(problem, node, f_limit) returns a solution, or failure and a new f-cost limit

if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

successors \leftarrow []

for each action in problem.ACTIONS(node.STATE) do

add CHILD-NODE(problem, node, action) into successors

if successors is empty then return failure, \infty

for each s in successors do /* update f with value from previous search, if any */

s.f \leftarrow max(s.g + s.h, node.f)

loop do

best \leftarrow the lowest f-value node in successors

if best.f > f_limit then return failure, best.f

alternative \leftarrow the second-lowest f-value among successors

result, best.f \leftarrow RBFS(problem, best, min(f_limit, alternative))

if result \neq failure then return result

RBFS 算法有时比 IDA*算法效率高，但是它同样需要重复生成大量结点。在图 3.27 中，RBFS 首先沿着经过 Rimnicu Vilcea 的路走，然后“改变主意”去尝试 Fagaras，最后又回心转意。求解思路的不断改变是因为每当扩展当前的最优路径时，它的 f 值很可能会增加——对于靠近目标的结点，h 通常不那么乐观。此时，次佳路径可能会成为最佳路径，所以搜索将会回溯。解路径的每次改变都对应于 IDA* 中的一次迭代，并且可能需要重新扩展已经遗忘的结点来重建最佳路径。

与 A* 算法一样，如果启发式函数 $ h(n) $ 是可采纳的，那么 RBFS 算法是最优的。它的空间复杂度是最佳解路径所在深度的线性关系，时间复杂度相对比较难刻画：取决于它的启发式函数的精确性和当扩展结点时改变最佳路径的频度两项因素。

(a) After expanding Arad, Sibiu, and Rimnicu Vilcea

（a）沿着经过 Rimnicu Vilcea 的路径前进，直到当前最佳叶结点（Pitesti）的值比最佳可选路径（Fagaras）差。（b）递归回溯，把被遗忘子树的最佳叶结点值（417）回填到 Rimnicu Vilcea；然后扩展结点 Fagaras，得到最佳叶结点值 450。（c）递归回溯，把被遗忘子树的最佳叶结点值（450）回填到 Fagaras；再扩展 Rimnicu Vilcea。这样，因为最佳可选路径（经过 Timisoara）的代价至少是 447，继续扩展 Bucharest

IDA*和RBFS的问题在于它们使用的内存过于小了。在两次迭代之间，IDA*只保留一个数字：当前的f代价界限值。RBFS在内存中保留的信息多一些，但也只用到线性空间：即便有更多可用的内存，RBFS也没有办法利用。因为两个算法都忘记了它们做过什么，所以算法终止时有些状态可能重复扩展多次。更坏的是，图中的冗余路径会带来复杂度的潜在的指数级的增长（见3.3节）。

因此，充分利用内存看来是明智的。已经有两个算法这样做了，它们是 MA*（内存受限 A*）和 SMA*（简化的 MA*）。我们将描述 SMA*算法，因为它更简单。SMA*算法很像 A*算法，扩展最佳叶结点直到内存耗尽。就是说，要在搜索树中加入新结点就得抛弃一个旧结点。SMA*总是丢弃最差的叶结点——即 f 值最高的结点。像 RBFS 一样，SMA*把被遗忘结点的值回填给父结点。这样，被遗忘子树的祖先结点可以了解子树的最佳路径。有了这个信息，当所有其他路径看来比被遗忘路径要差的时候，SMA*可以重新生成该子树。换句话说，如果结点 n 的所有子孙结点都被遗忘了，我们不知道从 n 该走哪条路，但是我们知道从 n 去别处是否值得。

在这里描述完整的算法有些复杂了， $ ^{1} $但是有一点值得注意。我们提过 SMA*扩展最佳叶结点并且删除最差叶结点。如果所有的叶结点都有相同的 f 值时会怎样？为了避免算法选择同一个结点进行删除和扩展，SMA*扩展最新的最佳叶结点，删除最老的最差叶结点。仅在只有一个叶结点的情况下这两个才是同一个结点；在那种情况下，当前的搜索树必然是占满内存的一条从根结点到叶结点的单个路径。如果叶结点不是目标结点，那么即使它在最优解路径上，这个解在有效内存上也无法达到。因此，丢弃此结点，视它为没有后继。

如果有可到达的解——即如果最浅的目标结点的深度 d 小于内存大小（由结点数来表示），那么 SMA*算法是完备的。如果最优解是可到达的，那么这个算法也是最优的；否则算法会返回可以到达的最佳解。从实用的角度看，SMA*算法是最好的寻找最优解的通用算法，特别是当状态空间是一个图，单步代价不相等，并且与维护边缘结点集和探索集相比生成结点的开销更大的时候。

然而，对于一些非常困难的问题，SMA*算法会经常在候选解路径集里的路径之间换来换去，而内存中只能容纳其中一个很小的子集（这很像硬盘页面调度系统遇到的磁盘振荡问题）。这样，重复生成相同结点需要额外时间，这意味着一个在无限内存条件下能被A*算法解决的问题，对于SMA*算法会成为不可操作的。即，有限内存从计算时间角度能使一个问题变得相当棘手。目前没有理论能阐明时间和内存之间如何取舍处理，这是一个无法逃避的问题。唯一出路就是放弃寻找最优解。

3.5.4 学习以促搜索

我们提出了几个固定的搜索策略——宽度优先，贪婪最佳优先，等等——已经由计算机科学家设计实现。Agent 能够学习如何更好地搜索吗？答案是肯定的，其方法依赖于被称为元状态空间的重要概念。元状态空间中的每个状态都要捕捉一个程序的内部（计算）状态，程序是在目标层状态空间中搜索，如罗马尼亚问题。例如，A*算法的内部状态由当前的搜索树组成。元状态空间中的每个行动都是改变内部状态的计算步骤；例如，A*算法中每个计算步骤都扩展一个叶结点并将它的后继加入到搜索树中。因此，图3.24中可以看到搜索树按序不断增大，可以视为描述了元状态空间中的一条路径，其中路径上的每个状态是一棵目标层的搜索树。

图 3.24 中的路径有五步，包括扩展 Fagaras 的那一步，这步并不是很有用。对于更难

的问题，会有更多这样的错误步骤，元学习算法可以从这些经验中学到怎样避免探索没有希望的子树。这类学习技术将在第21章中描述。学习的目标是减小问题求解的总代价，在计算开销和路径代价之间取得最佳性价比。

3.6 启发式函数

本节我们将考察八数码问题的启发函数，以此为例探讨启发式的一般性质。

八数码问题是最早的启发式搜索问题之一。在 3.2 节我们提到过，这个游戏的目标是

把棋子水平或者竖直地滑动到空格中，直到棋盘局面和目标状态一致（图3.28）。

一个随机产生的八数码问题的平均解步数是22步。分支因子约为3（当空格在棋盘正中间的时候，有四种可能的移动；而当它在四个角上的时候只有两种可能；当在四条边上的时候有三种可能）。这意味着到达深度为22的穷举搜索树将考虑大约 $ 3^{22}\approx3.1\times10^{10} $个状态。图搜索可以

它的解路径为26步

把这个数目削减大约 170000 倍，因为只有 9!/2 = 181440 个可达到的不同状态。（参见习题 3.4。）这是一个容易管理的数目，但是考虑 15 数码问题，这个数目是大约 $ 10^{13} $，因此我们需要找到好的启发函数。如果想用 A*算法找到最短解路径，我们需要一个绝不会高估到达目标的步数的启发式函数。15 数码问题的启发式函数研究有很长的历史；这里有两个常用的：

$ h_{1} $ = 不在位的棋子数。图3.28中所有的8个棋子都不在正确的位置，因此起始状态的 $ h_{1}=8 $。 $ h_{1} $是一个可采纳的启发式函数，因为要把不在位的棋子都移动到正确位置上，每个错位的棋子至少要移动一次。

$ h_{2} $ = 所有棋子到其目标位置的距离和。因为棋子不能斜着移动，计算距离指的是水平和竖直的距离和。这时被称为市街区距离或曼哈顿距离。 $ h_{2} $ 也是可采纳的，因为任何移动能做的最多是把棋子向目标移近一步。图 3.28 中起始状态的棋子 1～8 得到的曼哈顿距离为

$$ h_{2}=3+1+2+2+2+3+3+2=18 $$

可以看到正如我们所希望的，这两个启发式函数都没有超过实际的解代价26。

3.6.1 启发式的精确度对性能的影响

一种刻画启发式的方法是有效分支因子 b*。对于某一问题，如果 A*算法生成的总结点数为 N，解的深度为 d，那么 b* 就是深度为 d 的标准搜索树为了能够包括 $ N+1 $ 个结点所必需的分支因子。即，

$$ N+1=1+b^{*}+(b^{*})^{2}+\cdots+(b^{*})^{d} $$

例如，如果 A*算法用52个结点在第5层找到了解，那么有效分支因子就是1.92。有效分支因子可能会因问题实例发生变化，但是在难题中通常它是相当稳定的（前面我们提到过，随着解路径所在深度的增加，A*算法扩展的结点数呈指数级增长，这导致了有效分支因子的存在）。所以，在一小部分问题集合上做实验以测量出 b*的值，有益于探讨启发式的总体实用性。设计良好的启发式会使b*的值接近于1，以合理的计算代价对大规模的问题进行求解。

为了测试启发式函数 $ h_1 $ 和 $ h_2 $，我们随机地产生了 1200 个八数码问题，解路径长度从 2 到 24 不等（每个偶数值有 100 个例子），分别用迭代加深搜索、使用 $ h_1 $ 与 $ h_2 $ 的 A* 树搜索对这些问题求解。图 3.29 给出了每种搜索策略扩展的平均结点数和有效分支因子。结果说明 $ h_2 $ 好于 $ h_1 $，并且远好于迭代加深搜索。在长度为 12 的解上，用 $ h_2 $ 作为启发式函数的 A* 算法的效率比无信息的迭代加深搜索高 50000 倍。

有人可能会问 $h_2$ 是否总是比 $h_1$ 好？答案是肯定的。这从两个启发式的定义很容易看出来，对于任意结点 $n$，$h_2(n) \geq h_1(n)$。因此称 $h_2$ 比 $h_1$ 占优势。优势可以直接转化为效率：使用 $h_2$ 的 A*算法永远不会比使用 $h_1$ 的 A*算法扩展更多的结点（除了 $f(n) = C^*$ 的某些结点）。证明很简单。回忆一下 3.5 节的讨论，每个 $f(n) < C^*$ 的结点都必将被扩展。还可以这样说，每个 $h(n) < C^* - g(n)$ 的结点一定会被扩展。但是因为对于所有的结点，它的 $h_2$ 值都至少和 $h_1$ 一样大，在使用 $h_2$ 的 A*搜索中被扩展的结点必定也会被使用 $h_1$ 的 A*所扩展，而 $h_1$ 还可能引起其他结点的扩展。所以，一般来讲使用值更大的启发式函数是好的，前提是计算该启发式花费的时间不是太多的话。

3.6.2 从松弛问题出发设计可采纳的启发式

我们已经看到 $ h_{1} $ （错位棋子数）和 $ h_{2} $ （曼哈顿距离）对于八数码问题者是相当好的启发式，而且 $ h_{2} $ 更好。那么 $ h_{2} $ 是如何被提出来的？计算机是否有能力机械地设计出这样的启发式？

$ h_{1} $ 和 $ h_{2} $ 估算的是八数码问题中剩余路径的长度，对于该问题的简化版本它们也是相当

精确的路径长度。如果游戏的规则改变为每个棋子可以随便移动，而不是只能移动到与其相邻的空位上，那么 $ h_{1} $将给出最短解的确切步数。类似地，如果一个棋子可以向任意方向移动一步，甚至可以移到已经被其他棋子占据的位置上，那么 $ h_{2} $将给出最短解的确切步数。减少了行动限制的问题称为松弛问题。松弛问题的状态空间图是原有状态空间的超图，原因是减少限制导致图中边的增加。

由于松弛问题增加了状态空间的边，原有问题中的任一最优解同样是松弛问题的最优解；但是松弛问题可能存在更好的解，理由是增加的边可能导致捷径。所以，一个松弛问题的最优解代价是原问题的可采纳的启发式。更进一步，由于得出的启发式是松弛问题的确切代价，那么它一定遵守三角不等式，因而是一致的（参见3.5节）。

如果问题定义是用形式语言描述的，那么有可能来自动构造它的松弛问题 $ ^{1} $。例如，如果八数码问题的行动描述如下：

$$ \begin{aligned}& 棋子可以从方格 A 移动到方格 B, 如果 \end{aligned} $$

A 与 B 水平或竖直相邻 而且 B 是空的，

我们可以去掉其中一个或者两个条件，生成三个松弛问题：

（a）棋子可以从方格 A 移动到方格 B，如果 A 和 B 相邻。

（b）棋子可以从方格 A 移动到方格 B，如果 B 是空的。

（c）棋子可以从方格 A 移动到方格 B。

由（a），我们可以得出 $ h_{2} $（曼哈顿距离）。原因是如果我们依次将每个棋子移入其目的位置， $ h_{2} $ 就是相应的步数。由（b）得到的启发式将在习题 3.31 中讨论。由（c）我们可以得出 $ h_{1} $（不在位的棋子数），因为如果把不在位的棋子一步移到其目的地， $ h_{1} $ 就是相应的步数。要注意的是：用这种技术生成的松弛问题本质上要能够不用搜索就可以求解，因为松弛规则使原问题分解成 8 个独立的子问题。如果松弛问题本身很难求解，使用它的值作为对应的启发式就得不偿失了。 $ ^{2} $

一个名为 ABSOLVER 的程序可以从原始的问题定义出发，使用 “松弛问题” 技术和各种其他技术自动地生成启发式（Prieditis，1993）。ABSOLVER 为 8 数码游戏找到比以前已有的启发式都好的新启发式，并且为著名的魔方游戏找到了第一个有用的启发式。

生成新的启发式函数的难点在于经常不能找到“无疑最好的”启发式。如果可采纳启发式的集合 $ h_{1}\cdots h_{m} $对问题是有效的，并且其中没有哪个比其他的更有优势，我们应该怎样选择呢？其实我们不用选择。我们可以这样定义新的启发式从而得到其中最好的：

$$ h(n)=\max\{h_{1}(n),\cdots,h_{m}(n)\} $$

这个合成的启发式使用的是对应于问题中结点的更精确的函数。因为它的每个成员启发式都是可采纳的，所以 h 也是可采纳的；也很容易证明 h 是一致的。此外，h 比所有成员启发式更有优势。

3.6.3 从子问题出发设计可采纳的启发式：模式数据库

可采纳的启发式也可以从考虑给定问题的子问题的解代价得到。例如，图3.30给出了图3.28所示的八数码问题的一个子问题。这个子问题涉及将棋子1、2、3、4移动到正确位置上。显然，这个子问题的最优解的代价是完整问题的解代价的下界。在某些情况下这实际上比曼哈顿距离更准确。

模式数据库（pattern databases）的思想就是对每个可能的子问题实例存储解代价——在我们的例子中，就是4个棋子和一个空位组成的可能状态。（其他4个棋子的位置与解决这个子问题是无关的，但是移动那四个棋子的代价也要算在总代价里。）接着，对搜索中遇到的每个完备状态计算其可采纳的启发式 $ h_{DB} $，计算通过在数据库里查找出相应的子问题进行。数据库本身的构造是通过从目标状态向后 $ ^{1} $搜索并记录下每个遇到的新模式的代价完成的；搜索的开销分摊到许多子问题实例上。

1-2-3-4 的选择是随机的；同样可以构造 5-6-7-8 或者 2-4-6-8 等的数据库。每个数据库都能产生一个可采纳的启发式，这些启发式可以像前面所讲的那样取最大值的方式组合使用。这种组合的启发式比曼哈顿距离要精确；求解随机的 15 数码问题时所生成的结点数要少 1000 倍。

有人可能会想，1-2-3-4 数据库和 5-6-7-8 数据库的子问题看起来没有重叠，从它们得到的启发式是否可以相加？相加得到的启发式是否还是可采纳的？答案是否定的，因为对于一给定状态，1-2-3-4 子问题的解和 5-6-7-8 子问题的解可能有一些重复的移动——不移动 5-6-7-8，1-2-3-4 也不可能移入正确位置，反之亦然。不过如果我们不计入这些移动又会怎样？就是说，我们记录的不是求解 1-2-3-4 子问题的总代价值，而只是涉及 1-2-3-4 的移动次数。这样很容易得出，两个子问题的代价之和仍然是求解整个问题的代价的下界。这就是不相交的模式数据库的思想。用这样的数据库，我们可以在几毫秒内解决一个随机的 15 数码问题——与使用曼哈顿距离启发式相比生成的结点数减少了 10 000 倍。对于 24 数码问题减少的结点数以百万倍计。

无交集的模式数据库在滑动棋子问题上相当可行，因为在问题可以分隔，使得每次移动只影响其中的一个子问题——因为一次只移动一个棋子。对于魔方这样的问题，这种划分相当困难，因为每步移动都会影响到26个立方体中的8块或9块。目前已经提出了更一

般的可相加的可采纳启发式应该用魔方问题中（Yang等，2008），但是还没有证明这种启发式要好于最好的不相加的启发式。

3.6.4 从经验中学习启发式

启发函数 $ h(n) $ 用来估计从结点 n 开始的解代价。Agent 怎样才能构造这样的函数？上节我们讨论了一个方案——即找出一些很容易找到最优解的松弛问题。另一个方案则是从经验里学习。“经验”在这里意味着求解大量的八数码问题。每个八数码问题的最优解都成为可供 $ h(n) $ 学习的实例。每个实例都包括解路径上的一个状态和从这个状态到达解的代价。从这些例子中，一个学习算法可以用来构造 $ h(n) $，（够幸运的话）它能预测搜索过程中所出现的其他状态的解代价。使用神经网络、决策树还有其他一些方法的学习技术，将在第18章中介绍（同样可以使用第21章中描述的强化学习方法）。

如果在状态描述外还能刻画给定状态的特征，归纳学习方法则是最可行的。例如，特征“不在位的棋子数”对于估算从一个状态到目标状态的真实距离可能是有用的。我们把这个特征记为 $ x_{1}(n) $。选取100个随机产生的八数码问题，统计它们实际的解代价。我们会发现当 $ x_{1}(n) $ 是5的时候，平均解代价约为14，等等。有了这些数据，就可以用 $ x_{1} $ 的值来预测 $ h(n) $。当然，我们还可以使用多个特征。第二个特征 $ x_{2}(n) $ 可以是“现在相邻但在目标状态中不相邻的棋子对数”。如何将 $ x_{1}(n) $ 和 $ x_{2}(n) $ 结合起来预测 $ h(n) $？通常的方法是使用线性组合：

$$ h(n)=c_{1}x_{1}(n)+c_{2}x_{2}(n) $$

常数 $ c_{1} $ 和 $ c_{2} $ 可以调整以符合解代价的实际数据。人们希望 $ c_{1} $ 和 $ c_{2} $ 都是正数，原因是错位棋子数和不正确的相邻对使问题求解变得更困难。要注意的是这个启发式确实满足目标状态 $ h(n)=0 $ 的条件，但不能保证可采纳或是一致性。

3.7 本章小结

本章介绍了在确定性的、可观察的、静态的和完全可知的环境下，Agent可以用来选择行动的方法。在这种情况下，Agent可以构造行动序列以达到目标；这个过程称为搜索。

在 Agent 可以开始搜索解之前，必须对目标和良定义的问题加以形式化。

一个问题由五个部分组成：初始状态，行动集合，转移模型描述这些行动的结果，目标测试函数和路径代价函数。问题的环境用状态空间表示。状态空间中从初始状态到达目标状态的路径是一个解。

搜索算法将状态和行动视为原子：不考虑它们可能包含的内部结构。

一般的 TREE-SEARCH 算法会考虑所有的可能来找寻一个解；GRAPH-SEARCH 算法则考虑避免冗余路径。

搜索算法的从完备性、最优性、时间复杂度和空间复杂度等方面来评价。复杂度依赖于状态空间中的分支因子 b，和最浅的解的深度 d。

无信息搜索方法只能访问问题的定义。基本算法如下：

宽度优先搜索总是扩展搜索树中深度最浅的结点。算法是完备的，在单位代价的情况下是最优的，但是具有指数级别的空间复杂度。

一致代价搜索扩展的是当前路径代价 $ g(n) $ 最小的结点，对于一般性的步骤代价而言算法是最优的。

深度优先搜索扩展搜索树中深度最深的结点。它既不是完备的也不是最优的，但它具有线性的空间复杂度。深度受限搜索在深度优先搜索上加了深度限制。

迭代加深搜索在不断增加的深度限制上调用深度受限搜索直到找到目标。它是完备的，在单位代价的情况下是最优的，它的时间复杂度可与宽度优先搜索比较，具备线性的空间复杂度。

双向搜索可以在很大程度上降低时间复杂度，但是它并不是总是可行的并且可能需要太多的内存空间。

有信息搜索可能需要访问启发式函数 $ h(n) $ 来估算从 n 到目标的解代价。

一般的最佳优先搜索算法根据评估函数选择扩展结点。

◆ 贪婪最佳优先搜索扩展 $ h(n) $ 最小的结点。它不是最优的，但效率较高。

◆ A*搜索扩展 $ f(n)=g(n)+h(n) $ 最小的结点。如果 $ h(n) $ 是可采纳的（对于 TREE-SEARCH）或是一致的（对于 GRAPH-SEARCH），A*算是完备的也是最优的。它的空间复杂度依然很高。

RBFS（递归最佳优先）和 SMA $ ^{*} $（简单内存受限 A $ ^{*} $）是鲁棒的、最优的搜索算法，它们使用有限的内存；只要时间充足，它们能求解 A $ ^{*} $算法因为内存不足不能求解的问题。

启发式搜索算法的性能取决于启发式函数的质量。好的启发式有时可以通过松弛问题的定义来构造，将子问题的解代价记录在模式数据库中，或者通过对问题类的经验学习得到。

参考文献与历史注释

状态空间搜索的研究发源于 AI 诞生初期。Simon 和 Newell 在逻辑理论家（1957）和 GPS（1961）上的工作奠定了作为搜索算法的地位，并确立了将问题求解视为典型的 AI 任务。Richard Bellman（1957）的研究工作表明了附加路径代价对化简优化算法的重要性。Nils Nilsson（1971）的“自动问题求解”为之建立了扎实的理论基础。

本章讨论的许多状态空间搜索问题都有很长的研究历史，并不像它们看起来那样不重要。Amarel（1968）详细分析了习题3.9的传教士和野人问题。早前也有人考虑过此问题——如Simon和Newell（1961）从AI的角度，Bellman和Dreyfus（1962）从运筹学的角度。

八数码问题是15数码问题的缩小版本，它的历史在Slocum和Sonneveld（2006）中有详细叙述。普遍认为它是由美国著名的游戏设计家SamLoyd（1959）设计的，他声称受到1891年或者更以前的影响。实际上此游戏由Noyes Chapman，纽约的一个邮递员，在19世纪70年代中期设计。（Chapman无法为此申请专利，因为1878年ErnestKinsey得到了

字母数字以及图片滑块游戏的专利)15 数字游戏很快流行起来，吸引了许多数学家（Johnson和Story，1879；Tait，1880）的注意力。《美国数学期刊》（American Journal of Mathematics）的编辑写道“15 数码游戏在上几周里出现在美国公众面前，也许可以比较保守地说它吸引了90%的人的注意，无论男女老少以及社会地位。” Ratner 和 Warmuth（1986）证明了由15 数码问题推广得到的一般的 $ n \times n $ 版本问题是 NP 完全问题。

八皇后问题首先匿名发表在 1848 年的德国国际象棋杂志《Schach》上；后来它被认为一个叫 Max Bezzel 的人写的。它在 1850 年重新发表并且吸引了当时的杰出数学家 Carl Friedrich Gauss 的注意，他尝试枚举所有可能的解；最初他找到了 72 个，后来他发现正确答案是 92 个，尽管 Nauck 在 1850 年先发表了全部 92 个解。Netto（1901）将该问题一般化到 n 皇后问题，Abramson 和 Yung（1989）找到了复杂度为 $ O(n) $ 的算法。

本章列出的现实世界搜索问题都是经过了大量研究的课题。选择最优的飞机航班的方法有很多专有特性，但是 Carl de Marcken（在私人信件中）证明了由于航班票价和限制的复杂性，使得选择最佳航线在理论上是不可判定的。旅行商问题（TSP）是理论计算机科学中一个标准的组合问题（Lawler 等人，1992）。Karp（1972）证明了 TSP 是 NP 难题，但是（Lin 和 Kernighan，1973）提出了有效的启发式近似方法。Arora（1998）提出了欧几里得 TSP 的完全多项式近似求解方案。Shahookar 和 Mazumder（1991）调查了 VLSI 的布局方法，并且在 VLSI 杂志上有大量关于布局优化的论文。机器人导航和装配问题将在第 25 章中讨论。

问题求解的无信息搜索算法是经典计算机科学（Horowitz 和 Sahni，1978）和运筹学（Dreyfus，1969）的中心话题之一。Moore（1959）形式化了宽度优先搜索并用于解决迷宫问题。动态规划（Bellman，1957；Bellman 和 Dreyfus，1962），被视为一种图的宽度优先搜索，它系统地记录了长度不断增加的所有子问题的解。Dijkstra（1959）的两点最短路径算法是一致代价搜索的起源。正是这些工作激发了探索集和边缘结点表的概念（开结点表和闭结点表）。

迭代加深搜索的思想由 Slate 和 Atkin（1977）首先设计出来，算法用于在 CHESS4.5 游戏程序中有效地利用棋钟。Martelli 的算法 B（1977）包含了部分迭代加深搜索同时讨论了 A* 在最坏情况下的性能，启发式是可采纳的但不是一致的。使迭代加深技术脱颖而出的是 Korf（1985a）。Pohl（1971）提出的双向搜索在一些情况下十分有效。

在问题求解中使用启发式信息最早出现在 Simon 和 Newell（1958）的一篇论文中，但是术语“启发式搜索”和使用估算目标距离的启发式函数却提出得比较晚（Newell 和 Ernst，1965；Lin，1965）。Doran 和 Michie（1966）对启发式搜索进行了广泛的实验研究。尽管他们分析了路径长度和“外显率”（路径长度和已经访问过的结点总数的比率），他们忽略了路径代价 $ g(n) $。Hart，Nilsson 和 Raphael（1968）提出了 A*算法，在启发式搜索中考虑当前路径代价，后人又做了一些修正（Hart 等人，1972）。Dechter 和 Pearl（1985）证明了 A*算法的最佳效率。

描述 A*算法的早期论文都强调了启发式函数的一致性。Pohl（1977）介绍了一个更简单的代替一致性的单调性条件，但是 Pearl（1984）证明了两种条件是等价的。

Pohl（1977）率先对启发式函数的误差和 A* 算法的时间复杂度之间的关系进行了研究。（Pohl，1977；Gaschnig，1979；Huyn 等人，1980；Pearl，1984）讨论了单位步骤代价和

单个目标结点情况下的基本结论，多个目标结点的情况可参见（Dinh 等人，2007）。Nilsson（1971）提出用“有效分支因子”来度量启发式搜索的效率；这与假设时间开销为 $ O((b^{*})^{d}) $ 等价。将树搜索扩展到图搜索，Korf 等人（2001）认为时间代价最好建模为 $ O(b^{d-k}) $，其中 k 依赖于启发式的精确程度；不过他的分析引起了一些矛盾。对于图搜索，Helmert 和 Röger（2008）注意到了几个众所周知的问题的最优解路径上包含指数级别的结点，也就意味着指数级别的时间复杂度，即使是在 h 的绝对误差为常量的情况下。

A*算法由很多变形。Pohl（1973）提出了使用动态加权，它用当前的路径长度与启发函数的加权和 $ f_{w}(n) = w_{gg}(n) + w_{h}h(n) $作为评估函数，而不是A*中简单的使用 $ f(n) = g(n) + h(n) $。权值 $ w_{g} $和 $ w_{h} $在搜索过程中动态调整。Pohl的算法被证明是 $ \varepsilon $可采纳的——就是说保证找到的解是在最优解的 $ 1 + \varepsilon $倍以内—— $ \varepsilon $是提供给算法的一个参数。算法也有同样的性质（Pearl，1984），它可以从边缘结点集中选取最低 $ f $代价的 $ 1 + \varepsilon $倍之内的结点来扩展。这种选取可以减小搜索开销。

A*算法的双向搜索版本也被提出；双向搜索 A*和地标的组合被用了微软的在线地图驾车路线规划服务（Goldberg 等人，2006）。在地址之间抓取一些路径后，算法在拥有 2400 万个地标的美国地图上通过搜索不到 0.1% 的地图就可以在两点之间找到最佳路径。其他双向搜索的方法包括宽度优待向后搜索至固定深度和向前 IDA*搜索（Dillenburg 和 Nelson，1994；Manzini，1995）。

A $ ^{*} $算法和其他状态空间搜索算法与运筹学中的分支限界技术关系紧密（Lawler 和 Wood，1966）。（Kumar 和 Kanal，1983；Nau 等人，1984；Kumar 等人，1988）深入研究了状态空间搜索和分支限界两者之间的关系。Martelli 和 Montanari（1978）证实了动态规划（参见第17章）与特定类型的状态空间搜索之间的联系。Kumar 和 Kanal（1988）尝试把启发式搜索、动态规划和分支限界技术“一统”为 CDP——“复合决策过程”。

在 20 世纪 50 年代末到 60 年代初计算机只有不超过几千字节的主存，因此内存受限的启发式搜索是早期研究的一个主题。最早的搜索程序 Graph Traverser（Doran 和 Michie，1966）提交在内存限制内最好的搜索结果。IDA*算法（Korf，1985a，1985b）是第一个广泛应用的最优的内存受限的启发式搜索算法，该算法也发展出很多变形。Patrick 等人（1992）分析了 IDA*算法的效率和使用实值启发式的困难。

RBFS 算法（Korf，1993）实际上要比图 3.26 中给出的算法复杂得多，它更接近于一个独立发展出来的迭代扩展算法（Russell，1992）。RBF 同时使用上限和下限；这两个算法使用可采纳启发式时表现相同，但是 RBFS 甚至使用非可采纳的启发式的时候也按照最佳优先的顺序来扩展结点。记录最佳可选路径的思想最早出现在 Bratko（1986）的 A*算法的 Prolog 实现中和 DTA*算法中（Russell 和 Wefald，1991）。后者的工作还讨论了元状态空间和元级学习。

Chakrabarti 等人（1989）提出了 MA*算法。SMA*，即简化的 MA*试图把 MA*作为IE 的比较（Russell，1992）。Kaindl 和 Khorsand（1994）用 SMA*产生双向搜索算法，该算法确实比以前的算法要快。Korf 和 Zhang（2000）提出了一种分治方法，Zhou 和 Hansen（2002）介绍了内存受限的 A*图搜索和一种转换成宽度优先搜索以提高内存使用效率的策略（Zhou 和 Hansen，2006）。Korf（1995）综述了内存受限的搜索技术。

Held 和 Karp（1970）提出了可采纳启发式可以通过问题的松弛而产生的思想，他们用

最小生成树启发式来求解 TSP 问题（参见习题 3.30）。

Prieditis（1993）在他和 Mostow（Mostow 和 Prieditis，1989）早期工作的基础上成功地完成了问题松弛过程的自动实现。Holte 和 Hernadvolgyi（2001）描述了这个自动化过程的最近几步。用模式数据库来产生可采纳启发式由 Gasser（1995）以及 Culberson 和 Schaeffer（1996，1998）提出；Korf 和 Felner（2002）描述了不相交的模式数据库；Edelkamp（2009）提出了使用符号模式的类似方法。Felner 等人（2007）提出了压缩模式数据库以节省空间的方法。Pearl（1984）以及 Hansson 和 Mayer（1989）深入地分析了启发式的概率解释。

迄今为止关于启发式和启发式搜索算法的最全面的资料是 Pearl 的教材《启发式》（Heuristics）（1984）。这本书全面地涵盖了 A*算法的广泛分支和变形，包括其性质的严格证明。Kanal 和 Kumar（1988）选编了启发式搜索方面的重要文章，Rayward-Smith 等人（1996）讨论了运筹学方法。一些新的搜索算法的研究——持续被发现——通常发表在如《人工智能》（Artificial Intelligence）和 Journal of the ACM 期刊上。

本章没有讨论并行搜索算法，部分是因为这需要先介绍并行计算机体系结构。并行搜索在20世纪90年代开始流行，已经成为AI和理论计算机科学的一个重要课题（Mahanti和Daniels，1993；Grama和Kumar，1995；Crauser等人，1998），特别是在新的多核和集群架构时代（Ralphs等人，2004；Korf和Schultze，2005）。（Korf，2008）研究了在需要大量磁盘存储的大规模图搜索中搜索算法的重要性。

习题

3.1 解释为什么问题的形式化必须在目标的形式化之后。

3.2 你的目标是让机器人走出迷宫。机器人面朝北，开始位置在迷宫中间。你可以让机器人转向面朝东、南、西或北。你可以让机器人向前走一段距离，在撞墙之前它会停步。

a. 将问题形式化。状态空间有多大？

b. 在迷宫中游走，在两条路或更多路交叉的路口可以转弯。重新形式化这个问题。现在状态空间有多大？

c. 从迷宫中的任一点出发，我们可以朝四个方向中的任一方向前进直到可以转弯的地方，而且我们只需要这样做。重新对这个问题进行形式化。我们需要记录机器人的方向吗？

d. 在我们对问题的最初描述中已经对现实世界进行了抽象，限制了机器人的行动并移除了细节。列出三个我们做的简化。

3.3 两个朋友住在地图（如图3.2给出的罗马尼亚地图）上的不同城市中。每一轮次，两个人都可以前进到地图上相邻的城市。从城市i到相邻城市j耗费的时间与城市间的距离 $ d(i,j) $相等，但是每一轮次先到达相邻城市的人要等另一人抵达他的相邻城市（到达后打手机），方可进入下一轮次。我们希望这两个朋友能尽快相遇。

a. 请详细形式化此问题（你会发现在这定义一些形式符号很有帮助）。

b. 用 $ D(i,j) $ 表示城市 i 和 j 之间的直线距离。下列启发式函数哪些是可采纳的？

(i) $ D(i,j) $;

(ii) $ 2D(i,j) $;

(iii) $ D(i,j)/2 $.

c. 是否存在完全联通图却没有解？

d. 是否存在这样的地图：所有解都需要一个朋友访问同一城市两次？

3.4 证明八数码问题的所有状态可以划分为两个不相交的子集，处在同一个子集中的状态之间可以相互到达，处在不同子集中的两个状态之间必不可达。（提示：参见 Berlekamp 等人（1982）。）设计一个算法判断一个给定的状态属于哪个子集，并解释为什么这对于生成随机状态是有用的。

3.5 用 3.2.1 节给出的“高效的”增量形式化方法处理 n 皇后问题。解释为什么状态空间至少有 $ \sqrt[3]{n} $ 个状态，估算穷举探索可行的 n 的最大值（提示：考虑一个皇后在每列中能够攻击到的最大方格数目，从而得出分支因子下界）。

3.6 对以下问题给出完整的形式化。选择的形式化方法要足够精确以便于实现。

a. 只用四种颜色对平面地图着色，要求每两个相邻的地区不能具有相同的颜色。

b. 屋子里有只3英尺高的猴子，离地8英尺的屋顶上挂着一串香蕉。猴子想吃香蕉。屋子里有两个可叠放、可移动、可攀爬的3英尺高的箱子。

c. 有这样一个程序，当输入一个包含很多记录的文件时会输出消息“不合法的输入记录”。每个记录的处理都是独立的。请找出报错的是哪个记录。

d. 有三个水壶，容量分别为12加仑、8加仑和3加仑，还有一个放液嘴。可以把水壶装满或者倒空，从一个壶倒进另一个壶或者倒在地上。请量出刚好1加仑水。

3.7 考虑从飞机看两点之间的最短路径问题，如图3.31所示，图中有很多凸多边形障碍。这是复杂环境中机器人要解决的导航问题的理想化。

a. 假设状态空间包含所有坐标 $ (x, y) $。状态空间有多大？有多少条路可以到达目标？

b. 简要回答为什么从一个多边形顶点到图中任何地方的最短路径一定会包含直线区段和多边形顶点。定义一个好的状态空间。分析状态空间的大小。

c. 定义实现该搜索问题所需要的函数，其中函数 ACTIONS 以一顶点为其输入，返回以该顶点为起点直线到达另一顶点的矢量集合（不要忘记同一多边形的邻居）。使用直线距离作为启发式函数。

d. 应用本章讨论的一个或多个算法求解此问题，并给出性能评价。

3.8 在 3.1.1 节，我们提到不会考虑代价为负数时的情况。本题我们更深入地讨论这种情况。

a. 假设行动可以是任一负数代价；解释为什么这种可能性会导致每一个最优算法都要探索整个状态空间。

b. 如果我们限定步骤代价一定要大于等于某一负数 c 是否会有帮助？考虑图搜索和树搜索两种情况。

c. 假设一组行动在状态空间组成了循环，所以以某顺序执行此行动集不会带来状态的任何改变。如果这些行动都是负数代价，这对此环境中追求最优行为的 Agent 而言意味着什么？

d. 假设某行动有很高的负数代价，不管是什么领域包含路径查找。例如，有些道路两边的风景太美了，完全不必理会时间和汽油的消耗。请在状态空间搜索的上下文中用术语精确解释，为什么人不会永远看下去？请解释在路径查找中如何定义状态空间和行动以使人工 Agent 避免循环。

e. 你能想出步骤代价这样带来循环的真实领域吗？

3.9 传教士和野人问题。三个传教士和三个野人在河的一岸，有一条能载一个人或者两个人的船。请设法使所有人都渡到河的另一岸，要求在任何地方野人数都不能多于传教士的人数。这个问题在 AI 领域中很有名，是因为它是第一个从分析的观点探讨问题形式化的论文的主题（Amarel，1968）。

a. 请对该问题进行详细形式化，只描述确保该问题求解所必需的特性。画出完整的状态空间图。

b. 应用合适的搜索算法求出该问题的最优解。对于这个问题检查重复状态是个好主意吗？

c. 这个问题的状态空间很简单，你认为是什么导致人们求解它很困难？

3.10 对以下术语给出你自己的定义：状态，状态空间，搜索树，搜索结点，目标，行动，转移模型和分支因子。

3.11 世界状态、状态描述和搜索结点有何不同？为什么要做这样的严格区分？

3.12 像 Go(Sibiu)这样的行动都会包含一组动作：点火汽车，松开刹车，加速然后前进，等等。把这些动作组合起来可以减少解的步骤数，从而减少搜索时间。假设我们走向极端，组合一个超级行动 Go。这样每个问题实例都可通过单个超级组合行动求解，如 Go(Sibiu) Go(Rimnicu Vilcea) Go(Pitesti) Go(Bucharest)。请解释在这种形式化下搜索是如何工作的。这是加速问题求解过程的实用方法吗？

3.13 证明 GRAPH-SEARCH 满足图 3.9 描述的图分离特性。（提示：证明一开始性质是保持的，然后证明如果迭代前性质保持，迭代后也会保持。）找出违反这条性质的搜索算法。

3.14 判断对错并说明理由：

a. 深度优先搜索至少要扩展与使用可采纳启发式的 A $ ^{*} $一样多的结点。

b. $ h(n)=0 $ 对于八数码问题是可采纳的启发式。

c. A*在机器人学中没有任何用处，原因是感知器、状态和行动都是连续的。

d. 即使是通话零代价的情况下，宽度优先搜索依然是完备的。

e. 假设车在棋盘上可以沿水平或垂直方向移动至任一方格中，但要注意不能跳过棋子。将车从方格 A 移到方格 B 的最小移动步数问题中，曼哈顿距离是可采纳的启

发式。

3.15 考虑起始状态为1、每个状态 k 都有两个后继 2k 和 2k+1 的状态空间。

a. 画出从 1~15 的状态空间。

b. 假设目标状态为11。请列出访问结点的顺序：宽度优先搜索、深度界限为3的深度受限搜索、迭代加深搜索。

c. 双向搜索求解此问题的有优势吗？两种方向的主支因子分别是多少？

d. 求解问题 c 是否需要对问题重新进行形式化成允许求解从状态 1 到一给定目标状态的问题时几乎没有搜索？

e. 调用行动从 k 到左边的 2k，和到右边的 2k+1。你能找到完全不用搜索就能求得解的算法吗？

3.16 图 3.32 中所示是铁路积木组合。任务是要将这些积木块联在一起组成铁路，要求不能有重叠的轨道不能有松动否则火车会开出去。

a. 假设积木块是精确无松动的。对此问题给出详细精确的形式化。

b. 选择一种无信息搜索方法完成这个任务并解释你选择的理由。

c. 解释为什么拿走任何一个开叉块会导致问题无解。

d. 对你形式化的状态空间给出上界（提示：考虑构造过程中的最大分支因子和最大深度，忽略重叠和松动。从每类只有一块开始）。

3.17 在 3.4.5 节，我们提到了迭代加长搜索，一致代价搜索的迭代法。它的思想是对路径代价使用不断增加的限制值。如果某个生成结点的路径代价值大于当前的限制，则马上丢弃此结点。每轮迭代的限制值被设为上轮迭代中丢弃的所有结点中最小的路径代价值。

a. 证明此算法对于一般的路径代价是最优的。

b. 考虑分支因子为 b、解深度为 d、单位代价的一致代价搜索树。迭代加长搜索需要经过多少次迭代才能找到解？

c. 考虑单步代价值为连续区间 $ [\varepsilon, 1] $，其中 $ 0 < \varepsilon < 1 $。在最坏情况下需要经过多少次迭代？

d. 实现该算法，将其应用于求解八数码问题和旅行商问题。比较该算法与一致代价搜索的性能，对结果给出评论。

3.18 找出一个状态空间，使用迭代加深搜索比深度优先搜索的性能要差很多（如，一个是 $ O(n^{2}) $，另一个是 $ O(n) $）。

3.19 编写程序，输入为两个网页的 URL，找出从一个网页到另一个网页的链接路径。用哪种搜索策略最适合？双向搜索适用吗？能用搜索引擎实现一个前任函数吗？

3.20 考虑图2.2定义的真空吸尘器世界问题。

a. 本章中哪种算法适合求解这个问题？这个算法是使用树搜索还是图搜索？

b. 使用你选择的算法来求解 $ 3 \times 3 $ 世界的最优行动序列，初始状态是上面三个方格里有灰尘，Agent 则在中心方格。

c. 构造真空吸尘器世界的搜索 Agent 并评价其性能，环境是 $ 3 \times 3 $ 方格，每个方格里有灰尘的概率是 0.2。在性能度量中不仅包括路径代价也要包括搜索开销，使用合理的转换比率。

d. 比较你最好的搜索 Agent 和简单的随机反射型 Agent 的性能，后者的策略是如果当前位置有垃圾就吸尘，否则就随机地移动。

e. 考虑如果世界扩大到 $ n \times n $ 会发生什么。当 n 变化时，搜索 Agent 和反射型 Agent 的性能会受到什么影响？

3.21 证明以下论点或举出反例：

a. 宽度优先搜索是一致代价搜索的一种特殊情况。

b. 深度优先搜索是最佳优先搜索的一种特殊情况。

c. 一致代价搜索是 A* 搜索的一种特殊情况。

3.22 对随机产生的八数码问题（用曼哈顿距离）和 TSP（用 MST——参见习题 3.30）问题，比较 A*算法和 RBFS 算法的性能。对结果进行讨论。八数码问题如果在启发式值上加上一个很小的随机数，会对 RBFS 的性能有何影响？

3.23 跟踪 A* 算法应用直线距离启发式求解从 Lugoj 到 Bucharest 问题的过程。给出结点扩展的顺序和每个结点的 f、g 和 h 值。

3.24 设计一个状态空间，对其使用 GRAPH-SEARCH 的 A* 得到次优解，其中 $ h(n) $ 是可采纳的而不是一致的。

3.25 启发式路径算法（Pohl，1977）是一种最佳优先搜索，它的评估函数是 $ f(n)=(2-w)g(n)+w h(n) $，假设 h 是可采纳的。w 取什么值能保证算法是最优的？当 w=0, w=1, w=2 时，分别是什么搜索算法？

3.26 考虑图 3.9 给出 2D 方格图没有边界的版本。开始状态为(0,0)，目标状态为 $ (x,y) $。

a. 状态空间的分支因子是多少？

b. 深度 $ k (k > 0) $ 有多少个状态？

c. 宽度优先树搜索扩展的最大结点数是多少？

d. 宽度优先图搜索扩展的最大结点数是多少？

e. $ h = |u - x| + |v - y| $ 对状态 $ (u, v) $ 是可采纳的启发式吗？请解释。

f. 使用 h 的 A* 图搜索扩展的结点数是多少？

g. 如果删除一些连线，h 还会是可采纳的吗？

h. 如果在一些非邻近状态间增加一些连线，h 还会是可采纳的吗？

3.27 n 辆车放置在 $ n \times n $ 网格的方格 $ (1,1) $ 至方格 $ (n,1) $ 中。这些车要以相反序移至另一端；从 $ (i,1) $ 开始的第 i 辆车，目标位置是 $ (n-i+1,n) $。每一轮，每辆车可以选择上、下、左、右各移动一格或静止不动；如果某辆车选择静止不动，跟它邻近的车（最多只能有一辆）可以跳过它。两辆车不能在同一格中。

a. 计算状态空间的大小，记为 n 的函数。

b. 计算分支因子的大小，记为 n 的函数。

c. 假设小车 i 坐标为 $ (x_{i}, y_{i}) $，并且网格中没有其他车辆，它的目标为 $ (n-i+1, n) $，请给出可采纳的启发式。

d. 对于整个问题而言，下列启发式函数哪个是可采纳的？请解释。

(i) $ \sum_{i=1}^{n} h_i $

(ii) $ \max(h_1, \cdots, h_n) $

(iii) $ \min(h_1, \cdots, h_n) $

3.28 设计一个启发函数，它在八数码问题中有时会估计过高，对某一特定问题它会求出次优解（可以用计算机编程找出）。证明：如果 h 被高估的部分不超过 c，A*算法返回的解代价比最优解代价多出的部分也不超过 c。

3.29 证明如果启发式是一致的，它一定是可采纳的。构造一个非一致的可采纳启发式。

3.30 旅行商问题（TSP）可以通过最小生成树（MST）启发式来解决，如果已经旅行已在进行中，MST 用于估计完成旅行的代价。一组城市的 MST 代价是连接所有城市的树的最小连接代价和。

a. 这个启发式是如何通过松弛的 TSP 问题得到的。

b. 说明为何 MST 启发式比直线距离启发式有优势。

c. 编写 TSP 问题的实例生成器，城市的位置用在单位正方形内的随机点表示。

d. 在文献中找到构造 MST 的有效算法，并将之应用 A* 图搜索来求解 TSP 问题实例。

3.31 在 3.6.2 节，我们定义了八数码问题的松弛：如果 B 是空的，一个棋子可以直接从方格 A 移到方格 B。求解该问题得出了 Gaschnig 启发式（Gaschnig，1979）。解释 Gaschnig 启发式至少和 $ h_{1} $（错位棋子数）一样精确的理由，举例说明它比 $ h_{1} $ 和 $ h_{2} $（曼哈顿距离）更精确的特例。解释如何能有效计算 Gaschnig 启发式。

3.32 我们给出了八数码问题的两个简单启发式：曼哈顿距离和错位棋子数。文献中的几个启发式声称是有所提高的——例如，Nilsson（1971），Mostow 和 Prieditis（1989），Hansson 等人（1992）。编程实现这些启发式并比较算法的性能。