第3章 搜索技术

搜索是人工智能的一个基本问题，它是推理不可分割的一部分。为了进行有效的搜索，需要将所求解的问题以适当的形式表示出来，一般情况下，不同的知识表示对应着不同的搜索过程。搜索可以根据知识表示方法分为状态空间搜索和与/或图搜索。状态空间搜索是指用状态空间来求解问题所进行的搜索。与/或图搜索是指用问题归约方法来求解问题所进行的搜索。

3.1 搜索的概念

3.1.1 基本概念

1. 什么是搜索

人工智能解决的问题大部分是结构不良或非结构化的问题，对于这样的问题一般不存在成熟的求解算法，而只能靠一步步摸索来寻求解答。正如瞎子爬山一样，他虽然有明确的目标即爬到山顶，但不知道山顶在何处，也不知道走什么样的路线才能达到山顶，他只能每走一步就试探一下周围的环境，选择最陡的方向前进。他可能走错方向，需要回过头来重走，也可能在一块平地上不知所措。像这样摸索着前进，不断搜寻前进方向的过程称为搜索。

对于一些结构性较好，理论上有算法可依的问题，由于问题本身的复杂性以及计算机在时间和空间上的局限性，有时也需要通过搜索来求解。例如在博弈问题中，计算机为了取得胜利，需要在每走一步棋之前，考虑到所有的可能性，然后选择最佳的走步。找到这样的算法并不困难，但计算机却要付出惊人的时间和空间上的代价。就可能的棋局来说，国际象棋有10120个棋局，围棋有10761个棋局，若把这些棋局都存储到计算机中去，需要占用巨大的存储空间，这是难以实现的。

2. 搜索的基本问题

在人工智能中，搜索一般包括两个基本问题，即“搜索什么”和“在哪里搜索”。“搜索什么”指的是目标，而“在哪里搜索”指的是搜索空间。搜索空间是一系列状态的汇集，通常是整个问题状态空间的一部分。人工智能中大部分问题的状态空间在问题求解之前不是全部知道的，因此人工智能搜索可以分为两个阶段：第一个阶段是状态空间的生成，第二个阶段是在该状态空间中对所求问题的状态进行搜索。

搜索策略的核心就是如何在一个比较大的问题状态空间中，只通过搜索比较小的范围，就找到问题的解。如果问题存在解，使用不同的搜索策略找到解时，搜索空间的大小是有区别的。一般来说，对于状态空间很大的问题，设计搜索策略的关键是解决组合爆炸问题。由于复杂问题的求解任务往往涉及许多解题因素，问题状态就可以通过解题因素的组合来加以表示（解题因素可设计为状态变量，如例2-2传教士和野人问题中的m、c和a）。所谓组合爆炸是指解题因素多时，因素组合的个数会呈爆炸性（指数级）增长，引起状态空间的急剧膨胀。例如某问题有4个因素，且每个因素有3个可选值，则因素的组合（即问题状态）有34 =81个；但若因素增加到10个，则组合的个数达310 =59049，状态空间扩大到729倍。解决组合爆炸问题的方法实际上就是选用好的搜索策略，使得只需搜索状态空间中很小的部分就能找到解。通过以上分析，状态空间、搜索空间和解路径的关系如图3-1所示。

通常，设计一个具体搜索策略需要考虑如下几个问题：首先，问题有解时，是否一定能找到解；其次，当搜索到解时，找到的是否为最佳解；再次，搜索过程是否能终止运行或是否会陷入一个死循环；最后，搜索的时间与空间复杂性如何或搜索的效率如何。

3.1.2 搜索的分类

通常情况下，可将搜索分成以下几类。

1. 正向搜索和逆向搜索

搜索根据其进行的方向，可分为正向搜索和逆向搜索。正向搜索是从初始状态出发，根据给出状态转换的操作算子集合，从一个给定状态变换到一个或多个新的状态，状态不断变换，直到产生一个满足目标要求的路径。搜索过程根据问题给定的约束知识指导搜索，使其沿着那些已知是正确的路线前进；逆向搜索则是先从目标状态出发，看哪些操作算子能产生该状态以及应用这些操作算子时相应地需要哪些条件，这些条件就是我们要到达的新的目标状态，这样搜索通过反向、连续不断地进行，一直找到问题给定的初始状态为止。它是通过目标来指导相关操作算子的搜索。

正向搜索与逆向搜索可以看成是对称的过程。那么如何判断选择哪种搜索方式更合理呢？可以依据下面两个因素：首先，判断初始状态与目标状态两者哪个状态集较小。在初始状态与目的状态中，往往从小的状态集出发朝大的状态集搜索，这样求解容易。其次，一般都是朝着分支因子（从一个节点出发可直接到达的平均节点数被称做分支因子）小的方向进行搜索。在本章介绍的搜索策略都是正向搜索。

2. 盲目搜索和启发式搜索

搜索根据是否有启发性信息，可分为盲目搜索和启发式搜索。盲目搜索又称无信息搜索，是一种穷举搜索。在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。盲目搜索简单易行，适合于许多复杂度不高的问题求解任务。而启发式搜索又称有信息搜索，它是指在搜索过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索方向，使搜索朝着最有希望的方向前进，并加速前进，找到最优解。可以看出启发式搜索因为利用了问题本身的特性，使它的搜索效率比盲目搜索高，也更易于求解复杂问题。

3. 树式搜索和线式搜索

搜索根据计算机实现的方式看，可分为树式搜索和线式搜索。树式搜索就是在搜索过程中记录所经过的所有节点和边，所记录的轨迹始终是一棵“树”，这棵树也就是搜索过程中所产生的搜索树。线式搜索在搜索过程中只记录那些当前认为是处在所找路径上的节点和边，所记录的轨迹始终是一条“线（折线）”。

4. 不回溯搜索和可回溯搜索

根据搜索过程中是否可回溯，搜索又分为不回溯搜索和可回溯搜索。不回溯搜索就是沿一条路一直前进，当该路无法扩展时，也不会退回来。例如爬山法是一种最简单的启发式搜索方法。人们在登山时，总是设法快速登上顶峰，所以只要好爬，总是选取最陡处，以求快速登顶。爬山实际上就是求函数极大值问题，不过这里不是用数值解法，而是依赖于启发性信息，试探性地逐步向顶峰逼近（广义地，逐步求精），直到登上顶峰。在爬山法中，限制只能向山顶爬去，即向目标状态逼近，不准后退，从而简化了搜索算法。这种不可回溯的搜索对于单一极值问题十分有效而又简便，但对于具有多极值的问题就无能为力了，不一定能到达最高峰。可回溯搜索是从一条路往前走，能进则进，不能进则退回来，换一条路再试。它相当于爬山的过程中记住了途经的岔路口，只要当前路径搜索失败就回溯（退回）到时序上最近的岔路口，向另一路径方向搜索，从而可以确保最后到达最高峰（即目标状态）。

3.2 状态空间搜索

当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。如果从状态空间图的角度来看，则对问题的求解就相当于在有向图上寻找一条从某一节点（初始状态）到另一节点（目标状态）的路径。事实上，有许多智力问题（如梵塔问题、传教士和野人渡河问题、旅行商问题和八皇后问题等）和实际问题（如定理证明、演绎推理、机器人规划等）都可以归结为在某一状态空间中寻找目标或路径的问题。因此研究状态空间搜索具有普遍的意义。下面先给出状态空间搜索的一般过程，再详细介绍盲目搜索和启发式搜索这两种搜索策略。

3.2.1 状态空间搜索的一般过程

首先给出一个八数码游戏的例子，回顾一下第2章所介绍的状态空间表示法，然后给出状态空间搜索的一般过程。在后面介绍搜索策略时将多次以这个例子展开阐述。

例3-1 八数码游戏。

在由3行和3列构成的九宫棋盘上放置数码为1到8的8个棋牌，剩下1个空格。游戏者只能通过棋牌向空格的移动来不断改变棋盘的布局。这种游戏求解的问题是如何移动棋牌才能从给定的初始布局（即初始状态）到达给定的目标布局（即目标状态），如图3-2所示。显然解路径实际上就是一个合法的棋牌移动序列。

解 用状态空间搜索方法解决该问题，应先为问题状态的表示建立数据结构，然后制定操作算子集。本例可以用一个3 × 3的矩阵来表示问题状态，每个矩阵元素Sij∈{0，1，…，8}，其中1≤i，j≤3，数字0则表示为空格。定义操作算子的最直观方法是，为每个棋牌制定一套可能的走步：左、上、右、下四种移动，这样就需32个操作算子。由于

只有紧靠空格的棋牌才能移动，因此最简单易行的方法是，仅为空格制定上述4种走步，那么就只需要4个操作算子。空格移动的唯一约束是不能移出棋盘。

在八数码的状态空间图中，一个节点代表一个棋局，相邻的节点就可以通过移动数码来产生。状态空间图中一条边也就代表一个移动规则或者移动规则的一次执行。

1. OPEN表和CLOSED表

OPEN表用于存放刚生成的节点，其形式如表3-1所示。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。

CLOSED表用于存放将要扩展或者已被扩展的节点，其形式如表3-2所示。所谓对一个节点进行扩展，就是指用合适的操作算子对该节点进行操作，生成一组子节点。

2. 状态空间搜索的一般过程

（1）把初始状态节点S0 放入OPEN表，并建立目前只包含S0 的图G。

（2）检查OPEN表是否为空，若为空则问题无解，退出。

（3）把OPEN表的第一个节点取出放入CLOSED表，并将该节点记为节点x。

（4）考察节点x是否为目标状态节点。若是，则求得了问题的解，退出。

（5）扩展节点x，生成一组子节点。把其中不是节点x先辈的那些子节点记为集合M，并把这些子节点作为节点x的子节点加入图G中。

（6）针对M中子节点的不同情况，分别进行如下处理：对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点x）的指针，并把它们放入OPEN表；对于那些先前已在G中出现过的M成员，确定是否需要修改它指向父节点的指针；对于那些先前已在G中出现并且已经扩展了的M的成员，确定是否需要修改其后继节点指向父节点的指针。

（7）按某种搜索策略对OPEN表中的节点进行排序；

（8）返回第（2）步。

通过循环地执行该算法，搜索图会因不断有新节点加入而逐步长大，直到搜索到目标状态节点。

3. 状态空间搜索过程的一些说明

（1）上述过程是状态空间搜索的一般过程，具有通用性。在此之后讨论的各种搜索策略都可看做是它的一个特例。各种搜索策略的主要区别是，对OPEN表中节点排序的准则不同。

（2）一个节点经一个操作算子操作后一般只生成一个子节点，但对一个节点可适用的操作算子可能有多个，此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点的父节点、祖父节点，此时不能把这些先辈节点作为当前扩展节点的子节点。

