《最佳调度问题(回溯算法)》由会员分享，可在线阅读，更多相关《最佳调度问题(回溯算法)（5页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析上机报告姓名：学号：日期：上机题目：最佳调度问题(回溯算法)实验环境：CPU:2.10GHz;内存:6G;操作系统：Win764位;软件平台:VisualStudio2008;一、算法设计与分析：题目最佳调度问题回溯算法设有个任务由个可并行工作的机器来完成，完成任务需要时间为。试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。算法思想：解空间的表示：一个深度为的叉树。第个任务的时间当前输出结果表示第个任务要运行在第台机器上第个机器上的运行时间基本思路：、搜索从开始结点(根结点)出发，以搜索整个解空间。2每搜索完一条路径则记录下time_min和序列，开始结点就成
2、为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。、如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。二、核心代码：boolplacetest(intk)inttime_max_K=time_machine1;for(inti=2;i=K;i+)if(timemachineitimemaxK)if(timeKtime_min)elsereturntrue;voidBacktrack(intk,i
3、ntt,intx口)if(kN)inttime_max_K=time_machine1;for(inti=2;i=K;i+)if(time_machineitime_max_K)timemaxK=timemachinei;if(timemaxKtimemin)time_min=time_max_K;for(inti=1;i=N;i+)Resi=xi;elsefor(inti=1;i=K;i+)xk=i;if(placetest(k)time_machinei+=tk;Backtrack(k+1,t,x);time_machinei-=tk;算法源代码（描述）最佳调度问题回溯算法设有个任务由个可并行工作的机器来完成，完成任务需要时间为。试设计一个算法找出完成这个任务的最佳调度，使完成全部任务的时间最早。附录（源代码）请输入任务个数和机器个数:最短运行时间即为任务中时间最长者!请分别输入个任务时间:程序运行时间:将第个任务放到第个机器上面
