5.1 算法设计-分枝限界法.ppt

2020 2 22 算法设计与分析演示稿纪玉波制作 C 1 算法设计与分析 分枝限界法 2020 2 22 算法设计与分析演示稿纪玉波制作 C 2 分枝限界法 branch and bound 有一些优化问题或对策问题除了用 穷举法 外没有太好的解法 回溯法就是针对这类问题的一种系统解决方法 此方法的思想是构成一棵树 树的每一层代表某一步的各种走法 某一待求量的各种取值或某一子问题的各种解决方案等 而树的每个终端结点表示每一种可能的最终解答 2020 2 22 算法设计与分析演示稿纪玉波制作 C 3 如果可能的解答数目太多 限于计算机容量和计算时间 不可能构成整个树 则至少构成该树的上面一些层 而将其终端结点标上一定的评价函数 以表示沿其子树进一步进行下去效果的优劣区别 对此树按类似后序遍历的次序进行分析 由每个中间结点的各个子树中挑选出其中最 合适 的一个 或根据子树的评价函数确定该中间结点的评价函数 如此进行下去直至根结点为止 即得到整个问题的解答 下面举几个例子 2020 2 22 算法设计与分析演示稿纪玉波制作 C 4 例1 八皇后问题 这是高斯1850年提出的一个著名问题 国际象棋中的 皇后 在横向 直向 和斜向都能走步和吃子 问在8 8 64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃 现已知此问题共有92种解 但只有12种是独立的 其余的都可以由这12种利用对称性或旋转而得到 2020 2 22 算法设计与分析演示稿纪玉波制作 C 5 为简单起见 以四皇后问题为例讲述此方法 设棋盘有4 4 16格 每行所摆的皇后都有四种可能的位置 四个皇后共有44 256种摆法 如将这些摆法都列出来再选其中合乎条件的方案 就太费时间了 现构成一个树 根结点的四个子树表示第一行的皇后的四种可能的位置 再下一层表示第二行的位置 设以F表示失败 S表示成功 如果上面的行已经无法摆了 则下面的行表示失败 S表示成功 如果上面的行已经无法摆了 则下面的行即不必再试 返回上一层再试其它分支 2020 2 22 算法设计与分析演示稿纪玉波制作 C 6 假设第一行的皇后先放在第一列 如图 a 所示 则第二行只有三 四列还可以摆 若暂先试第三列 第三行就完全无法再摆 只好回溯到上一层再试另一个分支 即第二行放第四列 这样第三行还剩第二列可以摆 但第四行又无法再摆了 此时只好返回到最上一层 改试第一行放第二列 最后构成的树如图2所示 共有两个可行方案 实际上这是两个对称的方案 2020 2 22 算法设计与分析演示稿纪玉波制作 C 7 2020 2 22 算法设计与分析演示稿纪玉波制作 C 8 图2 2020 2 22 算法设计与分析演示稿纪玉波制作 C 9 因为从所有失败的方案返回时该部分子树即不必保留 所以最终内存中只保留成功方案的几条单链分支 比图中所示之树还要简单 如果每试出一个成功方案就立即输出而不必存储 或只试出一个方案就可以了 则只需一个单链 更可以节约存储量 2020 2 22 算法设计与分析演示稿纪玉波制作 C 10 在用这种方法解决优化问题时 以下以最小化问题来说明 最大化问题也与此类似 如果能事先估计出每个分支的下界值 当某分支的下界值比已试过的方案的值还要高时 这整个子树即不必再考虑 因此常常可以大大节约运算时间 下面再以一个例子说明 2020 2 22 算法设计与分析演示稿纪玉波制作 C 11 例2 分派问题 这是整数规划问题中的一种特殊问题 现举一个数字例子 设有A B C D四位教师 每人都能教I II III IV四门课程 但各人备各门课所需时间不同 如下表所示 2020 2 22 算法设计与分析演示稿纪玉波制作 C 12 2020 2 22 算法设计与分析演示稿纪玉波制作 C 13 现要求每门课有一个人教 且每人只教一门课 问如何分配工作才可以使总备课时间最少 此问题如果用穷举法需要试4 24种方案 从中选优 现用分枝限界来解 2020 2 22 算法设计与分析演示稿纪玉波制作 C 14 首先要确定如何定问题的下界 设将每人只教一门课变成一人可以教多门课 这样一来得到的总备课时间最小值肯定不会比实际情况还大 可作为问题的下界 而且在这种假定下最小值的计算非常方便 只需将表中各列的最小值加起来即可 例如整个问题的下界为 A教I II IV课 B教II课 2 4 9 7 22 2020 2 22 算法设计与分析演示稿纪玉波制作 C 15 现构成一个树 根结点的四个子树表示I课选谁来教 再下一层表示I课教师选定后剩下的人谁教II课 如图所示 图中每结点旁的数字为该子问题的下界 如果一个结点有几个子树 则选下界最小的先处理 为什么 图中结点圆圈中数字表示处理顺序 2020 2 22 算法设计与分析演示稿纪玉波制作 C 16 2020 2 22 算法设计与分析演示稿纪玉波制作 C 17 首先计算选择I课教师四种方案子问题的下界 例如若选定A教I课 则B C D三人教II III IV课的最小值为B教II IV D教III课 下界为2 4 13 8 27 若选定B教I课 类似算出下界为41 15 10 9 7 41 四方案中以D教I课时的点 下界24为最小 故先由此向下进行 教I课的人选择以后 教二课的人有三种方案 类似地算出其下界值 其中又以B教II课的点 下界24为最小 再往下进行 教III课的人只有两种 下界分别为28和31 2020 2 22 算法设计与分析演示稿纪玉波制作 C 18 因前三门课的人定了后 第四门课实际上也就定了 故这已是实际所需的时间了 数值为31的点 当然应当舍弃 然后回溯到点 看另外两个点 和 它们的下界均比点 的28要大 不必再考虑 然后再向上回溯到点 看另外三个分枝 其中点 和点 的下界均大于28 故都应舍弃 唯有点 的下界为27 尚有可考虑的余地 由 向下进行 三个方案中点 12 和点 13 的下界均比28为大 当然不必再考虑 点 11 的下界虽然恰好等于28 但这只是下界 实际结果很可能比这还要差 充其量等于此值 故当问题要求只得到一种最好方案就够了时 也不必再向下作下去 这样最后得出以点 表示的方案 D I B II A III C IV 总的时间为28 2020 2 22 算法设计与分析演示稿纪玉波制作 C 19 由此例可以看出 分枝限界法的关键是恰当的选择子问题的下界 使之既要容易计算 又不要距离实际的值太远 例如上述例子中 若下界取得抬高就不会有多少好处了 2020 2 22 算法设计与分析演示稿纪玉波制作 C 20 例3 巡回推销员问题 设有5座城市 城市间的距离矩阵为 2020 2 22 算法设计与分析演示稿纪玉波制作 C 21 因dij dji 将矩阵D对角线以上的元素从小到大排列有d24 1 d13 2 d15 2 d25 3 d45 6 d35 9 d34 9 由于是5个城市 环绕一圈为5条边 则取距离最小的5条边并求和 得d13 d24 d15 d25 d45 1 2 2 3 6 14显然下标中5出现了3次 违背了一顶点不能有三条边相连的约束条件 如果不用d15而用下一条较小的边d35代替 则 2020 2 22 算法设计与分析演示稿纪玉波制作 C 22 d13 d24 d25 d45 d35 1 2 3 6 9 215依然出现3次 如果保留d15 用下一条较小的边d35代替d25 则d13 d24 d15 d45 d35 1 2 2 6 9 20按照深度优先方式搜索下去 现将搜索过程形象地表示如下图 2020 2 22 算法设计与分析演示稿纪玉波制作 C 23 2020 2 22 算法设计与分析演示稿纪玉波制作 C 24 搜索至第5步时发现d13 d24 d15 d25 d34 1 2 2 3 9 17并得一条回路 而且是最佳的回路 v1 v3 v4 v2 v5 v1其它路径因不合理或其下界都大于17故没有进一步搜索的价值 所以上述路径便是最佳路径 2020 2 22 算法设计与分析演示稿纪玉波制作 C 25 例4 同顺序加工任务安排问题设J1 J2 J3 J4是四项待加工的任务 它们的工序一样 即先在机器m1上加工 然后在机器m2上加工 最后在机器m3上加工 加工时间矩阵是 2020 2 22 算法设计与分析演示稿纪玉波制作 C 26 tij即为任务Ji在机器mj上加工所需时间 如若加顺序是 J2 J3 J1 J4则从开始到结束所需的时间可计算如下图 2020 2 22 算法设计与分析演示稿纪玉波制作 C 27 2020 2 22 算法设计与分析演示稿纪玉波制作 C 28 图中 表示机器空闲等待任务 比如机器m2加工J2于开始后15单位时间结束 但m3加工J3于19单位时间才能完结 所以机器m2于15至19单位时间内空闲着等待任务 加工顺序J2 J3 J1 J4需54单位时间 现在要找一最佳的加工顺序 使完成任务的总时间达到最短 2020 2 22 算法设计与分析演示稿纪玉波制作 C 29 分支限界法的关键在于估计下界 比如从Ji开始的加工顺序 估计加工所需的最短时间为 即在理想状态下机器m1加工完Ji 机器m2无空闲 最后在机器m3上加工的是任务Jk 其中k满足 2020 2 22 算法设计与分析演示稿纪玉波制作 C 30 即最后在机器m3上加工的任务恰好是机器m3上加工时间最短的任务Jk 当然Jk必须不是最先加工的任务Ji 如是 我们可以得出从任务Ji开始所需加工时间的下界 如下图所示 2020 2 22 算法设计与分析演示稿纪玉波制作 C 31 2020 2 22 算法设计与分析演示稿纪玉波制作 C 32 从图中可见 在这种理想状态下 以J1或J4开始的任务安排完成的时间可能最短 其中从J4开始的任务安排有 5 7 5 7 8 4 36即完成的时间不可能少于36单位 其余同理类推 一般从Ji开始 继以Jj的任务安排 理想完成时间应为 2020 2 22 算法设计与分析演示稿纪玉波制作 C 33 Ji Jj Jk的加工顺序所需的加工时间的最低界为 2020 2 22 算法设计与分析演示稿纪玉波制作 C 34 利用分枝限界方法求解的过程如下图 2020 2 22 算法设计与分析演示稿纪玉波制作 C 35 图中每个节点都有两个数 其中 里的数表示搜索顺序的序号 最优的加工顺序是 J1 J4 J3 J2总时数为38单位 相应安排如下图所示 2020 2 22 算法设计与分析演示稿纪玉波制作 C 36 2020 2 22 算法设计与分析演示稿纪玉波制作 C 37 依估计的时间最短优先搜索为原则 最先找到的最优结果为40单位 若估计的界不小于38 就无搜索的必要 从图中可知剪去的搜索树枝是非常可观 分支限界的效果是很理想的 2020 2 22 算法设计与分析演示稿纪玉波制作 C 38 综合以上几个例子 可以看到分支限界法的基本思想是采用DFS策略 并对每个结点估计一权值 在求极小值问题中对应于从该结点出