算法实验05贪心法的应用.doc

《算法实验05贪心法的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程实验报告课程名称算法分析与设计班级实验日期姓名学号实验成绩实验名称实验5：贪心算法的应用实验目的及要求1．理解贪心算法的概念；2．掌握贪心算法的基本思想。实验环境操作系统：WindowsIDE：VisualC++实验内容（1）活动安排问题设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si

2、活动i与活动j是相容的。随机生成n个任务（n=8,16,32…）,用贪心法求近似解，任选一种其它方法求最优解。做出图像，比较贪心法和你所选的另外一种方法的执行时间随n的变化曲线。比较计算结果，说明对该问题，贪心法是否一定会得到最优解，如果是，请给出证明或者说明理由，如果不是，请根据实验结果说明理由。（2）线段覆盖问题描述：在一维空间中随机生成N（N=8,16,32…）条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度（重叠区域只算一次）。分析算法的时间复杂度，画出算法的执行时间随N变化的曲线图。调贪心算法初步：试过程运行到一定规模：

3、线段覆盖总结我们容易验证贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。贪心算法并不是针对任何一个问题都存在最优解，但是针对会场安排问题可以得到最优解。我们可以从贪心算法得到的结果集仅进行倒推。首先去掉结果集中的第一个活动A，那么在剩下的活动中，结束时间最早的活动B的结束时间一定不早于A,那么A活动在最优解中一定合

4、理。再用同样的方式判断活动B,依次类推，则结果集就是最优解。可以分析得出，此次实验中关于时间复杂度，采用递归分析，与贪心算法时间相差不大，为O(n)，呈现正比例关系。附录#include#include#include#include#defineMAX1000000usingnamespacestd;intstar[MAX];//记录每个活动的开始时间intter[MAX];//记录每个活动的结束时间boolC[MAX];//记录是否选中intN;//存放问题规模clo

5、ck_tbegintimes,endtimes;//clock_t为clock()函数返回的变量类型doubleduration;//运行时间计算//随机数生成函数intnumber(){inta=rand()%10000+1;returna;}//初始化函数voidinit(){srand((unsigned)time(NULL));//给一个时间种子for(inti=0;ib?star[i]=b,ter[i]=a:star[i]=a,ter[i]=b;}}//进行排序

6、:按照结束时间排序voidSorts(){for(inti=0;iter[j+1]){//进行交换尾部时间inttemp=ter[j];ter[j]=ter[j+1];ter[j+1]=temp;//同时进行交换开始时间temp=star[j];star[j]=star[j+1];star[j+1]=temp;}}}return;}//贪心策略:从当前最优秀的解，开始寻找，一直找到最后。voidGreedySelector(){C[0]=true;intj=1;/

7、/记录最近一次加入C中的活动for(inti=1;i=ter[j]){//符合条件就选中C[i]=true;j=i;}else{C[i]=false;}}}//主函数intmain(){N=2;do{N*=2;init();//初始化Sorts();//排序begintimes=clock();//计时开始GreedySelector();endtimes=clock();//计时结束duration=1000*(double)(endtimes-begintime

8、s)/CLK_TCK;//总共用时(毫秒)cout<<"各活动的开始时间,结束时间分别为："<