《任务分配问题》由会员分享，可在线阅读，更多相关《任务分配问题（17页珍藏版）》请在金锄头文库上搜索。
1、组合问题中的分支限界法,任务分配问题,主讲人：郭嘉明 张旋,任务分配问题,任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图所示是一个任务分配的成本矩阵。,求最优分配成本的上界和下界 考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务1分配给人员a、任务2分配给人员b、任务3分配给人员c、任务4分配给人员d，其成本是9+4+1+4=18；或者应用贪心法求得一个近似解：将任务2分配给人员a、任务3分配给人员b、任务1分配给人员c、任务4分配给人员d，其成本是2+3+5+4=14。显然，14是一个更好的上界。为了获得下界，考
2、虑人员a执行所有任务的最小代价是2，人员b执行所有任务的最小代价是3，人员c执行所有任务的最小代价是1，人员d执行所有任务的最小代价是4。因此，将每一行的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（3和1来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是10, 14之间的某个值。,设当前已对人员1i分配了任务，并且获得了成本v，则限界函数可以定义为：,（2）在结点2，将任务1分配给人员a，获得的成本为9，目标函数值为9 + (3+1+4)=17，超出目标函数的界10, 14，将结点2丢弃；在结点3，将任务2分配给人员a，
3、获得的成本为2，目标函数值为2 + (3+1+4)=10，将结点3加入待处理结点表PT中；在结点4，将任务3分配给人员a，获得的成本为7，目标函数值为7 + (3+1+4)=15，超出目标函数的界10, 14，将结点4丢弃；在结点5，将任务4分配给人员a，获得的成本为8，目标函数值为8 + (3+1+4)=16，超出目标函数的界10, 14，将结点5丢弃；,应用分支限界法求解图所示任务分配问题，对解空间树的搜索如图所示，具体的搜索过程如下： （1）在根结点1，没有分配任务，根据限界函数估算目标函数值为2+3+1+4=10；,（3）在表PT中选取目标函数值极小的结点3优先进行搜索； （4）在结点
4、6，将任务1分配给人员b，获得的成本为2+6=8，目标函数值为8+(1+4)13，将结点6加入表PT中；在结点7，将任务3分配给人员b，获得的成本为2+3=5，目标函数值为5+(1+4)10，将结点7加入表PT中；在结点8。将任务4分配给人员b，获得的成本为2+7=9，目标函数值为9+(1+4)14，将结点8加入表PT中； （5）在表PT中选取目标函数值极小的结点7优先进行搜索； （6）在结点9，将任务1分配给人员c，获得的成本为5+5=10，目标函数值为10+4=14，将结点9加入表PT中；在结点10，将任务4分配给人员c，获得的成本为5+8=13，目标函数值为13+4=17，超出目标函数的
5、界10, 14，将结点10丢弃；,（7）在表PT中选取目标函数值极小的结点6优先进行搜索； （8）在结点11，将任务3分配给人员c，获得的成本为8+1=9，目标函数值为9+4=13，将结点11加入表PT中；在结点12，将任务4分配给人员c，获得的成本为8+8=16，目标函数值为16+4=20，超出目标函数的界10, 14，将结点12丢弃； （9）在表PT中选取目标函数值极小的结点11优先进行搜索； （10）在结点13，将任务4分配给人员d，获得的成本为9+4=13，目标函数值为13，由于结点13是叶子结点，同时结点13的目标函数值是表PT中的极小值，所以，结点13对应的解即是问题的最优解，搜索
6、结束。,为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表PT中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表PT和表ST的数据结构为(人员i-1分配的任务,lb),回溯过程是： (3,13)(1,13)(2,13)(0,10) 。,#include #include #include int n; /工人和任务的数目 int c10001000; unsigned int mincost = 100000; /设置的初始值,大于可能的费用 int task1000,temp1000,worker1000; void main() void Plan(int k,unsigne
7、d int cost); int i,j; printf(please input tasks and workers:); scanf(%d%d,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, ,Plan(0,0); /从任务0开始分配 printf(最小总费用:%dn,mincost); for(i=0;i=n 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; ,
