第3章搜索策略

从工程应用的角度讲，开发人工智能技术的一个主要目的就是解决非平凡问题，即难以用常规(数值计算、数据库应用等)技术直接解决的问题。这些问题的求解依赖于问题本身的描述和应用领域相关知识的应用。广义地说，人工智能问题可以看成一个问题求解的过程，因此问题求解是人工智能的核心问题，其要求是在给定条件下，寻求一个能在有限步骤内解决某类问题的算法。
按解决问题所需的领域特有知识的多少，问题求解系统可以划分为两大类： 知识贫乏系统和知识丰富系统。前者必须依靠搜索技术去解决问题，后者则求助于推理技术。
搜索直接关系到智能系统的性能与运行效率，因而美国人工智能专家尼尔森(N.J.Nilsson)把它列为人工智能研究的四个核心问题(知识的模型化和表示，常识性推理、演绎和问题求解，启发式搜索，人工智能系统和语言)之一。
现在，搜索技术渗透在各种人工智能系统中，在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈等领域都广泛使用，可以说，没有一种人工智能系统应用不到搜索方法。
本章首先讨论搜索的有关概念，然后着重介绍状态空间的知识表示和搜索策略，主要有基于状态空间图的搜索、盲目搜索、启发式搜索和与或图的搜索，最后讨论博弈问题的智能搜索算法。
3.1搜索策略概述
智能系统要解决的问题各种各样，其中大部分是结构不良或非结构化问题，对这样的问题一般没有算法可以求解，只能利用已有的知识一步步地摸索。此过程中存在如何寻找可用知识的问题。即如何确定推理路线，使其付出的代价尽可能地少，且问题又能得到较好的解决。例如，在推理中可能存在多条路线都可实现对问题的求解，这就存在按哪一条路线进行求解可以获得较高的运行效率的问题。
因此，对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。搜索就是找到智能系统的动作序列的过程。 
在智能系统中，即使对于结构性能较好、理论上有算法可依的问题，由于问题本身的复杂性以及计算机在时间、空间上的局限性，有时也需要通过搜索来求解。
在人工智能中，搜索问题一般包括两个重要的问题： 搜索什么、在哪里搜索。前者通常指的是搜索目标，而后者通常指的是搜索空间。搜索空间通常是指一系列状态的汇集，因此也称为状态空间。与通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不一定全部知道。所以，人工智能中的搜索可以分成两个阶段： 状态空间的生成阶段及该状态空间中对所求问题状态的搜索阶段。
根据在问题求解过程中是否运用启发性知识，搜索被分为盲目搜索和启发式搜索。
盲目搜索是指在问题的求解过程中，不运用启发性知识，只按照一般的逻辑法则或控制性知识，在预定的控制策略下进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。由于搜索总是按预先规定的路线进行，没有考虑问题本身的特性，这种方法缺乏对求解问题的针对性，需要进行全方位的搜索，所以没有选择最优的搜索途径。因此，这种搜索具有盲目性，效率较低，容易出现“组合爆炸”问题。典型的盲目搜索有深度优先搜索和宽度优先搜索。
启发式搜索是指在问题的求解过程中，为了提高搜索效率，运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门等实践经验和知识，指导搜索朝着最有希望的方向前进，加速问题求解过程并找到最优解。典型的启发式搜索有A算法和A*算法。
搜索问题中主要的工作是找到正确的搜索策略。搜索策略可以通过如下准则来评价。
（1） 完备性： 如果存在一个解答，该策略是否保证能够找到？
（2） 时间复杂性： 需要多长时间可以找到解答？
（3） 空间复杂性： 执行搜索需要多少存储空间？
（4） 最优性： 如果存在不同的解答，该策略是否可以发现最高质量的解答？
搜索策略反映了状态空间或问题空间的扩展方法，也决定了状态或问题的访问顺序。搜索策略不同，人工智能中搜索问题的命名也不同。例如，考虑一个问题的状态空间为一棵树的形式。如果根结点首先扩展，再扩展根结点生成的所有结点，然后是这些结点的后继，如此反复下去。这就是宽度优先搜索。另外，在树的最深一层的结点中扩展一个结点。只有当搜索遇到一个死亡结点(非目标结点且无法扩展)的时候，才返回上一层选择其他结点搜索。这就是深度优先搜索。无论是宽度优先搜索还是深度优先搜索，结点遍历的顺序一般都是固定的，即一旦搜索空间给定，结点遍历的顺序就固定了。这类遍历成为“确定性”的，也就是盲目搜索。而对于启发式搜索，在计算每个结点的参数之前都无法确定先选择哪个结点扩展，这种搜索一般也称为非确定的。
3.2基于状态空间图的搜索技术
搜索最适合设计基于一个操作算子集的问题求解任务，每个操作算子的执行均可使问题求解更接近于目标状态，搜索路径将由实际选用的操作算子的序列构成。本节主要介绍图搜索的基本概念、状态空间搜索以及一般图的搜索算法。
3.2.1图搜索的基本概念
1. 显式图与隐式图

为了求解问题，需要把有关的知识存储在计算机的知识库中。有以下两种存储方式。
(1)  显式存储(显式图)： 把与问题有关的全部状态空间图，即相应的有关知识(叙述性知识、过程性知识和控制性知识)全部直接存入知识库。
(2)  隐式存储(隐式图)： 只存储与问题求解有关的部分知识(部分状态空间)，在求解过程中，由初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求的目标状态，只需在知识库中存储局部状态空间图。
为了节约计算机的存储容量，提高搜索推理效率，通常采用隐式存储方式，进行隐式图搜索推理。
2. 图搜索的基本思想
图搜索是一种在图中寻找路径的方法，从图中的初始结点开始，至目标结点为止。其中，初始结点和目标结点分别代表产生式系统的初始数据库和满足终止条件的数据库。方法是先把问题的初始状态作为当前状态，选择适用的算符对其进行操作，生成一组子状态，检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解； 若不出现，则按某种搜索策略从已生成的状态中再选择一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。

3.2.2状态空间搜索
用搜索技术来求解问题的系统均定义一个状态空间，并通过适当的搜索算法在状态空间中搜索解答或解答路径。状态空间搜索的研究焦点在于设计高效的搜索算法，以降低搜索代价并解决“组合爆炸”问题。
1. 什么是状态空间图
例3.1钱币翻转问题。设有三枚钱币，其初始状态为“反、正、反”，欲得的目标状态为“正、正、正”或“反、反、反”。问题是允许每次只能且必须翻转一枚钱币，连翻三次。问能否达到目标状态。
要求解这个问题，可以通过引入一个三维变量将问题表示出来。设三维变量为： 
Q=(q1，q2，q3)
式中，qi=0 (i=1，2，3)表示钱币为正面，qi=1(i=1，2，3)表示钱币为反面。则三枚钱币可能出现的状态有8种组合： 
Q0=(0,0,0),Q1=(0,0,1),Q2=(0,1,0),Q3=(0,1,1)

Q4=(1,0,0),Q5=(1,0,1),Q6=(1,1,0),Q7=(1,1,1)
这时，问题可以表示为图3.1，它表示了全部可能的8种组合状态及其相互关系，其中每个组合状态均可认为是一个结点，结点间的连线表示了两结点的相互关系(如从Q5结点到Q4结点间的连线表示要将q3=1翻成q3=0，或反之)。现在的问题是，要从初始状态Q5，经过适当的路径(连线)，找到目标状态Q0或Q7。可以看出，从Q5不可能经过三步到达Q0，即不存在从Q5到达Q0的解。但从Q5出发到达Q7的解有7个，它们是aab，aba，baa，bbb，bcc，cbc和ccb。



图3.1三枚钱币问题的状态空间图


从这个问题的求解过程可看到，某个具体问题可经过抽象变为某个有向图中寻找目标或路径的问题。人工智能中把这种描述问题的


图3.2状态空间图的一般描述


有向图称为状态空间图，简称状态图。其中，状态图中的结点代表问题的一种格局，一般称为问题的一个状态； 边表示两结点之间的某种联系，可以是某种操作、规则、变换、算子或关系等。在状态图中，从初始结点到目标结点的一条路径，或者所找的目标结点，就是相应问题的一个解。其一般描述如图3.2所示。

在现实生活中，无论是智力问题(如梵塔问题、旅行商问题、八皇后问题、传教士过河问题等)还是实际问题(如定理证明、演绎推理、机器人行动规划等)都可以归结为在某一状态图中寻找目标或路径的问题。所以，状态图是一类问题的抽象表示。
2. 问题的状态空间表示法
状态空间表示法是指用“状态”和“操作”组成的“状态空间”来表示问题求解的一种方法。
1) 状态
状态(State)是指为了描述问题求解过程中不同时刻下状况(如初始状况、事实等叙述性知识)间的差异而引入的最少的一组变量的有序组合。状态常用矢量形式表示，即
S=［s0,s1,s2，…，si］T
其中，si(i=0,1,2,…)为分量。当给定每个分量的值ski(i=0，1，2，…)时，就得到一个具体的状态sk，即
sk=［sk0,sk1,sk2，…］T
状态的维数可以是有限的，也可以是无限的。另外，状态还可以表示成多元数组或其他形式。状态主要用于表示叙述性知识。
2) 操作
操作(Operator)也称为运算符或算符，它引起状态中的某些分量发生改变，从而使问题由一个具体状态改变到另一个具体状态。操作可以是一个机械的步骤、过程、规则或算子，指出了状态之间的关系。操作用于反映过程性知识。
3) 状态空间
状态空间(State Space)是指一个由问题的全部可能状态及其相互关系(操作)所构成的有限集合。
状态空间常记为二元组： 
(S，O)

其中，S为问题求解(搜索)过程中所有可能达到的合法状态构成的集合； O为操作算子的集合，操作算子的执行会导致问题状态的变迁。
这样，在状态空间表示法中，问题求解过程就转化为在图中寻找从初始状态S0出发到目标状态Sg的路径问题，也就是寻找操作序列α的问题。
作为状态空间表示的经典案例，我们来观察“传教士和野人问题”。设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵从三个约束： ①船上人数不得超过载重限量，设为K人； ②为预防野人攻击，任何时刻(包括两岸、船上)野人数目不得超过传教士人数N； ③允许在河的某一岸或者在船上只有野人而没有传教士。
为便于理解状态空间表示方法，我们简化该问题到一个特例： N=3，K=2； 并以变量m和c分别指示传教士和野人在左岸或船上的实际人数，变量b指示船是否在左岸(值1指示船在左岸，否则为0)。从而上述约束条件转变为m+c≤2,m≥c。

考虑在这个渡河问题中，左岸的状态描述(m、c和b)可以决定右岸的状态，所以整个问题状态就可以用左岸的状态来描述，以简化问题的表示。设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，


图3.3渡河问题的状态空间有向图


