第5章搜索策略.doc

第5章 搜索策略搜索是人工智能中的一个基本问题，（计算机的50%工作）并与推理密切相关, 一个智能系统搜索策略的优劣，将直接影响到该系统的性能与推理效率NP- （nondeterministic polynomial）旅行商问题：费用、落地时间、旅途与休息时间、 路线安排、约束条件等）5.1搜索的基本概念5. 1.1搜索的含义人工智能所研究的对象大多是属于结构不良（指所需信息不完整）或非结构化 （指没有现成的算法可依）的问题对于这些问题，一般很难获得其全部信息，更 没有现成的算法可供求解使用因此，只能依靠经验，利用已有知识逐步摸索求解 （仁者见仁，智者见智）像这种根据问题的实际情况，不断寻找可利用知识，从 而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索另一方面，对那些结构性能较好，理论上有算法可依的问题，如果问题或算法 的复杂性较高（如按指数形式增长），由于受计算机在时间和空间上的限制，也无 法付诸实用这就是人们常说的组合爆炸问题例如，64阶梵塔问题有雪（所需 要的存储空间为 3, 433, 683, 820, 292, 512, 484, 657, 849, 089, 281。

另一个例子 2“ , 几百年）状态，仅从空间上来看，这是一个任何计算机都无法存储的问题可见，理论上有算法的问题实际上不一定可解像这类问题，也需要采用搜索的方法来进行求解对于搜索的类型，可根据搜索过程是否使用启发式信息分为盲目搜索和启发 式搜索，也可根据问题的表示方式分为状态空间搜索和与/或树搜索盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改 变控制策略由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性， 因此这种搜索具有盲目性，效率不高，不便于复杂问题的求解启发式搜索是在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最 有希望的方向前进，加速问题的求解过程并找到最优解状态空间搜索是指用状态空间法来求解问题所进行的搜索与/或树搜索是指用问题归约法来求解问题所进行的搜索状态空间法和问题归约法是人工智能中最基本的两种问题求解方法，状态空间 表示法和与/或树表示法则是人工智能中最基本的两种问题表示方法5.1. 2状态空间法状态空间法是人工智能中最基本的问题求解方法，它所釆用的问题表示方法称 为状态空间表示法状态空间法的基本思想是用“状态”和“操作”来表示并求解 问题。

1. 状态空间表示法在状态空间表示法中，问题是用“状态”和“操作”来表示的，问题求解过程 是用“状态空间”来表示的1)状态状态(State)是表示问题求解过程中每一步问题状况的数据结构，它可形式地 表示为：Sk={SkO, Ski, ・・・}在这种表示方式中，当对每一个分量都给以确定的值时，就得到了一个具体的 状态实际上，任何一种类型的数据结构都可以用来描述状态，只要它有利于问题 求解，就可以选用2)操作操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的手 段当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化, 从而使问题从一个具体状态变为另一个具体状态操作可以是一个机械步 运算，一条规则或一个过程操作可理解为状态集合上的一个函数，它描述了状态 之间的关系3)状态空间状态空间(State Space)用来描述一个问题的全部状态以及这些状态之间的相 互关系状态空间常用一个三元组(S, F, G)来表示其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态 的集合状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图在状态 空间图中，节点表示问题的状态，有向边表示操作。

2. 状态空间问题求解任何以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法，简称状态空间法用状态空间法求解问题的基本过程是：首先为问题选择适当的“状 态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操 作”，递增地建立起操作序列，直到达到目标状态为止；最后，由初始状态到目标 状态所使用的算符序列就是该问题的一个解上述问题求解过程实际上是一个搜索过程，至于具体的搜索方法我们将在后面 详细讨论，这里仅是对状态空间法的一个一般描述3. 状态空间的例子F面通过具体例子来说明状态空间法例5.1二阶梵塔问题设有三根钢针，它们的编号分别是1号、2号和3号在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面要求 把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻 都不能使大的位于小的上面解：设用Sk= {SkO, Ski}表示问题的状态，其中，SkO表示金片A所在的钢针 号，Ski表示金片B所在的钢针号全部可能的问题状态共有以下9种（？ P32、P31)：S0=(l, 1) Sl=(l, 2) S2=(l, 3) S3= (2, 1) S4二⑵ 2) S5=(2, 3)S6= (3, 1) S7= (3, 2) S8=(3, 3)其中，初始状态so和目标 状态S4、S8如图5_1所不。

