FIFO分支定界算法初探

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:46:22

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：

1 ．产生当前扩展结点的所有孩子结点；

2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；

3 ．将其余的孩子结点加入活结点表；

4 ．从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式：

1 ． FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。

2 ．最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。假如要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；假如要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。

下面通过一个具体实例加深大家对 FIFO 分支定界算法的熟悉。

例： 装箱问题 (2001 年全国青少年信息学（计算机）奥林匹克分区联赛初中组复赛试题第四题 )
[ 问题描述 ]
有一个箱子容量为 v( 正整数， 0≤v≤20000) ，同时有 n 个物品 (0≤n≤30) ，每个物品有一个体积 ( 正整数 ) 。要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
[ 样例 ]

输入：

10 一个整数，表示箱子容量

3 一个整数，表示有 n 个物品

4 接下来 n 行，分别表示这 n 个物品的各自体积。

8

5

输出：

1 一个整数，表示箱子剩余空间。

分析： 根据题目要求，要从 n 个物品中任取若干个装入箱内，使得箱子的剩余空间最小，换句话说就是要尽可能地装满箱子。只要我们找到一种装载方案，在箱子的容量范围内，它的装载值为最大，即装入箱子的这些物品的体积之和为最大，那么箱子的容量与最优装载值之差就是问题的答案（最小剩余空间）。

要寻找这样一个最优装载值，我们不妨先考察一个简单的例子。比如：箱子容量 v=10 ，物品个数 n=3 ，第 1 个物品的体积 tiji[1] =4 ，第 2 个物品的体积 tiji[2] =8 ，第 3 个物品的体积 tiji[3] =5 。利用分支定界算法求解，首先要将问题的解空间组织成一棵树，如图。对于每一个物品，只有装入箱子和不装入箱子两种可能，我们用结点的两个孩子分别表示这两种可能，规定左孩子表示相应的物品装入箱子，右孩子表示相应的物品不装入箱子。树中结点左上角的数字为该结点对应的权值。例如 A 的左孩子 B 表示将第 1 个物品装入箱子， B 的权值 4 表示在结点 B 处，箱子中已装入物品的体积之和为 4 ；而 A 的右孩子 C 表示第 1 个物品不被装入箱子， C 的权值 0 则表示在结点 C 处，箱子中已装入物品的体积之和为 0 。同样， D 、 F 都表示将第 2 个物品装入箱子， D 的权值 12 表示在结点 D 处，箱子中已装入物品的体积之和为 12 ，……这样，解空间树中每一条从根结点到叶子结点的路径就表示一种可能的装载方案（暂时不考虑装载过程中必须满足的条件）。

在搜索过程中，我们设置变量 best 来保存当前的最优装载值。搜索从根结点 A 开始， A 是当前的扩展结点，此时活结点表中只有一个元素 -1 （标记本层尾部）， best=0 。按照分支定界算法的搜索策略，首先产生当前扩展结点 A 的孩子结点 B 和 C ；其次，在产生结点 B 和 C 的过程中，根据一定的条件（限界函数），抛弃不可能产生可行解（或最优解）的结点；再次，将剩下的 A 的孩子结点加入活结点表；最后，从当前的活结点表中取出下一个活结点作为新的扩展结点。如此重复，直到活结点表为空。

接下来还有一个问题，在产生当前扩展结点的孩子结点的过程中，孩子结点能否产生可行解（或最优解），怎样进行判定？即需要什么样的限界函数。

仔细分析题目要求，我们很轻易发现，题目中隐含着一个基本条件：装入箱子中的所有物品的体积之和不能超出箱子的容量，即：所装物品的体积之和 <= 箱子容量。另外，在对解空间树进行搜索的过程中，假如发现某子树不可能产生比当前最优解还要优的解，我们就没有必要对这棵子树进行搜索。这样处理可以加快搜索速度，提高程序的性能。令 Z 为解空间树第 i 层的一个结点， best 的定义如前， ew 为当前所装物品的体积之和。以 Z 为根的子树中没有叶结点的装载值会超过 ew+r ， 其中 r= 为剩余物品的体积之和

。因此，当 ew+r<=best 时，没有必要去搜索 Z 的右子树。

根据上面分析，可归纳算法程序如下：

1 ．输入基本数据；

2 ．建立活结点表；

3 ．基本变量初始化；

4 ．搜索解空间树。

其中，第 4 步需要进一步求精。

While true do

{ 检查左孩子 }

if 左孩子的权值 <= 箱子容量 then

if 当前装载体积 > 最优装载值 (best) then

best= 当前装载体积

endif

if 不是叶子结点 then

将左孩子结点加入活结点表中

endif

{ 检查右孩子 }

if 可以有一个更好的叶子结点 then

将右孩子结点加入活结点表中

endif

endif