（3）一个新生的子节点，它可能是第一次被生成的节点，也可能是最先前已作为其他节点的后继节点被生成过，而当前又作为另一个节点的后继节点被再次生成，那么将它作为哪个节点的后继节点呢？一般情况是由初始状态节点到该节点路径上的代价决定，即哪条路径代价小，则它就作为该路径上的相应节点的后继节点。

（4）在搜索过程中，一旦某个被考察的节点是目标状态节点就得到了一个解。如果在搜索中一直找不到目标状态节点，而且OPEN表中不再有可扩展的节点，则搜索失败，在第（2）步退出。由于盲目搜索仅适用于状态空间是树状结构的问题，因此对盲目搜索而言，不会出现第（6）步中的后两种情况。

（5）由上述搜索过程可以看出，问题求解过程实际上就是搜索过程，问题求解的状态空间图是通过搜索逐步形成的，边搜索边形成，而且搜索每前进一步，就要检查一下是否达到了目标状态，这样就可以尽量少生成与问题求解无关的状态，即节省了存储空间，又提高了求解效率。

（6）在搜索过程中CLOSED表中的节点及方向指针就构成了一个树，即搜索树。

3.2.2 盲目搜索策略

根据状态空间搜索的一般过程，可以发现，提高搜索效率的关键在于优化OPEN表中节点的排序方式。若每次排在表首的节点都在最终搜索到的解路径上，则搜索算法不会扩展任何多余的节点就可快速结束搜索。因此节点在OPEN表中排序方式成为研究搜索算法的焦点，并由此形成了多种搜索策略。

一种简单的排序策略就是按预先确定的顺序或随机地对新加入到OPEN表中的节点进行排序。这种盲目的搜索策略根据搜索顺序的不同，可以划分为广度优先搜索和深度优先搜索两种搜索策略。

1. 广度优先搜索

广度优先搜索总是把扩展当前节点后生成的子节点置于OPEN表的后端，将OPEN表作为队列表使用，即先进先出，以使搜索优先向横广方向发展。广度优先搜索算法如下：

（1）把初始状态节点S0 放入OPEN表中；

（2）若OPEN表为空，则搜索失败，退出。

（3）取OPEN表中前面第一个节点放在CLOSED表中，令该节点为x并以顺序编号n；

（4）若目标状态节点Sg=x，则搜索成功，结束。

（5）若x不可扩展，则转至步骤（2）；

（6）扩展x，将其所有子节点配上指向x的指针依次放入OPEN表的尾部，转至步骤（2）。

如果问题有解，OPEN表中必然出现目标状态节点Sg，那么搜索到目标状态节点Sg 时，搜索则结束，然后根据返回指针在CLOSED表中往回追溯，直到初始状态节点，所得路径即为问题的解路径。存在解的情况下，广度优先搜索算法能够在状态空间图中找到一条从起始状态节点到目标状态节点的最优路径，因此它适用于搜索最短解路径的情况。例3-1的八数码游戏采用了广度优先搜索，得到的搜索树如图3-3所示。图中节点旁边的数字为搜索顺序。

假设一棵搜索树最大深度为d（对于树的节点的深度定义如下：根节点的深度为0；除根节点外，其他节点的深度是其父节点的深度加1。），每个节点的分支因子都为b。广度优先搜索的时间复杂度与搜索的节点数目成正比。

对于d层搜索树，搜索的最小节点数目为：1 +b+b2 +…+bd-1 +1 =（bd -1）/（b -1）+1；

而搜索的最大节点数目为：1+b+b2 +…+bd=（bd+1 -1）/（b-1）。

所以，平均总的搜索的节点数目为：bd-1b-1 +1+bd+1 -1b-1[

]/2≈bd（b+1）/2（b-1）。

广度优先搜索的空间复杂度和时间复杂度一样，需要很大的空间。它需要把树的所有叶节点都同时存储起来。当根节点扩展后，队列表中有b个节点，第1层的最后一个节点扩展后，队列表中有（2b-1）个节点；而当第d层最后一个节点正在检查是否是目标状态节点时，在队列表中的节点数目最多，为bd。因此它的空间复杂度与队列表中的长度有关，在最坏情况下复杂度为O（bd），复杂度的表示方法见5.1节介绍。通过以上分析，可知广度优先搜索的时间和空间复杂度比较高，当目标状态节点离初始状态节点比较远时（即d比较大时），会产生许多无用节点，搜索效率较低。

2. 深度优先搜索

深度优先搜索总是把扩展当前节点后生成的子节点置于OPEN表的前端，将OPEN表作为栈使用，即后进先出，使搜索优先向纵深方向发展。深度优先搜索算法如下：

（1）把初始状态节点S0 放入OPEN表中；

（2）若OPEN表为空，则搜索失败，退出。

（3）取OPEN表中前面第一个节点放入CLOSED表中，令该节点为x并以顺序编号n；

（4）若目标状态节点Sg=x，则搜索成功，结束。

（5）若x不可扩展，则转至步骤（2）；

（6）扩展x，将其所有子节点配上指向x的返回指针依次放入OPEN表的首部，转至步骤（2）。

由算法可知，深度优先搜索可能会选择了一个错误路径而一直搜索下去，也可能找到一个解路径，但不是最优的路径。因此深度优先搜索既不是完备的，也不是最优的。对于例3-1的八数码游戏问题采用深度优先搜索，得到的搜索树如图3-4所示。图中节点旁边的数字为搜索顺序。

假设搜索树深度为d，分支因子为b。如果深度优先搜索在第d层最左边找到了目标，则检查的节点数为（d+1）；而在最右边找到了目标，则检查了树中所有的节点，数目为：

1+b+b2 +…+bd=（bd+1 -1）/（b-1）

所以，平均检查节点数目为两者求平均，即：

[（bd+1 -1）/（b-1）+（d+1）]/2≈b（bd+d）/2（b-1）

由此可知深度优先搜索的平均时间复杂度为O（bd）。

深度优先搜索对内存的需求比较适中，它只需要保存从根节点到叶节点的单条路径，包括在这条路径上每个节点的未扩展的兄弟节点。当搜索到第d层时，每个层次上都有（b-1）个未扩展的节点，需要存储的节点数目为d（b-1）+1，因此深度优先搜索的空间复杂度是b的线性函数O（bd）。通过上述分析可知，深度优先搜索比广度优先搜索的优点是占用较少的空间。

3. 有界深度优先搜索

对于深度d比较大的情况，深度优先搜索需要很长的运行时间，而且还可能找不到解。一种比较好的求解方法是，对搜索树的深度进行控制，即有界深度优先搜索。

有界深度优先搜索的过程总体上是按深度优先搜索方式进行的，但对搜索深度需要给出一个深度限制dm，当深度达到dm时，如果还未找到解，就停止对该分支的搜索，换到另外一个分支进行搜索。有界深度优先搜索算法如下：

（2）若OPEN表为空，则失败，退出。

（3）取OPEN表中前面第一个节点放入CLOSED表中，令该节点为x并以顺序编号n；

（4）若目标状态节点Sg=x，则成功，结束。

（5）若x的深度d（x）=dm，或者x无子节点，则转至步骤（2）；

（6）扩展x，将其所有子节点xi 配上指向x的返回指针后依次放入OPEN表中前部，置d（xi）=d（x）+1，转至步骤（2）。

如果深度界限设置为4，则八数码游戏采用有界深度优先搜索得到搜索树如图3-5所示。图中节点旁边的数字为搜索顺序。

有界深度优先搜索的核心问题是dm 的设置。若dm 设置太小，而解路径长度大于dm，则搜索过程找不到目标状态节点；若dm设置太大，搜索过程又会产生过多的无用节点，其时间和空间复杂度与深度优先搜索的时间和空间复杂度类似。

4. 迭代加深搜索方式

在有界深度优先搜索中，由于我们并不知道解路径的长度，到底将dm设置为多少，才可能让问题求解完成？为了解决上述问题，可采用如下方法：先任意给出一个较小的数作为dm，然后按有界深度优先搜索进行搜索，若在此深度限制内找到目标状态节点，则算法结束；否则，增大深度限制dm，继续搜索。这就是迭代加深搜索的基本思想，其算法如下：

（1）设置当前深度限制dm=0；

（2）把S0 放入OPEN表中，置S0 的深度d（S0）=0；

（3）若OPEN表为空，则转至步骤（8）；

（4）若x的深度d（x）=dm（深度限制值），或者x无子节点，则转至步骤（8）；

（5）取OPEN表中前面第一个节点放入CLOSED表中，令该节点为x并以顺序编号n；

（6）若目标状态节点Sg=x，则成功，结束。

（7）扩展x，将其所有子节点xi 配上指向x的返回指针后依次放入OPEN表中前部，置d（xi）=d（x）+1，转至步骤（3）。

（8）若dm小于最大节点深度，则dm=dm+1，返回步骤（2）；

（9）否则，搜索失败，退出。

迭代加深搜索试图尝试所有可能的深度限制：首先深度为0，然后为1，2，…，一直进行下去。由于很多节点可能重复搜索，迭代加深搜索看起来会很浪费。但实际上前一次搜索与后一次相比是微不足道的，这是因为一棵树的分支因子很大时，几乎所有的节点都在底层，对于上面个层次节点的多次重复扩展对整个系统来说影响不是很大。

根据搜索深度为j时，深度优先搜索方法生产节点数目为（bj+1 -1）/（b-1），则迭代加深搜索中失败搜索所产生的节点数目为：

可以简化为b（bd-d）/（b-1）2。

如果迭代加深搜索在最后一次搜索深度d找到了目标状态节点，则该次搜索的节点数目与典型的深度优先搜索相同，为b（bd+d）/2（b-1）。总的平均搜索节点数目为：

b（bd-d）/（b-1）2 +b（bd+d）/2（b-1）≈（b+1）bd+1/2（b-1）2

由此，迭代加深搜索与深度优先搜索的时间复杂度的比率为：

（b+1）bd+1/2（b-1）2∶b（bd+d）/2（b-1）

对于d比较大来说，可以简化为：

（b+1）∶（b-1）

而迭代加深搜索与广度优先搜索的时间复杂度的比率为：

（b+1）bd+1/2（b-1）2∶bd（b+1）/2（b-1）=b∶（b-1）

因此，当分支因子b=10时，迭代加深搜索比深度优先搜索增加20%左右的节点，而比广度优先搜索只增加11%的节点。

上述四种搜索策略的复杂度及使用情况，见表3-3。

这些搜索策略的共同点是，可直接应用于一般的图搜索算法实现，不需要设计特别的OPEN表节点排序方法，从而简单易行。但由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态节点后才碰到解。因此这些搜索策略并不适合太复杂的任务。为了提高搜索的效率，可以引入领域专门知识去指导OPEN表节点排序，这就是下面要介绍的启发式搜索策略。

3.2.3 启发式搜索策略

