算法第九章详解.ppt

1 第九章分支 限界法 2 9 1一般方法9 1 1LC 检索9 1 215 谜9 1 3LC 检索的抽象化控制9 1 4LC 检索的特性9 1 5分支 限界算法 3 9 1一般方法 分支 限界法类似于回溯法 也是一种在问题的解空间树上搜索问题解的算法 但二者搜索方式不同 以四皇后问题的解空间树为例 1 4 皇后问题的解空间树 x1 1 x2 2 结点编号 按深度优先次序 5 回溯法 使用限界函数的深度优先结点生成方法当前的E 结点一旦生成一个新儿子C C就变成新的E 结点 6 用回溯法解决四皇后问题 回溯法一共处理了16个结点 到达一个答案结点 结点31 7 分支 限界法 分支 限界法生成当前E 结点全部儿子之后 才从活结点表中选一个活结点作为新的E 结点 使用限界函数帮助避免生成不包含答案结点子树的状态空间 8 9 1一般方法 根据对状态空间树中结点检索次序的不同 分支 限界可以采用不同的活结点表 FIFO检索 活结点采用一张先进先出表 队列 LIFO检索 活结点采用一张后进先出表 堆栈 9 例9 1FIFO分枝限界法检索四皇后问题的状态空间树 4 皇后问题的状态空间树 图8 2 P195 1 2 18 34 50 3 8 13 19 24 29 35 40 45 51 56 61 活结点表 10 3 8 13 19 24 29 35 40 45 51 56 61 B 9 11 14 16 B B 30 32 B B 36 38 52 54 57 59 B B B 15 B 31 B B 答案节点 分枝限界法一共处理了31个节点 回溯法一共处理了16个节点 P198图8 6 11 9 1 1LC 检索 leastcost LC 检索的问题 只有这两种活结点表吗 队列实现的活结点表FIFO堆栈实现的活结点表LIFO对下一个E 节点的选择规则相当死板 在某种意义上是盲目的 对于可能快速检索到答案结点的结点没有给出任何优先权 12 B 在上例中 尽管在生成结点30后 该结点只要走一步就可到达答案结点31 但死板的FIFO规则却要求先扩展已生成的其他活结点 能否根据某个优先级 使得结点31比其他活结点具有更高的优先级 从而被快速得到 13 9 1 1LC 检索 leastcost 解决 对活结点使用一个 有智力的 排序函数c 来选取下一个E 结点 往往可以加快到达一答案结点的速度 14 要对活结点计算优先次序 必然要附加计算工作 即付出代价 对于任意结点X 要付出的代价可以用两种标准来度量 生成一个答案结点之前 子树X需要生成的结点数 在子树X中 离X最近的那个答案结点到X的路径长度 2 1 总是生成最小数目的结点 那条路径上的结点会成为E 结点 答案结点 结点1代价是4 18 3 29 2 30 1 15 结点成本函数c 有智力的 排序函数c也称为结点成本函数如果X是答案结点 则c X 是由状态空间树的根节点到X的成本 即所用的代价 可以是级数 计算复杂度等 如果X不是答案结点且子树X不包含任何答案结点 则c X 如果X不是答案结点 但子树X中包含答案结点 则c X 等于子树X中具有最小成本的答案结点的成本 16 函数c的计算工作量 结点成本函数c的计算工作量往往与原问题具有相同的复杂度 计算一个节点X的成本通常需要检索以X为根结点的整个子树才能确定 要得到精确的成本函数并不现实 一般大致估计结点成本 17 估计函数 X 设 X 是由X到达一个答案结点所需做的附加工作的估计函数 假设子树X中有答案结点 设X的儿子结点是Y 应有 Y X 因为Y到达答案结点的成本肯定比X到达答案结点的成本小 18 用 X 给活结点排序是否合适 若X是当前E 结点说明在活结点表中 X 最小 即 X 其他活结点 生成X的儿子结点Y 并放入活结点表则有 Y成为当前E 结点因为 Y X 其他活结点 故Y在X之后成为新的E 结点 该过程直到子树X全部检索完毕才可能生成子树X以外的结点 19 X 分析 只用 X 为结点排序是否适合 不适合 只考虑未来的可能的代价 导致算法偏向于纵深方向检索 理想 如果 X c X 总成立 那么问题可以用最小成本到达离根最近的答案结点 乐观的冒进 现实 但通常情况下 X 只是精确成本的一个估计值 因此偏于纵深检查可能会丢失掉更靠近根的答案结点 导致结果不理想 X 是对未来可能发生的成本估计 20 结点成本估计函数 考虑结点X到一个答案结点的估计成本 X 考虑根结点到结点X的成本h X X f h X X X h X 算法对活结点表进行检索时 优先选择更靠近答案结点且又离根结点较近的结点 函数f是一个非降函数 不妨将f的作用理解为调整h和 在成本估计函数 中的影响比例 21 LC 检索 LC 检索 LeastCostsearch 选取成本估计函数 的值最小的活结点作为下一个E 结点 伴有限界函数的LC 检索称为LC分枝 限界检索 f h X 结点X的级数 X 0时 则变为BFS检索 队列实现的广度优先检索 f h X 0 且每当Y是X的一个儿子时总有 X Y 时 则变为D 检索 堆栈实现 X f h X X BFS和D检索是LC 检索的特殊情况 22 子集和数问题的解空间树2 注 结点按D 检索方式编号 23 9 1 215 谜问题 a初始排列 问题描述在一个分成16格的方形棋盘上 放有15块编了号码的牌 对这些牌给定一种初始排列 要求通过一系列的合法移动将这一初始排列转换成目标排列 b目标排列 邻接空格的牌移到空格 24 9 1 215 谜问题 每移动一次 就产生一种新的排列 这些排列称为这个谜问题的状态 初始排列称为初始状态 目标排列称为目标状态 若由初始状态到某状态存在一系列合法的移动 则称该状态可由初始状态到达 一个初始状态的状态空间 由所有可从初始状态到达的状态构成 相当庞大 有必要在具体求解之前 判断目标状态是否在这个初始状态的状态空间中 25 9 1 215 谜问题 在具体求解问题之前判定 目标状态是否在这个初始状态的状态空间中 方法 对棋盘的方格位置编上1 16的号码 位置i是在右图的目标排列中放i号牌的方格位置 位置16是空格的位置 假设POSITION i 是编号为i的那块牌在初始状态下的位置号 1 i 16 POSITION 16 表示空格的位置 对于任意一种状态 LESS i 是使牌j 牌i 且POSITION j POSITION i 的j的数目 初始状态下 如果空格在右图的阴影位置中的某一格处 则令X 1 否则X 0 LESS 1 0LESS 4 1LESS 12 6 26 定理9 1 当且仅当 LESS i X是偶数时 图b所示的目标状态可由此初始状态到达 15 谜的状态空间树结点 棋盘的状态每个结点的儿子 状态X通过一次合法的移动可到达的状态移动牌与移动空格等效 上 右 下 左 的顺序 9 1 215 谜问题 1 i 16 判定目标状态是否在初始状态的状态空间中 27 求解方法 法1 宽度优先FIFO检索法2 深度优先检索法3 LC检索 28 上 右 下 左 右 左 上 下 右 下 左 上 下 左 下 下 左 左 下 左 上 下 宽度优先FIFO检索 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 离根结点最近的答案结点 上 右 下 左 29 求解方法 法1 宽度优先FIFO检索不管开局如何 不关心问题的具体实例 总是按千篇一律的顺序移动 法2 深度优先检索法3 LC检索 30 深度优先 1 2 上 右 3 4 下 下 5 下 6 左 7 上 右 下 左 8 上 9 上 上 10 右 11 下 12 31 求解方法 法1 宽度优先FIFO检索能找到离根最近的答案结点 但不管开局如何 不关心问题的具体实例 总是按千篇一律的顺序移动 法2 深度优先检索不管开局如何 不关心问题的具体实例 总是采取由根开始的最左路径 呆板而盲目 搜索过程中有可能远离目标 法3 LC检索 32 LC检索 给状态空间树的每个节点X赋予一定的成本c X 将根结点到最近目标结点路径上的每个结点的成本设置为这条路径的长度 其余结点成本赋值为 在宽度优先搜索方式下 首先将根结点作为E 结点 将成本为 的子结点统统杀掉 只保留与根结点成本相同的子结点 并使其成为下一个E 结点 该策略重复进行 直到找到目标结点为止 P221图9 3 a c 1 c 4 c 10 c 23 3 理想状态下 很不实际 基本不可能得到这样的函数c 33 便于计算成本估计值的函数 f X 是由根到结点X路径的长度 X 是以X为根的子树中由X到目标状态的一条最短路径长度的估计值 X f X X 定义 X 不在其目标位置的非空白棋牌数目 X 是c X 的下界 最小移动数 X 1 2 1 4 3 7 11 12 3 1 4 7 8 11 12 4 1 2 11 12 5 1 4 6 7 11 12 34 下 1 4 10 2 1 11 2 3 12 2 3 当前实例下 LC 检索几乎和使用精确函数c一样有效 LC 检索的选择性比很多检索方法强很多 35 45 46学时 36 结点成本函数c 有智力的 排序函数c也称为结点成本函数如果X是答案结点 则c X 是由状态空间树的根节点到X的成本 即所用的代价 可以是级数 计算复杂度等 如果X不是答案结点且子树X不包含任何答案结点 则c X 如果X不是答案结点 但子树X中包含答案结点 则c X 等于子树X中具有最小成本的答案结点的成本 回顾 C X 是结点X的客观存在的真实成本 但是很难事先得到 37 9 1 3LC 检索的抽象化控制 T是一棵状态空间树c是T中结点的成本函数c X 是根为X的子树中答案结点的最小成本 c T 是T中最小成本答案结点的成本 找到这样一个易于计算的c是很难的 用启发函数 来代替易于计算如果X是一个答案结点或者是一个叶结点 则c X X 38 抽象化控制思想 如果根结点T是答案结点 输出该节点 操作结束 否则 令T是当前的E 结点 此时活结点表为空 判断E的每个子结点X 如果X是答案结点 输出从X到T的路径 操作结束 否则 将X添加到活结点表中 如果活结点表中不再有结点 操作结束 否则从中选择一个函数值 最小的结点作为当前新的E 结点 重复步骤2 39 算法9 1LC 检索 LineprocedureLC T ifT是答案结点then 输出T return endifE T E 结点 将活结点表初始化为空loopforE的每个儿子XdoifX是答案结点then输出从X到T的那条路径return endifcallADD X X是新的活结点 PARENT X Erepeatif不再有活结点thenprint noanswernode stop endifcallLEAST E repeatEndLC 保存结点X的父结点E min堆 40 9 1 3LC 检索的抽象化控制 算法终止 找到答案结点或生成并检索了整棵有限状态空间树无限状态空间树的终止 至少有一个答案结点 且对 作出适当选择 没有答案结点的无限状态空间树 则不会终止 将检索局限在寻找估计成本不大于某个给定的限界C的答案结点 41 9 1 3LC 检索的抽象化控制 活结点表用队列实现FIFO检索LC算法活结点表用堆栈实现LIFO检索 得到下一个E 结点的选择规则不同 实际上 LC算法与状态空间树的宽度优先检索算法以及D 检索算法基本相同 42 9 1 4LC 检索的特性 LC是否一定能找得到具有最小成本c G 的答案结点G呢 10 0 20 2 20 20 10 4 10 10 答案结点 c E E c X c Y X Y 如果使每对c X c Y 的X Y结点都有 X Y 那么对于一棵存在答案结点的有限状态空间树 LC算法是否总会找到一个最小成本答案结点 最小成本结点 43 证明 已知若T有限且存在答案结点 LC一定能找到一个答案结点 下面证明满足定理9 2的条件时 LC能找到最小成本答案结点 定理9 2在有限状态空间树T中 对于每一个结点X 令 X 是c X 的估计值且具有以下性质 对于每一对结点Y Z 当且仅当c Y c Z 时有 Y Z 那么在使 作为c的估计值时 算法LC到达一个最小的成本答案结点且终止 44 假设LC在G处终止 c G c G 找到距离G和G 最近的共同祖先R R到G 的路径为R 1 k G R到G的路径为R 1 j G 若能检索到G 则R必在某时间成为E 结点 子结点 1和 1成为活结点 最小成本答案结点 答案结点 E c R c 1 c k c G c 1 c k c G c G 1 G k 1 在 i 1 i k 变成E结点并到达G 之前 1不能变成E 结点 与假设矛盾 命题得证 45 9 1 4LC 检索的特性 定理9 2在有限状态空间树T中 对于每一个结点X 令 X 是c X 的估计值且具有以下性质 对于每一对结点Y Z 当且仅当c Y c Z 时有 Y Z 那么在使用 作为c 的估计值时 算法LC到达一个最小的成本答案结点且终止 这样的 通常得不到 一般可以找到一个易于计算 且具有如下特性的 对于每一个结点X 有 X C X 算法LC仍然未必找到最小答案结点 46 算法LC仍然未必找到最小答案结点 47 如果规定 对于每一个结点X 有 X c X 且对于答案结点X有 X c X 则只要对算法LC稍作修改 就可以得到一个在达到最小成本答案结点时终止的检索算法 下面给出改进后的算法LC1 48 算法9 2找最小成本答案结点的LC 检索 LineprocedureLC1 T E T置活结点表为空loopifE是答案结点then输出从E到T的路径returnendifforE的每一个儿子XdocallADD X PARENT X Erepeatif不再有活结点thenprint Noanswernode stopendifcallLEAST E repeatEndLC1 生成结点后立即加入活结点表 E由LEAST方法筛选 从活结点表里选择 最小的 算法9 1可能选到第一个合适的儿子结点 算法9 2选中成本最小的儿子结点 49 算法可保证找到最小成本答案结点 算法终止于某个E 结点 此时该结点 记为E结点 是答案结点 往证该结点是最小成本答案结点对于活结点表中的任一结点L 有 E L 因为E是答案结点 所以该点的实际成本C E E 对于L 必有 L C L 因此C E E L C L 说明E结点的实际成本比其他活结点的实际成本都要小 因此是最小成本答案结点 50 9 1 5分枝 限界算法 分枝 限界方法 生成当前E 结点的所有儿子之后 入堆 再将另一个活结点变成E 结点 出堆 假定每一个答案结点X有一个与其相联系的成本函数c X 并且会找到最小成本的答案结点 成本估计函数 X c X 由任一结点X得出解的下界 智能 减少盲目性 设置最小成本的上界U 使算法加速 X U的所有活结点X可以被杀死 U的初值 启发式方法或 不断修改 只要U的初始值不小于最小成本答案结点的成本 就不会杀死可以到达最小成本答案结点的活结点 C X X U 51 9 1 5分枝 限界算法 最优化问题 极小化问题成本函数 代表最优解的答案结点的c X 是所有结点中成本最小的 目标函数可行解的目标函数值若X是可行解结点c X 若X是不可行解结点根为X的树中最小成本若X是部分解结点结点的成本状态空间树中每个答案结点都对应一个可行解 成本最小的答案结点对应最优解 估计函数 X c X 对目标函数进行估计 而不是估计达到一个答案结点在计算上的难易程度 52 9 1 5分枝 限界算法 带期限的作业排序问题 允许作业有不同的处理时间每个作业i与一个三元组联系 pi di ti 目标 n个作业的子集合J J中的作业都能在相应的期限内完成 且不在J中的作业招致的罚款总额最小 例 n 4 p1 d1 t1 5 1 1 p2 d2 t2 10 3 2 p3 d3 t3 6 2 1 p4 d4 t4 3 1 1 作业i的处理时间 如果没有在期限值之前完成 招致pi的罚款 53 1 2 3 4 5 6 7 9 10 11 x2 2 x2 3 x2 4 x2 3 x2 4 x2 4 x1 1 x1 2 x1 3 x1 4 x3 3 x3 4 x3 4 x3 4 12 13 14 8 15 元组大小可变的状态空间树 方形结点是不可行结点 圆形结点都是答案结点 对于圆形结点X C X 根为X的子树中结点的最小罚款对于方形结点X C X p1 d1 t1 5 1 1 p2 d2 t2 10 3 2 p3 d3 t3 6 2 1 p4 d4 t4 3 1 1 C 6 9 C 7 13 故C 2 9 54 25 1 2 3 6 7 14 15 30 31 28 29 12 13 26 27 4 10 23 21 5 11 9 19 x1 1 x1 0 x2 1 x3 1 x4 1 0 1 0 x2 0 x3 0 x3 1 x3 0 x2 1 x2 0 x3 1 x3 0 x3 1 x3 0 1 0 1 0 1 0 1 0 1 0 圆形叶结点是答案结点 22 元组大小固定的状态空间树 9 13 19 8 11 14 15 18 21 24 c 0 5 0 10 6 10 16 5 5 11 15 21 15 55 1 2 3 4 5 6 7 9 10 11 x2 2 x2 3 x2 4 x2 3 x2 4 x2 4 x1 1 x1 2 x1 3 x1 4 x3 3 x3 4 x3 4 x3 4 12 13 14 8 15 元组大小可变的状态空间树 方形结点是不可行结点 圆形结点都是答案结点 p1 d1 t1 5 1 1 p2 d2 t2 10 3 2 p3 d3 t3 6 2 1 p4 d4 t4 3 1 1 如何设置成本的估计函数 1 0 2 0 3 5 4 15 5 21 6 0 7 10 8 9 5 10 11 11 15 56 9 1 5分枝 限界算法 设SX是在结点X处选择的作业的子集 m max i i SX X piu X pi U min U X i mi SX i SX X对应的子集SX的成本值 罚款 子树X中最小成本答案结点的成本的简单上界 57 1 元组大小可变的状态空间树 u 2 p2 p3 p4 19 2 0 u 3 p1 p3 p4 14 3 5 u 4 p1 p2 p4 18 4 15 U 19 U 14 B u 5 p1 p2 p3 21 5 21 B u 6 p3 p4 9 6 0 U 9 u 7 p2 p4 13 7 10 B u 9 p1 p4 8 9 5 U 8 u 10 p1 p3 11 10 11 B p1 d1 t1 5 1 1 p2 d2 t2 10 3 2 p3 d3 t3 6 2 1 p4 d4 t4 3 1 1 58 47 48学时 59 1 元组大小可变的状态空间树 u 2 p2 p3 p4 19 2 0 u 3 p1 p3 p4 14 3 5 u 4 p1 p2 p4 18 4 15 U 19 U 14 B u 5 p1 p2 p3 21 5 21 B u 6 p3 p4 9 6 0 U 9 u 7 p2 p4 13 7 10 B u 9 p1 p4 8 9 5 U 8 u 10 p1 p3 11 10 11 B p1 d1 t1 5 1 1 p2 d2 t2 10 3 2 p3 d3 t3 6 2 1 p4 d4 t4 3 1 1 回顾 U如何得到 60 9 1 5分枝 限界算法 U修改之后 对于活结点表中满足 X U的X 可以当X即将成为E结点时将其杀掉对于 X U的结点X是否杀死 这取决于U的来源 U可能有两种来源 一个已找到的解的成本值 不是解成本的单纯上界如果U的来源是 那么相当于U本身就是一个解成本 结点Y 对于其他 X U 因为其真实成本C X X U 至多X的解成本与结点Y的解成本相同 不会比Y更小 所以X是没有意义的 可以杀死 61 如果U的来源是 即U不是一个解成本 而只是一个单纯的上界对于其他 X U 其真实成本C X X U 意味着存在着C X U的可能性假设这种情况出现 结点X是一个解 且其真实成本C X U 那么结点X就不能被杀死因为在此之前虽然上界是U 但是没有结点的成本可以达到U 而X的成本是可能达到U的 它可能会是一个最小成本结点 所以绝对不能杀死 如果U是由上界得到 为了避免误杀 X U的结点 可在得到U时将U稍微变大一点点 假设U是在处理结点Y时由上界u Y 得到 则令U u Y 62 如果U是由上界得到 为了避免误杀 X U的结点 可在得到U时将U稍微变大一点点 假设U是在处理结点Y时由上界u Y 得到 则令U u Y 此时 对于 X U 则有C X X U u Y u Y 即X的解成本一定比之前估计的上界值要大 不可能等于上界值 所以X是没有意义的 可以杀死 如此一来 对于修正后的U 无论其来源是 还是 只要 X U 则X结点可以被杀死 63 9 1 5分枝 限界算法 ADDQ X 将结点X加入队列DELETEQ X 将结点X从队列中删去cost X 若X是答案结点 对应解的成本u X 以X为根的子树中 可以估计到的最小成本上界ans answer的缩写 用来存放答案结点 64 lineprocedureFIFOBB T u cost E T PARENT E 0 ifT是解结点thenU min cost T u T ans TelseU u T ans 0endif将队列置为空loopforE的每个儿子Xdoif X UthencallADDQ X PARENT X Ecase X是解结点andcost X U U min cost X u X ans X u X U U u X endcaseendifrepeatloopif队列为空thenprint leastcost U whileans 0doprint ans ans PARENT ans repeatreturnendifcallDELETEQ E if E UthenexitendifrepeatrepeatendFIFOBB 为找出最小成本答案结点检索T 假定T至少包含一个解结点且 X c X u X 入队时修改U和ans 出队时判断是否杀死 此时的U与该结点入队时的U已不相同 估计函数小于U才入队 65 FIFO算法思想 初始化令根结点T是当前E 结点 对估计成本上界U和答案解ans赋初值 如果T是解结点 U