工作分配问题课件

回溯法之回溯法之回溯法之回溯法之工作分配问题工作分配问题工作分配问题工作分配问题 计科二班计科二班 IMP IMP回溯法之工作分配问题 计科二班 1 设有设有n n件工作分配给件工作分配给n n个人。将工作个人。将工作i i分配给第分配给第j j个人所需的费用为个人所需的费用为CijCij。试。试设计一个算法，为每一个人都分配设计一个算法，为每一个人都分配1 1件件不同的工作，并使总费用达到最小不同的工作，并使总费用达到最小。问题描述问题描述问题描述问题描述 设有n件工作分配给n个人。将工作i分配给第j个人2 n个工作分配给n个人，并且每个人的工作不同。因此，该问题的解空间是一个排列树。相应的排列树由work1:n给出。问题分析问题分析问题分析问题分析 n个工作分配给n个人，并且每个人的工作不同。因此3 在递归算法Backtrack中，当in时，算法搜索至叶节点，得到新的排列方案。if 当前总费用cc minc，更新minc。return回i-1层；问题分析问题分析问题分析问题分析 在递归算法Backtrack中，当in时，算法4 当i=n时，判断ccminc？即判断work1:i的费用是都优于当前最优值。若满足，则以深度优先方式递归搜索子树。否则，剪去子树。问题分析问题分析问题分析问题分析 当i=n时，判断ccn;work=new intn+1;for(i=1;i=n;i+)worki=i;c=new int*n+1;for(i=1;i=n;i+)ci=new intn+1;for(i=1;i=n;i+)for(int j=1;jcij;Work()Work()c=new 14void 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)Backtrack(int i)void Backtrack(int i)Backtra15int main()Work wk;wk.Backtrack(1);wk.Output();return 0;MainMainint main()Main16Thank You!Thank You!Thank You!17