第5章-搜索策略gy

第5章 搜索策略 搜索是人工智能中的一个基本问题，（计算机的50%工作）并与推理密切相关，一个智能系统搜索策略的优劣，将直接影响到该系统的性能与推理效率。（NP- (nondeterministic polynomial)旅行商问题：费用、落地时间、旅途与休息时间、路线安排、约束条件等）5.1 搜索的基本概念5.1.1 搜索的含义人工智能所研究的对象大多是属于结构不良（指所需信息不完整）或非结构化（指没有现成的算法可依）的问题。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。因此，只能依靠经验，利用已有知识逐步摸索求解（仁者见仁，智者见智）。像这种根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。另一方面，对那些结构性能较好，理论上有算法可依的问题，如果问题或算法的复杂性较高（如按指数形式增长），由于受计算机在时间和空间上的限制，也无法付诸实用。这就是人们常说的组合爆炸问题。例如，64阶梵塔问题有（所需要的存储空间为3,433,683,820,292,512,484,657,849,089,281 。另一个例子，几百年）状态，仅从空间上来看，这是一个任何计算机都无法存储的问题。可见，理论上有算法的问题实际上不一定可解。像这类问题，也需要采用搜索的方法来进行求解。对于搜索的类型，可根据搜索过程是否使用启发式信息分为盲目搜索和启发式搜索，也可根据问题的表示方式分为状态空间搜索和与/或树搜索。盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性，效率不高，不便于复杂问题的求解。启发式搜索是在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。状态空间搜索是指用状态空间法来求解问题所进行的搜索。与/或树搜索是指用问题归约法来求解问题所进行的搜索。状态空间法和问题归约法是人工智能中最基本的两种问题求解方法，状态空间表示法和与/或树表示法则是人工智能中最基本的两种问题表示方法。5.1.2 状态空间法状态空间法是人工智能中最基本的问题求解方法，它所采用的问题表示方法称为状态空间表示法。状态空间法的基本思想是用“状态”和“操作”来表示并求解问题。1. 状态空间表示法在状态空间表示法中，问题是用“状态”和“操作”来表示的，问题求解过程是用“状态空间”来表示的。(1) 状态状态(State)是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为： Sk=Sk0, Sk1, 在这种表示方式中，当对每一个分量都给以确定的值时，就得到了一个具体的状态。实际上，任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。 (2) 操作操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。(3) 状态空间状态空间(State Space)用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间常用一个三元组 (S, F, G)来表示。其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。2. 状态空间问题求解任何以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法，简称状态空间法。用状态空间法求解问题的基本过程是：首先为问题选择适当的“状态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。上述问题求解过程实际上是一个搜索过程，至于具体的搜索方法我们将在后面详细讨论，这里仅是对状态空间法的一个一般描述。3. 状态空间的例子下面通过具体例子来说明状态空间法。例5.1 二阶梵塔问题。设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。解：设用Sk=Sk0, Sk1表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种（？P32、P31）： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2) S5=(2, 3)S6=(3, 1) S7=(3, 2) S8=(3, 3)AB 1 2 3 1 2 3 1 2 3 S0=(1,1) S4=(2,2) S8=(3,3)图 51 二阶梵塔问题的部分状态其中，初始状态S0和目标状态S4、S8如图5-1所示。问题的初始状态集合为S=S0，目标状态集合为G=S4, S8。操作分别用A(i, j)和B(i, j)表示。其中，A(i, j)表示把金片A从第i号钢针移到j号钢针上；B(i, j)表示把金片B从第i号钢针移到第j号钢针上。共有12种操作，它们分别是：（下图有24条边，下边有12个操作如何对应，重复） A(1, 2) A(1, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2) （P32） B(1, 2) B(1, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2) （P32） 1,1 A(1,3) 2,1 3,1 B(1,2) 2,3 3,2 A(3,2) 3,3 1,3 1,2 2,2 图 52 二阶梵塔的状态空间图根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如图5-2所示。在该图中，从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从初始状态(1, 1)开始，通过使用操作A(1, 3)、B(1, 2)及A(3, 2)，可到达目标状态(2, 2)。5.1.3 问题归约 问题归约是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行分解或变换。当一个问题比较复杂时，如果直接进行求解往往比较困难，此时可通过分解或变换，将它转化为一系列较简单的问题，然后通过对这些较简单问题的求解来实现对原问题的求解。1. 问题的分解与等价变换当把一个问题归约为子问题时，可采用对原问题的分解或变换方法。(1) 分解(“与”)如果一个问题P可以归约为一组子问题P1,P2,Pn，并且只有当所有子问题Pi(i=1, 2, )都有解时原问题P才有解，任何一个子问题Pi(i=1, 2, )无解都会导致原问题P无解，则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等价。(2) 等价变换(“或”)如果一个问题P可以归约为一组子问题P1,P2,Pn，并且子问题Pi(i=1, 2, )中只要有一个有解则原问题P就有解，只有当所有子问题Pi(i=1, 2, )都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的“或”与原问题P等价。在实际问题的归约过程中，有可能需要同时采用变换和分解的方法。无论是分解还是变换，都是要将原问题归约为一系列本原问题。所谓本原问题是指那种不能（或不需要）再进行分解或变换，且可以直接解答的问题。本原问题可以作为终止归约的限制条件。2. 问题归约的与/或树表示把一个原问题归约为一系列本原问题的过程可很方便地用一个与/或树来表示。 P P1 P2 P3图 53 与树(1) 与树把一个原问题分解为若干个子问题可用一个“与树”来表示。例如，设P可以分解为三个子问题P1、P2、P3的与，则P和P1、P2、P3之间的关系可用如图5-4所示的一个“与树”来表示。在该树中，我们用相应的节点表示P、P1、P2、P3；并用三条有向边分别将P和P1、P2、P3连接起来，它表示P1、P2、P3是P的三个子问题。图中还有一条连接三条有向边的小弧线，它表示P1、P2、P3之间是“与”的关系，即节点P为“与”节点。 P P1 P2 P3图 54 或树(2) 或树把一个原问题变换为若干个子问题可用一个“或树”来表示。例如，设P可以变换为三个子问题P1、P2、P3的或，则P和P1、P2、P3之间的关系可用如图5-5所示的一个“或树”来表示。在该树中，我们用相应的节点表示P、P1、P2、P3；并用三条有向边分别将P和P1、P2、P3连接起来，它表示P1、P2、P3是P的三个子问题。图中的有向边不用小弧线连接，它表示P1、P2、P3之间是“或”的关系，即节点P为“或”节点。 P P1 P2 P3P11 P12 P31 P32 P33图 55 与/或树(3) 与/或树如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示。与/或树的例子如图5-6所示。事实上，一般的归约过程是需要用与/或树来表示的。在与/或树中，其根节点对应着原始问题。(4) 端节点与终止节点在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。(5) 可解节点与不可解节点在与/或树中，满足以下三个条件之一的节点为可解节点： 任何终止节点都是可解节点。 对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。 对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。 同样，可用类似的方法定义不可解节点： 不为终止节点的端节点是不可解节点。 对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。 对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。 P t t t 图 56 解树(6) 解树 由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。在解树中一定包含初始节点。例如，在图5-7所给出的与或树中，用粗线表示的子树是一个解树。在该图中，节点P为原始问题节点，用t标出的节点是终止节点。根据可解节点的定义，很容易推出原始问题P为可解节点。 问题归约求解过程实际上就是生成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，对于与/或树的搜索将在后面详细讨论。3. 问题归约的例子 1 2 3 1 2 3图 57 三阶梵塔问题例5.4 三阶梵塔问题。设有A、B、C三个金片及三根钢针，三个金片按自上而下从小到大的顺序穿在1号钢针上，要求把它们全部移到3号钢针上，而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图5-8所示。解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组 (i, j, k) 对应 （C大盘片，B中盘片，A小盘片）表示问题在任一时刻的状态，用“”表示状态的转换。在上述三元组中，i代表金片C所在的钢针号，j代表金片B所在的钢针号，k代表金片A所在的钢针号。利用问题归约方法，原问题可分解为以下三个子问题：(1) 把金片A及B移到2号钢针上的双金片移动问题。即 (1, 1, 1)(1, 2, 2)（搬走一叠）(2) 把金片C移到3号钢针上的单金片移动问题。即 (1, 2, 2)(3, 2, 2)（调整最大的盘子）(3) 把金片A及B移到3号钢针的双金片移动问题。即(3, 2, 2) (3, 3, 3)（其余盘子调位）其中，子问题(1)和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题(2)是本原问题，它已不需要再分解。 (1,1,1)(3,3,3) (1,1,1)(1,2,2) (1,2,2)(3,2,2) (3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,1,3)(1,2,3) (1,2,3)(1,2,2) (3,2,2)(3,2,1) (3,2,1)(3,3,1) (3,3,1)(3,3,3)图 58 三阶梵塔问题的与或树三阶梵塔问题的分解过程可用如图5-9所示的与/或树来表示。在该与/或树中，有7个终止节点，它们分别对应着7个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：(1, 1, 1)(1, 1, 3) (1, 1, 3)(1, 2, 3) (1, 2, 3)(1, 2, 2)(1, 2, 2)(3, 2, 2) (3, 2, 2)(3, 2, 1) (3, 2, 1)(3, 3, 1) (3, 3, 1)(3, 3, 3)5.2 状态空间的盲目搜索 状态空间的搜索策略可分为盲目搜索和启发式搜索两大类。尽管盲目搜索的性能不如启发式搜索，但由于启发式搜索需要抽取与问题本身有关的特征信息，而这种特征信息的抽取往往又比较困难，因此盲目搜索仍不失为一种有用的搜索策略。本节主要讨论状态空间的盲目搜索策略，对状态空间的启发式搜索放到下一节讨论。5.2.1 一般图搜索过程当用状态空间法解决问题时，有以下两个方面的因素需要考虑：一方面，对大问题计算机无法保存其全部状态空间；另一方面，对具体问题与解有关的状态空间一般仅是全部状态空间的一部分。因此，在问题求解过程中，没有必要生成和保存该问题的全部状态空间，只要能够生成和保存与解有关的那部分状态空间即可。解决这一问题的方法是采用状态空间搜索技术。对状态空间的搜索，由于问题的状态空间可用一个有向图来表示，因此状态空间搜索实际上就是一个对有向图的搜索。从图搜索的角度来看，状态空间搜索的基本思想是：先把问题的初始状态作为当前扩展节点对其进行扩展(树的生长)，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。上面给出的仅是状态空间搜索的基本思想，若要讨论状态空间搜索的一般算法，还需要设立Open表和Closed表这样两个数据结构。其中，Open表用于存放刚生成的节点，由于这些节点还没有进行扩展，因此Open表也称为未扩展节点表（相当于可用规则库）；Closed表用于存放已经扩展或将要扩展的节点，因此Closed表也称为已扩展节点表（相当于综合事实库）。此外，对问题的初始状态，搜索过程得到的搜索图，当前扩展节点新生成的子节点集，也都需要用相应的符号来表示。假设用S0表示问题的初始状态，G表示搜索过程所得到的搜索图，M表示当前扩展节点新生成的且不为自己先辈的子节点集（已经搜索过的节点，比如：机器人移动盒子，从a点b点,又从b点回到a点）。在上述假设下，状态空间的一般图搜索过程为：(1) 把初始节点S0放入Open表，并建立目前仅包含S0的图G；(2) 检查Open表是否为空，若为空，则问题无解，失败退出；(3) Open表的第一个节点取出放入Closed表，并记该节点为节点n；(4) 考察节点n是否为目标节点。若是则得到了问题的解，成功推出；(5) （通过操作）扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中。(6) 针对M中子节点的不同情况，分别作如下处理： 对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入Open表。 对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。 对于那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（又一次找到该结点的搜索方案，与前面的方案进行比较，选择代价最小的方案）(7) 按某种策略对Open表中的节点进行排序（相当于冲突消解）。(8) 转第(2)步。对上述搜索过程需作如下几点说明：(1) 上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对Open表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面（如何实现？），而深度优先搜索则把后生成的子节点排在前面（如何实现？）。(2) 在第(5)步对节点n扩展后，生成并记入M的子节点有以下三种情况： 该子节点原来从未被任何节点生成过，由n第一次生成； 该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成； 该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被n再次生成。 以上三种情况是对一般图搜索算法而言的。对于盲目搜索，由于其状态空间是树状结构，因此不会出现后两种情况，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。（因为是按预先设定好的线路进行，因此这种全搜索不会存在后两种情况），但是启发式搜索则不同。(3) 在第(6)步针对M中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由初始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。 S0 1 6 2 3 4 5图 59 扩展节点1以前的搜索图如果发生第种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由初始节点到该节点的路径上的代价。例如，设图5-10为搜索过程所形成的搜索图，其中实心圆点在Closed表中，代表已扩展了的节点；空心圆点在Open表中，代表未扩展的节点。假设现在要扩展节点1，并且只生成单一的后继节点2。但目前节点2已有父节点3，即节点2在先前扩展节点3时已经被生成了，现在又作为节点1的后继节点被再次生成。（相当于又搜索到一条生成路径）这时，为了确定哪一个节点作为节点2的父节点，需要计算路径代价。假设每条有向边的代价都为1，则从S0经节点1到节点2的代价为2，而从S0经节点3到节点2的代价为4。显然，这两条路经相比，从S0经节点1到节点2的代价较小。因此，应修改节点2指向父节点的指针，让它指向节点1，即把节点2的父节点由节点3改为节点1。另外，节点4既是节点2的后继节点，又是节点6的后继节点。在节点2指向父节点的指针被修改以前，从S0经节点2到节点4的代价为5，而从S0经节点6到节点4的代价为4，因此节点4以节点6为父节点。但是，当节点2指向父节点的指针被修改以后，从S0经节点2到节点4的代价仅为3。因此，节点4不能再以节点6为父节点，而应该以节点2为父节点，即需要修改节点4指向父节点的指针。此时的搜索图如图5-11所示。（生成痕迹保留，返回指针调整） 1 6 2 3 4 5图 5-11 扩展节点1后的搜索图(4) 在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树（生成树的生成过程就是为了得到搜索树，搜索树中不保留生成过程，因此，只有指向其父节点的指针。）。(5) 在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。(6) 如果搜索过程终止在第(2)步，即没有达到目标，且Open表中已无可供扩展的节点，则失败结束。5.2.2 广度优先搜索广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。这种搜索策略的搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。广度优先搜索算法如下：（用QUEUE）(1) 把初始节点S0放入Open表中；(2) 如果Open表为空，则问题无解，失败退出；(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；(5) 若节点n不可扩展，则转第(2)步；(6) 扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。 S0 Sg1 2 38 47 6 52 8 31 47 6 5 图 510 八数码难题例5.5 八数码难题。在33的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如图5-12所示。可以使用的操作有：（定义距离函数，评价每张与目标的距离）空格左移，空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。解：应用广度优先搜索策略，可以在第四级得到解，其搜索树如图5-13所示。由图5-13可以看出，解的路径是 S0381626 广度优先搜索是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。这些都是广度优先搜索的优点。广度优先搜索的主要缺点是盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。28314765 左 上 右 下28323283283141841416476576576575 上 下8328321471476565图 511 八数码难题的广度优先搜索5.2.3 深度优先搜索（用STACK）深度优先搜索是一种后生成的节点先扩展的策略。这种搜索策略的搜索过程是：从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。Open表是一种栈结构，最先进入的节点排在最后面（压在最下面），最后进入的节点排在最前面。深度优先搜索算法如下：(1) 把初始节点S0放入Open表中；(2) 如果Open表为空，则问题无解 ，失败退出；(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；（栈顶元素）28314765 左 上 右 下2832328328328314184141641647657657657575283283164164757528316754图 5124 八数码难题的深度优先搜索(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；(5) 若节点n不可扩展，则转第(2)步；(6) 扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。从以上过程可以看出，深度优先搜索和广度优先搜索的唯一区别是节点在Open表中的排列顺序不同。广度优先搜索是把最新生成的节点放在Open表的尾部（用队列实现），而宽度优先搜索则是把最新生成的节点放在Open表的首部（用堆栈实现）。例5.6 八数码难题。要求用深度优先搜索策略寻找从初始状态到目标状态的解路径。解：应用广度优先搜索策略，其部分搜索树如图5-14所示。在图5-14中，由于问题的目标尚未达到，因此搜索还需要继续进行下去。从深度优先搜索的算法可以看出，搜索一旦进入某个分支，就将沿着这个分支一直进行下去，如果目标恰好在这个分支上，则它可以很快找到解。但是，如果目标不在这个分支上，且该分支又是一个无穷分支，则搜索过程就不可能找到解。因此，深度优先搜索是一种不完备策略，即使问题有解，它也不一定能够找到解。此外，即使在能找到解的情况下，按深度优先找到的解也不一定是路径最短的解。5.2.4 有界深度优先搜索为了弥补上述两种策略的缺点，一种较好的折衷办法是在深度优先策略中引入深度限制，即采用有界深度优先搜索。有界深度优先搜索过程总体上按深度优先策略进行，但对搜索深度需要给出一个深度限制dm，当搜索深度达到了dm，但还没有找到目标时，就停止该分支的搜索，换到另外一个分支进行搜索。当给定的深度限制为dm时，有界深度优先搜索算法如下：(1) 把初始节点S0放入Open表中，置S0的深度d(S0)=0；(2) 如果Open表为空，则问题无解 ，失败退出；(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；(5) 如果节点n的深度d(n)=dm，则转第(2)步；(6)若节点n不可扩展，则转第(2)步；(7) 扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。例5.7 八数码难题。设深度限制dm=4，要求用有界深度优先搜索策略寻找从初始状态到目标状态的解路径。5.3 状态空间的启发式搜索 前面讨论的各种搜索方法都没有用到问题本身的特性信息，只是按照事先设定的线路进行搜索，具有较大的盲目性。事实上，如果能够利用搜索过程所得到的问题自身的一些特性信息来指导搜索过程，则对搜索将是十分有益的。这种利用问题自身的特性信息来引导搜索过程的搜索方法称为启发式搜索。由于启发式搜索方法具有较强的针对性，因此，可以缩小搜索范围，提高搜索效率。5.3.1 启发性信息和估价函数 启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。因此，在讨论启发式搜索方法之前需要先给出启发性信息与估价函数的概念。1. 启发性信息启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种： 有效地帮助确定扩展节点的信息； 有效的帮助决定哪些后继节点应被生成的信息； 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。2. 估价函数用来估计节点重要性的函数称为估价函数。估价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为： f(n)=g(n)+h(n)其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。对g(n)的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0，得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g(n)的值。对h(n)的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h(n)为启发函数。例5.9 八数码难题。设问题的初始状态S0和目标状态Sg如图5-12所示，且估价函数为 f(n)=d(n)+W(n)其中，d(n)表示节点n在搜索树中的深度；W(n)表示节点n中“不在位”的数码个数。请计算初始状态S0的估价函数值f(S0)。解：在本例的估价函数中，取g(n)=d(n)，h(n)=W(n)。它说明是用从S0到n的路径上的单位代价表示实际代价，用n中“不在位”的数码个数作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。对初始节点S0，由于d(S0)=0，W(S0)=3，因此有 f(S0)=0+3=3这个例子仅是为了说明估价函数的含义及估价函数值的计算。在问题搜索过程中，除了需要计算初始节点的估价函数之外，更多的是要计算新生成节点的估价函数值。5.3.2 A算法在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。1. 全局择优搜索在全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：(1) 把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；(2) 如果Open表为空，则问题无解 ，失败退出；(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；(4) 考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；(5) 若节点n不可扩展，则转第(2)步；(6) 扩展节点n，生成其子节点ni(i=1, 2, )，计算每一个子节点的估价值f(ni)(i=1, 2, )，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；(7) 根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；(8) 转第(2)步。 由于上述算法的第(7)步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第(3)步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。对上述算法进一步分析还可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。283147654 4 5 5 28323S1283283141841416476576576575 5 6 4 683283S2232321471418418476565765765 4 S312384765 4 6123Sg1238 478476565图 518 八数码难题的全局择优搜索树例5.10 八数码难题。设问题的初始状态S0和目标状态Sg如图5-12所示，估价函数与例5.9相同。请用全局择优搜索解决该问题。解：这个问题的全局择优搜索树如图5-18所示。在图5-18中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数值的计算为：f(S2)=d(S2)+W(S2) =2+2=4从图5-18还可以看出，该问题的解为：S0S1S2S3Sg2. 局部择优搜索在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：(1) 把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；(2) 如果Open表为空，则问题无解 ，失败退出；(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；(4) 考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；(5) 若节点n不可扩展，则转第(2)步；(6) 扩展节点n，生成其子节点ni(i=1, 2, )，计算每一个子节点的估价值f(ni)(i=1, 2, )，并按估价值从小到大的顺序依次放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。 由于上述算法的第(6)步仅是把刚生成的子节点按其估价函数值从小到大放入Open表的首部，这样在算法第(3)步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的深度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。 5.4 与/或树的盲目搜索前面曾经讨论过与/或树的概念和问题的与/或树表示。与/或树表示下的问题求解过程与状态空间法类似，也是通过搜索来实现对问题求解的。与/或树的搜索策略也分为盲目搜索和启发式搜索两大类。本节仅讨论盲目搜索策略，启发式搜索策略放到下一节讨论。5.4.1 与/或树的一般搜索与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：(1) 把原始问题作为初始节点S0，并把它作为当前节点；(2) 应用分解或等价变换操作对当前节点进行扩展；(3) 为每个子节点设置指向父节点的指针；(4) 选择合适的子节点作为当前节点，反复执行第(2)步和第(3)步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。上述搜索过程将形成一棵与/或树，这种由搜索过程形成的与/或树称为搜索树。当搜索成功时，经可解标记过程标识的由初始节点及其下属的可解节点构成的子树称为解树。搜索过程中的可解标识过程与不可解标记过程都是自下而上进行的，即由子节点的可解性确定父节点、祖父节点的可解性；由子节点的不可解性确定父节点、祖父节点的不可解性。在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。这种由可解子节点来确定其父节点、祖父节点为可解节点的过程称为可解标记过程；由不可解子节点来确定其父节点、祖父节点为不可解节点的过程称为不可解标记过程。由于与/或树搜索的目标是寻找解树，因此，如果搜索过程确定某个节点为可解节点，则其不可解的后裔节点就可从搜索树中删去；同样，如果搜索过程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。5.4.2 与/或树的广度优先搜索与/或树的广度优先搜索与状态空间的广度优先搜索类似，只是在搜索过程中需要多次调用可解标识过程或不可解标识过程，其搜索算法如下：(1) 把初始节点S0放入Open表中；(2) 把Open表的第一个节点取出放入Closed表，并记该节点为n；(3) 如果节点n可扩展，则做下列工作： 扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针； 考察这些子节点中有否终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解解节点进行标记。如果初始节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点。 转第(2)步。(4) 如果节点n不可扩展，则作下列工作： 标记节点n为不可解节点； 应用不可解标记过程对节点n的先辈中不可解解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点。 1 2 3A 4 t1 5t2 B t3 C图 521 与/或树的广度优先搜索 转第(2)步。例5.13 设有如图5-21所示的与/或树，节点按图中所标注的顺序号进行扩展，其中标有t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点。搜索过程为：(1) 先扩展1号节点，生成2号节点和3号节点，由于这两个子节点都不是终止节点，因此接着扩展2号节点，此时Open表中只剩下3号节点。(2) 扩展2号节点，生成A节点和4号节点。由于这两个子节点均不是终止节点，因此接着扩展3号节点，此时Open表中剩下A节点和4号节点。(3) 扩展3号节点，生成t1节点和5号节点。由于t1为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于t1的父节点是一个与节点，因此不能确定3号节点是否可解。下一步扩展A节点，此时Open表中剩下4号节点和5号节点。(4) 扩展节点A，由于A是端节点，因此不可扩展。调用不可解标记过程，由于2号节点是或节点， 因此不能确定2号节点是不可解节点。下一步扩展4号节点，此时Open表中仅剩下5号节点。(5) 扩展4号节点，生成t2节点和B节点。由于t2为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于4号节点是一个或节点，因此可标记它为可解节点。继续向上，可标记2号节点为可解节点，但不能标记1号节点为可解节点。下一步扩展5号节点，此时Open表为空。(6) 扩展5号节点，生成t3节点和C节点。由于t3为终止节点，则标记它为可解节点，并应用可解标记过程，对其先辈中的可解节点进行标记，由于5号节点是一个或节点，因此可标记它为可解节点。继续向上，可标记3号节点为可解节点。由于2号节点和3号节点都为可解节点，因此可标记1号节点为可解节点。(7) 搜索成功，得到由1、2、3、4、5号节点及t1、t2、t3节点构成的解树。该解树如图5-21中的出现所示。5.4.3 与/或树的深度优先搜索与/或树的深度优先搜索和与/或树的广度优先搜索过程基本相同，其主要区别在于Open表中节点的排列顺序不同。在扩展节点时，与/或树的深度优先搜索过程总是把刚生成的节点放在Open表的首部。同状态空间的深度优先搜索类似，与/或树的深度优先搜索也可以带有深度限制dm，其搜索算法如下：(1) 把初始节点S0放入Open表中；(2) 把Open表的第一个节点取出放入Closed表，并记该节点为n；(3) 如果节点n的深度等于dm，则转第(5)步的第点；(4) 如果节点n可扩展，则做下列工作： 扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针； 考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，