A问题的初始状态集合□B 「 —为S={SO},目标状态集合 U ——三 &1 2 3 1 2 3 1 2 3为G二{S4, S8}o操作分别S0=(l, 1) S4= (2, 2) S8= (3, 3)用A(i, j)和B(i, j)表示其中，A(i, j)表示把金片图5-1二阶梵塔问题的部分状态A从第i号钢针移到j号钢针上；B(i, j)表示把金片B从第i号钢针移到第j号 钢针上共有12种操作，它们分别是：(下图有24条边，下边有12个操作如何对 应，重复)A(l, 2) A(l, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2) (P32)B(l, 2) B(l, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2) (P32)根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如图5-2所示在该图中，从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解其 中，最短的路径长度是3,它由3个操作组成例如，从初始状态(1, 1)开始，通 过使用操作A(l, 3)、B(l, 2)及A(3, 2),可到达目标状态(2, 2) o5.1. 3问题归约问题归约是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行分解或变换。

当一个问题比较复杂时，如果直接进行求解往往比较困难，此时 可通过分解或变换，将它转化为一系列较简单的问题，然后通过对这些较简单问题 的求解来实现对原问题的求解1 •问题的分解与等价变换当把一个问题归约为子问题时，可采用对原问题的分解或变换方法⑴分解(“与”)如果一个问题P可以归约为一组子问题Pl, P2,…,Pn,并且只有当所有子问题 Pi(i=l, 2,・・・)都有解时原问题P才有解，任何一个子问题Pi(i=l, 2,…)无解 都会导致原问题P无解，则称此种归约为问题的分解即分解所得到的子问题的 “与”与原问题P等价2)等价变换(“或”)如果一个问题P可以归约为一组子问题Pl,P2,-,Pn,并且子问题Pi(i=l, 2,…)中只要有一个有解则原问题P就有解，只有当所有子问题Pi (1=1, 2,…) 都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换即变换所得 到的子问题的“或”与原问题P等价在实际问题的归约过程中，有可能需要同时采用变换和分解的方法无论是分 解还是变换，都是要将原问题归约为一系列本原问题所谓本原问题是指那种不能(或不需要)再进行分解或变换，且可以直接解答的问题。

本原问题可以作为终止归约的限制条件2•问题归约的与/或树表示把一个原问题归约为一系列本原问题的过程可很方便地用一个与/或树来表POOOOP1P2P3图5-3与树(1)与树把一个原问题分解为若干个子问题可用一个“与 树”来表示例如，设P可以分解为三个子问题P1、 P2、P3的与，则P和Pl、P2、P3之间的关系可用如图 5-4所示的一个“与树”来表示在该树中，我们用相 应的节点表示P、Pl、P2、P3；并用三条有向边分别将P和Pl、P2、P3连接起来，它表示Pl、P2、P3是P的三个子问题图中还有一条 连接三条有向边的小弧线，它表示Pl、P2、P3之间是“与”的关系，即节点P为“与”节点POPl P2 P3图5-4或树(2)或树把一个原问题变换为若干个子问题可用一个“或 树”来表示例如，设P可以变换为三个子问题P1、 P2、P3的或 则P和Pl、P2、P3之间的关系可用如图 5-5所示的一个“或树”来表示在该树中，我们用相 应的节点表示P、Pl、P2、P3；并用三条有向边分别将P和Pl、P2、P3连接起来，它表示Pl、P2、P3是P的三个子问题图中的有向边不用小弧线连接，它表示Pl、P2、P3之间是“或”的关系，即节点P为“或”节 点。

3)与/或树如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可0 oP12 P31 P32P33用一个“与/或树”来表示与/或树的例子如P11图5-5与/或树图5-6所示事实上，一般的归约过程是需要 用与/或树来表示的在与/或树中，其根节点 对应着原始问题4)端节点与终止节点在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终 止节点可见，终止节点一定是端节点，但端节点却不一定是终止节点5)可解节点与不可解节点在与/或树中，满足以下三个条件之一的节点为可解节点：① 任何终止节点都是可解节点② 对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点③ 对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节同样，可用类似的方法定义不可解节点:① 不为终止节点的端节点是不可解节点② 对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节 点③ 对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可 解节点6)解树由可解节点构成,并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节点的子树为解树。

在解树中一定包含初始节点例如，在图5-7所给岀的与或树中，用粗线表示的子树是一个解树在该图中，节点P为原始问题节点，用to标出的节点是终止节点根据可解节点的定义,很容易推出原始问题P为可解节点问题归约求解过程实际上就是生成解图5-6解树树，即证明原始节点是可解节点的过程这一过程涉及到搜索的问题，对于与/或树的搜索将在后面详细讨论3 •问题归约的例子例5. 4三阶梵塔问题设有A、B、C三个金片及三根钢针，三个金片按自 上而下从小到大的顺序穿在1号钢针 上，要求把它们全部移到3号钢针上,而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面,图5-7三阶梵塔问题如图5-8所示o解：这个问题也可用状态空间法来解,不过本例主要用它来说明如何用归约法来解决问题为了能够解决这一问题，首先需要定义该问题的形式化表示方法设用三元组（i, j, k）对应 （C大盘片。