问题状态以三元组(m，c，b)表示，则问题求解任务可描述为： (3，3，1)→(0，0，0）。在这个问题中，状态空间可能的状态总数为4×4×2=32，由于要遵守安全约束，只有20个状态是合法的。

下面是几个不合法状态的例子： (1，0，1)，(1，2，1)，(2，3，1)。鉴于存在不合法状态，还会导致某些合法状态不可达，例如状态(0，0，1),(0，3，0)。结果，这个问题总共只有16个可达的合法状态。
渡河问题中的操作算子可以定义两类，即L(m，c)、R(m，c)，分别指示从左岸到右岸的划船操作和从右岸回到左岸的划船操作。m和c取值的可能组合只有5个： （1，0），（2，0），（1，1），（0，1），（0，2）。故共有10个操作算子。
可以画出相应于渡河问题状态空间的有向图，如图3.3所示。由于划船操作是可逆的，所以结点间的连线有双向箭头，弧标签指示船上传教士和野人的人数，显然每个结点都只能取L和R操作之一，这取决于状态变量b的值。



由此可以看出： 
（1） 用状态空间方法表示问题时，必须定义状态的描述形式，通过使用这种描述形式把问题的一切状态都表示出来。另外，还要定义一组操作，通过使用这些操作把问题由一种状态转变为另一种状态。
（2） 问题的求解过程是一个不断把操作作用于状态的过程。如果在使用某个操作后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用操作构成的序列。
（3） 要使问题由一种状态转变到另一种状态，就必须使用一次操作。这样，在从初始状态转变到目标状态时，可能存在多个操作序列(得到多个解)。其中使用操作最少或较少的解才为最优解(因为只有在使用操作时所付出的代价为最小的解才是最优解)。
（4） 对其中的某一个状态可能存在多个操作，使该状态变到几个不同的后继状态。那么到底用哪个操作进行搜索呢？这依赖于搜索策略。不同的搜索策略有不同的顺序，这是本章后面要讨论的问题。
在智能系统中，为了进行问题求解，必须用某种形式把问题表示出来，其表示是否合适将直接影响到求解效率。状态空间表示法就是用来表示问题及其搜索过程的一种方法，是人工智能科学中最基本的形式化方法，也是问题求解技术的基础。
3. 状态空间搜索的基本思想
状态空间搜索的基本思想是通过搜索引擎寻找一个操作算子的调用序列，使问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的解答路径。搜索引擎可以设计为任意实现搜索算法的控制系统。
通常，状态空间的解答路径有多条，但最短的只有一条或少数几条。上述渡河问题就有无数条解答路径(因为划船操作可逆)，但只有4条是最短的，都包含11个操作算子的调用。由于一个状态可以有多个可供选择的操作算子，导致了多个待搜索的解答路径。例如，图3.3中初始状态结点有3个操作算子可供选用。这种选择在逻辑上称为“或”关系，意指只要其中有一条路径通往目标状态，就能获得成功解答。由此，这样的有向图称为或图，常见的状态空间一般都表示为或图，因而也称一般图。
除了少数像渡河这样的简单问题，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图，即在搜索解答路径的过程中只画出搜索时直接涉及的结点和弧线，构成所谓的搜索图。
作为一般图搜索的另一个例子，下面观察智力游戏八数码问题。
八数码游戏在由3行和3列构成的九宫棋盘上进行，棋盘上放置数码为1~8的8个棋牌，剩下一个空格，游戏者只能通过棋牌向空格的移动来不断改变棋盘的布局。这种游戏求解的问题是： 给定初始布局(初始状态)和目标布局(目标状态)，如何移动棋牌才能从初始布局到达目标布局，如图3.4所示。显然，解答路径实际上就是一个合法的走步序列。


为了用一般图搜索方法解决该问题，先为问题状态的表示建立数据结构，再制定操作算子集。以3×3的一个矩阵来表示问题状态，每个矩阵元素Sij∈{0,1,2，…,8}； 其中1≤i，j≤3，数字0指示空格，数字1~8指示数码。于是图3.4中的八数码问题就可表示为矩阵形式，如图3.5所示。



图3.4八数码游戏实例




图3.5八数码问题的矩阵表示


定义操作算子的直观方法是为每个棋牌都制定一套可能的走步： 左、上、右、下四种移动，这样就需32个操作算子。简单易行的方法是仅为空格制定这四种走步，因为只有紧靠空格的棋牌才能移动。空格移动的唯一约束是不能移出棋盘。假设在搜索过程的每一步都能选择最合适的操作算子，则图3.4中的八数码问题解决时，一次搜索过程涉及的状态所构成的搜索图(这里实际是搜索树)如图3.6所示，其中粗线代表解决路径。




图3.6八数码问题的一次搜索图


八数码游戏可能的棋盘布局(问题状态)总共9!=362880个，由于棋盘的对称性，实际只有这个总数的一半。显然，我们无法直观地画出整个状态空间的一般图，但搜索图则小得多，可以图示。所以，尽管状态空间很大(例如国际象棋)，但只要确保搜索空间足够小，就能在合理的时间范围内搜索到问题解答。
搜索空间的压缩程度主要取决于搜索引擎采用的搜索算法。换言之，当问题有解时，使用不同的搜索策略，找到解答路径时，搜索图的大小是有区别的。一般来说，对于状态空间很大的问题，设计搜索策略的关键考虑是解决“组合爆炸”问题。复杂的问题求解任务往往涉及许多解题因素，问题状态可以通过解题因素的特别组来加以表示(解题因素可设计为状态变量，如传教士和野人问题中的m、c和b)。所谓“组合爆炸”意指解题因素多时，因素的可能组合个数会爆炸性(指数级)增长，引起状态空间的急剧膨胀。例如，某问题有4个因素，且每个因素有3个可选值，则因素的组合(问题状态)有34=81个； 但若因素增加到10个，则组合的个数达310=34 ×36=81×729，即状态空间扩大到729倍。解决组合爆炸问题的方法实际上就是选用好的搜索策略，使得在搜索状态空间的很小部分中就能找到解答。
3.2.3一般图搜索过程
一般图搜索过程是由尼尔森提出的一个著名的图搜索过程，是表达能力很强的一个搜索策略框架。在此过程中要用到OPEN表和CLOSE表。其中，OPEN表用于待扩展的结点，结点进入OPEN表中的排列顺序由搜索策略决定； CLOSE表用于存放已经扩展的结点，当前结点进入CLOSE表的最后。
为了给出一般图搜索过程，特做如下符号说明。
 S0： 初始状态结点。
 G： 搜索图。
 OPEN： 存放待扩展的结点的表。
 CLOSE： 存放已被扩展的结点的表。
 MOVEFIRST(OPEN)： 取OPEN表首的结点作为当前要被扩展的结点n，同时将结点n移至CLOSE表。
一般图搜索过程划分为以下两个阶段。
1) 初始化 
建立只包含初始状态结点S0的搜索图： 
G:={S0}
OPEN:={S0}
CLOSE:={}
2) 搜索循环
（1）  MOVEFIRST(OPEN)： 取出OPEN表首的结点n作为扩展的结点，同时将其移到CLOSE表。
（2）  扩展出n的子结点，插入搜索图G和OPEN表。
（3）  适当地标记和修改指针。
（4）  排序OPEN表。


图3.7搜索过程中的指针修改


通过循环执行该算法，搜索图G会因不断有新结点加入而逐步长大，直到搜索到目标结点。
上述过程生成一个显式图G(称为搜索图)，由返回指针确定G的子图T(称为搜索树)，OPEN表中的结点是T的叶结点。
在搜索图中标记从子结点到父结点的指针，方便了在搜索到目标状态时快速返回解答路径： 自初始状态S0到目标状态的一个结点序列。
为说明搜索过程中子结点分类和指针修改的作用，观察图3.7中的示例。



当前被扩展的结点为ni，它可扩展出下列三类结点。
第1类： 全新结点，如结点n1和n2。
第2类： 已出现在CLOSE表中的结点，如结点n3。
第3类： 已出现在OPEN表中的结点，如结点n4。
假设结点n3和n4经由新父结点ni到初始状态结点S0的路径代价比经由老父结点nj的要小，则结点n3和n4原指向结点nj的指针都移走，改为指向结点ni。由于n3自身已扩展出子结点n31和n32，而n32有2个父结点，因此应修改n32指向父结点的指针(从原先指向nj改为指向n3)，鉴于n3或许并不在最终得到的解答路径上，故这种指针修改并不值得进行。简单地把结点n3放回到OPEN表，而不修改其子结点指针，起到了推迟修改的作用。以后一旦结点n3被从OPEN表中取出重新扩展时，会重新扩展出n32,这时n32成为第二类子结点，再修改指针也不迟。

3.3盲目搜索
在一般图搜索算法中，提高搜索效率的关键在于优化OPEN表中结点的排序方式，若每次排在表首的结点都在最终搜索到的解答路径上，则算法不会扩展任何多余的结点就可快速结束搜索。所以排序方式成为研究搜索算法的重点，并由此形成了多种搜索策略。
一种简单的排序策略就是按预先确定的顺序或随机排序新加入OPEN表中的结点，常用的方式是宽度优先和深度优先。
宽度优先、深度优先及其改进算法的缺点是结点排序的盲目性，由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态结点后才得到解答，所以这类搜索也称为盲目搜索。
3.3.1宽度优先搜索
宽度优先搜索(BreadthFirst Search，BFS)又称为广度优先搜索。
1. 宽度优先搜索的基本思想
宽度优先搜索是指从初始结点S0开始，向下逐层搜索，在n层结点未搜索完之前，不进入n+1层搜索，同层结点的搜索次序可以任意。即： 先按生成规则生成第一层结点，在该层全部结点中沿宽(广)度进行横向扫描，检查目标结点Sg是否在这些子结点中。若没有，则再将所有笫一层结点逐一扩展，得到第二层结点； 并逐一检查第二层结点中是否包含有Sg，如此依次按照生成、检查、扩展的原则进行下去，直到发现Sg为止。
2. 宽度优先搜索算法
算法3.1宽度优先搜索算法。

PROCEDURE Breadth-First Search

BEGIN

把初始结点放入队列； 

REPEAT

取得队列最前面的元素为current； 

IF current=goal

成功返回并结束； 

ELSE DO

BEGIN

若current有子结点，则current的子结点以任意次序添加到队列的尾部； 

END

UNTIL 队列为空;

END.

例3.2通过挪动积木块，希望从初始状态达到一个目标状态，即三块积木堆叠在一起。积木A在顶部，积木B在中间，


图3.8积木问题


积木C在底部，如图3.8所示。请画出按照宽度优先搜索策略所产生的搜索树。


这个问题的唯一操作算子为MOVE(X，Y)，即积木X搬到Y(积木或桌面)上面。如挪动积木A到桌面上表示为MOVE(A，Table)。该操作算子可运用的先决条件如下。
(1)  被挪动的积木的顶部必须为空。
(2)  若Y是积木(不是桌面)，则积木Y的顶部也必须为空。
(3)  同一状态下，运用操作算子的次数不得多于一次。
经分析，该宽度优先搜索树如图3.9所示。 



图3.9积木问题的宽度优先搜索树


3. 宽度优先搜索的时间复杂度
为了便于分析，考虑一棵树，其每个结点的分支系数为b，最大深度为d。其中分支系数是指一个结点可以扩展产生的新的结点数目。因此搜索树的根结点在第一层会产生b个结点，每个结点又都产生b个新结点，这样在第二层会有b2个结点。因此，目标不会出现在深度为d-1层，失败搜索的最小结点数目为
1+b+b2+…+bd－1=(bd－1)/(b－1)
而在找到目标结点之前可能扩展的最大结点数目为
1+b+b2+…+bd－1+bd=(bd+1－1)/(b－1)
对于d层，目标结点可能是第一个状态，也可能是最后一个状态。因此，平均需要访问的d层结点数目为(1+bd)/2。所以平均总的搜索结点数目为
bd－1b－1+1+bd2≈bd(b+1)2(b－1)
宽度优先搜索的时间复杂度是b的指数函数O(bd)，因此宽度优先搜索的时间复杂度和搜索的结点数目呈正比。
4. 宽度优先搜索的空间复杂度
宽度优先搜索中，空间复杂度和时间复杂度一样，需要很大空间，这是因为树的所有叶结点同时需要储存起来。根结点扩展后，队列中有b个结点。第一层的最左边结点扩展后，队列中有2b-1个结点。当d层最左边的结点正在检查是否为目标结点时，在队列中的结点数目最多，为bd。该算法的空间复杂度和列对长度有关，在最坏的情况下约为指数级O(bd)。
表3.1所示给出了宽度优先搜索的时间和空间需求情况，其中分支系数b=10，每秒处理1000个结点，每个结点都需要100字节。
5. 宽度优先搜索的优缺点
宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标结点距离初始结点较远时会产生许多无用的结点，搜索效率低。从表3.1可以看出，宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时尤为严重，且空间需求是比执行时间更严重的问题。 


表3.1宽度优先搜索的时间和空间需求




深度结点数时间空间
01个1μs100B

2111个1s11KB
411111个11s1MB
6106个18min111MB
8108个31h11GB
101010个128d1TB
121012个35a111TB
141014个3500a11111TB


宽度优先搜索也有优点： 由于宽度优先搜索总是在生成扩展完N层的结点之后才转向N+1层，所以目标结点如果存在，用宽度优先搜索算法总可以找到该目标结点，而且是最小(最短路径)的结点。但实际意义不大，当状态的后裔数的平均值较大时，这种“组合爆炸”就会使算法耗尽资源，在可利用的空间中找不到解。
3.3.2深度优先搜索
1. 深度优先搜索的基本思想

