第6章 分支限界法.pptx_第1页
第6章 分支限界法.pptx_第2页
第6章 分支限界法.pptx_第3页
第6章 分支限界法.pptx_第4页
第6章 分支限界法.pptx_第5页
已阅读5页,还剩41页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第六章分支限界法 1 本章主要知识点 理解分支限界法的剪枝搜索策略掌握分支限界法的算法框架队列式 FIFO 分支限界法优先队列式分支限界法通过应用范例学习分支限界法的设计策略单源最短路径问题装载问题 0 1背包问题 最大团问题 旅行售货员问题批处理作业调度问题 2 6 1分支限界法的基本思想 分支限界法与回溯法的不同 1 求解目标 回溯法的求解目标是找出解空间树中满足约束条件的所有解 而分支限界法的求解目标则是找出满足约束条件的一个解 或是在满足约束条件的解中找出在某种意义下的最优解 2 搜索方式的不同 回溯法以深度优先的方式搜索解空间树 而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树 3 6 1分支限界法的基本思想 2 分支限界法基本思想分支限界法常以广度优先或以最小耗费 最大效益 优先的方式搜索问题的解空间树 在分支限界法中 每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点 就一次性产生其所有儿子结点 在这些儿子结点中 导致不可行解或导致非最优解的儿子结点被舍弃 其余儿子结点被加入活结点表中 此后 从活结点表中取下一结点成为当前扩展结点 并重复上述结点扩展过程 这个过程一直持续到找到所需的解或活结点表为空时为止 4 6 1分支限界法的基本思想 分支限界方法找最优解的效率比回溯法高 原因在于采用了最小代价估值函数指导搜索 在活节点表中 选择有最小代价估值的节点作为扩展节点 即总是向最有可能获得最优解的子树上扩展 并且采用限界函数U杀死活节点表中不可能成为最优解的节点 提高算法的效率 5 6 1分支限界法的基本思想 比回溯法多的两个条件对于一棵解空间树上的每一个节点所代表的部分解 要计算出通过这个部分解繁衍出的任何解在目标函数上的最佳值边界目前求得的最佳解的值算法会为每一节点x计算一个界 任何可能在以x为根的子树中生成的结点所给出的解 其值都不可能超出这个界 如果边界值不能超越最佳解 这个节点就是一个没有希望的节点 这就是分支限界法的主要思想 6 6 1分支限界法的基本思想 3 常见的两种分支限界法 1 队列式 FIFO 分支限界法按照队列先进先出 FIFO 原则选取下一个节点为扩展节点 不足 对结点的选择规则相当死板 具有一定的 盲目 性 这种选择规则不利于快速检索到一个能够到达答案的结点 2 优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点 对活结点使用一个 有智能 的排序函数C 来选取下一个结点 往往可以加快获取答案的速度 最大优先队列 使用最大堆 体现最大效益优先最小优先队列 使用最小堆 体现最小费用优先 7 6 20 1背包问题 FIFO队列式分支限界法的基本思想 8 A BC EFG 活节点队列 P 45 P 50 P 25 P 25 P 0 N 3 c 30 w 16 15 15 p 45 25 25 可行性约束函数 6 20 1背包问题 优先队列式分支限界法的基本思想首先 要对输入数据进行预处理 将各物品依其单位重量价值从大到小进行排列 算法首先检查当前扩展结点的左儿子结点的可行性 如果该左儿子结点是可行结点 则将它加入到子集树和活结点优先队列中 当前扩展结点的右儿子结点一定是可行结点 仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列 当扩展到叶节点时为问题的最优值 结点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和 9 6 20 1背包问题 优先队列式分支限界法的基本思想 10 使用最大堆上界up 68 3bound inti 实现下界L 45贪心算法实现Bestp为当前最优值 则L 45 bestp up 68 3 6 20 1背包问题 11 while i n 1 非叶结点doublewt cw w i if wtbestp bestp cp p i 加入活节点队列 i 1是层数addLiveNode up cp p i cw w i i 1 enode true up bound i 1 if up bestp 检查右儿子节点 右子树可能含有最优解addLiveNode up cp cw i 1 enode false 加入活节点队列 取下一个扩展节点 略 分支限界搜索过程 可行性约束 上界约束 6 3单源最短路径问题 1 问题描述 12 下面以一个例子来说明单源最短路径问题 在下图所给的有向图G中 每一边都有一个非负边权 要求图G的从源顶点s到目标顶点t之间的最短路径 6 3单源最短路径问题 13 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树 其中 每一个结点旁边的数字表示该结点所对应的当前路长 6 3单源最短路径问题 2 算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表 其优先级是结点所对应的当前路长 算法从图G的源顶点s和空优先队列开始 结点s被扩展后 它的儿子结点被依次插入堆中 此后 算法从堆中取出具有最小当前路长的结点作为当前扩展结点 并依次检查与当前扩展结点相邻的所有顶点 如果从当前扩展结点i到顶点j有边可达 且从源出发 途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度 则将该顶点作为活结点插入到活结点优先队列中 这个结点的扩展过程一直继续到活结点优先队列为空时为止 14 6 3单源最短路径问题 3 剪枝策略在算法扩展结点的过程中 一旦发现一个结点的下界不小于当前找到的最短路长 则算法剪去以该结点为根的子树 在算法中 利用结点间的控制关系进行剪枝 从源顶点s出发 2条不同路径到达图G的同一顶点 由于两条路径的路长不同 因此可以将路长长的路径所对应的树中的结点为根的子树剪去 15 节点A控制节点 16 实例 算法过程 算法从源节点S和空优先队列开始 S被扩展 3个子节点1 2 3 被插入堆中 计算0 1 0 2 0 3当前最短路径长为2 将当前最短路径的节点1扩展 即走0 1 2 0 1 5和0 1 4 但是在计算0 1 2过程中当前最短路径为3 0 2 减掉0 1 2上以2为根的子树 将2进行扩展 走bg和bf将3进行扩展 走ch选择路径长最小0 1 5的节点5作为扩展节点 当前最短路径为4 同时减掉0 2 5路径中以5为根的子树 17 实例 算法过程 当前最短路径为4 以5作为扩展节点 走0 1 5 6和0 1 5 8 但是路径0 1 5 6的长度不小于已存的最短路径0 2 6 不再扩展 同时 减掉0 3 6路径中以6为根节点的子树 下一个活节点6成为扩展节点 走0 2 6 9和0 2 6 8 选择9节点作为扩展节点 18 实例 算法过程 当前最短路径长为6 选择9节点作为扩展节点 走0 2 6 9 8 0 2 6 9 10路径 此时0 2 6 9 8中路径长度大于0 1 5 8 所以选择0 1 5 8中节点8作为扩展节点 将节点8作为扩展节点 0 1 5 8 10路径长度大于0 2 6 9 10 选择路径0 2 6 9 10作为最短路径 从S到T的最短路径为0 2 6 9 10 长度为8 19 6 3单源最短路径问题 20 while true 搜索问题的解空间for intj 1 j n j if a enode i j Float MAX VALUE 取下一个活节点作为当前扩展节点 A 图的邻接矩阵Dist j 从源点到顶点j的最短路径顶点i和j间有边 且此路径长小于原先从原点到j的路径长 6 4布线问题 问题描述 印刷电路板将布线区域划分成n n个方格阵列 要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案 在布线时 电路只能沿直线或直角布线 为了避免线路相交 已布了线的方格做了封锁标记 其他线路不允许穿过被封锁的方格 21 举例说明 一个7 7方格阵列布线如下 起始位置是a 3 2 目标位置是b 4 6 阴影方格表示被封锁的方格 那么一条从a到b的最短布线方案如下图红色路径所示 a到b的最短距离是9 6 4布线问题 算法的思想用队列式分支限界法来考虑布线问题 布线问题的解空间是一个图从起始位置a开始将它作为第一个扩展结点 与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中 并且将这些方格标记为1 即从起始方格a到这些方格的距离为1 接着 算法从活结点队列中取出队首结点作为下一个扩展结点 并将与当前扩展结点相邻且未标记过的方格标记为2 并存入活结点队列 这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止 表示没有通路 即加入剪枝的广度优先搜索 22 2 6 4布线问题 最开始 队列中的活节点为标1的格子 随后经过一个轮次 活节点变为标2的格子 以此类推 一旦b方格成为活节点便表示找到了最优方案 为什么这条路径一定就是最短的呢 这是由于我们这个搜索过程的特点所决定的 假设存在一条由a至b的更短的路径 b结点一定会更早地被加入到活节点队列中并得到处理 23 6 4布线问题 如何构造最优解 在搜索的过程中我们虽然可以知道结点距起点的路径长度 却无法直接获得具体的路径描述 方法 从目标方格开始向起始方格回溯 逐步构造出最优解 也就是每次向标记距离比当前方格距离少1的相邻方格移动 直至到达起始方格时为止 24 6 4布线问题 算法实现 1 定义一个表示电路板上方格位置的类Position 它的2个成员row和col分别表示方格所在的行和列 在方格处 布线可沿右 下 左 上4个方向进行 沿这4个方向的移动分别记为0 1 2 3 下表中 offset i row和offset i col i 0 1 2 3 分别给出沿这4个方向前进1步相对于当前方格的相对位移 25 移动方向的相对位移 6 4布线问题 2 用二维数组grid表示所给的方格阵 初始时 grid i j 0 表示该方格允许布线 而grid i j 1表示该方格被封锁 不允许布线 为了便于处理方格边界的情况 算法在所给方格阵列的四周设置一道 围墙 即增设标记为 1 的附加方格 26 6 4布线问题 3 初始化算法开始时 测试初始方格与目标方格是否相同 如果相同 则不必计算 直接返回最短距离0 否则 算法设置方格阵列的边界 初始化位移矩阵offset 因为数字0和1用于表示方格的开放或封锁状态 所以在表示距离时不用这两个数字 算法将起始位置的距离标记为2 实际距离应为标记距离 2 4 算法搜索步骤 算法从起始位置start开始 标记所有标记距离为3的方格并存入活节点队列 然后依次标记所有标记距离为4 5 6 的方格 直到目标方格finish或活节点队列为空时为止 27 6 4布线问题 28 Position offset newPosition 4 offset 0 newPosition 0 1 右offset 1 newPosition 1 0 下offset 2 newPosition 0 1 左offset 3 newPosition 1 0 上 定义移动方向的相对位移 for inti 0 i size 1 i grid 0 i grid size 1 i 1 顶部和底部grid i 0 grid i size 1 1 左翼和右翼 设置边界的围墙 PrivatestaticbooleanfindPath 计算从start到finish的最短布线路径 找到最短路径则返回true 否则返回falseif start row finish row 相邻方格数 上下左右 29 标记可达方格位置ArrayQueueq newArrayQueue 扩展节点队列Positionnbr newPosition 0 0 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 将当前节点nbr加入队列 30 是否到达目标位置finish if nbr row finish row 存放最短路径 31 从目标位置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 newPosition nbr row nbr col 向前移动 returntrue 32 6 4布线问题 讨论 为什么这个问题用回溯法来处理就是相当低效的 回溯法的搜索是依据深度优先的原则进行的 如果我们把上下左右四个方向规定一个固定的优先顺序去进行搜索 搜索会沿着某个路径一直进行下去直到碰壁才换到另一个子路径 但是我们最开始根本无法判断正确的路径方向是什么 这就造成了搜索的盲目和浪费 更为致命的是 即使我们搜索到了一条由a至b的路径 我们根本无法保证它就是所有路径中最短的 这要求我们必须把整个区域的所有路径逐一搜索后才能得到最优解 所以 布线问题不适合用回溯法解决 33 6 5旅行售货员问题 问题描述 给定n个顶点的带权图G V E 图中各边的权为正数 图中的一条周游路线是包括V中的每个顶点在内的一条回路 一条周游路线的费用是这条路线上所有边的权之和 34 6 5旅行售货员问题 FIFO分支限界法优先队列式分支限界法剪枝函数 35 剪枝函数 设bestc是当前已经寻找到的最优解回路的最小费用 cc记录了当前已经搜索过的路径x 1 i 的费用 当cc 剩余路径的费用和 bestc时 可剪去子树 6 5旅行售货员问题 36 4 实例 FIFO队列式 队列 B CDE FGHIJK 59 66 25 26 30 35 40 6 4 14 24 11 6 5旅行售货员问题 优先队列式 37 A B C D E I H N J K P Q 1 2 3 4 2 4 4 2 3 3 2 优先队列 极小堆 B E D C H J K I C N P I Q C 4 6 30 14 24 11 26 25 25 59 6 5旅行售货员问题 算法描述 算法开始时创建一个最小堆 用于表示活结点优先队列堆中每个结点的子树费用的下界lcost值是优先队列的优先级接着计算出图中每个顶点的最小费用出边并用minout记录如果所给的有向图中某个顶点没有出边 则该图不可能有回路 算法结束如果每个顶点都有出边 则根据计算出的minout做算法初始化 38 6 5旅行售货员问题 privatestaticclassHeapNodeimplementsComparable floatlcost 子树费用的下界 优先队列的优先级floatcc 当前费用floatrcost 剩余所有结点的最小出边费用的和ints 结点在排列树中的层次int x 当前结点对应的路径 staticfloat a 图G的邻接矩阵 39 6 5旅行售货员问题 PublicstaticfloatbbTSP intv 解旅行售货员问题的优先队列式分支限界法 初始化int x newint n for inti 0 i n i x i i 1 初始化x 1 2 3 4 HeapNodeenode newHeapNode 0 0 minSum 0 x floatbestc Float MAX VALUE 当前最优值 40 6 5旅行售货员问题 搜索排列树 堆不为空且当前结点不是叶子结点时while enode null 加入活结点队列 41 循环的终止条件是排列树的一个叶结点成为当前扩展结点 6 5旅行售货员问题 else 当s n 2 产生当前扩展节点的儿子结点for inti enode s 1 i n i if a x enode s x i Float MAX VALUE 可行儿子结点floatcc enode cc a x enode s x i fl

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论