从当前活结点表中取下一个结点作为新的扩展结点

if 到达层的尾部 then

if 活结点表为空 then

输出问题的解

结束对解空间树的搜索

endif

添加尾部标记

从当前活结点表中取下一个结点作为新的扩展结点

产生新的层号 i

产生新的 r （剩余物品的体积之和）

endif

end{while}

第 2 步活结点表的建立，可以使用队列来实现。分支定界算法的解空间比回溯算法大得多，因此在建立队列的时候，最好使用链队列，这样可以提高程序的性能。 QBASIC 语言不支持指针这种数据类型，假如用 QBASIC 语言进行编程，链队列的建立将会变得比较困难。所以，下面的参考程序，我们将以 PASCAL 语言给出。

PASCAL 语言参考程序如下：

program c2001_4(input,output);

type{ 链队列抽象数据类型说明 }

queueptr=^queuenode;

queuenode=record

data:integer;{ 数据域 }

next:queueptr{ 指针域 }

end;

linkedquetp=record

front,rear:queueptr

{front 为队头指针， rear 为队尾指针 }

end;

var

v,n,i,j,x,ew,wt,best,r:integer;

p,s:queueptr;

q:linkedquetp;

tiji:array[1..30]of integer;

flag:boolean;

procedure init_linkedqueue(var q:linkedquetp);

{ 设置一个空的链队列 }

begin

new(q.front);q.rear:=q.front

q.front^.next:=nil

end;

procedure add(var q:linkedquetp;x:integer);

{ 在已知链队列 q 中插入队尾元素 x}

begin

new(p);p^.data:=x;p^.next:=nil;

q.rear^.next:=p;q.rear:=p

end;

function delete(var q:linkedquetp):integer;

{ 若链队列 q 不空，则删除队尾元素并返回该元素，否则返回 -2}

begin

if q.front=q.rear

then delete:=-2

else begin

s:=q.front^.next;

q.front^.next:=s^.next;

if s^.next=nil then q.rear:=q.front;

x:=s^.data;

dispose(s);

delete:=x

end

end;

function empty(q:linkedquetp):boolean;

{ 若链队列 q 为空队列，则返回函数值“ true ”，否则返回函数值“ false ” }

begin

if q.rear=q.front

then empty:=true

else empty:=false

end;

begin

{ 输入 }

write('Please input V:');readln(v);

write('Please input N:');readln(n);

writeln('Please input tiji:');

for i:=1 to n do

readln(tiji[i]);

init_linkedqueue(q);{ 建立活结点表（表中记录着各活结点对应的权值） }

add(q,-1);{ 向活结点表添加元素 -1 ，标记本层尾部 }

i:=1;ew:=0;best:=0;r:=0;flag:=true;{i ：扩展结点的层； ew ：扩展结点的权值； best ：目前最优装载值； r ：剩余物品的体积之和； flag ：循环控制变量（用来标识是否结束循环，若活结点表为空，则 flag=false ，退出循环） }

for j:=2 to n do

r:=r+tiji[j];

while flag do

{ 搜索解空间树 }

begin

wt:=ew+tiji[i];{ 产生左孩子的权值 }

if wt<=v{ 可行的左孩子 }

then begin

if wt>best

then best:=wt;

if i<n

{ 若不是叶子结点，则添加到活结点表中 }

then add(q,wt)

end;

{ 检查右孩子 }

if (ew+r>best) and (i<n)

{ 可以有一个更好的叶子 }

then add(q,ew);

{ 将右孩子添加到活结点表中 }

ew:=delete(q);{ 从活结点表中取下一个活结点作为新的扩展结点 }

if ew=-1{ 到达层的尾部 }

then begin

if empty(q){ 活结点表为空 }

then begin

writeln('best=',v-best);

{ 输出最优剩余空间值 }

flag:=false

{ 结束循环的条件成立 }

end;

add(q,-1);{ 添加尾部标记 }

ew:=delete(q);{ 从活结点表中取下一个活结点作为新的扩展结点 }

i:=i+1;{ 改变层号 }

r:=r-tiji[i]

{ 改变剩余物品的体积之和 }

end

end

end.

结束语： 分支定界算法和回溯算法是在问题的解空间上搜索问题的解的两种基本方法，回溯算法通常采用深度优先的方法搜索解空间树，而分支定界算法则采用广度优先或最小耗费优先的方法搜索解空间树。很多能够使用分支定界算法解决的问题，都可以使用回溯算法加以解决。大家在学习的时候，对同一个问题要多尝试不同的方法，将它们加以比较，这样不但可以找到较好的解决方案，还可以加深大家对不同算法思想的理解。

上一篇：{应用}初识回溯算法 人气:4668
下一篇：{应用}初识动态规划算法 人气:6889

C语言程序设计视频教程