深度优先搜索(DepthFirst Search，DFS)是一种一直向下的搜索策略，从初始结点S0开始，按生成规则生成下一级各子结点，检查是否出现目标结点Sg； 若未出现，则按“最晚生成的子结点优先扩展”的原则，用生成规则生成再下一级的子结点，再检查是否出现Sg； 若仍未出现，则再扩展最晚生成的子结点。如此下去，沿着最晚生成的子结点分支，逐级“纵向”深入搜索。
一个有解的问题常常含有无穷分支，深度优先搜索过程如果误入无穷分支，则不可能找到目标结点，因此它是不完备的。与宽度优先搜索不同，深度优先搜索找到的解也不一定是最佳的。
2. 深度优先搜索算法
深度优先搜索算法仅对有限状态空间类问题具有算法性，但无可采纳性。一般来说，它仅是一个过程，需要进一步改进。下面的方法就是基于栈实现的深度优先搜索算法。
算法3.2深度优先搜索算法。

PROCEDURE Depth-First Search

BEGIN

把初始结点压入栈，并设置栈顶指针； 

WHILE  栈不空  DO

BEGIN

弹出栈顶元素； 

IF 栈顶元素=goal，成功返回并结束； 

ELSE 以任意次序把栈顶元素的子结点压入栈中； 

END WHILE

END.

例3.3八数码难题： 已知8个数的初始布局和目标布局如图3.10所示。


图3.10八数码问题

求解时，首先生成一个结点的搜索树，按照深度优先搜索算法可以生成图3.11的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为5。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。




图3.11深度优先搜索解决八数码问题


3. 深度优先搜索的时间复杂度
如果搜索在d层最左边的位置找到了目标，则检查的结点数为d+1。另外，如果只是搜索到d层，在d层的最右边找到了目标，则检查的结点包括了树中所有结点，其数量为
1+b+b2+…+bd=(bd+1－1)/(b－1)

所以，平均来说，检查的结点数量为
(bd+1－1)/［2(b－1)］+(1+d)/2≈b(bd+d)/［2(b－1)］
上式就是深度优先搜索的平均时间复杂度，即深度优先搜索的时间复杂度是b的指数函数O(bd)。
4. 深度优先搜索的空间复杂度
深度优先搜索对内存的需求是比较适中的，只需保存从根到叶的单条路径，包括在这条路径上每个结点的未扩展的兄弟结点，其存储器要求是深度约束的线性函数。当搜索过程到达最大深度时，所需内存最大。假设每个结点的分支系数均为b，考虑深度为d的结点时，保存在内存中的结点数量包括到达深度d时所有未扩展的结点以及正在被考虑的结点。因此，在每个层次上都有b-1个未扩展的结点，总的内存需要量为d(b-1)+1。所以，深度优先搜索的空间复杂度是b的线性函数O(bd)。
5. 深度优先搜索的优缺点
深度优先搜索算法比宽度优先搜索算法需要较少的空间，只需要保存搜索树的一部分，由当前正在搜索的路径和该路径上还没有完全展开的结点标记所组成。因此，深度优先搜索的存储器要求是深度约束的线性函数。
但是其主要问题是可能搜索到错误的路径上。很多问题可能具有很深甚至是无限的搜索树，如果不幸选择了一个错误的路径，则深度优先搜索会一直搜索下去，而不会回到正确的路径上。这样，对于这些问题来说，深度优先搜索要么陷入无限的循环而不能给出一个答案，要么最后找到一个路径很长且不是最优的答案。也就是说，深度优先搜索既不是完备的，也不是最优的。
3.3.3有界深度搜索和迭代加深搜索 
对于深度d比较大的情况，深度优先搜索需要很长的运行时间，而且还可能得不到解答。一种比较好的问题求解方法是对搜索树的深度进行控制，即有界深度优先搜索方法。有界深度优先搜索过程总体上按深度优先算法进行，但对搜索深度需要给出一个深度限制dm，当深度到达dm的时候，如果还没有找到解答，就停止对该分支的搜索，换到另一个分支进行搜索。
有界深度优先搜索的搜索过程如下。
(1)  把初始结点S0放入OPEN表中，置S0的深度d(S0)=0。 
(2)  如果OPEN表为空，则问题无解，失败并退出。
(3)  把OPEN表中的第一个结点取出放入CLOSE表中，并按顺序冠以编号n。
(4)  考查结点n是否为目标结点。若是，则求得了问题的解，成功并退出。
(5)  如果结点n不可扩展或者深度d(n)=dm，则转第(2)步。
(6)  扩展结点n。将其子结点放入OPEN表的首部，并为其配置指向父结点的指针，然后转第(2)步。
对于有界深度搜索策略，有以下几点需要说明。
（1） 深度限制dm很重要。当问题有解且解的路径长度小于或等于dm时，则搜索过程一定能够找到解，但与深度优先搜索一样，并不能保证最先找到的是最优解，这时有界深度搜索是完备的但不是最优的。但是当dm取得太小，解的路径长度大于dm时，则搜索过程中就找不到解，这时搜索过程是不完备的。
（2） 深度限制dm不能太大。当dm太大时，搜索过程会产生过多的无用结点，既浪费了计算机资源，又降低了搜索效率。有界深度搜索的时间和空间复杂度与深度优先搜索类似，空间是线性复杂度Obdm，时间是指数复杂度为O(bdm)。
（3） 有界深度搜索的主要问题是深度限制值dm的选取。该值也被称为状态空间的直径，如果该值设置得比较合适，则会得到比较有效的有界深度搜索。但对很多问题，我们并不知道该值到底为多少，直到该问题求解完成了，才可以确定深度限制值dm。为了解决上述问题，可采用如下的改进方法： 先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束； 如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。这就是迭代加深搜索的基本思想。
迭代加深搜索 (Iterative Deepening Search，IDS)是一种回避选择最优深度限制问题的策略，试图尝试所有可能的深度限制： 首先深度为0，然后深度为1，最后为2，等等，一直进行下去。如果初始深度为0，则该算法只生成根结点，并检测它。如果根结点不是目标，则深度加1，通过典型的深度优先算法，生成深度为1的树。同样，当深度限制为m时，树的深度也为m。
迭代加深搜索看起来会很浪费，因为很多结点都可能扩展多次。然而对于很多问题，这种多次的扩展负担实际上很小。直觉上可以想象，如果一棵树的分支系数很大，几乎所有的结点都在最底层上，则对于上面各层结点，多次扩展对整个系统的影响不是很大。
搜索深度为h时，由深度优先搜索方法生成的结点数为
(bh+1－1)/(b－1)
由迭代加深搜索过程中的失败搜索所产生的结点数量的总和为
［1/(b－1)］∑d-1h=0(bh+1－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+12(b－1)2
那么，迭代深度搜索和深度优先搜索的时间复杂度的比率为
(b+1)bd+12(b－1)2∶b(bd+d)2(b－1)
对于比较大的d来说，上式简化为
(b+1)bd+12(b－1)2∶bd2(b－1)=(b+1)∶(b－1)
迭代深度搜索和宽度优先搜索的时间复杂度的比率为
(b+1)bd+12(b－1)2∶bd(b+1)2(b－1)=b∶(b－1)
对于一个分支系数b=10的深度目标，迭代深度搜索比深度优先搜索增加20%左右的结点，只比宽度优先搜索增加了11%左右的额外结点。而且，分支系数越大，重复搜索所产生的额外结点比率越小，因此迭代加深搜索和深度优先搜索方法、宽度优先搜索方法相比并没有增加很多的时间复杂度。也就是说，迭代加深搜索的时间复杂度为O(bd)，空间复杂度为O(bd)，既能满足深度优先搜索的线性存储要求，又能保证发现最小深度的目标。
算法3.3迭代加深搜索算法

PROCEDURE Iterative Deepening Search

BEGIN

设置当前深度限制=1;

把初始结点压入栈,并设置栈顶指针;

WHILE  栈不空并且深度在给定的深度限制之内  DO  

BEGIN

弹出栈顶元素； 

IF  栈顶元素=goal，返回并结束;

ELSE  以任意的顺序把栈顶元素的子结点压入栈中;

END

END WHILE

深度限制加1,并返回2;

END.

3.3.4搜索最优策略的比较 
宽度优先搜索、深度优先搜索和迭代加深搜索都可以用于生成和测试算法，然而宽度优先搜索需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。迭代加深搜索对一棵深度受控的树采用深度优先的搜索，结合了宽度优先和深度优先搜索的优点。和宽度优先搜索一样，它是最优的，也是完备的，且对空间要求和深度优先搜索一样是适中的。表3.2给出了这四种搜索策略的比较。


表3.2四种搜索策略的比较




标准宽度优先深度优先有界深度迭代加深

时间bdbmblbd
空间bdbmblbd
最优是否否是
完备是否如果l>d,是是

注： b是分支系数； d是解答的深度； m是搜索树的最大深度； l是深度限制。


3.4启发式搜索
前面讨论的各种搜索方法都是按事先规定的路线进行搜索，没有用到问题本身的特征信息，具有较大的盲目性，产生的无用结点较多，搜索空间较大，效率不高。如果能够利用问题自身的特征信息指导搜索过程，则可以缩小搜索范围，提高搜索效率。
启发式搜索通常用于两种问题： 正向推理和反向推理。正向推理一般用于状态空间的搜索。在正向推理中，推理是从预先定义的初始状态出发向目标状态方向执行。反向推理一般用于问题规约中。在反向推理中，推理是从给定的目标状态向初始状态执行。在前一类使用启发式函数的搜索算法中，包括通常所谓的OR图算法或者最好优先算法，以及根据启发式函数的不同而得到的其他算法，如A*算法等。另外，启发式反向推理算法通常称为ANDOR图搜索算法，如AO*算法等。
3.4.1启发性信息和评估函数
如果在选择结点时能充分利用与问题有关的特征信息，估计出结点的重要性，就能在搜索时选择重要性较高的结点，以利于求得最优解。我们把这个过程称为启发式搜索。“启发式”实际上代表了“大拇指规则”(Rule of Thumb)： 在大多数情况下是成功的，但不能保证一定成功。
与被解问题的某些特征有关的控制信息(如解的出现规律、解的结构特征等)称为搜索的启发信息，反映在评估函数中。评估函数的作用是估计待扩展各结点在问题求解中的价值，即评估结点的重要性。 
评估函数f(x)定义为从初始结点S0出发，约束地经过结点x到达目标结点Sg的所有路径中的最小路径代价估计值。其一般形式为
f(x)=g(x)+h(x)
其中，g(x)表示从初始结点S0到结点x的实际代价； h(x)表示从x到目标结点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，被称为启发式函数。启发式方法把问题状态的描述转换成了对问题解决程度的描述，用评估函数的值表示。 
3.4.2启发式搜索A算法
在一般图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为启发式搜索过程。该过程是按f(x)排序OPEN表中的结点，f(x)值最小者排在首位，优先加以扩展，体现了最佳优先(bestfirst)搜索策略的思想。
启发式搜索过程的设计与一般图搜索过程相同，也划分为两个阶段。
1) 初始化 
建立只包含初始状态结点s的搜索图，即
G∶={s}
OPEN∶={s}
CLOSED∶={}
2) 搜索循环
（1）  MOVEFIRST(OPEN)： 取出OPEN表首的结点n。
（2）  扩展出n的子结点，插入搜索图G和OPEN表。
（3）  适当地标记和修改指针(子结点→父结点)。
（4）  排序OPEN表(评价函数f(n)的值排序)。
通过循环执行该算法，搜索图会因不断有新结点加入而逐步长大，直到搜索到目标结点。
如同一般图搜索过程一样，启发式搜索过程标记和修改指针方法如下。
（1） 扩展出n的子结点ni，插入搜索图G和OPEN表。对每个子结点ni，计算
f(n,ni)=g(n,ni)+h(ni)
（2） 适当地标记和修改指针(子结点→父结点)。
① 全新结点： f(ni)=f(n,ni)。
② 已出现在OPEN表中的结点。
③ 已出现的CLOSED表中的结点。
IFf(ni)>f(n,ni)THEN

令f(ni)=f(n,ni)
修改指针指向新父结点n。

(3) 排序OPEN表(f(n)值从小到大排序)。
算法3.4A算法

