1、完整版分支限界算法作业分配问题分支限界法的研究与应用摘 要： 分支限界法与回溯法的不同:首先,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。其次，回溯法以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。再者，回溯法空间效率高；分支限界法往往更“快”。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点
2、中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。常见的分支限界法有：队列式分支限界法，按照队列先进先出原则选取下一个结点为扩展结点。栈式分支限界法，按照栈后进先出原则选取下一个结点为扩展结点。优先队列式分支限界法，按照规定的结点费用最小原则选取下一个结点为扩展结点（最采用优先队列实现）。分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中
3、,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。关键词： 分支限界法 回溯法 广度优先 分支搜索法 第1章 绪论 31.1 分支限界法的背景知识 31.2 分支限界法的前景意义 32.2 分支限界法的一般性描述 6第3章 作业分配问题 73.1 问题描述 73.2 问题分析 73.3 算法设计 83.4 算法实现 103.5 测试结果与分析 12第4章 结论 13参考文献 14第1章 绪论1.1 分支限界法的背景知识 分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有
4、的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。（1) FIFO搜索先进先出搜索算法要依赖“队”做基本的数据结构。一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点为当前扩展结点,直到找到一个解或活结点队列为空为止。（2) LIFO搜索后进先出搜索算法要依赖“栈”做基本的数据结构。一开始,根结点入栈.从栈中弹出一个结点为当前扩展结点。
5、对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再众栈中弹出一个结点为当前扩展结点,，直到找到一个解或栈为空为止。（3）优先队列式搜索为了加速搜索的进程，应采用有效地方式选择E-结点进行扩展。优先队列式搜索，对每一活结点计算一个优先级， 并根据这些优先级，从当前活结点表中优先选择一个优先级最高的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。1.2 分支限界法的前景意义在现实生活中，有这样一类问题：问题有n个输入，而问题的解就由n个输入的某种排列或某个子集构成，只是这个排列或子集必须满足某些事先给定的条件。把那些必
6、须满足的条件称为约束条件；而把满足约定条件的排列或子集称为该问题的可行解。满足约束条件的子集可能不止一个，也就量说可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也可能给出了一定的标准，这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值的可行解，称为最优解。如工作安排问题，任意顺序都是问题的可行解，人们真正需要的是最省时间的最优解。用回溯算法解决问题时，是按深度优先的策略在问题的状态空间中，尝试搜索可能的路径，不便于在搜索过程中对不同的解进行比较，只能在搜索到所有解的情况下，才能通过比较确定哪个是最优解。这类问题更适合用广度优先策略搜索，因为在扩展结点时，可以在E-结点
7、的各个子结点之间进行必要的比较，有选择地进行下一步扩展。分支限界法就是一种比较好的解决最优化问题的算法。分支限界法是由“分支”策略和“限界”策略两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索；“限界”策略是为了加速搜索速度而采用启发信息剪枝的策略。第2章 分支限界法的理论知识2.1 问题的解空间树 1 x1=1 x1=0 2 3 x2=1 x2=0 x2=1 x2=0 4 5 6 7x3=1 x3=0 x3=1 x3=0 x3=1 x3=0 x3=1 x3=0 8 9 10 11 12 13 14 15子集树在FIFO分支搜索方法中,在搜索当前E-结点全部儿子后,其儿子成为
8、活结点,E-结点变为死结点;活结点存储在队列中,队首的活结点出队后变为E-结点,其再生成其他活结点的儿子直到找到问题的解或活结点队列为空搜索完毕.这里采用地构造解空间二叉树的方法,问题的解就是二叉树中的某一个分支.这个解是要搜索到二叉树的叶结点才能确定的,且只须记录最优解的叶结点,就能找到问题的解.比较方便的存储方式是二叉树要有指向父结点的指针,以便从叶结点回溯解的方案.又为了方便知道当前结点的情况,还要记录当前结点是父结点的哪一个儿子.FIFO分支搜索算法框架如下:假定问题解空间树为T,T至少包含一个解结点(答案结点).u为当前的最优解,初值为一个较大的数;E表示当前扩展的活结点,x为E的儿
9、子,s(x)为结点x下界函数,当其值比u大时,不可能为最优解,不断续搜索此分支,该结点不入队;当其值比u小时,可能达到最优解,断续搜索此分支,该结点入队;cost(X)当前叶结点所在分支的解.search(T) leaf=0; 初始化队; ADDQ(T); parent(E)=0; while(队不空) DELETEQ(E) for(E的每个儿子X) if(s(X)u) ADD Q(X); parent(X)=E; if(X是解结点) U=min(cost(X),u); leaf=x; printf(least cost=%f,u); while(leaf!=0) printf(%f,leaf
10、); leaf=parent(leaf);找最小成本的LC分支-限界算法框架与FIFO分支-限界算法框架结构大致相同,只是扩展结点的顺序不同,因而存储活结点的数据结构不同.FIFO分支-限界算法用队存储活结点,LC分支-限界算法用堆存储活结点,以保证比较优良的结点行被扩展.且对于LC分支-限界算法,当扩展到叶结点就已经找到最优解,可以停止搜索.2.2 分支限界法的一般性描述分支限界有3种不同的搜索方式:FIFO、LIFO和优先队列。对于先进先出搜索(FIFO),其算法要依赖“队”做基本的数据结构。一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结
11、点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点为当前扩展结点,直到找到一个解或活结点队列为空为止。对于后进先出搜索(LIFO),其算法要依赖“栈”做基本的数据结构。一开始,根结点入栈.从栈中弹出一个结点为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈,再众栈中弹出一个结点为当前扩展结点,，直到找到一个解或栈为空为止。对于优先队列式扩展方式，不加入限界策略其实是无意义的，因为要说明解的最优性，必需搜索完问题全部解空间，才能下结论。优先队列式搜索通过结点的优先级，可以使
12、搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后将当前最优解作为一个“标准”，对上界（或下界）不可能达到（或大于）这个“标准”的分支，则不去进行搜索，这样剪枝的效率更高，能较好地缩小搜索范围，从而提高搜索效率。这种搜索策略称为优先队列式分支限界法，即“LC-检索”。优先队列式分支限界法进行算法设计的要点如下：（1）结点扩展方式：无论哪种分支限界法，都需要有一张活结点表。优先队列的分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。（2）结点优先级确定：优先队列中结点优先级常规定为一个与该结点相关的数
13、值w，w一般表示以该结点为根的子树中的分支（其中最优的分支）接近最优解的程度。（3）优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考试到搜索算法每次只扩展一个结点，使用数据结构中介绍的堆排序比较合适，这样每次扩展结点时，比较交换的次数最少。第3章 作业分配问题3.1 问题描述题1:作业分配问题：设有A,B,C,D,E, 等n个人从事J1,J2,J3,J4,J5,等n项工作，每人只能从事一项任务，每个任务由不同的工人从事有着不同的费用，求最佳安排使费用最低。要求：输出每人所从事的工作任务以及最佳安排的最低费用。题2: 有两艘船和需要装运的n个货
14、箱，第一艘船的载重量是c1，第二艘船的载重量是c2，Wi是货箱i的重量，且W1+W2+W3+W4+.+Wn=c1+c2。希望确定是否有一种可将所有n个货箱全部装船的方法。要求:输出每艘船最终载重量.3.2 问题分析分支搜索法是一种在问题解空间上进行搜索尝试的算法。是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：(1)产生当前
15、扩展结点的所有孩子结点；(2)在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；(3)将其余的孩子结点加入活结点表；(4)从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解（最优解）或活结点表为空。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。题1:先看一个实例,设有A,B,C,D,E 5人从事J1,J2,J3,J4,J5项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。J1J2J3J4J5A10111047B13101085C59774D151210115E1011884要求：输出每人所从事的工
16、作项目以及最佳安排的最高效益。考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务J1分配给人员A,任务J2分配给人员B,任务J3分配给人员C,任务J4分配给D,任务J5分配给E,其总效益是10+10+7+11+4=42;或者应用贪心法求得一个近似解:人员A从事J2时效益最大,将任务J2分配给人员A,剩余工作中人员B从事J1时效益最大,任务J1分配给人员B,J3、J4、J5中人员D从事J4时效益最大,任务J4分配给人员D,J3和J5中人员C从事J3时效益最大,任务J3分配给人员C,任务J5只能分配给人员E,其总效益是11+13+11+7+4=46.显然,42和46都不能确定是最优
17、解,有可能还有比其更大的效益,这两个解其一并不一定是一个最可行的选择,它们仅仅提供了一个参考,这样,可以以其中一个作为参考来进一步对各种作业分配方案进行搜索,比较其每种分配方式的效益.最大的总效益为最优解,其分配方案为最佳分配方案.题2: 先看一个实例,当n=3,c1=c2=50,w=10,40,40时,可将货箱1,2装到第一艘船上,货箱3装到第二艘船上.但如果w=20,40,40,则无法将货箱全部装船.由此可知问题可能有解,可能无解,也可能有多解.下面以找出问题的一个解为目标设计算法.虽然是关于两艘船的问题,其实只讨论一艘船的最大装载问题即可.因为当第一艘船的最大装载为bestw时,若w1+
18、w2+wn-bestw=c2则可以确定一种解,否则问题就无解.这样问题转化为第一艘船的最大装载问题.3.3 算法设计题1:问题的解空间为一个子集树,所有可能的解都可通过一个求解树给出.也就是算法要考虑任务是否分配给人员的情况组合,n个任务分配给n个人员的组合共n*n种情况,作业分配子集树是n=4的子集树它是用FIFO分支搜索算法解决该问题的扩展结点的过程编号的. 1 个人作业分配 2 3 1 3 4 2 2 4 5 3 4 5 3 5 4 5 5 4 4作业分配子集树在任务分配中,如实例中若n=4时,J1分配给A则向左走,否则往右走,直到走到最后,把最终的总效益求出,并把第一次求出的总效益作为
19、最大效益与后边的总效益相比较,比其大者,交换两者,大的作为最大效益.依次方法,直到找到最优解,并输出其值以及其最大效益时的最佳分配方案.(1)用FIFO分支搜索所有的分支,并记录已搜索分支的最优解,搜索完子集树也就找出了问题的解.图中结点1为第零层,是初始E-结点;扩展后结点2,3为第一层;3,4,2是第一个任务分配出去后的下一层扩展结点,4,5,3,4,5是第二个任务分配出去后下一层的扩展结点(即分配情况).(2)用taski来表示任务是否分配及分配了给哪个工人,即taski=0时表示任务i未分配, taski=j表示任务i分配给了工人j;用workerk=0或1来表示工人k是否分配了任务,
20、 workerk=0表示工人k未分配任务, workerk=1表示工人k已分配了任务.(3)把最低费用用mincost来表示和cij表示工人j执行任务i时的费用,并把cij和mincost分别初始化为c10001000和100000;同时把aski和tempi、workeri的存储空间初始为task1000和temp1000、worker1000,之后把其初始化为0.(4)用Plan(int k,unsigned int cost)来对分配作业的解空间树进行搜索,搜索的时候,每个活结点要记录下搜索的路径(即分配方案),存储在tempi中,并求出费用cost,然后cost与最小费用mincost
21、进行比较,较小者是最小费用,其分配方案为最佳分配方案.(5)下面的算法中用Plan(int k,unsigned int cost)中的第二个for循环来实现对解空间树的搜索, 第一次for(i=0)时，找出0号工人分别执行0，1，2，3，4号任务时总花费最小; 第二次for(i=1)时，找出1号工人分别执行除0号工人的任务以外任务时总花费最小，并与i=0时的总花费最小比较; 第五次for(i=4)时，找出总花费最小，并与上次的总花费最小比较;依次类推对解空间树进行搜索.第一个for循环把cost与mincost进行比较,求出最小费用并记录出最小费用的分配方案.题2:转化为一艘船的最优化问题后
22、,问题的解空间为一个子集树(问题的解空间树中的子集树).也就是算法要考虑所有物品取舍情况的组合.(1)要想求出最优解,必须搜索到叶结点.所以要记录树的层次,当层次为n+1时,搜索完全部叶结点,算法结束.不同于回溯算法,分支搜索过程中活结点的“层”是需要标识的,否则在入队后无法识别结点所在的层.下面算法,每处理完一层让“-1”入队,以此来标识“层”,并用记数变量i来记录当前层.(2)每个活结点要记录当前船的装载量.(3)为了突出算法思想,对数据结构队及其操作只进行抽象描述.用Queue代表队列类型，则Queue Q：定义了一个队列Q，相关操作有：add（Q，.）表示入队；Empty（Q）测试队列
23、是否为空，为空则返回真值。Delete（Q，.）；表示出队。3.4 算法实现算法1如下:#include #include #include int n; /工人和任务的数目int c10001000;unsigned int mincost = 100000; /设置的初始值,大于可能的费用int task1000,temp1000,worker1000;void main() void Plan(int k,unsigned int cost); int i,j; printf(please input tasks and workers:); scanf(%d%d,&n,&n); pri
24、ntf(输入每个工人完成各个工作的费用:n); for(i=0;in;i+) /设置每个任务由不同工人承担时的费用及全局数组的初值 /*taski:值为0表示任务i未分配,值为j表示任务i分配给工人j; workerk:值为0表示工人k未分配任务,值为1表示工人k已分配任务;*/ workeri = 0; taski = 0; tempi = 0; for(j=0;jn;j+) scanf(%d,&cij); Plan(0,0); /从任务0开始分配 printf(最小总费用:%dn,mincost); for(i=0;i=n & costmincost) mincost = cost; fo
25、r(i=0;in;i+) tempi = taski; /工人i完成任务tempi else for(i=0;in;i+) /分配任务k if(workeri=0) workeri = 1; taskk = i; /第一次for(i=0)时，找出0号工人分别执行0，1，2，3，4号任务时总花费最小 /第二次for(i=1)时，找出1号工人分别执行除0号工人的任务以外任务时总花费最 /小，并与i=0时的总花费最小比较 /. /第5次for(i=4)时，找出总花费最小，并与上次的总花费最小比较 Plan(k+1,cost+cki); workeri = 0; taskk = 0; 算法2如附件:3
26、.5 测试结果与分析实验结果1截图如下:作业分配实验结果2截图如下:载重问题第4章 结论分支限界法是由“分支”策略和“限界”策略两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索；“限界”策略是为了加速搜索速度而采用启发信息剪枝的策略。分支搜索的一种搜索方式FIFO，在搜索当前E-结点全部儿子后，其儿子结点成为活结点，E-结点变为死结点；活结点存储在队列中，队首的活结点出队后变为E-结点，其再生成其他活结点的儿子直到找到问题的解或活结点队列为空搜索完毕，例如算法2的载重问题。在算法2中，根据分支搜索，再加上限界策略把不符合约束条件的分支给剪掉。分支搜索的另一种搜索方式优先队列搜
27、索，它通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后将当前最优解作为一个“标准”，对上界（或下界）不可能达到（或大于）这个“标准”的分支，则不去进行搜索，这样剪枝的效率更高，能较好地缩小搜索范围，从而提高搜索效率。其中优先队列分支限界法进行算法设计的有一要点优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成了优先队列。算法1则是利用了这一思想进行算法设计的，也通过最大效益的分配方案为最佳解的限界来进行筛选最优解，算法1也利用了广度优先的思想进行了算法设计。分支算法的求解目标是找出满足约束条件的一个解，或是在满足条件的解中找
28、出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解，即算法1。相对于回溯法而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。仅就限界剪枝的效率而言，优先队列的分支限界法显然要更充分一些。回溯法则因为层次的划分，可以在上界函数值小于当前最优解时，剪去以该结点为根的子树，也就是节省了搜索范围；分支限界法在这方面除了可以做到回溯法能做到的之外，若采用优先队列的分支限界法，有上界函数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立刻终止其余的过程。由以上例子可以说明优先队列的分支限界法更像是有选择、有目的地
29、进行深度优先搜索，时间效率、空间效率都是比较高的。参考文献1吕国英，任瑞征，钱宇华.算法设计与分析.贪婪算法2谭浩强.c程序设计（第四版） 附件#include #include#define MAX 100struct Queue float lMAX; int head,tail;void InitialQ(Queue &q) q.head = q.tail = 0;void Add(Queue &q,float i) q.lq.tail = i; q.tail+;void Delete(Queue &q,float &i) if(q.head q.tail) i = q.lq.head; q.head +; else exit(1); bool Empty(Queue& q) if(q.head q.tail) return false; else return true;float bestw,w100;int n;Queue Q;int main() InitialQ(Q); float c1,c2,s=0; int i; float MaxLoading(float c); scanf(%f%f%d,&c1,&c2,&n); fo
