第二章3问题规约要点解析.ppt

问题求解的基本方法问题规约 № * 一 问题规约 概念： 把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解 问题的解答就由子问题的解答联合构成 问题归约可以递归地进行，直到把问题变换为本原问题的集合 本原问题就是不可或不需再通过变换化简的原子问题 № * 问题归约的描述 SP = ( S , O ) S--在问题求解（即有哪些信誉好的足球投注网站）过程中所有可达的合法状态 构成的集合 O--操作算子的集合，操作算子的执行导致状态的变迁 问题状态可以通过子问题状态的联合加以表示 操作算子的执行则导致问题的变换 № * 变换可区分为以下三种情况： （1） 状态变迁 导致问题从上一状态变迁到下一状态，这就是一般图有哪些信誉好的足球投注网站技术中操作算子的作用 （2） 问题分解 分解问题为需同时处理的子问题，但不改变问题状态 （3） 基于状态变迁的问题分解 先导致状态变迁，再实现问题分解，实际上 就是前二个操作的联合执行 № * 问题归约的例子：字母重写问题 　初始状态为字母列表（A B C）， 目标状态为只包含字母x、y、z的字母列表 操作算子分为两类： （1） 面向问题分解，由单一操作算子Split(n)实 现，n是当前问题（子问题）状态节点 （2） 面向状态变迁，设计为字母列表的重写规则： № * (A) ? (D F), 　　(A) ? (G)，　　(B C) ? (E)，　　(B) ? (H)，　 (C) ? (I J K)，　(D) ? (x)，　　(E) ? (y z)，　　 (F) ? (x y z)，　　(G) ? (z)，　　　 (H) ? (x x)，　　(I) ? (y y)，　　 (J) ? (z z)，　　(K) ? (x z)。 № * 求解重写问题的与或图 № * (A B C) ?(A)(B C), (A B C) ?(A)(B)(C), (A)?(D) (F), 　(A)?(G)，(B C)?(E) ，(B)?(H)，(C)?(I)(J)(K) 。 № * 紧凑的与或图 № * 结论 在字母重写问题的规约过程中，各子问题相互独立，所以子问题的进一步归约和本原问题的求解无交互作用，可按任意次序进行 然而，对于其他复杂的问题，还需要考虑各子问题求解的次序 № * 练习 设某字母重写问题的初始状态为（C, B, Z），目标状态是只含字母M的列表，给定以下重写规则，　　　　　C ? (D, L)　　　　　C ?(B, M)　　　　　B ? (M, M)　　　　　Z ?(B, B, M)画出相应于该重写问题的与或图，指出解图并给出解答。 № * 与或图去掉自节点(c)到节点(D)和(L)的连接符的其余部分就是解图 解答为(M,M,M,M,M,M,M,M,M,M) № * 举例说明 （1）梵塔问题 № * 问题：三个柱子标记为1、2、3 尺寸为小、中、大的三个圆盘标记为A、B、C 初始状态下三个盘按A、B、C顺序堆放在1号柱子上 目标状态下三个盘以同样次序顺序堆放在3号柱子上 规则： 每次只能搬一个盘子，且较大盘不能压放在较小盘之上 № * 求解： 三元素列表作为数据结构描述问题状态，三个元素依次指示盘子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） 第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), 现在所有子问题均为本原问题 № * （2）符号积分问题 　 ∫（sin3x + x4/(x2 + 1)）dx　　=∫sin3xdx + ∫(x4/(x2 + 1))dx　　=∫-(1 - cos2x)dcosx + ∫(x2 - 1 + 1/(1 + x2))dx　　=(∫-dcosx + cos2xdcosx) + (∫x2dx - ∫dx + ∫(1/(1 + x2))dx）　　= -cosx + cos3x/3 + x3/3 - x + arctgx 归约为若干本原积分问题——可利用积分表直接求出原函数 № * (3)分子结构识别问题