PROCEDURE Heuristic Search A  

BEGIN

建立一个只有初始结点S0的搜索图G，把S0放入OPEN表； 计算f(S0)=g(S0)+h(S0)； 假定初始时CLOSED表为空。

WHILE  OPEN表不空  DO

BEGIN

从OPEN表中取出f值最小的结点(第一个结点)，并放入CLOSED表中。假设该结点的编号为n。

IF  n是目标，则停止； 返回n，并根据n的反向指针指出的从初始结点到n的路径。

ELSE DO

BEGIN

扩展结点n。

IF  结点n有后继结点。

BEGIN

(1) 生成n的子结点集合{mi}，把mi作为n的后继结点加入G，并计算f{mi}。

(2) IF mi未曾在G中出现过(未曾在OPEN和CLOSED表中出现过)THEN 将它们配上刚计算过的f值，设置返回到n的指针，并把它们放入OPEN表中。

(3) IF mi已经在OPEN表中 THEN该结点一定有多个父结点，在这种情况下，计算当前的路径g值，并和原有路径的g值相比较： 若前者大于后者，则不做任何更改； 如果前者小于后者，则将OPEN表中的该结点的f值更改为刚计算的f值，返回指针更改为n。

(4) IF mi已经存在于CLOSED表中 THEN 该结点同样也有多个父结点。在这种情况下，同样计算当前路径的g值和原来路径的g值。如果当前的g值小于原来的g值，则将表中该结点的g、f值及返回指针进行类似(3)步的修改，并要考虑修改表中通过该结点的后继结点的g、f值及返回指针。

(5) 按f值的从小到大的次序，对OPEN表中的结点进行重新排序。

END IF

END ELSE

END WHILE

END.

下面以八数码游戏为例，观察A算法的应用。
对于八数码问题，评估函数可表示为
f(x)=d(x)+w(x)
其中，d(x)为g(x)的度量，其值为当前被考查和扩展的结点n在搜索图中的结点深度； w(x)为启发式函数h(x)度量，其值是结点x与目标状态结
点Sg相比较错位的棋牌个数。一般来说，某结点的w(x)越大，即“不在目标”的数码个数越多，说明它离目标结点越远。


图3.12要解决的八数码问题

设想当前要解决的八数码问题如图3.12所示。
初始状态结点的评价函数值f(x)=0+4=4，则应用A算法搜索解答路径十分快捷，除了个别走步判断失误(结点d的选用和扩展)，其他的走步选择全部正确。
图3.13所示给出了搜索图，并以字母标识每个结点，字母后的括号中给出评价函数f的值,且每次循环从OPEN选取扩展的结点用方框框出，最终的g即目标结点。


图3.13应用A算法的八数码搜索图


OPEN和CLOSED表中的结点变化如表3.3所示。


表3.3每个搜索循环结束时OPEN表和CLOSED表中的结点




循环OPEN表CLOSED表
初始化(S)()

1(b c a)(S)
2(d e a c i)(S b)
3(e a c i k j)(S b d)
4(l a c i k j m)(S b d e)
5(n a c i k j m)(S b d e l)
6(g a c i k j m o)(S b d e l n)
7成功结束

3.4.3实现启发式搜索的关键因素
鉴于启发式搜索在提高搜索效率和解决“组合爆炸”问题中的作用，相关的研究成为人工智能形成和成长期的重要议题之一，也产生了许多成熟的研究成果，并且至今启发式搜索仍是一个活跃的研究领域。下面就实现启发式搜索应考虑的关键因素进行讨论。
1. 搜索算法的可采纳性
在搜索图存在从初始状态结点到目标状态结点解答路径的情况下，若一个搜索法总能找到最短(代价最小)的解答路径，则称该算法具有可采纳性。例如，宽度优先的搜索算法就是可采纳的，只是其搜索效率不高。
2.  启发式函数的强弱及其影响
首先引入评价函数： 
f*(x)=g*(x)+h*(x)
f*(x)、g*(x)、h*(x)分别指当经由结点x的最短(代价最小)解答路径找到时实际的路径代价(长度)、该路径前段(自初始状态结点到结点x)代价和后段(子结点x到目标状态结点)代价。在存在多个目标状态的前提下，h*(x)取最小者。
可以用h(x)接近h*(x)的程度去衡量启发式函数的强弱。当h(x)＜h*(x)且两者差距较大时，h(x)过弱，从而导致OPEN表中结点排序的误差较大，易于产生较大的搜索图； 反之，当h(x)>h*(x)，则h(x)过强，使A算法失去可采纳性，从而不能确保找到最短解答路径。显然，设计恒等于h*(x)的h(x)是最为理想的，其确保产生最小的搜索图(因为OPEN表中结点的排序正确)，且搜索到的解答路径是最短的。
对于复杂的问题求解任务，设计恒等于h*(x)的h(x)是不可能的。为此，取消恒等约束，设计接近又总是不大于h*(x)的h(x)成为应用A*算法搜索问题解答的关键，以压缩搜索图，提高搜索效率。可以证明，对于解决同一问题的两个算法A1和A2，若总有h1(x)≤h2(x)≤h*(x)，则t(A1)≥t(A2)。其中，h1、h2分别是算法A1、A2 的启发式函数，t指示相应算法达到目标状态时搜索图包含的结点总数。再以八数码游戏为例，正因为w(x)≤p(x)≤h*(x)，所以采用p(x)扩展出的结点总数不会比采用w(x)时多。更明显的例子是采用宽度优先法解决八数码问题，其相当于h(x)≡0，则图3.13中的搜索树会变得比采用w(x)时庞大得多。
3.  设计h(x)的实用考虑
随着问题求解任务复杂程度的增加，即便是设计接近又总是不大于h* (x)的 h(x)也变得更困难，而且往往会导致在h(x)上的繁重计算工作量。若h(x)的计算开销过大，即使最短路径找到，实际的搜索代价也会高居不下，因为路径选择代价随h(x)的计算开销而增大。删除h(x) ≤ h*(x)的约束，将会使h(x)的设计容易得多，但也由此丢失了可采纳性(可能丢失最短解答路径)。不过在许多实用场合，人们并不要求找到最优解答(最短解答路径)，通过牺牲可采纳性来换取h(x)设计的简化和减少计算h(x)的工作量还是可行的。
从评价函数f(x)=g(x)+h(x)可以看出，若h(x)≡0，则意味着先进入OPEN表的结点会优先被考查和扩展，因为即使不以d(x)作为g(x)， 通常先进入OPEN表的结点x也具有较小的g(x)值，从而使搜索过程接近于宽度优先的搜索策略； 反之，若g(x)≡0，则导致后进入OPEN表的结点会优先被考查和扩展，因为后进入OPEN表的结点x往往更接近于目标状态，即h(x)值较小，从而使搜索过程接近于深度优先的搜索策略。
为更有效地搜索解答，可使用评价函数f(x)=g(x)+wh(x)，w用作加权。在搜索图的浅层(上部)，可让w取较大值，以使g(x)所占比例很小，从而突出启发式函数的作用，加速向纵深方向搜索； 一旦搜索到较深的层次，又让w取较小值，以使g(x)所占比例很大，并确保wh(x)≤h*(x)，从而引导搜索向横广方向发展，寻找到较短的解答路径。
3.4.4A*算法
1.  A*算法的概念和过程 

为考察启发式搜索A算法的可纳性，将评价函数f与f*相比较，实际上，f(x)、g(x)和h(x)分别是f*(x)、g*(x)和h*(x)的近似值。在理想的情况下，设计评价函数f时可以让g(x)=g*(x)，h(x)=h*(x)，则应用该评价函数的A算法就能在搜索过程中每次都能正确地选择下一个从OPEN表中取出加以扩展的结点，从而不会扩展任何无关的结点，就可顺利地获取解答路径。然而g*(x)和h*(x)在最短解答路径找到前是未知的，因此几乎不可能设计出这种理想的评价函数； 而且对于复杂的应用领域，即便设计接近于f*的f往往也是困难的。一般来讲，g(x)的值容易从已生成的搜索树中计算出来，不必专门定义计算公式。例如，就以结点深度d(x)作为g(x)，并有g(x)≥g*(x)。然而h(x)的设计依赖于启发式知识的应用，所以如何挖掘贴切的启发式知识是设计评价函数乃至A*算法的关键。
前述八数码游戏示例(见图3.13)使用的启发式函数w(x)就不够贴切，从而在搜索过程中错误地选用了结点d加以扩展。其实我们可以设计更接近于h*(x)的h(x)，如p(x)，其值是结点x与目标状态结点相比较，假设每个错位棋牌在不受阻拦的情况下，移动到目标状态相应位置所需走步(移动次数)的总和。显然，p(x)比w(x)更接近于h*(x)，因为p(x)不仅考虑了错位因素，还考虑了错位的距离(移动次数)。
返回到图3.13，若启发式函数h(x)采用p(x)，则初始状态结点的评价函数值f(s)=5。在第二个搜索循环结束时，OPEN表中的结点排序为： e a c d i,这些结点的评价函数值依次为： 5 7 7 7 7； 而在使用w(x)情况下，OPEN表中的结点排序为d e a c i，评价函数值依次为： 5 5 6 6 6。显然，p(x)使得用w(x)不能区分的结点d(5)和e(5)区分为d(7)和e(5)，从而搜索过程不再会错误选择结点d，而是选择结点e加以扩展，如图3.14所示。 



图3.14应用启发式函数p(x)的八数码问题搜索图


可以证明，若确保对于搜索图中的结点x，总是有h(x)≤h*(x)， 则A算法具有可采纳性，即总能搜索到最短(代价最小)的解答路径。
我们称满足h(x)≤h*(x)的A算法为A*算法。
A*算法过程如下。
(1)  把S放入OPEN表，记f=h，令CLOSED为空表。
(2)  若OPEN为空表，则宣告失败并退出。
(3)  选取OPEN表中未设置过的具有最小f值的结点为最佳结点BestNode，并把它放入CLOSED表。
(4)  若BestNode为一目标结点，则成功求得一解并退出。
(5)  若BestNode不是目标结点，则扩展之，产生后继结点Successor。
(6)  对每个Successor进行下列过程。 
①  建立从Successor返回BestNode的指针； 
②  计算g(Successor)=g(BestNode)+g(BestNode,Successor)； 
③  如果Successor∈OPEN，则此结点为OldNode，并把它添至后继结点表BestNode中； 
④  比较新旧路径代价。如果g(Successor)<g(OldNode)，则重新确定OldNode的父结点为BestNode，记下较小代价g(OldNode)，并修正f(OldNode)值； 
⑤ 若至OldNode结点的代价较低或一样，则停止扩展结点； 
⑥ 若Successor不在OPEN表中，则看其是否在CLOSED表中； 
⑦ 若Successor在CLOSED表中，则转向③步骤； 
⑧ 若Successor既不在OPEN表中又不在CLOSED表中，则把它放入OPEN表中，并添入后裔表BestNode，然后转向第(7)步。
(7)  计算f值，然后转入第(2)步。
2.  A*算法性质
首先定义下面的符号。
 C(ni,nj)： 从结点ni到结点nj的费用。
 K(ni,nj)： 从结点ni到结点nj最小代价路径的费用。
 g： 一个目标结点。
 G： 目标结点的集合。
 Pn－g： 从结点n到g的路径。
 Pn－G： 从结点n到目标结点集合G的路径集合。
 g*(n)： 从起始结点(根结点)s到结点n所有路径的最小费用，g*(n)=K(s,n)。
 h*(n)： 从结点s到G的所有路径中最小的费用，对所有的g∈G,h*(n)=minK(n,g)。
 C*： 从结点s到G的所有路径中最小代价路径的费用，C*=h*(s)。
