分支限界法最好的PPT.ppt

计算机算法设计与分析 NorthChinaElectricPowerUniversity ComputerAlgorithmsDesign Analysis 第七章分支限界法 分支限界法的基本思想 单源最短路径问题 布线问题 NorthChinaElectricPowerUniversity 方格调整问题 1分支限界法的基本思想 分支限界法类似于回溯算法 也是一种在问题的解空间树T上搜索问题的解的算法 和回溯法的区别 1 求解目标不同 回溯法的求解目标是找出T中满足约束条件的所有解 而分支限界法的求解目标则是找出满足约束条件的一个解 或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解 即在某种意义下的最优解 2 结点的扩展方式不同 回溯法以深度优先的方式搜索解空间树 而分支限界法则以广度优先或最小耗费优先的方式搜索解空间树 在扩展结点处 先生成所有的儿子结点 然后再从当前的扩展结点表中选择下一个扩展结点 3 活结点成为扩展结点的机会不同 在回溯法中每个结点可能有多次机会成为扩展结点 而分支限界法中每个活结点只有一次机会成为扩展结点 NorthChinaElectricPowerUniversity 分支限界法以广度优先或最小耗费优先的方式搜索问题的解空间树 在搜索问题的解空间树时 每一个活结点只有一次机会称为扩展结点 活结点一旦成为扩展结点 就一次性产生其所有的儿子结点 在这些儿子结点中 那些导致不可行解或非最优解的儿子结点被舍弃 其余的儿子结点被加入活结点表中 此后 从活结点表中选择下一个结点成为当前扩展结点 并重复上述结点扩展过程 这个过程一直持续到找到所需的解或活结点表为空时为止 分支限界法的搜索策略 NorthChinaElectricPowerUniversity 根据从活结点表中选择下一结点的不同方式 分支限界法分为两类 1 队列式分支限界法 队列式分支限界法将活结点表组织成一个队列 并按照队列的先进先出的原则选取下一个结点称为当前结点 2 优先队列式分支限界法 优先队列式分支限界法将活结点表组织成一个优先队列 并按照优先队列中规定的优先级选取优先级最高的下一结点成为当前扩展结点 在算法实现时 通常用一个最大堆来实现最大优先队列 用最小堆来实现最小优先队列 用优先队列法解具体问题时 应根据具体问题的特点选用最大优先队列或最小优先队列来表示解空间的活结点表 A B C D E F G H I J L K M N O x1 1 x1 0 x2 1 x2 0 x3 1 x3 0 x3 1 x3 0 x2 1 x2 0 x3 1 x3 0 x3 1 x3 0 例 0 1背包问题n 3 C 20 p1 p2 p3 20 15 25 w1 w2 w3 10 5 15 求X x1 x2 x3 使背包价值最大 10 20 15 35 15 35 10 20 10 20 5 15 20 40 15 35 5 15 20 40 0 0 0 0 15 25 20 40 20 40 0 0 20 40 当前最优解 可行解 中间计算结果 A B C D E F G H I J L K M N O 1 0 1 0 1 0 1 0 1 0 1 0 1 0 解空间树T 例 0 1背包问题n 3 C 20 p1 p2 p3 20 15 25 w1 w2 w3 10 5 15 求X x1 x2 x3 使背包价值最大 10 20 15 35 10 20 5 15 0 0 0 0 优先队列式分支限界法 当我们找最优解时 我们可以像回溯法一样 用剪枝函数来加速搜索 比如我们给出每一个可行结点相应的子树可能获得的最大价值的上界 如果这个上界不会比当前最优值大 则说明相应的子树不含问题的解 可以剪去 当然我们也可以把这个上限作为每个结点在优先队列式分支限界法中的优先级 这种方法可能会更快找到最优解 堆是满足下列性质的数列 R1 R2 Rn 或 若将此数列看成是一棵完全二叉树 则堆或是空树或是满足下列特性的完全二叉树 其左 右子树分别是堆 并且当左 右子树不空时 根结点的值小于 或大于 左 右子树根结点的值 堆的补充知识 1 堆的定义 2 最小堆的C 描述 templateclassMinHeap Arrayarray intcount public MinHeap unsignedintn MinHeap EnQueue Object 3 最小堆的插入和删除 1 插入 3 4 6 7 5 插入2 3 4 6 7 5 3 4 6 7 5 3 4 6 7 5 2 voidMinHeap EnQueue Object 2 删除 3 4 6 7 5 删除2 4 3 6 7 5 4 3 6 7 5 2 3 4 7 5 6 3 4 7 5 6 Object NorthChinaElectricPowerUniversity 2 单源最短路径问题 1 问题描述 1 2 3 4 30 10 20 6 4 5 给定一个带权有向图G V E 其中每条边的权是一个非负实数 另外 还给定V中的一个顶点 称为源 计算从源到所有其他各顶点的最短路径长度 这里路径的长度是指路上各边权之和 这个问题称为单源最短路径问题 例 下图为一包含4个顶点的无向图 其中顶点1为源 求顶点1到其它各顶点的最短路径及其长度 s 2 算法思想 单源最短路径问题可用分支限界法求解 由于要找的是从源到各顶点的最短路径 所以选用最小堆来表示优先队列 其优先级是结点所对应的当前路长 从图G的源s和空优先队列开始 结点s被扩展后 它的儿子结点依次被插入堆中 此后 算法从堆中取出具有最小当前路长的结点作为当前扩展结点 并依次检查与当前扩展结点邻接的所有顶点 如果从当前扩展顶点i到顶点j有边可达 且从源出发 途经顶点i再到顶点j所相应的路径长度小于当前最优路径长度 则将该顶点作为活结点插入到活结点优先队列中 这个结点扩展过程一直重复到活结点优先队列为空时为止 在具体实现算法时 用邻接矩阵表示所给的图G 用数组dist记录从源到各顶点的距离 用数组prev记录从源到各顶点的路径上的前驱顶点 3 算法描述 templateclassGraph friendvoidmain void public voidShortestPaths int private intn 图G的顶点数int prev 前驱顶点数组Type c 图G的邻接矩阵Type dist 最短距离数组 templateclassMinHeapNode friendGraph public operatorint const returnlength private inti 顶点编号Typelength 当前路长 templatevoidGraph ShortestPaths intv MinHeap H 1000 MinHeapNodeE E i v E length 0 dist v 0 while true for intj 1 jN N i j N length dist j H Insert N try H DeleteMin E catch OutOfBounds break 2020 3 15 19 可编辑 1 2 3 4 30 10 20 6 4 5 1 0 0 dist 1 0dist 2 30 14 11dist 3 6dist 4 4 2 1 30 3 1 6 4 1 4 3 1 6 2 1 30 E H 4 1 4 2 1 30 3 1 6 2 1 30 3 1 6 2 1 30 2 4 14 3 1 6 2 4 14 2 1 30 2 3 11 2 4 14 prev 1 0prev 2 1 4 3prev 3 1prev 4 1 2 3 11 2 1 30 2 4 14 2 4 14 2 1 30 2 1 30 3 布线问题 1 问题描述 印刷电路板将布线区域分成n m个方格阵列 精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案 在布线时 电路只能沿直线或直角进行 为了避免线路相交 已布了线的方格做了封锁标记 其他线路不允许穿过被封锁的方格 如下图所示 在一个7 7的方格阵列中布线 其中起始位置a 3 2 目标位置b 4 6 阴影方格表示被封锁的方格 从起始位置a开始将它作为第一个扩展结点 与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中 并将这些方格标记为1 即从起始方格a到这些方格的距离为1 接着 从活结点队列中取出队首结点作为下一个扩展结点 并将与当前扩展结点相邻且未标记过的方格标记为2 并存入活结点队列 这个过程一直持续到算法搜索到目标方格b或活结点队列为空时为止 在实现上述算法时 首先定义一个表示电路板上方格位置的类Position 它的2个私有成员row和col分别表示方格所在的行和列 在电路板的任何一个方格处 布线可沿右 下 左 上四个方向进行 沿这4个方向的移动分别记为移动0 1 2 3 在下面的表格中 offset i row和offset i col i 0 1 2 3 分别给出沿这4个方向前进1步相对于当前方格的相对位置 2 算法思想 移动方向的相对位移 移动i 方向 offset i row offset i col 0 右 0 1 1 下 1 0 2 左 0 1 3 上 1 0 在实现上述算法时 用一个二维数组grid表示所给的方格阵列 grid i j 0方格 i j 允许布线 1方格 i j 不允许布线 算法将起始位置的距离标记为2 因为0 1用于表示方格的开放或封锁状态 实际距离应为标记距离减2 算法从起始位置start开始 标记所有标记距离为3的方格并存入活结点队列 然后依次标记所有标记距离为4 5 的方格 直到达到目标方格finish或活结点队列为空时为止 对于前面的例子 计算过程过程和结果如下 由于每个方格成为活结点进入活结点队列最多1次 因此活结点队列中最多只处理O mn 每个扩展结点需O 1 时间 因此算法共耗时O mn 构造相应的最短距离需要O L 时间 其中L是最短布线路径的长度 2 9 9 012345678 12345678 boolFindPath Positionstart Positionfinish int grid start row start col 2 LinkQueueQ do for inti 0 i NumOfNbrs i nbr row here row offset i row nbr col here col offset i col if grid nbr row nbr col 0 grid nbr row nbr col grid here row here col 1 if nbr row finish row 构造最短布线路径PathLen grid finish row finish col 2 path newPosition PathLen 从目标位置finish开始向起始位置回溯here finish for intj PathLen 1 j 0 j path j here 找前驱位置for inti 0 i NumOfNbrs i nbr row here row offset i row nbr col here col offset i col if grid nbr row nbr col j 2 break here nbr 向前移动 returntrue 问题 有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船 其中集装箱i的重量为Wi 且 wi C1 C2 要求一个合理的装载方案可将这n个集装箱装上这两艘轮船 4 装载问题 i 1 n 容易证明 如果一个给定的装载问题有解 则采用下面的策略可以得到一个最优装载方案 1 首先将第一艘轮船尽可能装满 2 然后将剩余的集装箱装到第二艘轮船上 于是这个问题等价于这样一个问题 选取集装箱的一个子集 使该子集中集装箱重量之和最接近C1 由此可知 这实际上是一个特殊的0 1背包问题 Xi 0 1 1 i n wixi C1使得max wixi n i 1 i 1 n 显然其解空间树是一颗子集树 我们用队列式分支限界法求解 1 队列式分支限界法 解空间树是一个完全二叉树 实际上是在对一个完全二叉树进行广度优先遍历 我们只求出最优值 然后再讨论如何求最优解 我们用一个函数Maxloading实施对解空间的搜索 用队列Q存放活动结点在队列Q中我们用weight表示每个活结点所相应的当前载重量 另外我们还设置了一个特殊标志当weight 1时 表示队列已到达解空间树同一层结点的尾部 我们举例说明一下 函数EnQueue用于将活结点加入到活结点队列Q中 该函数首先检查I是否等于n 如果i n 则表示当前活结点为一个叶结点 由于叶结点不会被进一步扩展 因此不必加入到活结点队列Q中 当检查到该叶结点表示的可行解优于当前最优解时 更新当前最优解 当i n时 表示当前结点是一个内部结点 应加入到活动结点队列Q中 函数MaxLoading再开始时I初始化为1 bestw初始化为零 表示当前的最优载重量 此时活动结点队列为空 我们将同一层结点尾部标志 1加入到活动结点队列中 表示此时位于第一层结点的尾部 Ew存储当前扩展结点所相应的载重量 在while循环中 首先检测当前扩展结点的左儿子结点 代表该集装箱被装茹 是否可行 即装入后是否大于轮船的容积 如果可行则调用EnQueue函数将其加入到活动结点队列Q中 然后将其右儿子加入到活动结点队列Q中 右儿子一定可行 两个儿子结点加入后 当前扩展结点被舍弃 活动结点队列中的首结点被取出作为当前扩展结点 由于队列中每一层结点后都有一个尾部标志 1 故在取出首元素后队列一定不为空 当取出的元素为 1时 在判断当前队列是否为空 如果队列非空 则将为不标记 1加入到活结点队列中 算法开始处理下一层结点 具体程序如下 算法描述 templateVoidEnQueue Queue templateTypeMaxLoading Typew Typec intn 队列式分支限界法 返回最优载重量 初始化QueueQ 活结点队列Q Add 1 同层结点尾部标志Inti 1 当前扩展结点所处的层TypeEw 0 扩展结点所相应的载重量Bestw 0 当前最优载重量 搜索子集空间树While true 检查左儿子结点If Ew w i c x i 1Enqueue Q Ew w i bestw i n 右儿子结点总是可行的 不用检测Enqueue Q Ew w i bestw i n x i 0 Q Delete Ew 取下一扩展结点If Ew 1 同层结点尾部if Q IsEmpty returnbestw Q Add 1 同层结点尾部标志Q Delete Ew 取下一扩展结点i 进入下一层 我们可以对上边算法进行改进 因为上述算法没有用到我们的剪枝函数 当bestw是最优解 Ew是当前扩展结点所相应的重量 r是加入此结点重量后的剩余集装箱的重量 则当Ew r bestw时 可以剪去它的右分支 即不再把右分支结点加入活动结点队列 2 优先队列式分支限界法 解装载问题的优先式分支限界法将活结点表存储于一个最大堆中 活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和 活动表中优先级最大的结点成为下一个扩展结点 优先队列中活结点的优先级为x uweight 以结点x为根的子树中所有结点的载重量不超过x uweight 子集树中叶结点所相应的载重量与其优先级一样 因此在优先队列式分支限结法中 一旦有一个叶结点成为当前扩展结点 则可以断言该叶结点所相应的解即为最优解 此时可以终止算法 我们在算法的搜索过程中保存当前已构造出的部分结空间树 这样在算法确定了达到最优值的叶结点时 就可以在结空间树中从该叶结点开始向跟结点回溯 构造树相应的最优解 用一个元素类型为HeapNode的最大堆来表示活结点优先队列 其中Uweight是活结点优先级 上界 level是活结点在子集树中所处的层序号 Ptr是指向活结点在子集树中相应结点的指针 子集空间树中结点类型为bbnode 下边主要看一下实施优先队列式分支搜索的过程 函数MaxLoading具体实施这一搜索过程 在函数MaxLoading中 定义最大堆的容量为1000 第i 1层结点的剩余重量r i w j 变量E指向子集树中当前扩展结点 Ew是相应的