启发式搜索策略的目标是，通过优先考察最有希望出现在较短解路径上的节点，来显著提高搜索的有效性。启发式搜索是利用启发性信息进行指导的搜索。启发性信息就是有利于尽快找到问题之解的信息，按其用途可分为如下3种：

（1）用于扩展节点的选择。即决定应先扩展哪一个节点，以免盲目地扩展。

（2）用于生成节点的选择。即在扩展一个节点的过程中，用于决定将生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。

（3）用于删除节点的选择。即决定应该从搜索树中抛弃或修剪哪些节点，以免造成进一步的时空浪费。

需要指出的是，不存在适合所有问题的万能启发性信息，即不同的问题有不同的启发性信息。本节只讨论利用上述第一种启发性信息的状态空间的搜索方式，即决定哪个是下一步要扩展的节点。

下面分别介绍以启发函数作为指导节点扩展的搜索算法，即局部择优法和全局择优法；以代价函数指导节点扩展的搜索算法，即分支界限法和最近择优法；以估价函数作为指导节点扩展的搜索算法的最佳图搜索法。

1. 局部择优法和全局择优法

（1）启发函数

在启发式搜索中，通常用启发函数来表示启发性信息。启发函数是用来估计搜索树上节点x与目标状态节点Sg接近程度的一种函数，通常记为h（x）。因此，启发式搜索可以看做是在盲目搜索基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。

启发函数并无固定的模式，需要针对具体问题进行具体分析。通常可以与目标状态的某种差异或某种概率进行度量。例如，八数码游戏中h（x）可以表示为节点x的数码棋局同目标棋局相比，数码位置不同的个数。

（2）全局择优法

全局择优法也称为最好优先搜索，是在OPEN表中保留所有已生成而未考察的节点，并计算它们的h（x）值，从中选出最优节点进行扩展。其算法如下：

① 把初始状态节点S0 放入OPEN表中，计算h（S0）；

② 若OPEN表为空，则搜索失败，退出。

③ 移出OPEN表中第一个节点x放入CLOSED表中，并以顺序编号n；

④ 若目标状态节点Sg=x，则搜索成功，结束。

⑤ 若x不可扩展，则转至步骤（2）；

⑥ 扩展x，计算每个子节点xi 的函数值h（xi），并将所有子节点配以指向x的返回指针后放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转至步骤（2）。

以例3-1的八数码游戏为例，令启发函数h（x）为节点x的棋局与目标棋局相比数码位置不同的个数，则搜索树如图3-6所示，图中节点旁边的数字为该节点启发函数的值。

（3）局部择优法

局部择优法是当一个节点被扩展以后，计算每一个子节点的h（x）值，并选择值为最小者作为下一个要考察的节点，由于它每次都只是在子节点范围内选择下一个要考察的节点。其搜索过程如下：

① 把初始状态节点S0 放入OPEN表中，计算h（S0）；

② 若OPEN表为空，则搜索失败，退出。

③ 移出OPEN表中第一个节点x放入CLOSED表中，并以顺序编号n；

④ 若目标状态节点Sg=x，则搜索成功，结束。

⑤ 若x不可扩展，则转至步骤②；

⑥ 扩展x，计算每个子节点xi 的函数值h（xi），按子节点的函数值大小以升序排列，并依次放入OPEN表的首部，为每个字节点配以指向x的返回指针，转至步骤②。

2. 分支界限法和最近择优法

（1）代价函数

在状态空间图的边上附有权值，它表示边的一种度量。把这种状态空间图称为加权状态空间图，其转化为的树型结构，称为代价树。所谓代价，可以指两点之间的距离、交通费用或所需时间等。

代价函数通常记为g（x），它表示从初始状态节点S0 到节点x的代价。用c（xi，xj）表示父节点xi 到子节点xj的代价，从而有g（xj）=g（xi）+c（xi，xj）。

（2）分支界限法

分支界限法也称最小代价优先法。每次从OPEN表中选出g（x）值最小的节点对其进行考察。它与全局最优搜索类似，仅是选取扩展节点的标准不同，一个是代价值最小，一个是启发函数值最小。其中，g（x）值是从初始状态节点S0 方向计算而来，它即与节点有关，也与边有关；而h（x）值则是从目标状态节点方向计算而来，它与节点有关，与边则可能有关或无关，具体计算方法也因问题而定。

例3-2 图3-7（a）是五个城市交通路线图，A城市是出发地，E城市是目的地，两城市之间的交通费用（代价）如图中数字所示。试求从A到E最小费用的旅行路线。

解 画出其如图3-7（b）所示的代价树。在代价树中，首先对A进行扩展，得到C1 和B1，由于C1 的代价小于B1 的代价，所以把C1 送入CLOSED表进行考察。对C1 扩展得到D1，由于B1 的代价小于D1，所以把B1 送入CLOSED表进行考察。扩展B1 得到D2 和E1，在OPEN表中的D1，D2 和 E1 三个节点中，它们的代价 g（D1）＜g（D2）＜g（E1），所以把 D1 送入CLOSED表进行考察。扩展D1 得到E2 和B2，在OPEN表中g（E2）=g（D2）＜g（B2）＜g（E1），所以考察E2。E2 是目标状态节点。所以采用分支界限法得到路径为ACBE，这是一条最小费用路径。

（3）最近择优法

最近择优法也称为爬山法，每次选取扩展节点中g（x）值最小的节点对其进行考察。与局部择优搜索类似，同样仅是选取扩展的节点的标准不同。

例3-2采用最近择优法，在代价树中，首先对A进行扩展，得到C1 和B1，由于C1 的代价小于B1 的代价。所以把C1 送入CLOSED表进行考察。对C1 扩展得到D1，因为只得到一个子节点D1，所以把D1 送入CLOSED表进行考察。对D1 扩展得到E2 和B2，E2 的代价小于B2，所以把E2 送入CLOSED表进行考察，E2 是目标状态节点。所以采用最近择优法，得到的路径为ACDE。

3. 最佳图搜索算法

最佳图搜索算法也称为A∗算法，是对A算法的一个改进。

（1）估价函数

在启发函数和代价函数的基础上，一种有效的方法就是设计体现启发性信息的估价函数来计算每个节点的得分，以便用于排列它们在OPEN表中的位置。估价函数可以设计为如下形式

f（x）=g（x）+h（x）其中，g（x）为从初始状态节点S0 到节点x已经付出的最小代价；h（x）为从节点x到目标Sg估计的最小代价，它体现了问题的启发性信息，其形式要根据问题的特性确定；估价函数f（x）表示从初始状态节点S0 到达节点x，已经付出的代价与节点x到达目标状态节点Sg的接近程度估计值的总和。

估价函数的作用就是估计OPEN表中各个节点的重要程度，以决定它们在OPEN表中的次序。

（2）A算法

A算法是根据f（x）值对OPEN表中的节点排序，f（x）值最小者排在首位，优先加以扩展，体现了最佳优先搜索策略的思想。A算法的具体步骤如下：

① 把附有f（S0）的初始状态节点S0 放入OPEN表；

② 若OPEN表为空，则搜索失败，退出。

③ 移出OPEN表中第一个节点x放入CLOSED表中，并以顺序编号n；

④ 若目标状态节点Sg=x，则搜索成功，结束。

⑤ 若x不可扩展，则转至步骤②；

⑥ 扩展x，生成一组附有f（xi）的子节点，对这组子节点作如下处理：首先考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无x的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f（xi）值，修改原则是“抄f（xi）值小的路走”。然后对其余子节点配上指向x的返回指针后放入OPEN表中，并对OPEN表按f（xi）值以升序排序，转至步骤②。

下面以例3-1的八数码游戏为例，观察A算法的应用。

令f（x）=d（x）+w（x）。其中，d（x）是当前被考察和扩展的节点x在搜索图中的节点深度；而启发函数w（x）的值是节点x与目标状态节点Sg 相比较，错位的棋牌个数。由此可知，初始状态节点的估价函数值f（x）=0+3=3。算法A搜索的解路径十分快捷，除了个别走步判断失误外（节点d的选用和扩展）其他的走步选择全部正确，如图3-8所示，图中字母后的括号中给出估价函数f（x）的值。每个搜索循环结束时OPEN表和CLOSED表中的节点变化如表3-4所示。

（3）A∗算法

A算法并不能保证当图中存在从初始状态节点到目标状态节点的最佳路径时，一定能找到它。那么如何才能确保找到这条最佳路径呢？为此，需要定义估价函数

f∗（x）=g∗（x）+h∗（x）其中，g∗（x）为从初始状态节点S0 到节点x的实际最小代价；h∗（x）为从节点x到目标状态节点Sg的实际最小代价；f∗（x）为初始状态节点S0 经节点x到目标状态节点Sg 的实际最小代价。如果存在多个目标状态，那么h∗（x）取h∗（x，Sgi）中最小者。

估价函数f（x）与f∗（x）相比较，实际上f（x）、g（x）和h（x）分别是f∗（x）、g∗（x）和h∗（x）的估计值。g∗（x）和h∗（x）在最短解路径找到之前是未知的，而且对于复杂的应用领域，要设计出接近于f∗（x）的f（x）往往也是困难的。

例如，以节点深度d（x）作为g（x），并有g（x）≥g∗（x），在算法执行过程中随着更多的搜索信息获得，g（x）的值将呈下降趋势。h（x）的设计则依赖于启发性信息的应用，其中h（x）是h∗（x）的下界，即对所有节点x都有h（x）≤h∗（x）。如果对上述A算法再限制其估价函数中的启发函数h（x），对所有的节点x均有h（x）≤h∗（x），则它就称为A∗算法。

当问题有解时，A∗算法一定能找到一条到达目标状态节点的最佳路径。例如在极端情况下，若h（x）≡0（肯定满足下界范围条件），因而一定能找到最佳路径。此时若g（x）≡d（x），则算法等同于广度优先算法。前面已提到过，广度优先算法能保证找到一条到达目标状态节点最小长度的路径，因而这个特例从直观上就验证了A∗算法的一般结论。

A∗算法中，限制h（x）≤h∗（x）的原因是为了保证取得最佳解。在前面介绍A算法时，启发函数h（x）是h∗（x）的一种近似估计，但对h（x）本身没有任何具体的限制，因此也就无法具体讨论算法的一些性质。而A∗算法具有如下一些性质。

1）A∗算法的可采纳性

对于可解状态空间来说，如果一个搜索算法能在有限步内终止，并且能找到最佳解，则称该搜索算法是可采纳的。

A∗算法是可采纳的，即它能够在有限步内终止并找到最佳解。下面分三点证明这一结论。

① 对于有限图，A∗算法一定会在有限步内终止。

证明 对于有限图，其节点个数有限，所以A∗算法在经过若干次循环之后只能出现两种情况。一种是由于搜索到目标状态节点而终止，另一种是由于OPEN表中的节点被取完而终止。不管发生那种情况，A∗算法都能在有限步内终止。