A*算法具有下列性质。
性质3.1对最优路径P*s－G上的任何结点n*都满足下面等式： 
f*(n*)=C*
证明： 
f*(n*)=g*(n*)+h*(n*)
=K(s,n*)+minK(n*,g)
=minK(s,g)
=C*g∈G
从性质3.1可以直接得到下面的结论： (1)f*(s)=C*； (2)f*(g)=C*。
性质3.2任何结点n，如果不在任何一条最优路径上，则有
f*(n)＞C*
证明： 该性质可以直接从上面的性质得到。
关于启发式函数，给出下面的定义。
定义3.1启发式函数h（n）称为可纳的，如果有： h(n)≤h*(n)。
性质3.3在A*算法结束之前，在P*s－G上存在OPEN结点n′，有f*(n′)≤C*。
证明： 考虑P*s－G中的一条最优路径P*s－g。假设P*s－g=s,n1,n2,…,n′,…,g，并令n′是P′s-G上深度最浅的OPEN结点。因为在算法结束前g并不是CLOSED，n′是OPEN的。另外，因为n′得所有祖先都是CLSOED结点，因此s,n1,n2,…,n′是最优路径，所以n′的指针一定是沿着路径P*s－g的。因此，有g(n′)=g*(n′)，这样： 
f(n′)=g*(n′)+h(n′)
≤g*(n′)+h(n′)(根据启发式函数可纳性的定义)
=f*(n′)
=C*
性质3.4A*算法是可纳的。
证明： 假设A*算法终止在目标结点t∈G上，并且f(t)=g(t)＞C*，然而在A*算法中，如果t被选择作为扩展结点的话，则对所有OPEN结点n有f(t)≤f(n)。这说明在算法终止之前，OPEN表中任何结点n都有f(n)＞C*。
然而这与性质3.3相矛盾，因此如果算法终止在结点t， 则一定有g(t)=C*，即A*找到的是最优路径。
定义3.2一个启发式函数称为单调的，对所有的(n，n′)，如果满足h(n)≤C(n,n′)+h(n′)，
则n′是n 的后继。
性质3.5每个一致的启发式函数是可采纳的。
证明： 由于h(n)是一致的，则有
h(n)≤K(n,n′)+h(n′)
用g代替n′，则有
h(n)≤K(n,g)+h(g)

h(n)≤h*(n)
这即是可采纳性条件。
对于八数码游戏，从当前被扩展结点x到目标状态结点的最短路径——棋牌移动的最少次数必定不少于错位棋牌的个数(因为有些棋牌可能需移动多于一次才能到达目标状态的相应位置)，也必定不会少于错位棋牌不受阻挡情况下移动到目标状态相应位置的移动次数总和(因为有些棋牌的移动可能会受阻挡)，从而采用w(x)和p(x)作为评价函数时，A*算法都是可纳的。
接着给出下面的性质3.6。
性质3.6如果h(n)满足单调限制，则A*算法扩展的结点序列的f值是非递减的，即
f(ni)≤f(ni+1)
A*算法的搜索效率很大程度上取决于启发式函数h(n)。一般来说，在满足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大说明它携带的启发式信息越多，A*算法搜索时扩展的结点就越少，搜索效率就越高。A*算法的这一特征也成为信息性。
性质3.7设有两个A*算法A1*和A2*：  
A1*： f1(n)=g1(n)+h1(n)

A2*： f2(n)=g2(n)+h2(n)
如果A2*比A1*有更多的启发性信息，即对所有非目标结点，均有
h2(n)＞h1(n)
则在搜索过程中，被A2*扩展的结点也必然被A1*扩展。
证明略。
3.4.5迭代加深A*算法 
迭代加深搜索算法以深度优先的方式在有限制的深度内搜索目标结点。在每个深度上，该算法在每个深度上检查目标结点是否出现，若出现，则停止，否则深度加1，继续搜索。而A*算法是选择具有最小估价函数值的结点扩展。由于A*算法把所有生成的结点保存在内存中，所以A*算法在耗尽计算时间之前一般早已经把空间耗尽了。目前开发了一些新的算法，目的是为了克服空间问题，但一般不满足最优性或完备性，如迭代加深A*算法IDA*、简化内存受限A*算法SMA*等。
迭代加深A*搜索算法IDA*是上述两种算法的结合，这里启发式函数用作深度的限制，而不是选择扩展结点的排序。下面简单介绍IDA*算法。
算法3.5迭代加深IDA*算法

PROCEDURE IDA*

BEGIN

初始化当前的深度限制c=1;

把初始结点压入栈; 

WHLE  栈不空  DO

BEGIN

弹出栈顶元素n;

IFn=goal  THEN 结束, 返回n以及从初始结点到n的路径;

ELSE DO

BEGIN

FORn的每个子结点n′;

IFf(n′)≤c    THEN  把n′压入栈;

ELSEc′=min(c′, f(n′));

END FOF

END

END WHILE

IF栈为空并且c′=∞THEN停止并退出;

IF栈为空并且 c′≠∞THENc=c′ , 并返回2;

END.

上述算法涉及两个深度限制。如果栈中所含结点的所有子结点的f值小于限制值c,则把这些子结点压入栈中，以满足迭代加深算法的深度优先准则。否则，即结点n的一个或多个子结点n′的f值大于限制值c，则结点n的 c′设置为 min(c′，f(n′))。该算法终止的条件为： 找到目标结点(成功结束)，或者栈为空并且限制值c′=∞。
IDA*算法和A*算法相比，主要优点是对于内存的需求。A*算法需要指数级数量的存储空间，因为没有深度方面的限制。而IDA*算法只有当结点n的所有子结点n′的f(n′)小于限制值c时才扩展它，这样就可以节省大量的内存。
另外，当启发式函数是最优的时候，IDA*算法和A*算法扩展相同的结点，并且可以找到最优路径。
3.5回溯搜索和爬山法
在g(x)=0的情况下，若限制只用评价函数f(x)=h(x)去排序新扩展出来的子结点，即局部排序，就可实现较为简单的搜索策略： 回溯策略和爬山法。由于简单易行，在不要求最优解答的问题求解任务中，回溯策略得到广泛的应用。爬山法则适用于能逐步求精的问题。
3.5.1爬山法
爬山法是实现启发式搜索的最简单方法。人们在登山时总是设法快速登上顶峰，只要好爬，总是选取最陡处，以求快速登顶。爬山实际上是求函数极大值问题，不过这里不是用数值解法，而是依赖于启发式知识，试探性地逐步向顶峰逼近(广义地，逐步求精)，直到登上顶峰。
在爬山法中，限制只能向山顶爬去，即向目标状态逼近，不准后退，从而简化了搜索算法； 不需设置OPEN和CLOSED表，因为没有必要保存任何待扩展结点； 仅从当前状态结点扩展出子结点(相当于找到上爬的路径)，并将h(x)最小的子结点(对应于到顶峰最近的上爬路径)作为下一次考察和扩展的结点，其余子结点全部丢弃。
爬山法对于单一极值问题(登单一山峰)十分有效且简便，但对于具有多极值的问题无能为力，因为很可能会因错登高峰而失败——不能到达最高峰。
算法3.6爬山法

PROCEDURE Hill-Climbing

BEGIN

确定可能的开始状态并测量它们与目标结点的距离(f)； 

以f升序排列，把这些结点压入栈； 

REPEAT

弹出栈顶元素； 

IF  栈顶元素=goal，返回并结束； 

ELSE 把该元素的子结点以f升序排列压入栈中； 

UNTIL  栈为空； 

END.

爬山法一般有下面三个问题。
（1）  局部最大： 由于爬山法每次选择f值最小的结点时都是从子结点范围内选择，选择范围较窄，因此爬山法是一种局部择优的方法。局部最大一般比状态空间中全局最大要小，一旦到达了局部最大，算法就会停止，即便该答案可能并不能让人满意。
（2）  平顶： 平顶是状态空间中评估函数值基本不变的一个区域，也称为高地，在某一局部点周围f(x)为常量。一旦搜索到达了一个平顶，搜索就无法确定要搜索的最佳方向，会产生随机走动，这使得搜索效率降低。
（3）  山脊： 山脊可能具有陡峭的斜面，所以搜索可以比较容易地到达山脊顶部，但是山脊的顶部到山峰之间可能倾斜得很平缓。除非正好有合适的操作符直接沿着山脊的顶部移动，否则该搜索可能会在山脊的两面来回震荡，搜索的前进步伐会很小。
在每种情况中，算法都会到达一个点，使得算法无法继续前进。如果出现这种情况，可以从另一个点重新启动该算法，这称为随机重启爬山法。爬山法是否成功和状态空间“表面”的形状有很大的关系： 如果只是很少的局部最大，随机重启爬山法将会很快地找到一个比较好的解答。如果该问题是NP完全的，则该算法不可能好于指数时间，这是因为一定具有指数数量的局部最大值。然而，通常经过比较少的步骤，爬山法一般可以得到比较合理的解答。
3.5.2回溯策略
回溯策略可以有效地克服爬山法面临的困难，其保存了每次扩展出的子结点，并按h(x)值升序排列。如此，相当于爬山的过程中记住了途经的岔路口，只要当前路径搜索失败就回溯(退回)到时序上最近的岔路口，向另一路径方向搜索，从而可以确保最后到达最高峰(目标状态)。
实现回溯策略的有效方式是应用递归过程去支持搜索和回溯。令PATH、SXL、x、x′ 为局部变量。
 PATH： 结点列表，指示解答路径。
 SXL： 当前结点扩展出的子结点列表。
 MOVEFIRST(SXL)： 把SXL表首的结点移出，作为下一次要扩展的结点。
 x、x′： 分别指示当前考察和下一次考察的结点。
该递归过程的算法就取名为BackTrack(x)，参数x为当前被扩展的结点，算法的初次调用式是BackTrack(s)，s即为初始状态结点。
算法过程如下。
(1)  若x是目标状态结点，则算法的本次调用成功结束，返回空表； 
(2)  若x是失败状态结点，则算法的本次调用失败结束，返回'FAIL'； 
(3)  扩展结点x，将生成的子结点置于列表SXL，并按评价函数f(k)=h(k)的值升序排序(k指示子结点)； 
(4)  若SXL为空，则算法的本次调用失败结束，返回'FAIL'； 
(5) x′=MOVEFIRST(SXL)； 
(6)  PATH=BackTrack(x′)； 
(7)  若PATH='FAIL'，返回到(4)； 
(8)  将x′ 加到PATH表首，算法的本次调用成功结束，返回PATH。
在该递归回溯算法中，失败状态通常意指三种情况： ①不合法状态(如传教士和野人问题中所述的那样)； ②旧状态重现(如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环)； ③状态结点深度超过预定限度(如八数码游戏中，指示解答路径不超过6步)。
失败状态实际上定义了搜索过程回溯的条件，回溯条件是搜索进入“死胡同”，由该算法的第(4)步定义。由于回溯是递归算法，解答路径的生成是从算法到达目标状态后逆向进行的，首先产生空表，然后每回到算法的上一次调用就在表首加入结点x′，直到顶层调用返回不包含初始状态结点s的解答路径。
影响回溯算法效率的关键因素是回溯次数。鉴于回溯是搜索到失败状态时的一种弥补行为，只要能准确地选择下一步搜索考察的结点，就能大幅减少甚至避免回溯。所以，设计好的启发式函数h(x)是至关重要的。
3.6问题规约和与或图启发式搜索
3.6.1问题规约

问题规约是人们求解问题常用的策略，把复杂的问题变换为若干需要同时处理的较简单的子问题后，再加以分别求解。只有当这些子问题全部解决后，问题才算解决，问题的解答就由子问题的解答联合构成。问题规约可以递归地进行，直到把问题变换为本原问题的集合。所谓本原问题，就是不可或不需再通过变换化简的“原子”问题，本原问题的解可以直接得到或通过一个“黑箱”操作得到。
问题规约是一种广义的状态空间搜索技术，其状态空间可表示为三元组： 
SP=(S0,O,P)
其中，S0是初始问题，即要求解的问题； P是本原问题集，其中的每个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题； O是操作算子集，是一组变换规则，通过一个操作算子把一个问题化成若干个子问题。
变换可区分为以下三种情况： 
（1）  状态变迁： 导致问题从上一状态变迁到下一状态，这就是一般图搜索技术中操作算子的作用。
（2）  问题分解： 分解问题为需同时处理的子问题，但不改变问题状态。
（3）  基于状态变迁的问题分解： 先导致状态变迁，再实现问题分解，实际上就是前两个操作的联合执行。
作为问题规约的例子，观察下面的符号积分求解问题： 初始状态为∫f(x)dx，目标状态为可直接求原函数和积分的本原问题，如∫sin(x)dx，∫cos(x)dx等。而操作算子就是积分变换规则。
下面就是一次典型的积分变换。
∫sin3x+x4x2+1dx=∫sin3xdx+∫x4x2+1dx
=13∫sin3xd(3x)+∫x4－1+1x2+1dx
=13∫sin3xd(3x)+∫(x2－1)dx+∫1x2+1dx
=－13cos3x+x33－x+arctanx+c
通过上面的变换可以看出，问题规约的实质是从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题规约为一个平凡的本原问题集合。
在简单问题的规约过程中，各子问题相互独立，所以子问题的进一步规约和本原问题的求解无交互作用，可按任意次序进行。然而对于许多复杂问题，子问题仅相对独立，之间仍存在一定的交互作用。在这种情况下，正确安排子问题求解的先后次序，甚至子子问题求解的次序是重要的。
例如，梵塔问题，其问题描述如下： 有编号为1、2、3的三个柱子和标识为A、B、C的尺寸依次为小、中、大的三个有中心孔的圆盘； 初始状态下三个盘按A、B、C顺序堆放在1号柱子上，目标状态下三个盘以同样顺序堆放在3号柱子上，盘子的搬移须遵守以下规则： 每次只能搬一个盘子，且较大盘不能压放在较小盘之上，如图3.15所示。




