工作分配问题课件.ppt

《工作分配问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、回溯法之工作分配问题计科二班IMP设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。问题描述n个工作分配给n个人，并且每个人的工作不同。因此，该问题的解空间是一个排列树。相应的排列树由work[1:n]给出。问题分析在递归算法Backtrack中，当i>n时，算法搜索至叶节点，得到新的排列方案。if当前总费用cc>minc，更新minc。return回i-1层；问题分析当i<=n时，判断cc

2、，剪去子树。问题分析给定3件工作，i号工人完成j号工作的费用如下：1023234345问题示例1、利用回溯法思想，首先分配的是：10：c[1][1]3:c[2][2]5:c[3][3]cc=18问题示例2、此时，所有工人分配结束，回溯到第2个工人重新分配：10：c[1][1]4:c[2][3]4:c[3][2]cc=18问题示例3、第2个工人已经回溯到n，再回溯到第1个工人重新分配：2：c[1][3]2:c[2][1]5:c[3][3]cc=9问题示例4、回溯到第2个工人重新分配：2：c[1][2]4:c[2][3]3:c[3][1]cc=9问题示例5、再回溯到第1个工人重新分

3、配：3：c[1][3]2:c[2][1]4:c[3][2]cc=9问题示例6、回溯到第2个工人重新分配：3：c[1][3]3:c[2][2]3:c[3][1]cc=9问题示例classWork{//工作类public:Work(){}voidBacktrack(inti){}voidOutput(){}public:intn,i,j;int**c;int*work;intcc,minc;voidswap(int&a,int&b){}};ClassWorkWork()Work(){cc=0;minc=10000;ifstreamin("input.txt");in>>n;work

4、=newint[n+1];for(i=1;i<=n;i++)work[i]=i;c=newint*[n+1];for(i=1;i<=n;i++)c[i]=newint[n+1];for(i=1;i<=n;i++){for(intj=1;j<=n;j++)in>>c[i][j];}}voidBacktrack(inti){if(i>n){//已得到一个可行解if(cc

5、;Backtrack(i+1);cc-=c[i][work[i]];swap(work[j],work[i]);}}}Backtrack(inti)intmain(){Workwk;wk.Backtrack(1);wk.Output();return0;}MainThankYou!