算法课件六分支定界

LOGO1v1 1 概述概述v2 2 分支限界法分支限界法v3 3 应用举例应用举例11 概述概述1LOGO21.1.概述概述v搜索法搜索法在动态产生问题的解空间，并搜索问题的可行在动态产生问题的解空间，并搜索问题的可行解或最优解。解或最优解。在生成的结点中，抛弃那些不满足约束条件在生成的结点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点。（或者说不可能导出最优可行解）的结点。v搜索方式搜索方式深度优先搜索深度优先搜索广度优先搜索广度优先搜索21.概述搜索法概述搜索法2LOGO31.1.概述概述v方法方法1 1：深度优先搜索：深度优先搜索通常深度优先搜索法不全部保留结点，扩展完通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效生内存溢出时，深度优先搜索不失为一种有效的求解方法。的求解方法。31.概述方法概述方法1：深度：深度优优先搜索先搜索3LOGO41.1.概述概述v方法方法2 2：广度优先搜索：广度优先搜索广度优先搜索算法，一般需存储产生的所有结广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存因此，程序设计中，必须考虑溢出和节省内存空间的问题。空间的问题。但广度优先搜索法一般无回溯操作，即入栈和但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索快。出栈的操作，所以运行速度比深度优先搜索快。41.概述方法概述方法2：广度：广度优优先搜索先搜索4LOGO52.2.分支限界法分支限界法采用广度优先产生状态空间树的结点，并使用剪采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为枝函数的方法称为分支限界法分支限界法。所谓所谓“分支分支”是采用广度优先的策略，依次生是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。成扩展结点的所有分支（即：儿子结点）。所谓所谓“限界限界”是在结点扩展过程中，计算结点是在结点扩展过程中，计算结点的的上界上界（或（或下界下界），边搜索边减掉搜索树的某），边搜索边减掉搜索树的某些分支，从而提高搜索效率些分支，从而提高搜索效率52.分支限界法采用广度分支限界法采用广度优优先先产产生状生状态态空空间树间树的的结结点，并使用剪点，并使用剪5LOGO6分支限界算法思想分支限界算法思想v对对对对E-E-节点的扩充方式：引入节点的扩充方式：引入节点的扩充方式：引入节点的扩充方式：引入活节点表活节点表活节点表活节点表v【思想】每个活节点有且仅有一次机会变成【思想】每个活节点有且仅有一次机会变成【思想】每个活节点有且仅有一次机会变成【思想】每个活节点有且仅有一次机会变成 E-E-节点。节点。节点。节点。当一个节点变为当一个节点变为当一个节点变为当一个节点变为E-E-节点时，则生成从该节点移动一节点时，则生成从该节点移动一节点时，则生成从该节点移动一节点时，则生成从该节点移动一步即可到达的所有新节点。步即可到达的所有新节点。步即可到达的所有新节点。步即可到达的所有新节点。在生成的节点中，在生成的节点中，在生成的节点中，在生成的节点中，抛弃抛弃抛弃抛弃那些不可能导出（最优）可行解的节点，其余节点那些不可能导出（最优）可行解的节点，其余节点那些不可能导出（最优）可行解的节点，其余节点那些不可能导出（最优）可行解的节点，其余节点加入加入加入加入活节点表，然后从表中选择一个节点作为下一活节点表，然后从表中选择一个节点作为下一活节点表，然后从表中选择一个节点作为下一活节点表，然后从表中选择一个节点作为下一个个个个E-E-节点。节点。节点。节点。v从活节点表中取出所选择的节点并进行扩充，直到从活节点表中取出所选择的节点并进行扩充，直到从活节点表中取出所选择的节点并进行扩充，直到从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。找到解或活动表为空，扩充过程才结束。找到解或活动表为空，扩充过程才结束。找到解或活动表为空，扩充过程才结束。6分支限界算法思想分支限界算法思想对对E-节节点的点的扩扩充方式：引入活充方式：引入活节节点表点表6LOGO7不同的活结点表形成不同的分枝限界法：不同的活结点表形成不同的分枝限界法：FIFOFIFO分支限界法分支限界法（队列式分支限界法）：活结（队列式分支限界法）：活结点表是先进先出队列点表是先进先出队列LIFOLIFO分支限界法分支限界法:活结点表是堆栈活结点表是堆栈最小耗费或最大收益法分支限界法最小耗费或最大收益法分支限界法（优先队列（优先队列式分支限界法）式分支限界法）:活结点表是优先权队列，活结点表是优先权队列，LCLC分分支限界法将选取具有最高优先级的活结点出队支限界法将选取具有最高优先级的活结点出队列，成为新的扩展结点。列，成为新的扩展结点。几种常见的分支限界法几种常见的分支限界法7不同的活不同的活结结点表形成不同的分枝限界法：几种常点表形成不同的分枝限界法：几种常见见的分支限界法的分支限界法7LOGO8FIFO分支定界法分支定界法v在解空间树上的在解空间树上的在解空间树上的在解空间树上的FIFOFIFO法，类似从根节点出发的法，类似从根节点出发的法，类似从根节点出发的法，类似从根节点出发的BFSBFS方法；方法；方法；方法；v与与与与BFSBFS的区别在于：在的区别在于：在的区别在于：在的区别在于：在FIFOFIFO分支定界中，不可行分支定界中，不可行分支定界中，不可行分支定界中，不可行的节点不会被搜索！的节点不会被搜索！的节点不会被搜索！的节点不会被搜索！8FIFO分支定界法在解空分支定界法在解空间树间树上的上的FIFO法，法，类类似从根似从根节节点出点出8LOGO9示例示例1：0/1背包问题解背包问题解1vFIFOFIFO分支定界分支定界分支定界分支定界vn=3,w=20,15,15,p=40,25,25,c=30n=3,w=20,15,15,p=40,25,25,c=30E-E-节点节点节点节点 活节点表活节点表活节点表活节点表A AB B C CB BC C E EC CE EF F GGE EF F GG解解解解1 1：1,0,0,1,0,0,收益收益收益收益4040F FGG解解解解2 2：0,1,1,0,1,1,收益收益收益收益5050GGNULLNULL20352015353015159示例示例1：0/1背包背包问题问题解解1FIFO分支定界分支定界n=3,w=9LOGO10最大收益最大收益-分支定界思想分支定界思想vv使用一个最大堆：其中的使用一个最大堆：其中的使用一个最大堆：其中的使用一个最大堆：其中的 E-E-节点按照每个活节点收益值节点按照每个活节点收益值节点按照每个活节点收益值节点按照每个活节点收益值的的的的降序降序降序降序，或是按照活节点任意子树的叶节点所能获得的收，或是按照活节点任意子树的叶节点所能获得的收，或是按照活节点任意子树的叶节点所能获得的收，或是按照活节点任意子树的叶节点所能获得的收益估计值的益估计值的益估计值的益估计值的降序降序降序降序从队列中取出。从队列中取出。从队列中取出。从队列中取出。vvFIFOFIFO分支分支分支分支-限界算法用队存储活结点，优先队列式分支限限界算法用队存储活结点，优先队列式分支限限界算法用队存储活结点，优先队列式分支限限界算法用队存储活结点，优先队列式分支限界法用堆存储活结点，以保证比较优良的结点先被扩展。界法用堆存储活结点，以保证比较优良的结点先被扩展。界法用堆存储活结点，以保证比较优良的结点先被扩展。界法用堆存储活结点，以保证比较优良的结点先被扩展。且对于优先队列式分支限界算法，一旦扩展到叶结点就已且对于优先队列式分支限界算法，一旦扩展到叶结点就已且对于优先队列式分支限界算法，一旦扩展到叶结点就已且对于优先队列式分支限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。经找到最优解，可以停止搜索。经找到最优解，可以停止搜索。经找到最优解，可以停止搜索。vv采用广度优先搜索策略的目的是采用广度优先搜索策略的目的是采用广度优先搜索策略的目的是采用广度优先搜索策略的目的是:尽早发现剪枝点。尽早发现剪枝点。尽早发现剪枝点。尽早发现剪枝点。10最大收益最大收益-分支定界思想使用一个最大堆：其中的分支定界思想使用一个最大堆：其中的 E-节节点按点按10LOGO11 个元素的序列个元素的序列当且仅当满足下述关系时，称之为堆当且仅当满足下述关系时，称之为堆或或堆11 个元素的序列当且个元素的序列当且仅仅当当满满足下述关系足下述关系时时，称之，称之为为堆或堆堆或堆11LOGO13示例示例2：旅行商问题：旅行商问题vFIFO分支定界分支定界E-E-节点节点节点节点 活节点表活节点表活节点表活节点表B BC CD D E EF F GGC C D D E EE EF F GG HHI I J JKKF F路径路径路径路径1234112341，5959GG路径路径路径路径1243112431，6666HH路径路径路径路径1324113241，2525I IJ JKK路径路径路径路径13421342，不展开，不展开，不展开，不展开路径路径路径路径1423114231，2525路径路径路径路径14321432，不展开不展开不展开不展开13示例示例2：旅行商：旅行商问题问题FIFO分支定界分支定界E-节节点点 活活节节13LOGO14示例示例2解法解法2：最小耗费法：最小耗费法v使用最小堆存储活节点使用最小堆存储活节点E-E-节点节点节点节点 活节点表活节点表活节点表活节点表B BE E D D C CE ED DJ JKK C CD DHHJ JKKI IC CHH路径路径路径路径1324113241，2525【定界函数定界函数】如果一个如果一个节点的定界值不比当前节点的定界值不比当前最优旅行更小，则将被最优旅行更小，则将被删除而不被展开！删除而不被展开！306424141126【注注】活节点表采用堆结构活节点表采用堆结构35 405521192914示例示例2解法解法2：最小耗：最小耗费费法使用最小堆存法使用最小堆存储储活活节节点点E-节节点点 14LOGO0-1背包问题解背包问题解3：最大收益法：最大收益法v假设有4个物品，重量分别是（4,7,5,3），价值分别是（40,42,25,12），背包容量是W=10。v单位重量价值分别为：（10,6,5,4）0-1背包背包问题问题解解3：最大收益法假：最大收益法假设设有有4个物品，重量分个物品，重量分别别是（是（415LOGO算法算法课课件六分支定界件六分支定界16LOGO17o队列式分支限界法程序框架队列式分支限界法程序框架o设设T为状态空间树的根结点；初始化队列为状态空间树的根结点；初始化队列Q；o将将T入队；入队；o循环，直到队列循环，直到队列Q空（无解）：空（无解）：o 结点结点e出队；出队；o 若若e是回答结点，则是回答结点，则o 输出解或求解路径；输出解或求解路径；o 否则否则o 检查检查e的所有子结点的所有子结点x：o 若若x满足约束条件，则满足约束条件，则 o 将将x入队；入队；o 记录搜索路径；记录搜索路径；17队队列式分支限界法程序框架列式分支限界法程序框架17LOGO18v优先队列式分支限界法程序框架优先队列式分支限界法程序框架设T为状态空间树的根结点；C(x)为耗费估计函数；初始化优先队列Q；计算C(T)，并将T入队；循环，直到队列Q空（无解）：结点e出队；若e是回答结点，则 输出解或求解路径，求解结束；否则 检查e的所有子结点x：若x满足约束条件，则 计算C(x)，并将x入队；记录搜索路径；18优优先先队队列式分支限界法程序框架列式分支限界法程序框架18LOGO算法算法课课件六分支定界件六分支定界19LOGO示例3：装载问题1.问题描述有一批共个集装箱要装上有一批共个集装箱要装上2 2艘载重量分别为艘载重量分别为C1C1和和C2C2的轮船，其中集的轮船，其中集装箱装箱i i的重量为的重量为WiWi，且，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这这2 2艘轮船。如果有，找出一种装载方案。艘轮船。如果有，找出一种装载方案。容容易易证证明明：如如果果一一个个给给定定装装载载问问题题有有解解，则则采采用用下下面面的的策策略略可可得得到到最优装载方案。最优装载方案。(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。示例示例3：装：装载问题载问题1.问题问题描述有一批共个集装箱要装上描述有一批共个集装箱要装上2艘艘载载20LOGO 问问题题描描述述：印印刷刷电电路路板板将将布布线线区区域域划划分分成成n*mn*m个个方方格格阵阵列列。精精确确的的电电路路布布线线问问题题要要求求确确定定连连接接方方格格a a的的中中点点到到方方格格b b的的中中点点的的最最短短布布线线方方案案。在在布布线线时时，电电路路只只能能沿沿直直线线或或直直角角布布线线。为为了了避避免免线线路路相相交交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格示例示例4：布线问题：布线问题 问题问题描述：印刷描述：印刷电电路板将布路板将布线线区域划分成区域划分成n*m个方格个方格阵阵列列21LOGO 布线问题适合采用队列式分支限界法来解决。布线问题适合采用队列式分支限界法来解决。从从起起始始位位置置a a开开始始将将它它作作为为第第一一个个扩扩展展结结点点。与与该该结结点点相相邻邻并并且且可可达达的的方方格格被被加加入入到到活活结结点点队队列列中中，并并且且将将这这些些方方格格标标记记为为1 1，表表示示它它们们到到a a的的距离为距离为1 1 接接着着从从活活结结点点队队列列中中取取出出队队首首作作为为下下一一个个扩扩展展结结点点，并并将将与与当当前前扩扩展展结结点点相相邻邻且且未未标标记记过过的的方方格格标标记记为为2 2，并并存存入入活活节节点点队队列列。这这个个过过程程一一直直继续到算法搜索到目标方格继续到算法搜索到目标方格b b或活结点队列为空时为止（表示没有通路）或活结点队列为空时为止（表示没有通路）布布线问题线问题适合采用适合采用队队列式分支限界法来解决。列式分支限界法来解决。22LOGO最开始，队列中的活结点为标最开始，队列中的活结点为标1 1的格的格子，随后经过一个轮次，活结点变为标子，随后经过一个轮次，活结点变为标2 2的的格子，以此类推，一旦格子，以此类推，一旦b b方格成为活节点便方格成为活节点便表示找到了最优方案。为什么这条路径一表示找到了最优方案。为什么这条路径一定就是最短的呢？这是由于我们这个搜索定就是最短的呢？这是由于我们这个搜索过程的特点所决定的，假设存在一条由过程的特点所决定的，假设存在一条由a a至至b b的更短的路径，的更短的路径，b b结点一定会更早地被加结点一定会更早地被加入到活结点队列中并得到处理。入到活结点队列中并得到处理。最开始，最开始，队队列中的活列中的活结结点点为标为标1的格子，随后的格子，随后经过经过一个一个轮轮次，活次，活结结点点23LOGO问题：问题：FIFO搜索或搜索或LIFO搜索也可以通过加入搜索也可以通过加入“限界限界”策略加速搜索，与优先队列式分支限界法策略加速搜索，与优先队列式分支限界法LC-检索检索的区别在哪儿呢？的区别在哪儿呢？答案：答案：由于由于FIFO搜索或搜索或LIFO搜索是盲目地扩展结点，搜索是盲目地扩展结点，当前最优解距真正的最优解距离较大，作为当前最优解距真正的最优解距离较大，作为“界界”所起所起到的剪枝作用很有限，不能有效提高搜索速度。到的剪枝作用很有限，不能有效提高搜索速度。问题问题：FIFO搜索或搜索或LIFO搜索也可以通搜索也可以通过过加入加入“限界限界”策略加策略加24LOGO25作业作业v实现旅行商问题的分支限界实现旅行商问题的分支限界实现旅行商问题的分支限界实现旅行商问题的分支限界FIFOFIFO、优先队列求解、优先队列求解、优先队列求解、优先队列求解v实现实现实现实现0-10-1背包问题的分支限界背包问题的分支限界背包问题的分支限界背包问题的分支限界FIFOFIFO、优先队列求、优先队列求、优先队列求、优先队列求解解解解v*印刷电路板排列问题印刷电路板排列问题印刷电路板排列问题印刷电路板排列问题v要求：要求：要求：要求：必做：旅行商问题、必做：旅行商问题、必做：旅行商问题、必做：旅行商问题、0-10-1背包问题任选一题完成背包问题任选一题完成背包问题任选一题完成背包问题任选一题完成 选做：印刷电路板排列问题选做：印刷电路板排列问题选做：印刷电路板排列问题选做：印刷电路板排列问题 提交代码和报告提交代码和报告提交代码和报告提交代码和报告 报告内容：分析所实现问题的程序执行过程报告内容：分析所实现问题的程序执行过程报告内容：分析所实现问题的程序执行过程报告内容：分析所实现问题的程序执行过程25作作业实现业实现旅行商旅行商问题问题的分支限界的分支限界FIFO、优优先先队队列求解列求解25LOGO算法算法课课件六分支定界件六分支定界26LOGO算法算法课课件六分支定界件六分支定界27LOGO算法算法课课件六分支定界件六分支定界28LOGO算法算法课课件六分支定界件六分支定界29LOGO算法算法课课件六分支定界件六分支定界30LOGO算法算法课课件六分支定界件六分支定界31