第六章 分支限界法.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第六章 分支限界法.ppt》由会员分享,可在线阅读,更多相关《第六章 分支限界法.ppt(51页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第6章 分支限界法 Branch and Bound 16.1 分支限界法的基本思想分支限界法的基本思想nBreadth-first search n分支限界法与回溯法分支限界法与回溯法(1)求解目标求解目标:回溯法的求解目标是找出解空间树:回溯法的求解目标是找出解空间树中满足约束条件的中满足约束条件的所有解所有解所有解所有解,而分支限界法的求解,而分支限界法的求解目标则是找出满足约束条件的目标则是找出满足约束条件的一个解一个解一个解一个解,或是在满,或是在满足约束条件的解中找出在某种意义下的足约束条件的解中找出在某种意义下的最优解最优解最优解最优解。(2)搜索方式的不同搜索方式的不同:回溯法
2、以:回溯法以深度优先的方式深度优先的方式深度优先的方式深度优先的方式搜搜索解空间树,而分支限界法则以索解空间树,而分支限界法则以广度优先或以最广度优先或以最广度优先或以最广度优先或以最小耗费优先的方式小耗费优先的方式小耗费优先的方式小耗费优先的方式搜索解空间树。搜索解空间树。6.1分支限界法的基本思想分支限界法的基本思想2分支限界法的搜索策略分支限界法的搜索策略在扩展结点处,先生成其所有的儿子结点(分支),在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。然后再从当前的活结点表中选择下一个扩展结点。为了有效的选择下一扩展结点,以加速搜索的进程,为了有效的
3、选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值,并根据这些已在每一活结点处,计算一个函数值,并根据这些已计算出的函数值,从当前活结点表中选择一个最有计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解最优解的分支推进,以便尽快地找出一个最优解。6.1分支限界法的基本思想分支限界法的基本思想36.1分支限界法的基本思想分支限界法的基本思想4分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费(最大效益)分支限界法常以广度优先或以最小
4、耗费(最大效益)优先的方式搜索问题的解空间树。优先的方式搜索问题的解空间树。此后,从活结点表中取下一结点成为当前扩展结此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或续到找到所需的解或活结点表为空时为止活结点表为空时为止。在分支限界法中,每一个活结点在分支限界法中,每一个活结点只有一次机会只有一次机会成成为扩展结点。活结点一旦成为扩展结点,就为扩展结点。活结点一旦成为扩展结点,就一次一次性产生其所有儿子结点性产生其所有儿子结点。在这些儿子结点中,导。在这些儿子结点中,导致不可行解或导致非最优解的儿子
5、结点被舍弃,致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。其余儿子结点被加入活结点表中。6.1分支限界法的基本思想分支限界法的基本思想5分枝限界法(分枝限界法(branch-and-bound)分枝限界法的思想是构成一棵树,树的每一层代表某一步的各种走法,某一待求量的各种取值或某一子问题的各种解决方案等,而树的每个终端结点表示每一种可能的最终解答。6 如果可能的解答数目太多,限于计算机容量和计算时间,不可能构成整个树,则至少构成该树的上面一些层,而将其终端结点标上一定的评价函数,以表示沿其子树进一步进行下去效果的优劣区别。对此树按类似后序遍历的次序进行分析,由每个中间
6、结点的各个子树中挑选出其中最“合适”的一个,或根据子树的评价函数确定该中间结点的评价函数。如此进行下去直至根结点为止,即得到整个问题的解答。下面举几个例子。7例1八皇后问题。这是高斯1850年提出的一个著名问题:国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子,问在88=64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃。现已知此问题共有92种解,但只有12种是独立的,其余的都可以由这12种利用对称性或旋转而得到。8为简单起见,以四皇后问题为例讲述此方法。设棋盘有44=16格,每行所摆的皇后都有四种可能的位置,四个皇后共有44=256种摆法。如将这些摆法都列出来再选其中合乎条件的方案,
7、就太费时间了。现构成一个树,根结点的四个子树表示第一行的皇后的四种可能的位置;再下一层表示第二行的位置;。设以F表示失败,S表示成功。如果上面的行已经无法摆了,则下面的行表示失败,下面的行即不必再试,返回上一层再试其它分支。9假设第一行的皇后先放在第一列,如图(a)所示,则第二行只有三、四列还可以摆。若暂先试第三列,第三行就完全无法再摆,只好回溯到上一层再试另一个分支,即第二行放第四列。这样第三行还剩第二列可以摆,但第四行又无法再摆了。此时只好返回到最上一层,改试第一行放第二列,。最后构成的树如图2所示,共有两个可行方案,实际上这是两个对称的方案。1011图212因为从所有失败的方案返回时该部
8、分子树即不必保留,所以最终内存中只保留成功方案的几条单链分支,比图中所示之树还要简单。如果每试出一个成功方案就立即输出而不必存储,或只试出一个方案就可以了,则只需一个单链,更可以节约存储量。13在用这种方法解决优化问题时(以下以最小化问题来说明,最大化问题也与此类似),如果能事先估计出每个分支的下界值,当某分支的下界值比已试过的方案的值还要高时,这整个子树即不必再考虑,因此常常可以大大节约运算时间。下面再以一个例子说明14例2分派问题。这是整数规划问题中的一种特殊问题,现举一个数字例子。设有A、B、C、D四位教师,每人都能教I、II、III、IV四门课程,但各人备各门课所需时间不同,如下表所示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六章 分支限界法 第六 分支 限界
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内