文档介绍：2017/11/11
计算机算法设计与分析
1
第六章 分支限界法
2017/11/11
计算机算法设计与分析
2
分支限界法
分支限界法也是在问题的解空间树T上搜索问题解的算法。
2017/11/11
计算机算法设计与分析
3
分支限界法的基本思想
构造问题的解空间树。
以广度优先或以最小耗费优先方式搜索解空间树。
活结点一旦成为扩展结点,就一次性产生其所有儿子结点。
不能产生可行解或肯定不能产生最优解的儿子被删除,其余的被加入活结点表中。
从活结点表中取下一结点成为当前扩展结点,重复上述过程,直至找到所需的解或活结点表为空。
怎么取?
从下一扩展结点的不同方式导致不同的分支限界法。
FIFO分支限界法
将活结点表组织成为一个队列,按先进先出原则选择下一个结点。
优先队列分支限界法
将活结点表组织成为一个优先队列,并按队列中规定的优先级来选取优先级最高的下一个结点。通常,用一个与结点相关的数值p来表示。在算法实现时,通常采用堆结构实现。
2017/11/11
计算机算法设计与分析
4
分支限界法与回溯法的比较
相同点:都是在解空间树上搜索问题解
不同点:
搜索方式不同:前者用的是深度优先搜索,后者用的是广度优先搜索或以最小耗费优先的方式搜索。
扩展结点的方式不同:前者扩展结点有多次机会成为扩展结点,后者只有一次机会。
2017/11/11
计算机算法设计与分析
5
S11
0-1背包问题的状态空间树
下面是n=3的0-1背包问题的状态空间树,其中:w=[16,15,15],p = [45,25,25],c =30 。采取队列式分支限界法。
SI
1
S1
0
S0
1
0
S10
1
S01
0
S00
1
S111
0
S110
1
S101
0
S100
1
S011
0
S010
1
S001
0
S000
S1
S10
S0
SI
S10
SI
S1
S100
S01
S00
S0
S100
2017/11/11
计算机算法设计与分析
6
搜索路径的构造
在回溯法中,每次仅考察一条路径,因而只需要构造这一条路径即可:前进时记下相应结点,回溯时删去最末尾结点的记录。这比较容易实现。
在分支限界法中,是同时考察若干条路径,那么又该如何构造搜索的路径呢?
对每一个扩展的结点,建立三个信息:
(1)该结点的名称;
(2)它的评价函数值;
(3)指向其前驱的指针;
这样一旦找到目标,即可逆向构造其路径。
2017/11/11
计算机算法设计与分析
7
分支限界法的一般算法
计算初始结点s的f(s); [s, f(s), nil]插入队列;
while (队列≠Φ) {
从队列中取出[p, f(p), x]。(根据具体方式,可以选择下一结点或f(p)为最小(大));
若p是目标,则成功返回;否则
产生p的后继,并将后继结点插入队列中(可以按照一定规则淘汰一些结点)
将[p, f(p), x]从队列中删除;
}
2017/11/11
计算机算法设计与分析
8
装载问题
有一批共n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量为wi,且。要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。
可证明,采用如下策略可以得到一个最优装载方案:先尽可能的将第一艘船装满,其次将剩余的集装箱装到第二艘船上。
这样我们要想办法尽可能的将第一艘船装满,即该问题等价于一个特殊的0-1背包问题:
2017/11/11
计算机算法设计与分析
9
用分支限界法解装载问题
可以用回溯法解装载问题,。
我们同样可以用分支限界法来解装载问题。
首先来看看用队列式分支限界法解该问题。
2017/11/11
计算机算法设计与分析
10
设置初始值,EW=0,bestw=0,i = 1
(-1) ; //同层结点尾部标志
While(true){
if(左儿子结点是活结点)
将该结点插入队列中;
将右儿子结点插入队列中;
取下一个扩展结点。
if(同层结点尾部){
if( 队列空) return 最优值;
插入同层结点尾部标记;
取下一扩展结点;
i++ ;}
}
队列式分支限界法解装载问题
数据结构:
Q:活结点队列
EW:扩展结点对应的载重量
Bestw:当前最优载重量。
X[]:对应的最优解。
计算初始结点s的f(s); [s, f(s), nil]插入队列;
while (队列≠Φ) {
从队列中取出[p, f(p), x]。(根据具体方式,可以选择下一结点或f(