② 对于无限图，只要从初始状态节点到目标状态节点有路径存在，则A∗算法也必然会终止。

证明 第一步先证明在A∗算法结束之前，OPEN表中总存在节点n′，它是最佳路径上的一个节点，且满足f（x′）≤f∗（S0）。

设最佳路径是S0，x1，x2，…，xm，S∗g，由于 A∗算法中的 h（x）满足 h（x）≤h∗（x），所以f（S0），f（x1），f（x2），…，f（xm）均不大于f（S∗g）=f∗（S0）。

又因为A∗算法是全局择优的，所以在它结束前，OPEN表中一定含有S0，x1，x2，…，xm，S∗g中的一些节点，设x′是其中最前面一个，则它必然满足 f（x′）=f∗（S0）。至此，第一步证明结束。

第二步用反证法，即假设A∗算法不终止，则会得出与上一步矛盾的结论，从而说明A∗算法一定会终止。

假设A∗算法不终止，并设e是图中各条边的最小代价，d∗（xi）是从S0 到节点xi 的最佳路径长度，则显然有g∗（xi）≥d∗（xi）× e。

又因为g（xi）≥g∗（xi），所以有g（xi）≥d∗（xi）× e。

因为h（xi）≥0，f（xi）≥g（xi），故得到f（xi）≥d∗（xi）× e。

由于A∗算法不终止，随着搜索进行，d∗（xi）会无限增大，从而使f（xi）也无限增大。这就与上一步证明得出的结论矛盾，因为对可解状态空间来说，f∗（S0）一定有极限值。

所以，只要从初始状态节点到目标状态节点有路径存在，即使对于无限图，A∗算法也一定会终止。

③ A∗算法一定终止在最佳路径上。

证明 假设A∗算法不是在最佳路径上终止，而是在某个目标状态节点t处终止，即A∗算法未能找到一条最佳路径，则f（t）=g（t）＞f∗（S0）。

但由②的证明可知，在A∗算法结束之前，OPEN表中存在节点x′，它在最佳路径上，且满足f（x′）≤f∗（S0）。

此时，A∗算法一定会选择x′来扩展而不会选择t，这就与假设矛盾。所以，A∗算法一定终止在最佳路径上。

根据可采纳性定义及以上证明可知A∗算法是可采纳的。同时由上面的证明还可得知：A∗算法选择扩展的任何一个节点x满足如下性质：f（x）≤f∗（S0）。

2）A∗算法的最优性

A∗算法的搜索效率很大程度上取决于h（x），在满足h（x）≤h∗（x）的前提下，h（x）的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越少，搜索效率越高。

定理3-1 有两个A∗算法A1 和A2，若A2 比A1 有较多的启发性信息（即对所有非目标状态节点均有h2（x）＞h1（x）），则在具有一条从S0 到Sg 的状态空间图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1 所扩展，即A1 扩展的节点至少和A2 一样多。

证明 对节点的深度应用数学归纳法。

① 对深度d（x）=0的节点（即初始状态节点S0），定理结论成立，即若S0 为目标状态节点，则A1 和A2 都不扩展S0，否则A1 和A2 都扩展了S0（归纳法前提）。

② 设深度d（x）≤k，对所有路径的叶节点，定理结论都成立（归纳法假设）。

③ 要证明d（x）=k+1时，所有路径的叶节点，结论成立，用反证法证明。

设A2 搜索树上有一个节点x（d（x）=k+1）被A2 扩展了，而对应于A1 搜索树上的这个节点x，没有被A1 扩展。根据归纳法假设条件，A1 扩展了x的父节点，则x在A1 搜索树上，因此A1 结束时，x必定保留在其OPEN表上。x没有被A1 选择扩展，有f1（x）≥f∗（s），即g1（x）+h1（x）≥f∗（S0）

所以

另一方面A2 扩展了x，则有f2（x）≤f∗（S0），即

所以

由于d=k时，A2 扩展的节点，A1 也一定扩展，故有

g1（x）≤g2（x）（因A1 扩展的节点数可能较多）

所以

比较式（3-2）、式（3-3）可得：至少在节点x上有h1（x）≥h2（x），这与定理的前提条件矛盾，因此存在节点x的假设不成立。

由这个定理可知，使用启发函数h（x）的A∗算法，比不使用h（x）（h（x）≡0）的算法，求得最佳路径时扩展的节点数要少。

再以例3-1八数码游戏为例，启发函数p（x），其值是节点x与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。p（x）比w（x）更接近于h∗（x），因为p（x）不仅考虑了错位因素，还考虑了错位的距离（移动次数），其搜索树如图3-9所示，图中字母后的括号中给出估价函数值。

若启发函数h（x）采用p（x），则初始状态节点的估价函数值f（S0）=4。在第一个搜索循环结束时，OPEN表中的节点排序为：bacd，这些节点的估价函数值依次为：4666；而在使用w（x）情况下（见图3-7），OPEN表中的节点排序为abcd，估价函数值依次为：4455。显然，p（x）使得用w（x）不能区分的节点a（4）和b（4）区分为a（6）和b（4），从而搜索过程不再会错误选择节点a，而是一下子就选对了节点b加以扩展。正因为w（x）≤p（x）≤h∗（x），所以采用p（x）扩展出的节点总数不会比采用w（x）时多。

3）h（x）的单调性限制

所谓单调性限制是指h（x）满足如下两个条件：

① h（S0）=0；

② 设xj是节点xi 的任意子节点，则有：h（xi）-h（xj）≤c（xi，xj）。

其中，Sg是目标状态节点；c（xi，xj）是节点xi 到其子节点xj的边代价。

定理3-2 若h（x）满足单调限制，则由A∗算法所扩展的节点序列，其f（x）值是非递减的，即f（xi）≤f（xj）。

证明 由单调限制条件

h（xi）-h（xj）≤c（xi，xj）

即

f（xi）-g（xi）-f（xj）+g（xj）≤c（xi，xj）

f（xi）-g（xi）-f（xj）+g（xi）+c（xi，xj）≤c（xi，xj） f（xi）-f（xj）≤0

定理3-3 若h（x）满足单调限制条件，则A∗算法扩展了节点x之后，就已经找到了到达节点x的最佳路径。即若A∗算法选x来扩展，在单调限制条件下有g（x）=g∗（x）。

证明 设x是A∗算法选做扩展的任一节点，若x=s，显然有g（s）=g∗（s）=0，因此考虑x≠s的情况。我们用序列P=（s，x1，…，xk-1，x）表达到达x的最佳路径。现在从OPEN中取出非初始状态节点x扩展时，假定没有找到P，这时CLOSED中一定会有P中的节点（至少s是在CLOSED中，x刚被选做扩展，不在CLOSED中），把P序列中（依顺序检查）最后一个出现在CLOSED中的节点称为xj，那么xj+1是在OPEN中（xj+1≠x），由单调限制条件，对任意i有

因为xi 和xi+1在最佳路径上，所以有

g∗（xi+1）=g∗（xi）+c（xi，xi+1）

代入式（3-4）式后有

g∗（xi）+h（xi）≤g∗（xi+1）+h（xi+1）

这个不等式对P上所有相邻的节点都合适，若从i=j到i=k-1应用该不等式，并利用传递性有

g∗（xl+1）+h（xl+1）≤g∗（xk）+h（xk）

即

另一方面，A∗选x来扩展，必有

比较式（3-5）和式（3-6）得g（x）≤g∗（x），但已知g（x）≥g∗（x），因此选x扩展时必有g（x）=g∗（x），即找到了到达x的最佳路径。

定义满足单调条件的h（x），是避免重复扩展节点的好办法。但是对于实际问题来说，有时定义一个单调的h（x）并不是一件很容易的事，那么也可以通过修改算法，来达到避免或者减少重复节点扩展的问题。

（4）提高A∗算法搜索效率的措施

在设计启发函数时，可以通过以下几种措施进一步提高A∗算法的搜索效率。

① 在一些情况下，牺牲可采纳性有利于提高搜索效率。也就是说，h（x）不是h∗（x）的下界，算法虽然不能保证找到的是最短路径，但往往对简化h（x）的计算和快速求解都有利。

② 引入权重调节。对于估价函数f（x）=g（x）+h（x），当h（x）≡0 时，倾向于先进入OPEN表的节点会优先被考查和扩展，先进入的节点x往往具有较小的g（x）值，接近于广度优先的搜索策略；当g（x）≡0时，则倾向于后进入OPEN表的节点会优先被考查和扩展，后进入的节点x往往更接近于目标状态，即h（x）值较小，接近于深度优先的搜索策略。

因此为了更有效地搜索解答，可令估价函数f（x）=g（x）+wh（x），w用做加权。搜索图的浅层（上部），可以让w取较大值，使g（x）所占比例很小，突出启发函数的作用，加速向纵深方向搜索；搜索到较深的层次，又让w取较小值，以使g（x）所占比例很大，并确保wh（x）≤h∗（x），搜索向横广方向发展，寻找到较短的解路径。

③ 启发函数的精确度对性能的影响。搜索效率的一个度量是有效分支因子b∗，它描述了一个搜索过程朝着目标前进的激烈程度。如果搜索树中每个非树叶节点都有b∗个子节点，树中的叶节点的深度均为d，树中的节点总数是N，则b∗和路径长度d以及生成的总节点数N之间有下列关系：N+1=1+b∗ +（b∗）2 +…+（b∗）d。根据上述分析，可以看出被发现路径的长度（代价）、在所发现路径上被扩展的节点数和h（x）的计算量这三个因素影响A∗算法的效率。

4. 启发式搜索的适用性讨论

启发式搜索的估价函数可设计为全局或局部的估价器。对于复杂的问题往往将估价函数设计为局部的估价器，因为全局的估价器难以设计。局部估价器可以使搜索过程依赖于丰富的领域知识，它往往可设计为规则组去识别合适的操作算子，以推进搜索过程到下一状态。

启发式搜索技术的应用面临三个关键选择：首先，是确定性搜索方式，还是非确定性搜索方式；其次，是搜索目标状态本身，还是搜索达到目标状态的解路径（往往表示为状态或操作算子序列）；再次，是要求搜索一个解，还是全部或最佳解。可以说，后两者在一定程度上决定了前者。

对于复杂问题的状态空间，搜索路径上有许多分支。所谓确定性方式，就是利用启发性信息选取最好的分支，而舍弃所有其余分支不再予以考虑。在仅靠启发性信息不足以保证在所选路径上搜索成功时，非确定性方式无疑是明智的选择。尤其是要求获得最佳解答的场合，更需要采用非确定性方式，因为只有穷尽搜索到全部成功路径，才能判断最佳者。

