人工智能及应用_ch5_3.ppt

1、与或树搜索,问题归约 与或树搜索,问题归约,问题归约的基本思想：将复杂问题通过分解和变换转化为一系列较为简单的问题，然后通过对这些较简单的问题求解来实现对原问题的求解。,问题的分解,如果一个问题P可以归约为一组子问题P1， P2，。 ，Pn，并且只有所有子问题都有解时原问题才有解，任何一个子问题无解都会导致原问题无解，则称此种归约为问题的分解。,等价变换,如果一个问题P可以归约为一组子问题P1， P2，。 ，Pn，并且只要有一个子问题有解时原问题就有解，只有当所有子问题都无解时才会导致原问题无解，则称此种归约为问题的等价变换。,本原问题,那种不能（或不需要）再进行分解或变换，且可直接解答的子问

2、题称为本原问题。 问题归约就是通过分解和变换将原问题化为一系列本原问题。,问题归约的与或树,原问题分解为若干子问题可以用与树表示； 原问题变换为若干子问题可以用或树表示。,P,P1,P2,P3,P,P1,P2,P3,与树,或树,问题归约的与或树,如果一个问题既需要通过分解，又需要变换才能得到本原问题时，归约过程需要用与或树表示。,P,P1,P2,P3,P4,P5,P6,端结点与终止结点,在与或树中，没有子结点的结点为端结点。 本原问题所对应的结点称为终止结点。,终止结点,端结点,？,可解结点,在与或树中，满足以下三个条件之一的结点为可解结点： 任何终止结点都是可解结点。 对或结点，当其子结点至

3、少有一个为可解结点时，则该结点就是可解结点。 对与结点，只有当其所有子结点全部为可解结点时，该与结点才是可解结点。,不可解结点,在与或树中，满足以下三个条件之一的结点为不可解结点： 不为终止结点的端结点是不可解结点。 对或结点，只有当其所有子结点全部为不可解结点时，该或结点是不可解结点。 对与结点，当其子结点至少有一个为不可解结点时，则该结点就是不可解结点。,解树,由可解结点构成，并且由这些可解结点可以推出初始结点（一般对应着原始问题）为可解结点的子树为解树。 问题的归约求解过程实际上就是生成解树的过程。,归约示例,例：三阶梵塔问题。设有三根针，编号分别是1号、2号和3号。在初始时，1号针上穿

4、有A、B、C三个金片，要求把这三个金片全部移到3号针上，规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。,B,A,C,1,2,3,归约示例,解：设问题的状态描述为 (x,y,z) x-A在的针号 y-B在的针号 z-C在的针号,归约示例,将A及B移到2号针的问题表示为： (1,1,1)(1,2,2) 将C移到3号针的问题表示为： (1,2,2)(3,2,2) 把A、B移到3号针的问题表示为： (3,2,2)(3,3,3),归约示例,(1,1,1)(3,3,3),(1,2,2)(3,2,2),(3,2,2)(3,3,3),(1,1,1)(1,2,2),(1,1,1)(1,1,3),

5、(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),与或树的一般搜索,把原始问题作为初始结点S0，并把它作为当前结点； 应用分解或等价变换操作对当前结点进行扩展； 为每个子结点设置父结点。 选择合适的子结点作为当前结点，反复执行(2)和(3)步，在此期间需要多次调用可解标记或不可解标记过程，直到初始结点被标记为可解结点或不可解结点为止。,与或树的广度优先搜索,把初始结点S0放入OPEN表中； 把OPEN表中的第一个结点取出放入CLOSED表，并记该结点为n； 如果结点n可扩展，则做下列工作： 扩展

6、结点n，将子结点放入OPEN表尾部，并为每个子结点设置父结点； 考察这些结点是否有终止结点。若有，则标记这些结点为可解结点，并对其父结点及先辈结点中的可解结点进行标记。如初始结点S0能够被标记为可解结点，得到解树成功退出；若不能，从OPEN表中删去具有可解先辈的结点； 转2步,与或树的广度优先搜索,如果结点n不可扩展，则做下列工作： 标记结点n为不可解结点； 对结点n的先辈中不可解结点进行标记。如初始结点S0能够被标记为不可解结点，搜索失败，退出；若不能，从OPEN表中删去具有不可解先辈的结点； 转2步,示例,1,5,4,2,3,t2,t3,t1,B,C,A,解树的代价,解树的代价按如下规则计算： 若n为终止结点，则其代价h(n)=0； 若n为或结点，则其代价h(n)=minc(n,ni)+h(ni) 若n为与结点，则其代价h(n)=maxc(n,ni)+h(ni) 若n为端结点，但不是终止结点，则h(n)=； 根结点的代价为解树的代价。,希望树,为了找到最优解树，搜索时应该选择最有希望成为最优解树一部分的结点进行扩展。由于这些结点及其父结点所构成的与或树最有可能成为最优解树的一部分，故称为希望