算法分析——5.ppt

算法设计与分析 ——分支限界法 分支限界法 分支限界法 与回溯法类似，都是在问题的解空间树上有哪些信誉好的足球投注网站问题解的算法； 求解目标：找出满足约束条件的解 可行解或最优解 有哪些信誉好的足球投注网站策略 根据限界函数值，剔除那些导致不可行解或非最优解的子结点，使有哪些信誉好的足球投注网站过程仅限制在剩余的分支内进行； 提纲 分支限界法的基本思想 实例分析 本章小结 提纲 分支限界法的基本思想 实例分析 本章小结 分支限界法 Vs 回溯法 相同点： 两者在进行问题求解前，都需要完成解空间的定义和组织； 都是通过在解空间有哪些信誉好的足球投注网站来寻找问题的解； 分支限界法 Vs 回溯法 不同点： 有哪些信誉好的足球投注网站方式 回溯法：深度优先； 分支限界法：广度优先； 有哪些信誉好的足球投注网站策略 回溯法：根据剪枝函数，选择下一个扩展接点并按深度优先方式进行有哪些信誉好的足球投注网站； 分支限界法：在扩展结点处，先产生其所有的子结点（分支），然后根据限界函数，确定哪些子结点将导致不可行解或非最优解，将这些子结点剔除，用剩下的子结点构造当前的活结点表，然后从该表中取一个结点作为当前扩展结点，并重复上述过程； 分支限界法的主要分类 分支限界法的主要分类 根据从活结点表中选择下一个扩展结点的方式 队列式FIFO分支限界法 优先队列式分支限界法 队列式FIFO分支限界法 队列式FIFO分支限界法 算法思想：将活结点表组织成一个队列，并按队列的先进先出FIFO原则选取下一个结点作为当前扩展结点； 优先队列式分支限界法 优先队列式分支限界法 算法思想：将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级，选取剩余队列中优先级最高的下一个结点作为当前扩展结点； 实例说明 实例说明 0-1背包问题 TSP问题 实例说明 实例说明 0-1背包问题 TSP问题 实例说明——0-1背包问题 n=3的0-1背包问题 w=[16,15,15] p=[45,25,25] c=30 实例说明 实例说明 0-1背包问题 TSP问题 实例说明——TSP问题 提纲 分支限界法的基本思想 实例分析 本章小结 实例分析 单源最短路径问题 装载问题 布线问题 0-1背包问题 最大团问题 TSP问题 电路板排列问题 批处理作业调度 算法思想 算法思想 采用优先队列式分支限界法 以当前结点所对应的路径长度为参考标准(路径长度越短，优先级越高） 限界函数设计 利用已经获得的当前最短路径长度Lmin为基准，对那些结点所对应路径长度大于Lmin的情况，剪去以该结点为根的子树； 利用结点间的控制关系进行剪枝 对于通过不同路径到达同一顶点的两条路径，路径长度短的结点（控制结点）控制路径长度长的结点（被控制结点） ?将被控制结点所对应的子树剪去 实例分析 最优解 问题描述 求解出发点 容易证明，如果一个给定的装载问题有解，则采用以下策略可以得到最优装载方案： 首先将第一艘船尽可能装满； 等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1 将剩余的集装箱装上第二艘船； 算法思想 算法思想 解空间树 子集树 分支限界法 队列式 优先队列式 队列式 队列式 算法实现：检查当前结点的深度 i=n 表示当前活结点为叶结点，不需要加入到活结点队列中，只要检查该结点表示的可行解是否优于当前最优解，并适时更新当前最优解 in 表示当前结点为内部结点，应加入到活结点队列中 限界函数设计 限界函数 是否超过船的负荷限制 根据当前已知的最优解bestw来进行剪枝 当前扩展结点所对应的重量ew； 剩余集装箱的重量r； ——如果ew+r=bestw，则进行剪枝（剪去右子树，因为右子树为0，表示下一个集装箱没有被选中） ——提早更新bestw（在每次进入左子树时更新） 优先队列式 优先队列式 思路：根据活结点X在优先队列中的优先级 优先级定义 从根结点到结点X的路径所对应的载重量+剩余集装箱的重量 优先队列中优先级最大的活结点成为下一个扩展结点 一旦有一个叶结点成为当前扩展结点，则该叶结点所对应的解就是最优解 优先级策略的实现方式 优先级策略的实现方式 第一种，在结点优先队列的每一个活结点中保存从解空间树的根结点到该结点的路径； 在到达最优值的叶结点时，在该结点处同时得到相应的最优解； 第二种，在算法的有哪些信誉好的足球投注网站过程中保存当前已构造出的部分解空间树。 当达到最优值的叶结点时，可以在解空间树中从该叶结点开始向根结点回溯，从而构造出最优解。 教材中所选用的方案 布线问题 布线问题 问题描述：确定连接方格a的中点到方格b的中点的最短布线路径。 布线时，电路只能沿直线或直角布线 其他线路不允许穿过已布线的方格 算法设计思想 算法设计思想 解空间：图 有哪些信誉好的足球投注网站策略：队列式分支限界法 从起始位置a开始，将其作为第一个扩展结点。与该扩展结点相邻并且可达的方格（有相邻边且未被标记）作为可行结点被加入到活动结点队列中，