《工作分配问题课件.ppt》由会员分享，可在线阅读，更多相关《工作分配问题课件.ppt（17页珍藏版）》请在三一办公上搜索。
1、回溯法之工作分配问题,计科二班 IMP,设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。,问题描述,n个工作分配给n个人，并且每个人的工作不同。因此，该问题的解空间是一个排列树。 相应的排列树由work1:n给出。,问题分析,在递归算法Backtrack中，当in时，算法搜索至叶节点，得到新的排列方案。 if 当前总费用cc minc，更新minc。 return回i-1层；,问题分析,当i=n时，判断ccminc？即判断work1:i的费用是都优于当前最优值。 若满足，则以深度优先方式递归搜索子树。 否则
2、，剪去子树。,问题分析,给定3件工作，i号工人完成j号工作的费用如下： 10 2 3 2 3 4 3 4 5,问题示例,1、利用回溯法思想，首先分配的是： 10：c11 3: c22 5: c33 cc=18,问题示例,2、此时，所有工人分配结束，回溯到第2个工人重新分配： 10：c11 4: c23 4: c32 cc=18,问题示例,3、第2个工人已经回溯到n，再回溯到第1个工人重新分配： 2： c13 2: c21 5: c33 cc=9,问题示例,4、回溯到第2个工人重新分配： 2： c12 4: c23 3: c31 cc=9,问题示例,5、再回溯到第1个工人重新分配： 3： c13
3、 2: c21 4: c32 cc=9,问题示例,6、回溯到第2个工人重新分配： 3： c13 3: c22 3: c31 cc=9,问题示例,class Work /工作类public:Work()void Backtrack(int i) void Output()public:int n,i,j;int *c;int *work;int cc,minc;void swap(int ,Class Work,Work(),Work() cc=0; minc=10000; ifstream in(input.txt); inn; work=new intn+1; for(i=1;i=n;i+)
4、 worki=i;,c=new int*n+1; for(i=1;icij; ,void Backtrack(int i) if(in) /已得到一个可行解 if(ccminc) /更新最小费用 minc=cc; return;for(int j=i;j=n;j+) if(ccminc) /搜索子树swap(worki,workj);cc+=ciworki;Backtrack(i+1);cc-=ciworki;swap(workj,worki); ,Backtrack(int i),int main()Work wk;wk.Backtrack(1);wk.Output();return 0;,Main,Thank You!,
