第九章 分支限界法.pptVIP

算法分析与设计 主讲: 徐晓蓉 计算机科学与技术学院 第九章 分枝限界法 主要内容 一般方法 分枝限界法的基本思想 分枝限界法的算法框架 分枝限界法的分类 应用举例 数码问题 0/1背包 旅行商问题 9.1 一般方法 1. 分支限界法与回溯法的不同 （1）概念: 深度优先生成状态空间树中的结点,并使用剪枝函数的的求解方法称为回溯法; 广度优先生成状态空间树中的结点，并使用剪枝函数的求解方法称为分枝限界法. （2）求解目标： 回溯法的求解目标是找出解空间树中满足约束条件的所有解或最优解; 分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （3）有哪些信誉好的足球投注网站方式的不同： 回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树; 分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 9.1 一般方法 2. 分支限界法基本思想 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 9.1 一般方法 3. 常见的三种分支限界法 （1）FIFO分支限界法 活结点表是先进先出队列,按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）LIFO分支限界法 活结点表是堆栈,按照栈后进先出（LIFO）原则选取下一个节点为扩展节点。 （3）LC(优先队列式)分支限界法 活结点表是优先权队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 9.1 一般方法 例9-1(4-皇后问题)用FIFO分支限界法求解4-皇后问题 9.1 一般方法 9.1 一般方法 回溯法,FIFO分支限界法和LIFO分支限界法选择活结点作为新的扩展结点的方法是盲目的，只是机械的按照FIFO或LIFO原则选取下一个活结点.而LC分支限界法可根据活结点的优先权选择活结点作为扩展结点. 9.1 一般方法 5. LC分支限界法 LC分枝限界法:可根据活结点的优先权选择结点作为扩展结点 用途: 1,求解问题的一个可行解 2,求解最优化问题的最优解 采用LC分枝限界法时，为了去掉盲目性，尽快有哪些信誉好的足球投注网站到一个答案结点，可对活结点表使用一个”有智力”的评价函数作为优先权来选择下一个扩展结点，该评价函数通过衡量一个活结点的有哪些信誉好的足球投注网站代价，来确定哪个活结点能够引导尽快到达一个答案结点. 9.1 一般方法 (1)代价函数c(.) 9.1 一般方法 (2)相对代价函数g(.) 9.1 一般方法 (3)相对代价估计函数 9.1 一般方法 用LC分枝限界法求解数码问题 9.1 一般方法 用LC分枝限界法求解数码问题 9.1 一般方法 9.1 一般方法 9.1 一般方法 9.2 求最优解的分枝限界法 9.2 求最优解的分枝限界法 9.2 求最优解的分枝限界法 基于上下界函数的分枝限界法的限界方法: 算法要求U的初值大于最优解的代价，并在有哪些信誉好的足球投注网站状态空间树的过程中不断修正U的值，对于某个结点X,U的值可按如下原则修正: (1)若X是答案结点,cost(X)是X所代表的可行解的目标函数值，U(X)是该子树上最小代价答案结点代价的上界值，则U=min(cost(X),U(X)+ε,U) (2)如果Ｘ代表部分向量，则U=min(U(X)+ε,U) 9.4 0/1背包 9.4 0/1背包 9.4 0/1背包 9.4 0/1背包 9.4 0/1背包 9.5 旅行商问题 9.5.1. 问题描述 某售货员要到n个城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 9.5旅行商问题 2)上下界函数的设计 定义9-3,如果矩阵的一行(列)中至少包含一个零且其余元素非负，则称此行(或列)已归约 定义9-4,如果一个矩阵的所有行和列均已归约,则称此矩阵为归约矩阵 归约的方法:对矩阵的一行(列)进行归约，可通过将该行(列)中的每个元素减去