图3.15梵塔问题


以三元素列表作为数据结构描述问题状态，三个元素依次指示盘子A、B、C所在的柱子编号。如此梵塔问题描述为(1,1,1)(3,3,3)。可以把该问题规约为三个子问题(1,1,1) (2,2,1)、(2,2,1)(2,2,3)和(2,2,3)(3,3,3)，即先把A、B盘搬到柱子2，再把C盘搬到柱子3，最后把A、B盘搬到柱子3。第1、3两个子问题再分别规约为子子问题如下： (1,1,1)(3,1,1)、(3,1,1)(3,2,1)、(3,2,1)(2,2,1)，即依次搬A盘到柱子3，B盘到柱子2，A盘到柱子2；  (2,2,3)(1,2,3)，(1,2,3)(1,3,3)、(1,3,3)(3,3,3)，即依次搬A盘到柱子1、B盘到柱子3、A盘到柱子3。现在所有子问题均为本原问题，只要依次解决就可到达目标状态。梵塔问题的子问题和子子问题之间有交互作用，必须注意正确的排序。其状态空间图表示如图3.16所示，在图中已标出正确的结点生成顺序。




图3.16梵塔问题的状态空间图表示


可以看出，应用问题规约策略求解问题的原理简单，方法有效，因此得到了广泛和深入的研究及应用。
3.6.2与或图表示
通过问题规约可以看到，对于一个复杂的问题，我们常常把此问题分解成若干个子问题。如果把每个子问题都解决了，整个问题也就解决了。如果子问题不容易解决，还可以再分成子问题，直至所有的子问题都解决了，则这些子问题的解的组合就构成了整个问题的解。与或图(ANDOR Graph，AOG)是用于表示此类求解过程的一种方法，是一种图或树的形式，是基于人们在求解问题时的一种思维方法。
（1）  分解： 树。把一个复杂的问题P分解为与之等价的一组简单的子问题P1，P2，…，Pn，而子问题还可分为更小、更简单的子问题，以此类推。当这些子问题全都解决后，原问题P也就解决了； 任何一个子问题Pi (i=1，2，…，n)无解，都将导致原问题P无解。这样的问题与这一组子问题之间形成了“与”的逻辑关系。这一分解过程可用一个有向图来表示； 问题和子问题都用相应的结点表示，从问题P到每个子问题Pi都只用一个有向边连接，然后用一段弧将这些有向边连起来，以标明它们之间存在的“与”的关系。这种有向图称为“与”图或者“与”树。
（2）  等价变换： “或”树。把一个复杂的问题P经过等价变换转变为与之等价的一组简单的子问题P1，P2，…，Pn，而子问题还可再等价变换为若干更小、更简单的子问题，如此下去。当这些子问题中有任何一个子问题Pi (i=1，2，…，n)有解时，原问题P也就解决了； 只有当全部子问题无解时，原问题P才无解。这样的问题与这一组子问题之间形成了“或”的逻辑关系。这一等价变换同样可用一个有向图来表示，这种有向图称为“或”图或者“或”树。表示方法类似“与”图的表示，只是在“或”图中不用弧将有向边连起来。
（3）  与或图。在实际问题求解过程中，常常是既有分解又有等价变换，因而常将两种图结合起来一同用于表示问题的求解过程。此时，所形成的图就称为“与或”图或者“与或”树。
可以把与或图视为对一般图(或图)的扩展； 或反之，把一般图视为与或图的特例，即一般图不允许结点间具有“与”关系，所以又可把一般图称为或图。与一般图类似，与或图也有根结点，用于指示初始状态。由于同父子结点间可以存在
“与”关系，父、子结点间不能简单地以弧线关联，因此需要引入“超连接”概念。同样原因，在典型的与或图中，解答路径往往不复存在，代之以广义的解路径——解图。
图3.17是一个抽象的与或图简例，结点的状态描述不再显式给出。


图3.17与或图简例

下面就基于该简例引入和解释与或图搜索的基本概念。
（1）  K连接。用于表示从父结点到子结点间的连接，也称为父结点的外向连接，并以圆弧指示同父子结点间的 “与”关系，K为这些子结点的个数。一个父结点可以有多个外向的K连接。例如，根结点n0就有2个K连接： 一个2连接指向子结点n1和n2，另一3连接指向子结点n3、n4 和n5。K大于1的连接也称为超连接，K等于1时超连接蜕化为普通连接，而当所有超连接的K都等于1时，与或图蜕化为一般图。
（2）  根、叶、终结点。无父结点的结点称为根结点，用于指示问题的初始状态； 无子结点的结点称为叶结点。由于问题规约伴随着问题分解，因此目标状态不再由单一结点表示，而是由一组结点联合表示。能用于联合表示目标状态的结点称为终结点； 终结点必定是叶结点，反之不然； 非终结点的叶结点往往指示了解答搜索的失败。
（3）  解图的生成。在与或图搜索过程中，可以这样建立解图： 自根结点开始选一个外向连接，并从该连接指向的每个子结点出发，再选一个外向连接，如此反复，直到所有外向连接都指向终结点为止。例如，从图3.17与或图根结点n0开始，选左边的K=2的外向连接，指向结点n1和n2，再从n1、n2分别选外向连接； 从n1选左边的K=1的外向连接，指向n6，依次进行，直到终结点n14、n18、n19和n20； 从n2只有一个K=1的外向连接指向终结点n9。如此，生成如图3.18(a)所示的一个解图。注意，解图是遵从问题规约策略而搜索到的，解图中不存在结点或结点组之间的“或”关系； 换言之，解图纯粹是一种“与”图。另外，正因为与或图中存在“或”关系，所以往往会搜索到多个解图，本例中就有四个(见图3.18)。


图3.18四个可能的解图


为确保在与或图中搜索解图的有效性，要求解图是无环的，即任何结点的外向连接均不得指向自己或自己的先辈，否则会使搜索陷入死循环。换言之，会导致解图有环的外向连接不能选用。下面给出关于解图、解图代价、能解结点和不能解结点的定义。
（1）  解图： 与或图(记为G) 中任一结点(记为n)到终结点集合的解图(记为G′)是G的子图。
 若n是终结点，则G′就由单一结点n构成。
 若n有一外向K连接指向子结点n1,n2,…，nk，且每个子结点都有到终结点集合的解图，则G由该K连接和所有子结点的解图构成。
 否则不存在n到终结点集合的解图。 
（2）  解图代价： 以C(n)指示结点n到终结点集合解图的代价，并令K连接的代价就为K。
（3）  能解结点。
 终结点是能解结点； 
 若结点n有一外向K连接指向子结点n1,n2,…，nk，且这些子结点都是能解结点，则n是能解结点。
（4）  不能解结点。
 非终结点的叶结点是不能解结点； 
 若结点n的每个外向连接都至少指向一个不能解结点，则n是不能解结点。
关于能解结点和不能解结点如图3.19所示。



图3.19能解结点和不能解结点


3.6.3与或图的启发式搜索
与或树的启发式搜索算法也称为AO*算法，此过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望称为最优解树的子树。最优解树是指代价最小的那棵解树。那么如何计算解树的代价呢？下面先讨论这个问题。
1. 解图的代价 
要寻找最优解树，首先需要计算解树的代价。在与或树的启发式搜索过程中，解树的代价可按如下规则计算。
(1)  若n是终止结点，则其代价h(n)=0。
(2)  若n为或结点，且子结点为n1,n2,…，nk，则n的代价为
h(n)=min1≤i≤k［c(n,ni)+h(ni)］

其中，c(n,ni)是结点n到其子结点ni的边代价。
(3)  若n为与结点，且子结点为n1,n2,…，nk，则n的代价可用和代价法或最大代价法计算。和代价法计算公式为
h(n)=∑ki=1［c(n,ni)+h(ni)］
最大代价法计算公式为
h(n)=max1≤i≤k［c(n,ni)+h(ni)］
(4)  若n是端结点，但不是终止结点，则n不可扩展，其代价定义为h(n)=∞。
(5)  根结点的代价即为解树的代价。
例3.4设图3.20是一棵与或树，其中包括两棵解树，左边的解树由S0、A、t1、C及t3组成，右边的解树由S0、B、t2、D及t4组成。在此与或树中，t1、t2、t3、t4为终结点，E、F是端结点，边上的数字是该边的代价。请计算解树的代价。



图3.20与或树的代价


解： 先计算左边的解树。
按和代价计算，即
h(S0)=2+4+6+2=14
按最大代价计算，即
h(S0)=8+2=10
再计算右边的解树。
按和代价计算,即
h(S0)=1+5+3+2=11
按最大代价计算，即
h(S0)=6+2=8
在本例中，无论是按和代价还是按最大代价，右边的解树都是最优解树。但在有些情况下，当采用的代价法不同时，找到的最优解树有可能不同。
2.  AO*搜索
与一般图(或图)的搜索过程类似，引入应用领域的启发式知识去引导搜索过程，可以显著提高搜索的有效性，加速搜索算法的收敛。考虑与或图中搜索的是解图，非由相邻结点间路径连接成的解路径，所以估算评价函数f(n)的第一分量g(n)没有意义，只需估算第二分量h(n)。注意，h(n)也不是对于最小路径代价的估计，而是对于最小解图代价的估计。另外，由于与或图中子结点或子结点组间可以存在“或”关系，所以在搜索过程中会同时出现多个候选的待扩展局部解图，应估计所有这些局部解图的可能代价，并从中选择一个可能代价最小的用于下一步搜索。解图以递归方式生成，解图的代价也以递归方式计算，所以一旦某父结点n的由外向K连接指向的子结点n1,n2,…，nk都估算了其h(ni)(i=1，2，…，k)的值，则从父结点n到终结点集合解图的可能代价f(n)可以用公式
f(n)=K+h(n1)+h(n2)+…+h(nk)
计算，并用于取代原先在扩展出结点n时直接基于h(n)估算而得出的f(n)值。显然，基于子结点h(ni)算出的f(n)更为准确。如此递归，可以计算出更为准确的f(n0)，即从初始状态结点到终结点集合的解图的可能代价。
下面就给出实现与或图启发式搜索的AO*算法，然后再讨论该算法应用的若干问题。
AO*搜索过程
设： 
 G： 指示搜索图。
 G′： 被选中的待扩展局部解图。
 LGS： 候选的待扩展局部解图集。
 n0： 指示根结点，即初始状态结点。
 n： 被选中的待扩展结点。
 fi(n0)： 第i个候选的待扩展局部解图的可能代价。
