分支限界作业分配

第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项工作，每人只能从事一项，他们的效益如图所示，求最佳安排使效益最高。   J1 J2 J3 J4 J5 A 10 11 10 4 7 B 13 10 10 8 5 C 5 9 7 7 4 D 15 12 10 11 5 E 10 11 8 8 4             要求：输出每人所从事的工作项目以及最佳安排的最高效益。 考虑任意一个可行解,例如矩阵中的对角线是一个合法的选择,表示将任务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)用task[i]来表示任务是否分配及分配了给哪个工人,即task[i]=0时表示任务i未分配, task[i]=j表示任务i分配给了工人j;用worker[k]=0或1来表示工人k是否分配了任务, worker[k]=0表示工人k未分配任务, worker[k]=1表示工人k已分配了任务. (3)把最低费用用mincost来表示和c[i][j]表示工人j执行任务i时的费用,并把c[i][j]和mincost分别初始化为c[1000][1000]和100000;同时把ask[i]和temp[i]、worker[i]的存储空间初始为task[1000]和temp[1000]、worker[1000],之后把其初始化为0. (4)用Plan(int k,unsigned int cost)来对分配作业的解空间树进行搜索,搜索的时候,每个活结点要记录下搜索的路径(即分配方案),存储在temp[i]中,并求出费用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 c[1000][1000]; unsigned int mincost = 100000; //设置的初始值,大于可能的费用 int task[1000],temp[1000],worker[1000]; 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;i=n && cost标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载