最终解是目标状态还是解路径影响着确定性或非确定方式的选择。如果要求解是解路径，则需要寻找较好的操作算子序列，那么确定性搜索方式显然难以奏效。但若只要求到达目标状态，而又有较多路径可达，则确定性方式易于奏效。

常用的非确定性搜索方式又可分为两类：最佳优先搜索和深度优先加回溯搜索。前者将估价器作为加在各搜索分支上的通断开关，使搜索过程总是在总体上最有希望的分支上进展；后者则是局部最优的搜索方法，系统总是在当前状态直接产生的后继状态中利用启发性信息选取最有希望的状态推进搜索过程。由于允许估价不精确，甚至知识贫乏，搜索有可能失败，这就需要通过回溯去纠正错误，以使搜索能在新的路径上展开。但是最佳优先和深度优先加回溯的效率都十分低。

3.3 与/或图搜索

3.3.1 与/或图搜索的一般过程

同状态空间图一样，与/或图也是问题求解的一种抽象表示。事实上许多问题的求解过程都可以用与/或图搜索来描述，所以研究与/或图搜索也具有普遍意义。

用与/或图来描述问题的求解过程，就是将原问题通过有关规则不断分解（子问题）或变换（为等价问题），直到问题分解或变换为一些直接可解的子问题，或者不可解也不能再分解或变换的子问题为止。然后根据所得到的搜索树确定原问题的可解性。如果可解，则由搜索树找出解图或解树。由于一般的与/或图涉及一些复杂的处理，下面首先介绍一种特殊的与/或图，即与/或树搜索的一般过程。

与/或树的一般搜索过程如下：

（1）把原始问题作为初始状态节点S0，把S0 放入OPEN表；

（2）移出OPEN表的第一个节点x放入CLOSED表，并以顺序编号n；

（3）若节点x可扩展，则做下列工作：

① 扩展x，将其子节点配上指向父节点的指针放入OPEN表；

② 考察这些子节点中是否有终止节点。若有，则标记它们为可解节点，并将它们放入CLOSED表，然后由它们的可解返回推断其先辈节点的可解性，并对其中可解节点进行标记。如果初始状态节点S0 也被标记为可解节点，则搜索成功，结束。

③ 删去OPEN表中那些具有可解先辈的节点，转至第（2）步；

（4）若x不可扩展，则做下列工作：

① 标记x为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中不可解的节点进行标记，如果初始状态节点S0 也被标记为不可解节点，则搜索失败，退出。

② 删去OPEN表中那些具有不可解先辈节点，转至第（2）步；

由上述与\或树搜索过程可知，与/或图搜索的目标是寻找解图或解树，从而求得原始问题的解。如果在搜索的某一时刻，通过可标示过程能够确定初始状态节点是可解的，则此初始状态节点及其下属的可解节点就构成了解图或解树。如果在某时刻被选为扩展的解点不可扩展，并且它不是终止节点，则此节点就是不可解节点。此时可应用不可解标示过程确定初始状态节点是否为不可解节点，如果可以肯定初始状态节点是不可解的，则搜索失败；否则继续扩展节点。

可解与不可解标示过程都是自下而上进行的，即由子节点的可解性来确定父节点的可解性。可解标示过程是由可解子节点来确定父节点、祖父节点等先辈节点为可解节点的过程。如果某个节点已经标记为可解节点，其后裔中不可解节点就不可再有用，可从搜索树中删去。不可解标示过程是由不可解的子节点来确定父节点、祖父节点等先辈节点为不可解节点的过程。如果某个节点被标记为不可解节点，其全部后裔节点不再有用，从搜索树中删去，但当前节点还不能删去，因为在判断先辈节点的可解性时还要用到它。

3.3.2 与/或图的盲目搜索策略

与/或图的搜索同样可以分为盲目搜索和启发式搜索两类。盲目搜索包括广度优先搜索和深度优先搜索，它们的共同特点是：

（1）搜索从初始状态节点开始，先自上而下进行搜索，寻找终止节点及叶节点，然后再自下而上进行标记，一旦初始状态节点被标记为可解节点，搜索就不再继续进行。

（2）与/或图的盲目搜索一般得到的是解树。

（3）搜索都是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与/或树中所处的位置，而不考虑要付出的代价。因此求得的解树不一定是代价最小的解树，即不一定是最优解树。

它们的不同之处，体现在与/或树的一般搜索过程的第（3）步中第①点。

广度优先搜索方式是“扩展 x，将其子节点配上指向父节点的指针放入 OPEN 表的尾部。”；而深度优先搜索方式则是“将其子节点配上指向父节点的指针放入OPEN表的首部。”

为了求得最佳解树，就要在每次确定欲扩展的节点时，先往前多看几步，计算一下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索的方法称为与/或树的有序搜索，它是一种重要的启发式搜索策略。

3.3.3 与/或图的启发式搜索策略

与状态空间搜索过程类似，引入应用领域的启发性信息去引导搜索过程，可以显著提高搜索的有效性，加速搜索算法的收敛。考虑到与/或图中搜索的是解树（或解图），不是由相邻节点间连接成的解路径，因此在上一节估价函数f（x）中的g（x）就没有意义了，而只需估算h（x）就可以。需要注意的是此处的h（x）也并非对于最小路径代价的估计，而是对于代价最小解树（或解图）的估计。另外，由于与/或图中子节点或子节点组间可以存在“或”关系，在搜索过程中会同时出现多个候选的待扩展局部解树（或局部解图），因此应该估计所有这些局部解树（或局部解图）的可能代价，并从中选择一个可能代价最小的用于下一步搜索。由于解树（或解图）以递归方式生成，所以解树（或解图）的代价也以递归方式计算。一旦某个父节点x的外向k-连接指向k个子节点（x1，x2，…，xk），若每个子节点的估计值为h（xi）的值（i=1，2，…， k），则从父节点x到终止节点集合构成的解树（或解图）的可能代价f（x）可以用公式：

f（x）=k+h（x1）+h（x2）+…+h（xk）

计算，并用于取代原先在扩展出节点x时直接基于h（x）估算而得出的f（x）值。显然，基于子节点h（xi）算出的f（x）更为准确。如此递归计算，可以计算出更为准确的f（x0），即从初始状态节点到终止节点集合的解图的可能代价。

1. 与/或树的有序搜索

（1）解树的代价

为进行与/或树的启发式搜索，需要计算解树的代价，而解树的代价可通过计算解树中的节点的代价得到。

设c（xi，xj）表示节点xi到其子节点xj的代价，则计算节点xi 的代价的方法如下：

① 如果xi 是终止节点，则定义节点xi 的代价h（xi）=0；

② 如果xi 是“或”节点，xj1，xj2，…，xjx是它的子节点，则节点xi的代价由下式计算得到

③ 如果xi 是“与”节点，则节点xi的代价有两种计算方法：和代价法及最大代价法。若按和代价法进行计算，则有

若按最大代价法进行计算，则有

④ 如果xi 不可扩展，且又不是终止节点，则定义h（xi）=∞。

例3-3 图3-10是一棵与/或树，其中包括两棵解树，一棵解树由S0，A，t1 和t2 组成；另一棵解树由S0， B，D，G，t4 和t5 组成。在此与/或树中，t1，t2，t3，t4 和 t5为终止节点；E和F是叶节点，代价均为∞；边上的数字是该边的代价。

解 由左边的解树可得：

按和代价：h（A）=11，h（S0）=13

按最大代价：h（A）=6，h（S0）=8

由右边的解树可得：

按和代价：h（G）=3，h（D）=4，h（B）=6，h（S0）=8

按最大代价：h（G）=2，h（D）=3，h（B）=5，h（S0）=7

显然，若按和代价计算，右边子树是最佳解树，其代价为8；若按最大代价计算，右边的解树仍然是最佳解树，其代价是7。有时用不同的计算代价方法得到的最佳解树并不相同。

（2）希望树

无论是用和代价方法还是用最大代价方法，当要计算任一节点x的代价h（x）时，都要求已知其子节点yi 的代价h（yi）。然而，搜索是自上而下进行的，除非节点x的全部子节点都是

解决办法是根据问题本身提供的启发性信息定义一个启发函数，由此启发函数估计出其子节点yi 的代价h（yi），然后再按和代价或最大代价算出节点x的代价值h（x），利用h（x）可计算x的父节点、祖父节点，直到S0 的h值，由此各先辈节点的代价，自下而上逐层推算出来。同理，当某个子节点yi 被扩展后，计算h（yi）。而此时算出的h（yi）可能与原先估算出的h（yi）不相同，这时应该用后算出的h（yi）取代原先估算出的h（yi），并且按此h（yi）自下而上地重新计算各个先辈节点的h值。当节点yi 的子节点又被扩展时，上述过程又要重复一遍。总之，每当有新一代节点生成时，都要自下而上地重新计算其先辈节点的代价h，这是一个自上而下地生成新节点，又自下而上地计算代价h的反复进行的过程。

有序搜索的目的就是求出最佳解树。每次选择扩展的节点时，都应选择有希望成为最佳解树的那一部分节点进行扩展。由于这些节点及其先辈节点（包括初始状态节点S0）所构成的与/或树有可能成为最佳解树的一部分，因此称它为“希望树”。

在搜索过程中，随着新节点不断生成，节点的代价值不断变化，因此希望树也是不断变化的。某一时刻，由这部分节点构成希望树，但到另一时刻，可能由另一些节点构成了希望树。但不管如何变化，任一时刻的希望树都必须包含初始状态节点S0，而且它是对最佳解树近根部分的某种估计。

下面给出希望树的定义：

① 初始状态节点S0 在希望树T中。

② 如果节点x在希望树T中，则一定有：

a. 如果x是具有子节点y1，y2，…，yn的“或”节点，则具有min{c（xi，yi）+h（yi）}值的那个子节点yi 也应在希望树T中。

b. 如果x是“与”节点，则它的全部子节点都应在希望树T中。

（3）与/或树的有序搜索

与/或树的有序搜索是一个不断选择、修正希望树的过程。如果问题存在解，则有序搜索一定会找到最佳解树。

与/或树的有序搜索过程如下：

（1）把初始状态节点S0 放入OPEN表中。

（2）求出希望树，根据当前搜索树中节点的代价h求出以S0 为根的希望树T。

（3）依次把OPEN表中希望树T的叶节点x选出放入CLOSED表中。

（4）如果节点x是终止节点，则做下列工作：

① 标示x为可解节点；

② 对希望树T应用可解标示过程，把x的先辈节点中的可解节点都标示为可解节点；

③ 若S0 能被标示为可解节点，则T就是最佳解树，成功退出。

④ 否则，从OPEN表中删去具有可解先辈的所有节点。

（5）如果节点x不是终止节点，且它不可扩展，则做下列工作：

① 标示x为不可解节点；

