第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为可解节点。 问题归约求解过程实际上就是生成解树，即证明原始节点是可解节点的过