AO*搜索过程如下。
(1)  G:=n0，LGS为空集。
(2)  若n0是终结点，则标记G:=n0为能解结点； 否则计算f(n0)=h(n0)，并把G作为0号候选局部解图加进LGS。
(3)  若n0标记为能解结点，则算法成功返回。
(4)  若LGS为空集，则搜索失败返回； 否则，从LGS选择fi(n0)最小的待扩展局部解图作为G′。
(5)  G′中选择一个非终结点的外端结点(尚未用于扩展出子结点的结点)作为n。
(6)  扩展n，生成其子结点集，并从中删去导致有环的子结点以及和它们“与”关系的子结点； 若子结点集为空，则n是不能解结点，从LGS删去G′(因为G′不可能再扩展为解图)； 否则，计算每个子结点ni的f(ni)，并通过建立外向K连接将所有子结点加到G中。
(7)  若存在j (j>1) 个外向K连接，则从LGS删去G′，并将j个新局部解图加进LGS。
(8)  G′中或在取代G′的j个新局部解图中用公式f(n)=K+h(n1)+h(n2)+…+h(nk)的计算结果取代原先的f(n)，并传递这种精化的作用到fi(n0)(i=1,2,…,j)； 同时将作为终结点的子结点标记为能解结点，并传递结点的能解性。 
(9)  返回(3)。
3.  AO*算法
算法3.7AO*算法

PROCEDURE AO*

BEGIN

设G仅由代表开始状态的结点组成(称此结点为Init),计算h(Init)。

REPEAT

跟踪从Init开始的已带标记的弧，如果存在，则挑选出现在此路径上但未扩展的结点之一扩展，称新挑选的结点为Node;

生成Node的后继结点。

IF  Node没有后继结点  THEN 令h(Node)=Futility，说明该结点不可解。

ELSE 后继结点称为Successor，对每个不是Node结点祖先的后记结点  DO

BEGIN

把Successor加到图G中;

若Successor是叶结点，那么将其标记为Solved，并令h(Successor)=0;

若Successor不是叶结点，则计算其h值。 

END.

将最新发现的信息向图的上部回传，具体做法为： 设S为一结点集，S包括已经做了Solved标记的结点，以及h已经做了改变，需要回传至其先辈结点的那些结点，初始S只包含结点Node。

REPEAT

从S中挑选一个结点，该结点在G中的子孙均不在S中出现(换句话说，保证对于每个正在处理的结点是在处理其任意祖先之前来处理该结点的)，称此结点为Current，并把它从S中去掉; 计算始于Current的每条弧的耗费。每条弧的耗费等于在该弧末端每一结点的h值之和加上该弧本身的耗费。从刚刚计算过的始于Current的所有弧的耗费中选出极小耗费作为Current的新h值; 把在上一步计算出来的带极小耗费的弧标记为始于Current的最佳路径。

IF 穿过新的带标记弧与Current连接的所有结点均标为Solved。

THEN  把Current标为Solved。 

IF  Current已标为Solved，或Current的耗费已经改变。

THEN 应把其新状态往回传。因此，要把Current的所有祖先加到S中。

UNTIL  S为空。

UNTIL  Init标为Solved(成功)，或Init的h值变得大于Fuitlity(失败)。

END.



图3.21结点编号后的与或图


下面就以图3.17所示与或图为简例，观察如何应用上述AO*算法来搜索解图。为了方便描述，给图中的每个结点进行编号，从n0到n20，如图3.21所示。

假定在搜索过程中扩展出来的某些结点的启发式函数f4(n0)=8h(ni)的估算如下： 

h(n0)=3，h(n1)=2，h(n2)=1，

h(n3)=1，h(n4)=4,h(n5)=2，

h(n6)=2，h(n7)=1，h(n8)=1，

h(n13)=3。
AO*算法工作的第一个循环扩展根结点n0产生2个候选的局部解图，编号为1(对应于2连接)和2(对应于3连接)，加入LGS并删去0号局部解图。 鉴于f1(n0)=5而f2(n0)=10，第二个循环就选中1号局部解图作为G′(图3.22(a))。随机选中n1加以扩展，建立2个外向连接，从LGS删去1号局部解图，将2个扩展出的新局部解图，编号为3(对应于1连接)和4(对应于2连接)，加入LGS。鉴于f3(n0)=6而 f4(n0)=7，第三个循环就选中3号局部解图作为G′。 随机选中n6加以扩展，建立1个外向连接(并由此扩展了3号局部解图)，并使f3(n0)=9。第四个循环就选中4号局部解图作为G′(此时f4(n0)=7，最小)，随机选中n7加以扩展，建立1个外向连接，并维持f4(n0)不变。由于新扩展出的结点n14是终结点，标记其为能解结点，并递归地标记结点n7为能解结点。第五个循环仍选中4号局部解图作为G′，随机选中n8加以扩展，建立1个外向连接，并使f4(n0)=8。标记新扩展出的终结点n15为能解结点，递归地标记结点n8和n1为能解结点。第六个循环仍选中4号局部解图作为G′，扩展结点n2，标记新扩展出的终结点n9为能解结点，递归地标记结点n2和n0为解结点。至此算法AO*成功搜索到解图，且解图代价为8。


图3.22算法AO*搜索过程中解图的形成


4.  算法应用的若干问题
1)  从局部解图中选择加以扩展的结点
鉴于与或图搜索的是解图而非解路径，所以选择f(n)=h(n)的值最小的结点加以扩展，并不一定会加速搜索过程。反而应选择导致解图代价发生较大变化的结点优先加以扩展，以使搜索的注意力快速地聚焦到实际代价较小的候选解图上。然而，这种选择需要附加启发式知识。若应用领域挖掘不出这样的启发式知识，可随机选择加以扩展的结点。
2)  AO*算法的可采纳性
AO*算法的应用要求遵从以下约束： 总能满足h(n)≤h*(n)，且确保h(n)满足单调限制条件。只有遵从该约束，AO*算法才是可采纳的，即当某与或图存在解图时，应用AO*算法一定能找出代价最小的解图。
类似于算法A*，h*(n)是实际的代价最小解图找到时解图的代价，我们通常只能设计接近于h*(n)的h(n)，单调限制条件表示为
h(n)≤K+h(n1)+h(n2)+…+h(nk)
其中，n1,n2,…,nk是结点n通过K连接指向的子结点。若将h(n)的值视为粗略的估计，而K+h(n1)+h(n2)+…+h(nk)的值视为细致的计算，则单调限制可理解为： 粗略的估计总是不超过细致的计算。
3)  搜索算法AO*与A*的比较
（1）  AO*应用于与或图搜索，且搜索的是解图； 而AO*则应用于一般图(或图)搜索，且搜索的是解答路径。
（2）  AO*选择估算代价最小的局部解图加以优先扩展； 而A*选择估算代价最小的路径加以优先扩展。 
（3）  AO*不需考虑评价函数f(n)的分量g(n)，只需对新扩展出的结点n计算h(n)，以用于修正fi(n0)； 而 A*则需同时计算分量g(n)和h(n)，以评价结点n是否在代价最小的路径上。
（4）  AO*应用LGS存放候选的待扩展局部解图，并依据fi(n0)值排序； 而A*则应用OPEN表和CLOSED表分别存放待扩展结点和已扩展结点，并依据f(n)值排序。
4)  解图代价的重复计算
解图中某些子结点可能会有多个父结点，或者说多个结点的外向连接符可能指向同一个子结点。依据前述解图代价的递归计算方式，显然这种子结点到终结点集合解图的代价在计算自根结点n0出发的解图时被重复累计了。为正确计算解图的代价，必须删除重复的累计。例如，图3.21(d)中的解图结点n10和n11到终结点n16和n17的解图代价被分别重复累计了2次，如此整个从根结点n0到终结点集的解图代价为14； 若删除重复的累计，实际解图代价为11。
3.7博弈
广义的博弈涉及人类各方面的对策问题，如军事冲突、政治斗争、经济竞争等。博弈提供了一个可构造的任务领域，在这个领域中具有明确的胜利和失败。同样，博弈问题对人工智能研究提出了严峻的挑战。例如，如何表示博弈问题的状态、博弈过程和博弈知识等。所以，在人工智能中，通过计算机下棋等研究博弈的规律、策略和方法是有实用意义的。
机器博弈的研究广泛而深入，早在20世纪50年代，就有人设想利用机器智能来实现机器与人的博弈。国内外许多知名学者和科研机构都曾涉足这方面的研究，历经半个多世纪，目前已经取得了许多惊人的成就。1997年IBM公司的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。除此之外，加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为信息游戏世界冠军，且存在非确定因素的西洋双陆棋，美国卡内基梅隆大学的西洋双陆琪程序BKG也夺得了世界冠军。对围棋、中国象棋、桥牌、扑克等许多种其他种类游戏博弈的研究也在进行中。
这里讲的博弈是二人博弈，“二人零和、全信息、非偶然”博弈，博弈双方的利益是完全对立的。所谓“二人零和”，是指在博弈中只有“敌、我”二方。且双方的利益完全对立，其赢得函数之和为零，即
φ1+φ2=0
式中，φ1为我方赢得(利益)； φ2为敌方赢得(利益)。
也就是说,博弈的双方有三种结局。
(1)  我胜： φ1>0； 敌负： φ2=－φ1<0 e(p)=e(+p)－e(－p)。
(2)  我负： φ1=－φ2<0； 敌胜： φ2>0。
(3)  平局： φ1=0，φ2=0。
通常，在博弈过程中，任何一方都希望自己胜利。双方都采用保险的博弈策略，在最不利的情况下争取最有利的结果。因此，在某一方当前有多个行动方案可供选择时，总是挑选对自己最为有利而对对方最为不利的那个行动方案。
所谓“全信息”，是指博弈双方都了解当前的格局及过去的历史。所谓“非偶然”，是指博弈双方都可根据得失大小进行分析，选取我方赢得最大、敌方赢得最小的对策，而不是偶然的随机对策。
另外是机遇性博弈，是指不可预测性的博弈，如掷硬币游戏等。 这种博弈不在本节讨论的范围。先来看一个例子，假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆数量不等的钱币，两位选手轮流进行，直到每一堆都只有一枚或两枚钱币，不再能分为止，哪个遇到不能再分的情况，则就为输。
用数字序列加上一个说明表示一个状态，其中数字表示不同堆中钱币的数量，说明表示下一步由谁来分，如(7，MIN)表示只有一个由七枚钱币组成的堆，由MIN走，MIN有三种可供选择的分法，即(6，1，MAX)，(5，2，MAX)，(4，3，MAX)，其中MAX表示另一对手走，无论哪种方法，MAX都是在此基础上进行符合要求的再分，整个过程如图3.23所示。图3.23中已将双方可能的分法完全表示出来了，无论MIN开始时怎么走，MAX总可以获胜，取胜的策略用双箭头表示。



图3.23分钱币的博弈



实际的情况没有这么简单，任何一种棋都不可能将所有情况列尽，因此只能模拟人“向前看几步”，然后做出决策，决定自己走哪一步最有利。也就是说，只能给出几层走法，然后按照一定的估算方法，决定走哪一步棋。
在双人完备信息博弈过程中，双方都希望自己能够获胜。因此当一方走步时，都是选择对自己最有利而对对方最不利的走法。假设博弈双方为MAX和MIN。在博弈的每一步，可供他们选择的方案都有很多种。从MAX的观点看，可供自己选择的方案之间是“或”的关系，原因是主动权在自己手里，选择哪个方案完全由自己决定，而对那些可供MIN选择的方案之间是“与”的关系，这是因为主动权在MIN手中，任何一个方案都可能被MIN选中，MAX必须防止那种对自己最不利的情况出现。 
通过上面的例子可以看出，博弈过程也可以采用与或树进行知识表达，这种表达形式称为博弈树。由于博弈是敌我双方的智能活动，任何一方不能单独控制博弈过程，而是双方轮流实施其控制对策的过程。因此，博弈树是一种特殊的与或树。其中，不同级别(深度)的结点分别交替属于敌我双方，在博弈树生成过程中，由敌我双方轮流进行扩展，新生成的子结点交替出现。
经过分析，博弈树的特点如下。
（1）  与结点、或结点逐级交替出现，敌方、我方逐级轮流扩展其所属结点。
（2）  从我方观点，所有敌方结点都是与结点。因敌方必然选取最不利于我方的一招(棋步)，扩展其子结点。只要其中有棋步对我方不利，该结点就对我方不利。换言之，只有该结点的所有棋步(所有的子结点)皆对我方有利，该结点才对我方有利，故为与结点。
（3） 从敌方的观点，所有我方结点都是或结点。因为扩展我方结点的主动权在我方，可以选取最有利于我方的棋步，只要可走的棋步中有一招是有利的，该结点对我方就是有利的。即其子结点中任何一个对我方有利，则该结点对我方有利，故为或结点。
（4）  所有能使我方获胜的终局都是本原问题，相应的端结点是可解结点； 所有使敌方获胜的终局，对我方而言，是不可解结点。
（5） 先走步的一方(我方或敌方)的初始状态相应于根结点。
人工智能可以采用搜索方法来求解博弈问题，下面就来讨论博弈中最基本的两种搜索方法。 
3.7.1极大极小过程 
极大极小过程(MINMAX，MM)是考虑双方博弈若干步之后，从可能的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。
为此需要定义一个静态估价函数e(x)，以便对棋局的态势做出评估。这个函数可以根据棋局的态势特征进行定义。假定博弈双方分别为MAX和MIN，其中p代表棋局。规定： 有利于MAX方的态势： e(p)取正值； 有利于MIN方的态势： e(p)取负值； 态势均衡的时候： e(p)取零。
MINMAX基本思想如下。
(1)  当轮到MAX走步的结点时，MAX应考虑最好的情况(e(p)取极大值)。
(2)  当轮到MIN走步的结点时，MIN应考虑最坏的情况(e(p)取极小值)。
(3)  评价往回倒推时，相当于两位棋手的对抗策略，交替使用(1)和(2)两种方法传递倒推值，直至求出初始结点的倒推值为止。
由于我们是站在MAX立场上，因此应选择具有最大倒推值的走步。这一过程称为极大极小过程。 
例3.5如图3.24所示是向前看两步，共四层的博弈树，用□表示MAX，用○表示MIN，端结点上的数字表示它对应的估价函数的值，在MIN处用圆弧连接。 