② 对希望树T应用不可解标示过程，把x的先辈节点中的不可解节点都标示为不可解节点；

③ 若S0 能被标示为不可解节点，则失败，退出。

④ 否则，从OPEN表中删去具有不可解先辈的所有节点。

（6）如果节点x不是终止节点，但它可扩展，则做下列工作：

① 扩展节点x，产生x的所有子节点；

② 把这些子节点放入OPEN表中，并为每个子节点配置指向父节点（节点x）的指针；

③ 计算这些子节点的h值及其先辈节点的h值。

（7）转至第（2）步。

下面举例说明上述搜索过程。

例3-4 设初始状态节点S0，每次扩展两层，并设S0 经扩展得到如图3-11（a）所示的与/或树，其中子节点B，C，E和F用启发函数估算出的h值分别是h（B）=3，h（C）=3，h（E）=3，h（F）=2。

若按和代价计算，则得到h（A）=8，h（D）=7，h（S0）=8。

这里把边代价一律按1 计算。此时S0 的右子树是希望树。下面将希望树的节点进行扩展。

设对节点E扩展两层后得到如图3-11（b）所示的与/或树，节点旁的数字为用启发函数估算出的h值。则按和代价法计算得到h（G）=7，h（H）=6，h（E）=7，h（D）=11。此时，由S0 的右子树算出的h（S0）=12。但是由左子树算出的h（S0）=9。显然，左子树的代价小，所以现在改取左子树作为当前希望树。

假设对节点B扩展两层后得到如图3-11（c）所示的与/或树，节点旁的数字是对相应节点的估算值，节点L的两个子节点是终止节点，则按和代价法计算得到h（L）=2，h（M）=6， h（B）=3，h（A）=8。由此可推出h（S0）=9。这时左子树仍是希望树，继续对其扩展，然后该扩展节点C。

假设节点C扩展两层后得到如图3-11（d）所示的与/或树，节点旁的数字是对相应节点的估算值，节点N的两个子节点是终止节点。按和代价计算得到h（N）=2，h（P）=7，h（C）=3， h（A）=8。由此可推算出h（S0）=9。另外，由于N的两个子节点都是终止节点，所以N和C都是可解节点。再由前面推出B是可解节点，可推出A和S0 都是可解节点。这样就求出了代价最小的树，如图3-11（d）中粗线部分所示。该最佳解树是用和代价求出的，解树代价为9。

上面介绍了与/或树的启发式搜索算法，对于一般的与/或图也有类似的启发式搜索算法。特别地，与/或图搜索也有一个典型的启发式搜索算法——AO∗算法。

2. AO∗算法

AO∗算法类似于状态空间搜索中的A∗算法。在与/或图搜索中，由于“与”节点的存在，单纯对一个节点的估价已经不能反映解图的全面情况。与/或图中的解图相当于状态空间中的解路径。从对节点x的估价，即对“初始状态节点—节点x—目标状态节点”这一条路径的估价思路出发，我们可以很容易地想到，能否通过对局部解图进行估价，来达到类似于A∗算法的搜索目的。

对于与/或图来说，由于局部解图中有多个叶节点，不能像状态空间搜索那样，通过对某一个节点的估价来实现对整个局部解图的估价，而是要通过对局部解图的估价来选择待扩展的节点。

AO∗算法可以划分为两个阶段。

第一阶段：解图生成过程，即扩展节点。对于每一个已经扩展了的节点，AO∗算法都有一个指针，指向该节点的后继节点中代价值小的那个连接符。解图生成过程，就是从初始状态节点出发，按照该指针向下搜索，直到找到一个未扩展的节点为止。然后扩展该节点。从下面的讨论可以知道，这实际上扩展的是一个代价值最小的局部解图。

第二阶段：代价值计算过程。这是一个逆向的计算过程。设x为最新被扩展的节点，该节点有m个外向连接符连接x的所有后继节点。根据代价值的计算公式，可以计算出节点x相对于每一个外向连接符的代价值。从中选择一个最小值作为x的代价值，并标记一个指针指向产生最小代价值的外向连接符。对于x的父节点，进行同样的计算。重复这一过程，直到初始状态节点S0 为止。这时，从S0 出发，选择那些指针所指向的连接符得到的局部解图，为当前代价值最小的局部解图。当连接符全部为1-连接符时，局部解图就是一个路径，选择一个代价值最小的局部解图扩展，与上一节中“从OPEN表中选择一个f（x）值最小的节点扩展”是一致的。

（1）AO∗算法的实现过程

设：G表示指示搜索图；G′表示被选中的待扩展局部解图；LGS表示候选的待扩展局部解图集；S0 表示指示根节点，即初始状态节点；x表示被选中的待扩展节点；fi（S0）表示第i个候选的待扩展局部解图的可能代价。

该算法的实现过程如下：

① G：= S0，LGS为空集。

② 若S0 是终止节点，则标记S0 为可解节点；否则计算f（S0）=h（S0），并把G作为0号候选局部解图加进LGS。

③ 若S0 标记为可解节点，则算法成功返回。

④ 若LGS为空集，则搜索失败返回；否则从LGS选择fi（S0）最小的待扩展局部解图作为G′。

⑤ G′中选择一个非终止节点的外端节点（尚未用于扩展出子节点的节点）作为x。

⑥ 扩展x，生成其子节点集，并从中删去导致节点间出现环路的子节点以及和它们有“与”关系的子节点。若子节点集为空，则x是不可解节点，从LGS删去G′（因为G′不可能再扩展为解图）；否则，计算每个子节点 xi 的f（xi），并通过建立外向k-连接将所有子节点加到G中。

⑦ 若存在j个（j＞1）外向k-连接，则从LGS删去G′，并将j个新局部解图加进LGS。

⑧ G′中或在取代G′的j个新局部解图中用公式f（x）=k+h（x1）+h（x2）+…+h（xk）的计算结果取代原先的f（x），并传递这种精化的作用到fi（S0）（i=1，2，…，j）；同时将作为终节点的子节点标记为可解节点，并传递节点的可解性。

⑨ 返回第③步。

下面就以图2-9为例，观察如何应用上述AO∗算法来搜索解图，如图3-12所示。

假定在搜索过程中扩展出来的某些节点的启发函数h（xi）的估算如下：

h（x0）=3，h（x1）=2，h（x2）=4，h（x3）=4，h（x4）=1，h（x5）=1，h（x6）=2，h（x7）=h（x8）=0

开始时，只有一个初始状态节点x0，x0 被扩展，生成出节点x1、x4 和x5，产生两个局部解图编号为1（对应一个1-连接符指向x1）和2（对应一个2-连接符指向x4 和x5），加入LGS并删去0号局部解图。由已知条件知：h（x1）=2，h（x4）=1，h（x5）=1，并且已经假设k-连接符的代价值为k。所以f1（x0）=1+2=3，f2（x0）=2+1+1=4。

在第二次循环中选1号局部解图作为G′，扩展x1 节点，生成出节点x2 和x3，两个节点分别通过1-连接符与x1 连接。LGS中删去1号局部解图，并把扩展出的新局部解图编号为3（对应一个1-连接符指向x2）和4（对应一个1-连接符指向x3），加入LGS，由于h（x2）=h（x3）=4，更新x1 的h值，f3（x0）=f4（x0）=6＞f2（x0）。

在第三次循环中，选取2号局部解图作为G′，寻找未扩展的非终节点。这时x4 和x5 都是满足这一条件的节点，可以从它们中任意选择一个进行扩展。假定选择的是x5，则生成x6、x7和x8 三个节点。并把扩展的新局部解图编号为5（对应一个1-连接符指向x6）和6（对应一个2-连接符指向x7 和x8），并加入LGS。f5（x5）=2，指针指向2-连接符。更新x5 的f值，因此f5（x0）=6，f6（x0）= 5。局部解图6加入G′，因为f6（x0）＜f3（x0）=f4（x0），不需要改变指向连接符的指针。在本次循环中，由于x7 和x8 都是目标状态节点，是可解节点，而x5 通过一个2-连接符连接x7 和x8，所以x5 也被标记为可解节点。虽然x5 是可解节点，但由于x0 是通过一个2-连接符连接x5 和x4 的，而此时x4 还不是可解的，所以x0 还不是可解的。搜索将继续进行。至此第三次循环结束。

第四次循环，选择局部解图6作为G′，扩展x4，生成节点x5 和x8，并分别以1-连接符连接。把扩展的新局部解图7（对应一个1-连接符指向x5）和局部解图8（对应一个1-连接符指向x8），并加入LGS。因f7（x4）=3，f8（x4）=1，取最小的。扩展x4并没有改变它的f值。由于x8 是目标状态节点，是可解节点，而x4 通过一个1-连接符连接x8，因此x4 也被标记为可解节点。在第三次循环中，x5 已经被标记为可解节点。这样x4、x5 都是可解节点了，从而x0 也被标记为可解节点。而x0 是初始状态节点，至此搜索全部结束。从x0 开始，沿指向连接符的指针找到的解图即为搜索的结果。图3-13所示为得到的解图。

（2）AO∗算法应用的若干问题

（1）与/或图搜索的是解图而非解路径。选择f（x）值最小的节点加以扩展并不一定会加速搜索过程，应该选择导致解图代价发生较大变化的节点优先加以扩展，使搜索的注意力快速地聚焦到实际代价较小的候选解图上。在简单情况下，可随机选择加以扩展的节点。

（2）AO∗算法是可采纳的。当某与/或图存在解图时，应用AO∗算法一定能找出代价最小的解图。AO∗算法的应用要求遵从以下约束：

① 总能满足h（x）≤h∗（x），当实际的代价最小解图被找到时，h∗（x）为该解图的代价；

② 确保h（x）满足单调限制条件，即h（x）≤k+h（x1）+h（x2）+…+h（xk）。

（3）AO∗算法与A∗算法有类似之处，也存在较大区别。

①AO∗算法应用于与/或图搜索，且搜索的是解图；而A∗算法则应用于状态空间搜索，且搜索的是解路径。

② AO∗算法选择估算代价最小的局部解图加以优先扩展；而A∗算法选择估算代价最小的路径加以优先扩展。

③ AO∗算法不需考虑估价函数f（x）的分量g（x），只需对新扩展出的节点x计算h（x），以用于修正fi（S0）；而A∗算法则需同时计算分量g（x）和h（x），用以估价节点x是否在代价最小的路径上；

④AO∗算法应用LGS图集存放候选的待扩展局部解图，并依据fi（S0）值排序；而A∗算法则应用OPEN表和CLOSED表分别存放待扩展节点和已扩展节点，并依据f（x）值排序。

（4）解图代价的重复计算。解图中某些子节点可能会有多个父节点，或者说多个节点的外向连接符可能指向同一个子节点。依据前述解图代价的递归计算方式，显然这种子节点到终止节点集合解图的代价在计算自根节点S0 出发的解图时被重复累计了。为正确计算解图的代价，必须删除重复的累计。

