算法分析与设计第5章实验

《算法分析与设计第5章实验》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西南大学实验报告《算法设计与分析》课程2014-2015学年度第1学期《算法设计与分析》课程实验报告（四）实验题目回朔法——批处理作业调度实验时间第十周一、实验目的及要求1.理解回溯法的深度优先搜索策略；2.掌握用回溯法解题的算法框架；3.利用回溯法解决批处理作业调度问题，掌握回溯法的基本思想，能利用回溯法进行简单的算法分析和设计；6二、实验内容、过程和结果（实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果）1.问题描述：n个作业{1,2,…,n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处

2、理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi（1≤i≤n），批处理作业调度问题（batch-jobschedulingproblem）要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少；2.实验原理:设数组a[n]存储n个作业在机器1上的处理时间，b[n]存储n个作业在机器2上的处理时间，回溯法求解批处理调度问题的算法；3.算法实现代码：#include#include#include

3、h>#defineMAX500classFlowshop{private:intfirstTime;intsecondTime;inttotalTime;intbestTime;int*first;int*second;int*x;int*bestx;intnum;public:Flowshop(intnum){firstTime=0;secondTime=0;totalTime=0;bestTime=MAX;this->num=num;6first=newint[num+1];second=newint[num+1];bes

4、tx=newint[num+1];x=newint[num+1];for(inti=1;i<=num;i++){x[i]=i;}}voidbestFlowshop(){flowshop(1);}voidflowshop(inti){if(i>num){if(totalTime

5、[i]];inttemp=secondTime;if(firstTime>=temp){secondTime=firstTime+second[x[i]];totalTime+=secondTime;flowshop(i+1);totalTime-=secondTime;secondTime=temp;6}else{secondTime=temp+second[x[i]];totalTime+=secondTime;flowshop(i+1);totalTime-=secondTime;secondTime=temp;}fir

6、stTime-=first[x[i]];swap(i,k);}}voidswap(inti,intj){inttemp=x[i];x[i]=x[j];x[j]=temp;}voidinput(){inti=1;while(i<=num){cout<<"请输入任务"<>first[i];cout<<"请输入任务"<>second[i];++i;}}voiddisplay(){inti=1;while(i<=num){c

7、out<<"第"<

8、排列树，并且要搜索整个解空间树才能确定最优解，因此，其时间性能是O(n!)，效率上可能有点低。完成此次实验实践后，更加明白了6若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束，但如果使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束，