图3.24四层博弈树


图中结点处的数字，在端结点是估价函数的值，称它为静态值，在MIN处取最小值，在MAX处取最大值，最后MAX选择箭头方向的走步。 

例3.6一字棋游戏。设有一个三行三列的棋盘，如图3.25所示，两个棋手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。设MAX方的棋子用×标记，MIN方的棋子用○标记，并规定MAX方先走步。



为了不至于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下： 设棋局为p，估价函数为e(p)。
 若p是MAX必胜的棋局，则e(p)=+∞； 
 若p是MIN必胜的棋局，则e(p)=－∞； 
 若p是胜负未定的棋局，则e(p)=e(+p)－e(－p)。

其中，e(+p)表示棋局p上有可能使MAX成为三子成一线的数目； e(-p)表示棋局p上有可能使MIN成为三子成一线的数目，且具有对称性的两个棋局算作一个棋局。例如，棋局1状态如图3.26所示。


图3.25一字棋棋盘





图3.26棋局1




图3.27一字棋的棋局状态


其估价函数为
e(p)=e(+p)－e(－p)=6－4=2
在搜索过程中，具有对称性的棋局认为是同一棋局。例如，如图3.27所示的棋局可以认为是同一个棋局，这样可以大大减少搜索空间。



假设由MAX先走棋，且我们站在MAX立场上。图3.28给出了MAX的第一招走棋生成的博弈树。图中结点旁的数字分别表示相应结点的静态估值或倒推值。由图3.28可以看出，对于MAX来说最好的一招棋是S3，因为S3比S1和S2有较大的估值。 




图3.28一字棋极大极小搜索


3.7.2αβ过程 
上面讨论的极大极小过程会先生成一棵博弈搜索树，而且会生成规定深度内的所有结点，然后进行估值的倒推计算，这样使得生成博弈树和估计值的倒推计算的两个过程完全分离，因此搜索效率较低。如果能既生成博弈树又能进行估值的计算，则可能不必生成规定深度内的所有结点，从而减少搜索的次数，这就是下面要讨论的αβ过程。 
αβ过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此提高算法的效率。具体的剪枝方法如下。
(1)  对于一个与结点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父结点(一定是或结点)的估计倒推值的下确界α，即α≥β，则不必再扩展该MIN结点的其余子结点了(因为这些结点的估值对MIN父结点的倒推值已无任何影响)。这一过程称为α剪枝。
(2)  对于一个或结点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于MAX的父结点(一定是与结点)的估计倒推值的上确界β，即α≥β，则不必再扩展该MAX结点的其余子结点了(因为这些结点的估值对MAX父结点的倒推值已无任何影响)。这一过程称为β剪枝。
例3.7一个αβ剪枝的具体例子，如图3.29所示。其中最下面一层端结点旁边的数字是假设的估值。 




图3.29一个αβ剪枝的具体例子


在图3.29中，K、L、M的估值推出结点F的倒推值为4，即F的β值为4，由此可推出结点C的倒推值≥4。记C的倒推值的下界为4，不可能再比4小，故C的α值为4。
由结点N的估值推知结点G的倒推值≤1，无论G的其他子结点的估值是多少，G的倒推值都不可能比1大。因此，1是G的倒推值的上界，所以G的值≤1。另外，已知C的倒推值≥4，G的其他子结点又不可能使C的倒推值增大。因此对G的其他分支不必再搜索，相当于把这些分支剪去。由F、G的倒推值可推出结点C的倒推值≥4，再由C可推出结点A的倒推值≤4，即A的β值为4。另外，由结点P、Q推出的结点H的倒推值为5，因此D的倒推值 ≥5，即D的α值为5。此时，D的其他子结点的倒推值无论是多少都不能使D及A的倒推值减少或增大，所以D的其他分支被剪去，并可确定A的倒推值为4。以此类推，最终推出S0的倒推值为4。 
通过上面的讨论可以看出，αβ过程首先使搜索树的某一部分达到最大深度，这时计算出某些MAX结点的α值，或者是某些MIN结点的β值。随着搜索的继续，不断修改个别结点的α或β值。对任一结点，当其某一后继结点的最终值给定时，就可以确定该结点的α或β值。当该结点的其他后继结点的最终值给定时，就可以对该结点的α或β值进行修正。
注意：  α、β值修改有如下规律： ①MAX结点的α值永不下降； ②MIN结点的β值永不增加。
因此，利用上述规律进行剪枝，一般可以停止对某个结点搜索。剪枝的规则表述如下。
(1)  若任何MIN结点的β值小于或等于任何它的先辈MAX结点的α值，则可停止该MIN结点以下的搜索，然后该MIN结点的最终倒推值即为它已得到的β值。该值与真正的极大、极小值的搜索结果的倒推值可能不相同，但是对开始结点而言，倒推值是相同的，使用它选择的走步也是相同的。
(2)  若任何MAX结点的α值大于或等于它的MIN先辈结点的β值，则可以停止该MAX结点以下的搜索，然后该MAX结点处的倒推值即为它已得到的α值。
当满足规则(1)而减少了搜索时，进行了α剪枝； 而当满足规则(2)而减少了搜索时，进行了β剪枝。保存α和β值，并且就进行剪枝的整个过程通常称为αβ过程，当初始结点的全体后继结点的最终倒推值全部给出时，上述过程便结束。在搜索深度相同的条件下，采用这个过程所获得的走步跟简单的极大、极小过程的结果是相同的，区别只在于αβ过程通常只用少得多的搜索便可以找到一个理想的走步。 
3.8小结
本章讨论的知识搜索策略是人工智能研究的一个核心问题。搜索是人工智能的一种问题求解方法，搜索策略决定着问题求解的一个推理步骤中知识被使用的优先关系。在搜索中，知识利用得越充分，求解问题的搜索空间就越小。对这个问题的研究曾经十分活跃，而且至今仍不乏高水平的研究课题。正如知识表示一样，知识的搜索与推理也有众多的方法，同一问题可能采用不同的搜索策略，其中有的比较有效，而有的则不大适合具体问题。本章介绍的几种搜索策略主要适合解决不太复杂的问题。
本章首先介绍了基于状态空间图的搜索技术，给出了图搜索的基本概念，分析了状态空间图搜索和一般图搜索算法。在应用盲目搜索进行求解过程中，一般是“盲目”穷举，即不运用特别信息。在盲目搜索中最具代表的算法是宽度优先搜索和深度优先搜索。当状态空间比较大的时候，由于宽度优先需要很大的存储空间，因此宽度优先是不合适的。在很多典型的人工智能问题中，深度优先有着很多的应用，但深度优先不是一种完备的方法，因此迭代加深搜索应运而生，通过和A*算法结合，迭代加深搜索转化为IDA*算法，该算法已经有了很多的研究，并且在并行结构上实现。
在本章给出的启发式搜索中，最流行的是A*算法和AO*算法。A*算法用于或图，而AO*算法用于与或图。A*算法用于状态空间中寻找目标，以及从起始结点到目标结点的最优路径问题。AO*算法用于确定实现目标的最优路径。最近，有人通过机器学习的方法增强状态空间中结点的启发式信息，对A*算法算法进行扩展。
另外，本章还介绍了博弈问题，这可以看作是一种特殊的与或搜索问题。极大、极小方法和αβ剪枝技术在现在的一些博弈类游戏软件中是必不可少的。

习题
3.1简述一般图搜索算法，在搜索过程中OPEN表和CLOSE表的作用是什么？ 
3.2对比深度优先和宽度优先的搜索方法，为何说它们都是盲目搜索方法？ 
3.3简述有界深度搜索的步骤，并说明有界深度搜索与深度搜索的区别。
3.4什么是启发式搜索？什么是启发式信息？试列出几种不同的启发式搜索算法。
3.5说明启发式函数h(n)的强弱对搜索效率的影响； 实用上，如何使图搜索更为有效？
3.6什么是问题规约？为什么应用问题规约得到的状态空间可表示为与或图？
3.7举例说明与或图搜索的基本概念： K连接，根、叶、终结点，解图，解图代价，能解结点和不能解结点。
3.8阐述与或图启发式搜索的AO*算法，AO*算法的可采纳性条件是什么？为什么扩展局部解图时，不必选择h(n)值最小的结点加以扩展？
3.9比较启发式搜索AO*算法和A*算法，并说明两者差异的理由。
3.10设有三只琴键开关一字排开，初始状态为“关、开、关”，连按三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关，而且只能按一个开关。请画出状态空间图。
3.11卒子穿阵问题。要求一卒子从顶部通过图3.30所示的阵列到达底部。卒子行进中不可进入代表敌兵驻守的区域(标注1)，并不准后退。假定深度限制值为5。试按深度优先搜索方法，画出状态空间搜索树。

3.12圆盘问题。设有大小不等的三个圆盘A、B、C套在一根轴上，每个盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，其初始状态S0和目标状态Sg如图3.31所示，请用广度优先搜索和深度优先搜索，求出从S0到Sg的路径。



图3.30阵列图示意




图3.31圆盘问题



3.13对于八数码难题按下式定义估计函数： f(x)=d(x)+h(x)。其中，d(x)为结点x的深度； h(x)是所有棋子偏离目标位置曼哈顿距离


图3.32八数码问题

(棋子偏离目标位置的水平距离和垂直距离之和)，例如图3.32所示的初始状态S0： 8的曼哈顿距离为2； 2的曼哈顿距离为1； 6的曼哈顿距离为1； h(S0)=5。
(1)  用A*搜索法搜索目标，列出头三步搜索中的OPEN、CLOSED表的内容和当前扩展结点的f值。
(2)  画出搜索树和当前扩展结点的f值。

3.14设有如下结构的移动奖牌游戏






BBWWE


其中，B表示黑色奖牌，W表是白色奖牌，E表示空格。游戏的规定走法如下。
(1)  任意一个奖牌可移入相邻的空格，规定其代价为1； 
(2)  任何一个奖牌可相隔1个其他的奖牌跳入空格，其代价为跳过奖牌的数目加1。
游戏要达到的目标是把所有W都移到B的左边。对于这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。你能否判别这个启发函数是否满足求解要求？在求出的搜索树中，对所有结点是否满足单调限制？
3.15图3.33是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其他各城市一次且仅一次，最后回到A城，请找出一条最优线路。

3.16设有如图3.34的与或树，请指出解树，并分别按和代价及最大代价求解树代价； 然后指出最优解树。



图3.33交通费用图




图3.34与或树


3.17设有如图3.35所示的博弈树，其中最下面的数字是假设的估值，试对该博弈树做如下工作。
(1)  计算各结点的倒推值； 
(2)  利用αβ剪枝技术剪去不必要的分支。



图3.35博弈树