3.3.4 博弈问题的启发式搜索策略

1. 博弈的基本概念

这里所讲的博弈，指的是类似于象棋这样的游戏问题。这类问题有以下一些特点：

（1）双人对弈，对垒的双方轮流走步。

（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。

（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。

此类博弈问题，可以这样来看：当轮到己方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的棋是“或”的关系。而对于轮到对方走棋时，对于已方来说，必须能够应付对手的每一种走棋。这就相当于这些棋是“与”的关系。

若把上述博弈过程用图表示出来，则得到的是一棵与/或树。这里要特别指出，该与/或树是根据某一方的立场得出的，绝不可一会儿站在这一方的立场上，一会儿又站在另一方的立场上。我们把描述博弈过程的与/或树称为博弈树，它有如下特点：

① 博弈的初始棋局是初始状态节点。

② 在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流扩展节点。

③ 所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。

下面通过分钱币游戏来演示该类博弈问题的与/或树表示过程。

例3-5 分钱币游戏。游戏规则：一堆硬币由两位选手轮流操作。第一位选手把硬币分成不相等的两堆，第二位选手把当前的任一堆再分成不相等的两堆。这样如此进行下去，直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。

解 假设数字序列x1，x2，…，xn为n堆钱币不同的个数，两位选手分别叫MAX和MIN，并由MIN开始分钱币。如果只有7枚硬币，博弈过程如图3-14所示。

对于分钱币游戏这种较简单的博弈，可以用类似于与/或图的搜索技术求出解图，解图代表了从初始棋局到目标棋局任何阶段上的弈法。显然这对许多复杂的博弈问题（如中国象棋、国际象棋等）是不可能实现的，因为在考虑完整的搜索策略时，即使是高性能的计算机来处理，也得花天文数字计的时间。由于启发式搜索并不可能使分支压缩到很少，因此这种完全取胜策略（或和局）必须丢弃，而应当把目标确定为寻找一步好棋，等对手回敬后再考虑寻找另一步好棋这种实际可行的实用策略。这种情况下每一步结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定。由此，一个实用的策略就是在一个阶段搜索结束后，从搜索树中提取一个优先考虑的“最好的”走步。下面就来讨论这种机理的搜索策略——极小极大搜索。

2. 极小极大搜索

极小极大搜索是博弈树搜索的基本方法，其思想是：

（1）设博弈树的双方中一方为A，另一方为B。极大极小搜索是为其中的一方寻找一个最优行动方案的方法。

（2）为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。具体地说，就是要考虑每一个方案实施后对方可能采取的所有行动，并计算可能的得分。

（3）为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树叶节点的得分。此时估算出来的得分称为静态估值。

（4）当叶节点的估值计算出来后，再来推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。

（5）如果一个行动方案能获得较大的倒推值，则它就是当前最好的方案。

下面以一字棋游戏为例演示极小极大搜索方法。

例3-6 一字棋游戏。

在一字棋博弈中，博弈者在3 ×3数组中轮流标记，一个标记（X），一个标记（O）。先用标记填满一行、一列或一条对角线者便赢得博弈。假设MAX标记（X），MIN标记（O），MAX先开始。在深度为2的范围内进行广度优先搜索，直到第二级节点全部产生，然后在这些节点代表的位置采用静态评估函数。给出位置p的静态评估函数e（p）如下：

假如对任何一方，p位置都不是取胜位置，则e（p）由如下公式计算

e（p）=（对MAX空着的完整的行、列或对角线总数）-（对MIN空着的完整的行、列或对角线总数）

假如对MAX来说，p是取胜位置，则e（p）= +∞。

假如对MIN来说，p是取胜位置，则e（p）= -∞。

假设考虑走两步的搜索过程，利用棋盘对称性的条件，则第一次调用算法产生的博弈树如图3-15所示，图中叶节点下面是计算的f（p）值，非叶节点的倒推值标记在圆圈内。为了使初始状态节点具有最大的倒推值，可以看出第一步最好走法是把棋子下在中央位置。

设MAX走完第一步后，MAX的对手是在×之上的格子中下子的，这时MAX就要在新格局下调用算法，第二次产生的博弈树如图3-16所示。

类似的第三次的博弈树如图3-17所示。至此MAX走完最好的走步后，不论MIN怎么走，都无法挽回败局，因此只好认输了。否则需要进行第四轮的搜索。

3. α-β剪枝技术

在极大极小搜索中，总是生成一定深度的博弈树，然后对节点进行估值，再计算出上层节点的倒推值，这样做效率较低。鉴于博弈树具有“与”节点和“或”节点逐层交替出现的特点，删去一些不必要的节点，从而减少搜索及计算的工作量。

α-β剪枝技术的一般规律：

（1）任何“或”节点x的α值，如果不能降低其父节点的β值，则对节点x以下的分支可以停止搜索，并使x的倒推值为α，这种剪枝称为β剪枝。

（2）任何“与”节点x的β值，如果不能降低其父节点的α值，则对节点x以下的分支可以停止搜索，并使x的倒推值为β，这种剪枝称为α剪枝。

例3-7 图3-18所示的博弈树搜索，就采用了α-β剪枝技术。

图中给出了一个d=4的博弈树的α-β剪枝过程，其中带圆圈的数字表示求静态估值及倒推值过程的次序编号。该图详细表示出了α-β剪枝过程的若干细节。初始状态节点的最终倒推值为1，该值等于某一个端节点的静态估值。最好优先走步是走向右分支节点所代表的棋局，要注意棋局的发展并不一定要沿着通向静态值为1的端节点这条路径走下去，这要看对手的实际响应而定。

为了完成α-β剪枝，至少部分搜索树要产生至最大深度值，因为α和β值需要基于叶节点的静态值。因此，使用α-β剪枝时通常用到深度优先搜索，而且，搜索中可以得到的剪枝数取决于早期的α、β值与最终倒推值的近似程度。

当β值比α值稍大或极相近情况下（即不满足α≥β的剪枝条件），这时也可以进行剪枝，以便有条件把搜索集中到会带来更大效果的其他路径上，这就终止了对效益不大的一些子树的搜索，提高了搜索效率。

4. 极小极大搜索的其他改进方法

除了α-β剪枝技术，还有如下改善极小极大搜索性能的基本方法：

（1）不严格限制搜索的深度。当到达深度限制时，如出现博弈棋局有可能发生较大变化时（如出现兑子棋局），则应多搜索几层，使棋局进入较稳定状态后再终止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响。这是等候状态平稳后终止搜索的方法。

（2）当算法给出所选的走步后，并不马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外。这是一种增添辅助搜索的方法。

（3）对某些博弈的开局阶段和残局阶段，往往总结有一些固定的对弈模式，因此可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。

3.4 通用问题的求解方法

除了前面介绍的状态空间搜索和与/或图搜索法外，生成-测试法、手段-目标分析法和约束满足法也都是通用问题的求解方法。

3.4.1 生成-测试法

一般生成-测试法往往采用两种基本模块，其一是生成模块，称为生成子（generator），用于枚举可能的解；其二是测试模块，称为测试子（tester），用于估价每个所提交的解，予以认可或者拒绝。

该方法常用的工作方式是，生成和测试往往交替进行。生成子在测试子之前产生所有可能的解。最后会出现如下三种情况：有可能在找到一个可取解时，测试即停止；也可能在找到令人满意数量的解时，测试才会停止；甚至有可能在找到所有可能解时，测试才停止。

生成-测试法最常用于求解识别问题。在识别问题中，生成子用来产生假设。比如查找一本关于树的树，用手指一页页翻过去，找到一幅与待识别树相像的插图便停下来。用手指翻页是生成过程，将插图与树匹配是测试过程。一个好的生成子应是完备的、无冗余的和有信息的。

状态空间搜索有时能表示为生成-测试法。搜索过程由两个部件合作完成：可能解的生成器和修剪不正确解答的测试器。生成器的性能取决于完备性和无冗余性，即能生成所有可能的解并只生成一次。在搜索过程中，生成器和测试器的工作往往需交替进行。使用生成-测试法应考虑的关键问题是，如何在生成器和测试器之间分配知识。经验证明，知识丰富的生成器会导致较高的搜索效率。实际应用的生成-测试法常是分层的，整个问题求解过程可视为不断搜索部分解答的过程，每一层的生成-测试法服务于搜索一个部分解答。搜索部分解答相当于解答分类，因此搜索树实际上就是分类树。分层的目的在于设计有力的测试器，以尽量早地（在搜索树上层）删除不合适的候选解，从而大幅度减少搜索量。

3.4.2 手段-目标分析法

手段-目标分析法是将目前状态与目标状态进行比较，找出它们之间最重要的差别，消除这一差别是当前的子目标。并依次进行下去，直至最终到达目标状态。手段-目标分析法在状态空间中产生一条路径。根据当前状态、目标状态及其差别的描述，确定下一步尝试哪一过程。下一步尝试哪一步的关键是关于当前状态与目标状态之间的差别描述。

图3-19中过程序列P1，…，P5 引起从初始当前状态出发的各状态之间的转移。该序列中，状态间的转移（即操作算子）过程的选择依据都是认为该过程可以消除当前状态至目标状态之间的差别。图中显示，过程P3 使解题过程离目标更远；最一般的手段-目标分析法无阻止倒退步的内在机制。幸好，过程P4 和过程P5 使解题过程重新趋近目标。我们可以看出作为启发式搜索的变种，手段-目标分析法可以分析操作算子对减少当前状态和目标状态之间差别的贡献，以决定操作算子的选用。

3.4.3 约束满足问题

很多问题可看成是满足约束条件的搜索问题。约束条件有时可以有效减小搜索空间。你可能需要计划一次从北京到广州的旅行，约束条件是要及时赶到参加一个会议或者旅行花费在预算之内。这类问题的求解任务就是寻找某问题的状态，使它满足一个给定的约束集。

约束满足问题是利用状态的结构以及通用的启发性信息来定义搜索算法的。在人工智能领域，很多问题都属于约束满足问题，即寻找满足一组约束的目标状态的问题。

1. 约束满足的基本概念

约束满足问题由一组变量x1，x2，…，xn对应于各个变量的值域R1，R2，…，Rn 和一组约束条件C1，C2，…，Cn组成。其中每个约束Ci（xi1，xi2，…，xin）是笛卡儿积Ri1 ×…× Rin的一个子集，它指定了相容的变量元组值。

约束满足问题的经典求解方法就是搜索，在问题空间搜索解的单一过程就变成两个并行的搜索：一个是工作于约束的问题空间，另一个是工作于原问题空间，但操作和启发函数应能顾及约束空间的当前状态。问题的一个状态是由对一些或全部变量的一个赋值定义的。操作也分为两种：一种是约束问题空间的操作，作用于当前约束状态产生新的约束，称为约束操作；一种是原问题空间的操作，作用于当前问题状态产生满足当前约束时新的部分解。问题的解是满足所有约束的完全赋值，或更进一步，使目标函数最大化。

