最佳调度问题(回溯算法)

《算法设计与分析》上机报告姓名：学号：日期：上机题目：最佳调度问题(回溯算法)实验环境：CPU:2.10GHz;内存:6G;操作系统：Win764位;软件平台：VisualStudio2008;一、算法设计与分析：题目:最佳调度问题(回溯算法)设有n个任务由m个可并行工作的机器来完成，完成任务i需要时间为ti。试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。算法思想：解空间的表示：一个深度为N的M叉树。t[i]:第i个任务的时间x[i]=j:当前输出结果Res[i]=j:表示第i个任务要运行在第j台机器上time_machine[i]:第i个机器上的运行时间基本思路：1、搜索从开始结点（根结点）出发，以DFS搜索整个解空间。2、每搜索完一条路径则记录下time_min和Res[i]序列，开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。3、如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。二、核心代码：boolplacetest(intk){inttime_max_K=time_machine[1];for(inti=2;i=K;i++){if(time_machine[i]time_max_K)time_max_K=time_machine[i];}if(time_max_Ktime_min)returnfalse;elsereturntrue;}voidBacktrack(intk,intt[],intx[]){if(kN){inttime_max_K=time_machine[1];for(inti=2;i=K;i++){if(time_machine[i]time_max_K)time_max_K=time_machine[i];}if(time_max_Ktime_min){time_min=time_max_K;for(inti=1;i=N;i++)Res[i]=x[i];}}else{for(inti=1;i=K;i++){x[k]=i;if(placetest(k)){time_machine[i]+=t[k];Backtrack(k+1,t,x);time_machine[i]-=t[k];}}}}三、结果与分析：附录（源代码）算法源代码（C++描述）/*最佳调度问题(回溯算法)设有n个任务由k个可并行工作的机器来完成，完成任务i需要时间为。试设计一个算法找出完成这n个任务的最佳调度，使完成全部任务的时间最早。*/#includeiostream#includectime#includewindows.husingnamespacestd;intK,N;int*time_machine;//[K+1]={0};int*Res;//[N+1];staticinttime_min=INT_MAX;boolplacetest(intk);voidBacktrack(intk,intt[],intx[]);intmain(){cout请输入任务个数和机器个数：endl;cinNK;if(N=K){cout最短运行时间即为任务中时间最长者！endl;return0;}int*t=newint[N+1];int*x=newint[N+1];cout请分别输入N个任务时间：endl;for(inti=1;iN+1;i++)cint[i];//t[8]={0,2,14,4,16,6,5,3};time_machine=newint[K+1];Res=newint[N+1];for(inti=1;iK+1;i++)time_machine[i]=0;for(inti=1;iN+1;i++){coutt[i]'';}coutendl;clock_tstart,finish;doubletotaltime;start=clock();Backtrack(1,t,x);finish=clock();//1msclock++totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout程序运行时间：totaltimes\n;for(inti=1;iN+1;i++)coutRes[i]'';coutendl;coutmintime:time_minendl;system(pause);return0;}boolplacetest(intk){inttime_max_K=time_machine[1];for(inti=2;i=K;i++){if(time_machine[i]time_max_K)time_max_K=time_machine[i];}if(time_max_Ktime_min)returnfalse;elsereturntrue;}voidBacktrack(intk,intt[],intx[]){if(kN){inttime_max_K=time_machine[1];for(inti=2;i=K;i++){if(time_machine[i]time_max_K)time_max_K=time_machine[i];}if(time_max_Ktime_min){time_min=time_max_K;for(inti=1;i=N;i++)Res[i]=x[i];}}else{for(inti=1;i=K;i++){x[k]=i;//将第k个任务放到第i个机器上面if(placetest(k)){time_machine[i]+=t[k];Backtrack(k+1,t,x);time_machine[i]-=t[k];}}}}