工作分配問題課件

回溯法之

工作分配問題計科二班IMP回溯法之

工作分配問題計科二班1

設(shè)有n件工作分配給n個人。將工作i分配給第j個人所需的費(fèi)用為Cij。試設(shè)計一個算法，為每一個人都分配1件不同的工作，并使總費(fèi)用達(dá)到最小。問題描述設(shè)有n件工作分配給n個人。將工作i分配給第j個人2n個工作分配給n個人，并且每個人的工作不同。因此，該問題的解空間是一個排列樹。相應(yīng)的排列樹由work[1:n]給出。問題分析n個工作分配給n個人，并且每個人的工作不同。因此3在遞歸算法Backtrack中，當(dāng)i>n時，算法搜索至葉節(jié)點，得到新的排列方案。if當(dāng)前總費(fèi)用cc>minc，更新minc。return回i-1層；問題分析在遞歸算法Backtrack中，當(dāng)i>n時，算法4當(dāng)i<=n時，判斷cc<minc？即判斷work[1:i]的費(fèi)用是都優(yōu)于當(dāng)前最優(yōu)值。若滿足，則以深度優(yōu)先方式遞歸搜索子樹。否則，剪去子樹。問題分析當(dāng)i<=n時，判斷cc<minc？即判斷work5

給定3件工作，i號工人完成j號工作的費(fèi)用如下： 1023 234 345

問題示例給定3件工作，i號工人完成j號工作的費(fèi)用如下：61、利用回溯法思想，首先分配的是： 10：c[1][1] 3:c[2][2] 5:c[3][3] cc=18

問題示例1、利用回溯法思想，首先分配的是：問題示例72、此時，所有工人分配結(jié)束，回溯到第2個工人重新分配： 10：c[1][1] 4:c[2][3] 4:c[3][2] cc=18

問題示例2、此時，所有工人分配結(jié)束，回溯到第2個工人重新分配：問題83、第2個工人已經(jīng)回溯到n，再回溯到第1個工人重新分配： 2：c[1][3] 2:c[2][1] 5:c[3][3] cc=9

問題示例3、第2個工人已經(jīng)回溯到n，再回溯到第1個工人重新分配：問94、回溯到第2個工人重新分配： 2：c[1][2] 4:c[2][3] 3:c[3][1] cc=9

問題示例4、回溯到第2個工人重新分配：問題示例105、再回溯到第1個工人重新分配： 3：c[1][3] 2:c[2][1] 4:c[3][2] cc=9

問題示例5、再回溯到第1個工人重新分配：問題示例116、回溯到第2個工人重新分配： 3：c[1][3] 3:c[2][2] 3:c[3][1] cc=9

問題示例6、回溯到第2個工人重新分配：問題示例12classWork{//工作類public: Work(){} voidBacktrack(inti){}voidOutput(){}public: intn,i,j; int**c; int*work; intcc,minc; voidswap(int&a,int&b){}};ClassWorkclassWork{//工作類ClassW13Work()Work(){cc=0;minc=10000;ifstreamin("input.txt");in>>n; work=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];} }Work()Work(){c=new14voidBacktrack(inti){ if(i>n){//已得到一個可行解 if(cc<minc)//更新最小費(fèi)用 minc=cc;return; } for(intj=i;j<=n;j++) { if(cc<minc){//搜索子樹 swap(work[i],work[j]); cc+=c[i][work[i]]; Backtrack(i+1); cc-=c[i][work[i]]; swap(work[j],work[i]); } }}Backtrack(inti)voidBacktrack(inti){Backtra15intmain(){ Workwk; wk.Backtrack(1); wk.Output(); return0;}Mainintmain(){Main16ThankYou!ThankYou!17回溯法之

工作分配問題計科二班IMP回溯法之

工作分配問題計科二班18

設(shè)有n件工作分配給n個人。將工作i分配給第j個人所需的費(fèi)用為Cij。試設(shè)計一個算法，為每一個人都分配1件不同的工作，并使總費(fèi)用達(dá)到最小。問題描述設(shè)有n件工作分配給n個人。將工作i分配給第j個人19n個工作分配給n個人，并且每個人的工作不同。因此，該問題的解空間是一個排列樹。相應(yīng)的排列樹由work[1:n]給出。問題分析n個工作分配給n個人，并且每個人的工作不同。因此20在遞歸算法Backtrack中，當(dāng)i>n時，算法搜索至葉節(jié)點，得到新的排列方案。if當(dāng)前總費(fèi)用cc>minc，更新minc。return回i-1層；問題分析在遞歸算法Backtrack中，當(dāng)i>n時，算法21當(dāng)i<=n時，判斷cc<minc？即判斷work[1:i]的費(fèi)用是都優(yōu)于當(dāng)前最優(yōu)值。若滿足，則以深度優(yōu)先方式遞歸搜索子樹。否則，剪去子樹。問題分析當(dāng)i<=n時，判斷cc<minc？即判斷work22

給定3件工作，i號工人完成j號工作的費(fèi)用如下： 1023 234 345

問題示例給定3件工作，i號工人完成j號工作的費(fèi)用如下：231、利用回溯法思想，首先分配的是： 10：c[1][1] 3:c[2][2] 5:c[3][3] cc=18

問題示例1、利用回溯法思想，首先分配的是：問題示例242、此時，所有工人分配結(jié)束，回溯到第2個工人重新分配： 10：c[1][1] 4:c[2][3] 4:c[3][2] cc=18

問題示例2、此時，所有工人分配結(jié)束，回溯到第2個工人重新分配：問題253、第2個工人已經(jīng)回溯到n，再回溯到第1個工人重新分配： 2：c[1][3] 2:c[2][1] 5:c[3][3] cc=9

問題示例3、第2個工人已經(jīng)回溯到n，再回溯到第1個工人重新分配：問264、回溯到第2個工人重新分配： 2：c[1][2] 4:c[2][3] 3:c[3][1] cc=9

問題示例4、回溯到第2個工人重新分配：問題示例275、再回溯到第1個工人重新分配： 3：c[1][3] 2:c[2][1] 4:c[3][2] cc=9

問題示例5、再回溯到第1個工人重新分配：問題示例286、回溯到第2個工人重新分配： 3：c[1][3] 3:c[2][2] 3:c[3][1] cc=9

問題示例6、回溯到第2個工人重新分配：問題示例29classWork{//工作類public: Work(){} voidBacktrack(inti){}voidOutput(){}public: intn,i,j; int**c; int*work; intcc,minc; voidswap(int&a,int&b){}};ClassWorkclassWork{//工作類ClassW30Work()Work(){cc=0;minc=10000;ifstreamin("input.txt");in>>n; work=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];} }Work()Work(){c=new31voidBacktrack(inti){ if(i>n){//已得到一個可行解 if(cc<minc)//更新最小費(fèi)用 minc=cc;return; } for(intj=i;j<=n;j++) { if(cc<minc){//搜索子樹 swap(work[i],work[j]); cc+=c[i][work[i]]; Backt