下面以八皇后游戏为例来分析。

例3-8 若把8 个皇后放在一个棋盘上，每行和每列只能有一个皇后，另外，一个皇后只能在任一行、列或对角线上（也就是说，按照国际象棋规则，没有皇后能被放在一个位置以便它能抓住任何其他的皇后）。这个问题的一个解法参见图3-20。

由于这种问题具有从集合{第1 行，第2 行，…，第8 行}到变量{第1 列的皇后位置，第2 列的皇后位置，…，第8 列的皇后位置}的赋值形式，所以称为赋值问题。

在这个问题中，一个明显的数据结构是一个8 ×8的数组，数组中的每个单元包含两个符号（1和0）中的一个，1代表皇后，0为空。一个根据条件定义的隐式目标状态是保证8 个皇后都是安全的，不会被抓住。连接状态描述的操作算子和数组转换的方式相一致。例如，一个操作算子在满足约束件下，增加一个皇后，或者它能把一个皇后移到另一个单元中。在赋值问题中，由于到达目标的路径并不重要，因此关于开始状态和操作算子是什么我们常有很多选择。

在约束满足问题的搜索方法中，初始状态节点是一些初始的数据结构，一个目标状态节点是由满足约束的数据结构（或状态描述）标识的节点，操作算子则将一个数据结构改变为另一个数据结构，

2. 约束传播

在搜索的早些时候，或开始之前就考虑某些约束，从而降低搜索空间。一种称为约束传播的计算技术有助于显著地减小搜索空间的大小。四皇后游戏是八皇后游戏的简化，即放在一个4 × 4棋盘中，彼此不能互相抓住。在四皇后游戏中，设有4个变量q1、q2、q3 和q4，其中下标1、2、3和4分别代表4列中的某一列，一个皇后可以放在其中之一上。每个变量的值可以是1、2、3和4，数值分别表示皇后放在对应的行。例如，当q3 =2时，一个皇后被放在第2行第3列。四皇后游戏对这些变量的值提出了约束，因此如果q1 =1，q2 就不能等于1或2。约束被表示在一个叫约束图的有向图中，在这个图中的每一个节点有一个变量和该变量的一组可能值标识。一个有向约束弧（i，j），连接着节点i和j，其中节点i的变量值受到节点j的变量约束。图3-21所示为4皇后游戏的一个约束图。

在这个问题中，每个变量约束着所有其他的变量，因此所有的节点之间都有弧存在。如果对于弧尾的每一个变量值至少有一个弧头的变量值没有违反约束，我们就说有向约束弧（i，j）是一致的。图3 -22 中的弧是一致的，因为对每对qi 和qj（i不等于j），对qi 的每一个值，有一个qj值没有违反约束。

给变量中的一个或几个赋值后，我们能用弧一致性概念排除其他变量的一些值。约束传播过程就是在图中的弧上进行迭代，使用弧一致性来排除弧尾的变量值。当没有更好的值能被删除时这个过程终止。现用

一个例子阐明这个过程。假如一个深度优先搜索过程通过给变量q1 赋值1开始（即把一个皇后放在第1行第1列）。应用到这个赋值的约束传播如下向前推进：

（1）考虑弧（q2，q1）：排除q2 =1和q2 =2，因为q1 的值（我们刚分配的值）和q2 的这些值不一致。

（2）考虑弧（q3，q1）：排除q3 =1和q3 =3，因为q1 的值和q3 的这些值不一致。

（3）考虑弧（q4，q1）：排除q4 =1和q4 =4，因为q1 的值和q4 的这些值不一致。

在约束传播的这一阶段（不完全），我们有图3-21。在图随后的约束传播过程中，排除q3的所有值，因此看到q1 =1时这个问题没有解法。在q1 =1的情况下不能再进行进一步的搜索，而是回溯到q1 =2的情况。

下面假定q =2进行约束传播。开始几步如下：

（1）考虑弧（q2，q1）：排除q2 =1，q2 =2和q2 =3。

（2）考虑弧（q3，q1）：排除q3 =2和q3 =4。

（3）考虑弧（q4，q1）：排除q4 =2。

我们得到图3-23。连续的约束传播使每个节点变量只有一个值，使所有的弧保持一致。因此，我们看到在完成搜索前只有一个解法，约束传播已经找到了那个解法。

3. 约束满足问题的搜索方法

约束满足问题的搜索方法通常采用回溯策略，而实现回溯策略的有效方式是应用递归过程去支持搜索和回溯。

回溯策略的实现过程如下：

① 令CLOSED、OPEN、x、x′为局部变量；

② CLOSED：节点列表，指示解路径；

③ OPEN：当前节点扩展出的子节点列表；

④ MOVE-FIRST（OPEN）：把OPEN表首的节点移出，作为下一次要加以扩展的节点；

⑤ x、x′分别指示当前考察和下一次考察的节点。

该递归过程的算法就取名为BACKTRACK（x），参数x为当前被扩展的节点，算法的初次调用式是BACKTRACK（S），S即为初始状态节点。算法的步骤如下：

① 若x是目标状态节点，则算法的本次调用成功，结束，返回空表；

② 若x是失败状态，则算法的本次调用失败，结束，返回′FAIL′；

③ 扩展节点x，将生成的子节点置于OPEN表，并按估价函数f（k）=h（k）的值从小到大排序（k指示子节点）；

④ 若OPEN表为空，则算法的本次调用失败，结束，返回′FAIL′；

⑤ x′= MOVE-FIRST（OPEN）；

⑥ CLOSED=BACKTRACK（x′）；

⑦ 若CLOSED=′FAIL′，返回到步骤④；

⑧ 将x′加到CLOSED表首，算法的本次调用成功，结束，返回CLOSED表。

该递归回溯算法中，失败状态通常指三种情况：①不合法状态，如传教士和野人问题中所述的那样；②旧状态重现，如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环；③节点深度超过预定限度，如八数码游戏中，指示解路径不超过6步。失败状态实际上定义了搜索过程回溯的条件；另一种回溯条件是搜索进入“死胡同”，由该算法的步骤④定义。由于回溯是递归算法，解路径的生成是从算法到达目标状态后逆向进行的，首先产生空表，然后每回到算法的上一次调用就在表首加入节点x′，直到顶层调用返回不包含初始状态节点 S0 的解路径。

影响回溯策略效率的关键因素是回溯次数。鉴于回溯是搜索到失败状态时的一种弥补行为，只要能准确地选择下一步搜索考察的节点，就能大幅度减少甚至避免回溯。所以，设计好的启发式函数h（x）是至关重要的。

作为例子，下面观察四皇后问题。

例3-9 设计启发式函数h（x），其值为状态 x下最新一个皇后位置（棋盘格子）所在的长对角线的长度（对角线上格子的个数）。相应的棋盘布局的变迁过程如图3-25所示。显然，由于使用了启发式函数h（x）对每一个当前考察节点产生的子节点进行局部排序，搜索过程仅经历了二次回溯就快速到达目标状态。若采用盲目搜索方式，每次将新产生的子节点按随机次序或固定顺序（如列的顺序）排序，则搜索过程会不得不面临很多次回溯。

小 结

本章分四部分详细地讨论了搜索策略。首先介绍了搜索的基本概念，并从不同角度对搜索进行了分类。然后从盲目搜索和启发式搜索两个策略较详细地讨论了状态空间搜索，并深入讨论了搜索算法的应用及研究工作中所提出的一些问题。启发式图搜索策略是人工智能系统中最常用的控制策略，它利用问题领域拥有的启发性信息来引导搜索过程，达到减小搜索范围，降低问题复杂度的目的。此外A∗算法的问题复杂性与h（x）的选取有关，一般情况下，A∗算法没有解决指数爆炸的问题。接着主要讨论了与/或树的有序搜索、与/或图的启发式搜索、AO∗算法和双人完备信息的博弈问题。AO∗算法通过估价函数f（x）=h（x）来引导搜索过程，适用于分解之后得到的子问题不存在相互作用的情况。双人完备信息的博弈问题，一般意义下求解的策略是要找到一个完全取胜的解图。实际上只有简单的博弈或复杂博弈的残局，这种完全取胜的策略才可行。最后介绍了其他通用问题的求解方法。生成-测试法、手段-目标分析法和约束满足都是常用通用问题的求解方法。

搜索策略是人工智能研究的核心课题之一，已有许多成熟的成果并在实践中得到广泛应用。实际应用中的研究工作，主要是解决算法复杂性的问题，探索有效和实用的搜索策略仍然是很有实际意义的工作。

练习题

3.1 阐述广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深搜索各自的特点及复杂度。

3.2 估价函数中，g（x）和h（x）各起什么作用？估价函数f（x）=（2-w）g（x）+wh（x）。算法中w取什么值能保证算法是最优的？当w=0时，这个算法是什么搜索？w=1呢？w=2呢？

3.3 滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下：

B B B W W W E

其中，B表示黑色将牌，W表示白色将牌，E表示空格。游戏的规定走法是：

（1）任意一个将牌可以移入相邻的空格，规定其耗散值为1；

（2）任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边（左边有无空格均可）。对这个问题，定义一个启发函数h（n），并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h（n）是否满足下界范围？在你的搜索树中，对所有的节点是否满足单调限制？

3.4 余一棋的博弈法如下：两棋手可以从5个钱币堆中轮流拿走一个、两个或三个钱币，拣起最后一个钱币者算输。试通过博弈证明，后走的选手必胜，并给出一个简单的特征标记来表示取胜策略。

3.5 给出一个关于α-β剪枝正确性的形式化证明。

3.6 综述图搜索的策略。

3.7 考虑下述的逻辑问题：有5套不同颜色的房子，住着5个来自不同国家的人，每个人都喜欢一种不同牌子的香烟、不同牌子的饮料和不同的宠物。给定下列已知条件：

英国人住在红色的房子里。

西班牙人养的是狗。

挪威人住在最左边的第一套房子里。

住在黄色房子里的人喜欢抽Kools牌香烟。

喜欢抽Chesterfields牌香烟的人住在养狐狸的人旁边。

挪威人住在蓝色房子旁边。

喜欢抽Winston牌香烟的人养了一只蜗牛。

喜欢抽Lucky Strike牌香烟的人喜欢喝橙汁。

乌克兰人喜欢喝茶。

日本人喜欢抽Parliaments牌香烟。

喜欢抽Kools牌香烟的人住在养马的人的隔壁。

住在中间房子里的人喜欢喝牛奶。

把这个问题表示成约束满足问题，并回答问题“斑马住在哪儿？以及哪套房子里的人喜欢喝水？”