算法分析与设计课程设计报告

算法分析与设计。

课程设计报告

课程名称算法分析与设计。

实验学期 2013 年至 2014 年第 1 学期。

所在学院理学院年级 2011

专业班级信息与计算科学3班

学生姓名郑松辉学号 201130760334 自评成绩 96 教师评成绩

指导教师赵峰

算法分析与设计》课程设计报告。

目录。1课程实验概述 4

1.1 问题概述 4

1.2 目的与任务 4

1.3 开发环境 4

1.4 参考资料 4

1.5 任务完成的一般过程 4

1.6 软件配置 5

2 个人的构思与创意 5

2.1 构思 5

2.2 特色 5

3 用贪心算法解决活动安排的问题的实验及其结果分析 5

3.1 贪心算法简介 5

3.2 贪心算法思路 6

3.3 贪心算法实现 6

3.4 算法结果 7

3.4.1 实验结果 8

3.4.2 结果分析 8

3.5 算法分析 9

3.5.1 关键**及解释 9

3.5.2 算法流程图 10

3.5.3 时间复杂度分析 11

4 实验个人小结 11

4.1总体实验分析总结 11

4.2 个人经验总结 11

4.2.1 收获 11

4.2.2 不足 12

1.1 问题概述。

设有n个活动的集合e=，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si=fj或者sj>=fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

1.2 目的与任务。

利用贪心算法的性质，通过选择适当的贪心策略的贪心算法解决活动安排问题，且能求得活动安排的最优解。

1.3 开发环境。

平台：windows 7；编程语言：c语言；

1.4 参考资料。

1] 算法设计与分析（第二版）王晓东编著清华大学出版社 2011

2] 标准c语言基础教程（第四版） [美]gary 电子工业出版社 2011

1.5 任务完成的一般过程。

完成过程如下图1所示：

图1 任务完成的一般过程。

1.6 软件配置。

编程工具：c-free5.0

2.1 构思。

此次课程设计的构思过程的核心是：贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合a的规模最大。

因此，这个方向非常明确，就是用贪心算法解决活动安排问题。

首先，贪心算法最大的难度在于选择贪心策略，只要选择正确的贪心策略就能通过贪心算法求得最优解，对于活动安排，以选择结束时间最早的活动为贪心策略是可以得到最优解的。

其次，既然是按照一定的顺序来选择活动，那么必将先要对活动按结束时间递增进行排序，因为排序后，编写贪心算法程序会变得十分简洁。

最后，在对所有活动进行选择完毕后，要程序中显示选择结果，以确实是否正确。

2.2 特色。

本次编程，个人觉得最大的特色就是把贪心选择算法程序和结果显示程序分离开成单独的模块，这样会使得贪心选择算法变得更加简洁易懂，便于浏览阅读。

其次，在界面设计上，为了让前后衔接的更加美观，也设置的两个**，以便显示输入是的活动表和排序后的活动表，这样可以很直观的看出此次设计的运行过程。

再者，我是通过设置全局变量，一次赋值或者排序后都可以在所有函数中调用，这也使得个模块的连接更加简单，没有复杂的地址调用，是**更具易读性。

3.1 贪心算法简介。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

3.2 贪心算法思路。

活动安排运用贪心算法的思路为，尽可能多的使更多的事件得到资源的安排。按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。

3.3 贪心算法实现。

贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合a的规模最大。这个结论可以用数学归纳法证明。

事实上，设e=｛1，2，..n｝为所给的活动集合。由于e中活动按结束时间的非减序列排列，故活动1具有最早的完成时间。

首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1。设是所给的活动安排问题的一个最优解，且a中活动也按结束时间非减序排序，a中的第一个活动是活动k。若k=1，则a就是以贪心选择开始的最优解；若k>1，则设。

由于f1fk，且a中活动是相容的。又由于b中活动个数与a中活动个数相同，且a是最优的，故b也是最优的。由此可见，此贪心策略能得到最优解。

由于贪心算法解决安排问题要考虑么个活动的结束时间，所以先将活动按照结束时间长短进行递增排序。本贪心算法在处理非减序排列活动队列时可以达到极高的效率。

例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

表1 已排序活动安排。

贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合a的活动，而空白长条表示的活动是当前正在检查相容性的活动。

图2贪心算法的计算过程图。

若被检查的活动i的开始时间si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合a中。

3.4 算法结果。

若所需安排的活动为：

表2 活动安排。

3.4.1 实验结果。

图3 运行结果。

3.4.2 结果分析。

首先对以上数据以结束时间递增顺序进行排序得到以下队列：

表3 对数据以结束时间递增顺序进行排序得到的队列。

然后按照贪心算法取结束时间提前的活动以为后续活动提供更多时间，同时在保证选择的活动的结束时间提前还要保证该活动与前一个活动相容。依次选择的活动为。

3.5 算法分析。

3.5.1 关键**及解释。

void greedyselect(int n)//活动的贪心选择

a[num[1]]=true;

int j=1;

for(int i=2;i<=n;i++)

if(s[i]>=f[j])

elsea[num[i]]=false;

这是整个贪心算法的核心，一个for循环，根据已经选择的贪心策略，对活动进行选择，其中布尔型数组a用与保存活动是否被选择，若被选择则保存为true，否则保存为false。

void greedysort(int n)//将活动按结束时间递增排序

int i,j,m;

for(i=1;i<=n;i++)

for(j=i;j<=n-1;j++)

if(f[j]>f[j+1])

m=f[j];

f[j]=f[j+1];

f[j+1]=m;

算法分析与设计课程设计报告

算法设计与分析课程设计报告

算法设计与分析课程设计报告

算法设计与分析课程设计报告

其他用户还读了