分支限界作业分配

第3章 作业分配问题3.1 问题描述题1:作业分配问题：设有A,B,C,D,E, 等n个人从事J1,J2,J3,J4,J5,等n项工作，每人只能从事一项任务，每个任务由不同的工人从事有着不同的费用，求最佳安排使费用最低。要求：输出每人所从事的工作任务以及最佳安排的最低费用。题2: 有两艘船和需要装运的n个货箱，第一艘船的载重量是c1，第二艘船的载重量是c2，Wi是货箱i的重量，且W1+W2+W3+W4+.+Wn=c1+c2。希望确定是否有一种可将所有n个货箱全部装船的方法。要求:输出每艘船最终载重量.3.2 问题分析分支搜索法是一种在问题解空间上进行搜索尝试的算法。是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：(1)产生当前扩展结点的所有孩子结点；(2)在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；(3)将其余的孩子结点加入活结点表；(4)从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解（最优解）或活结点表为空。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。题1:先看一个实例,设有A,B,C,D,E 5人从事J1,J2,J3,J4,J5项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。J1J2J3J4J5A10111047B13101085C59774D151210115E1011884要求：输出每人所从事的工作项目以及最佳安排的最高效益。考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务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都不能确定是最优解,有可能还有比其更大的效益,这两个解其一并不一定是一个最可行的选择,它们仅仅提供了一个参考,这样,可以以其中一个作为参考来进一步对各种作业分配方案进行搜索,比较其每种分配方式的效益.最大的总效益为最优解,其分配方案为最佳分配方案.题2: 先看一个实例,当n=3,c1=c2=50,w=10,40,40时,可将货箱1,2装到第一艘船上,货箱3装到第二艘船上.但如果w=20,40,40,则无法将货箱全部装船.由此可知问题可能有解,可能无解,也可能有多解.下面以找出问题的一个解为目标设计算法.虽然是关于两艘船的问题,其实只讨论一艘船的最大装载问题即可.因为当第一艘船的最大装载为bestw时,若w1+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则向左走,否则往右走,直到走到最后,把最终的总效益求出,并把第一次求出的总效益作为最大效益与后边的总效益相比较,比其大者,交换两者,大的作为最大效益.依次方法,直到找到最优解,并输出其值以及其最大效益时的最佳分配方案.(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是否分配了任务, 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进行比较,较小者是最小费用,其分配方案为最佳分配方案.(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:转化为一艘船的最优化问题后,问题的解空间为一个子集树(问题的解空间树中的子集树).也就是算法要考虑所有物品取舍情况的组合.(1)要想求出最优解,必须搜索到叶结点.所以要记录树的层次,当层次为n+1时,搜索完全部叶结点,算法结束.不同于回溯算法,分支搜索过程中活结点的“层”是需要标识的,否则在入队后无法识别结点所在的层.下面算法,每处理完一层让“-1”入队,以此来标识“层”,并用记数变量i来记录当前层.(2)每个活结点要记录当前船的装载量.(3)为了突出算法思想,对数据结构队及其操作只进行抽象描述.用Queue代表队列类型，则Queue Q：定义了一个队列Q，相关操作有：add（Q，.）表示入队；Empty（Q）测试队列是否为空，为空则返回真值。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);printf(输入每个工人完成各个工作的费用: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; for(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.5 测试结果与分析实验结果1截图如下:作业分配实验结果2截图如下:载重问题第4章 结论分支限界法是由“分支”策略和“限界”策略两部分组成。“分支”策略体现在对问题空间是按广度优先的策略进行搜索；“限界”策略是为了加速搜索速度而采用启发信息剪枝的策略。分支搜索的一种搜索方式FIFO，在搜索当前E-结点全部儿子后，其儿子结点成为活结点，E-结点变为死结点；活结点存储在队列中，队首的活结点出队后变为E-结点，其再生成其他活结点的儿子直到找到问题的解或活结点队列为空搜索完毕，例如算法2的载重问题。在算法2中，根据分支搜索，再加上限界策略把不符合约束条件的分支给剪掉。分支搜索的另一种搜索方式优先队列搜索，它通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后将当前最优解作为一个“标准”，对上界（或下界）不可能达到（或大于）这个“标准”的分支，则不去进行搜索，这样剪枝的效率更高，能较好地缩小搜索范围，从而提高搜索效率。其中优先队列分支限界法进行算法设计的有一要点优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成了优先队列。算法1则是利用了这一思想进行算法设计的，也通过最大效益的分配方案为最佳解的限界来进行筛选最优解，算法1也利用了广度优先的思想进行了算法设计。分支算法的求解目标是找出满足约束条件的一个解，或是在满足条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解，即算法1。相对于回溯法而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。仅就限界剪枝的效率而言，优先队列的分支限界法显然要更充分一些。回溯法则因为层次的划分，可以在上界函数值小于当前最优解时，剪去以该结点为根的子树，也就是节省了搜索范围；分支限界法在这方面除了可以做到回溯法能做到的之外，若采用优先队列的分支限界法，有上界函数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立刻终止其余的过程。由以上例子可以说明优先队列的分支限界法更像是有选择、有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。参考文献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);for(i=1;i=n;i+) scanf(%f,&wi);s=s+wi;if(s=c1|sc1+c2) printf(Non solution);return 0;MaxLoadin