問題描述：

有n份作業(yè)分配給n個人去完成，每人完成一份作業(yè)。假定第i個人完成第j份作業(yè)需要花費(fèi)cij時間， cij>0,1≦i,j≦n。試設(shè)計一個回溯算法，將n份作業(yè)分配給n個人完成，使得總花費(fèi)時間最短。

問題思路：

?

?

n分作業(yè)分配給n個人，共有A!中排列方式，深度優(yōu)先遍歷其排列數(shù)，如果遍歷的路徑已經(jīng)比當(dāng)前最小的話費(fèi)則舍棄對當(dāng)前路徑的遍歷，返回上層節(jié)點，尋找合適的路徑，即回溯，如果最后可行解比當(dāng)前的最小話費(fèi)小，那么就更行最佳的作業(yè)安排順序，同時更新最小的耗費(fèi)時間。

算法描述：

t?:遞歸的層數(shù)

curr?:當(dāng)前的實際時間花費(fèi)

bestw?:當(dāng)前的最優(yōu)的時間消耗

arrange：任務(wù)的安排

Backtrack(t)

　　if?t>=n?

　　　　then?if?curr<bestw

　　　　　　then?bestw?<-?curr??

　　　　　　　　update?arrange

　　　　　　ouput(arrange)

　　else?do

　　　　for?t?to?n?do

　　　　　　swap?the?arrange?of?t?and?i

　　　　　　compute?the?current?cost?of?the?arrange

　　　　　　if?curr<bestw?then?backtrack（t+1）???

　　　　　　swap?the?arrange?of?t?and?i

　　　　　　give?back?the?arrange?t?

?數(shù)據(jù)結(jié)構(gòu)的選擇：使用數(shù)組是想對任務(wù)工作的安排

算法的復(fù)雜度分析：O（n！）

算法的實現(xiàn)：

//backtrack.h #include <stdio.h> #include <stdlib.h> #include <limits.h>void backtrack(int t);//t為排列樹的深度 void getRslt(char filename[]);//從文件中讀取數(shù)據(jù)，求解結(jié)果 void output(int *arrange);//輸入最終的任務(wù)分配結(jié)構(gòu) void swap(int &a,int &b);//交換數(shù)組中的兩個元素//backtrack.cpp #include "backtrack.h" #include <malloc.h>int *arrange;// 最終的作業(yè)分配安排 int dataSize;//任務(wù)的個數(shù) 和人員的個數(shù)相同 int **cost;//鄰接矩陣用于存儲每個人完成每份作業(yè)所需要的時間消耗 int bestw=INT_MAX;//初始為最大的整數(shù) 若出現(xiàn)小的則更行 int curr=0; int *best_arrange;void getRslt(char filename[]) {FILE *fp;int i=0;int j=0; // curr=0; fp=fopen(filename,"r");if (!fp){printf("error,can not open the file%s",filename);return;}fscanf(fp,"%d",&dataSize);//開辟數(shù)據(jù)的空間，并將數(shù)據(jù)存在空間中best_arrange=(int*)malloc(dataSize*sizeof(int));cost=(int**)malloc(dataSize*sizeof(int*));for (i=0;i<dataSize;i++){cost[i]=(int*)malloc(dataSize*sizeof(int));if (!cost[i]){printf("error can not malloc the space!");}}for (i=0;i<dataSize;i++){for (j=0;j<dataSize;j++){fscanf(fp,"%d",&cost[i][j]);}}arrange=(int *)malloc(dataSize*sizeof(int));if (!arrange){printf("error,can not malloc a new space!");}for (i=0;i<dataSize;i++){arrange[i]=i;}backtrack(0);output(best_arrange);printf("the best time is:%d\n",bestw);//釋放開辟的空間避免內(nèi)存泄露 free(arrange);arrange=NULL;dataSize=0;for (i=0;i<dataSize;i++){free(*(cost+i));}free(cost);cost=NULL;bestw=INT_MAX;curr=0;free(best_arrange);best_arrange=NULL; } void backtrack(int t)//t表示第t個作業(yè)cost[i][j]第i個人完成第j個任務(wù)所要完成的時間 {int i=0;int j=0;if (t>=dataSize)//已經(jīng)達(dá)到葉子節(jié)點 遞歸出口 {if (curr<bestw){bestw=curr;for (j=0;j<dataSize;j++){best_arrange[j]=arrange[j];}}return;}elsefor (i=t;i<dataSize;i++)//選取要遞歸的節(jié)點，依次遞歸節(jié)點的每一個孩子 {swap(arrange[t],arrange[i]);//把第t個任務(wù)安排給arrang[i] 把第i個任務(wù)地第arrange[t]curr=curr+cost[arrange[t]][t];//當(dāng)前時間家讓把第t個任務(wù)我交給第arrange[i]所花費(fèi)的時間if(curr>bestw)//當(dāng)前的時間消耗已經(jīng)超過當(dāng)前的最佳時間 此時不用再遞歸其子節(jié)點 可以直接返回 { curr=curr-cost[arrange[t]][t];swap(arrange[t],arrange[i]);continue;//本次循環(huán)結(jié)束 }backtrack(t+1);//遞歸一直到葉節(jié)點curr=curr-cost[arrange[t]][t];//如果沒有解則回溯 swap(arrange[t],arrange[i]);} }void output(int *arrange)//打印最終的結(jié)果 {int i=0;printf("the arrange of the work is:\n");for (i=0;i<dataSize;i++){printf("the task %d is arranged to %d\n",(i+1),arrange[i]+1);}}void swap(int &a,int &b)//交換兩個數(shù)的數(shù)值 {int temp;temp=a;a=b;b=temp; }//main.cpp #include "backtrack.h" #include <string.h>int main() {char filename[256]="ddddd";while (1){printf("please input the name of data file(input ‘exit’to quit the program):\n");gets(filename);if (!strcmp(filename,"exit")){break;}getRslt(filename);}return 1; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/liwenzhu/p/3504287.html

總結(jié)

以上是生活随笔為你收集整理的回溯法实现n份作业分配给n个人完成的问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。