算法分析与设计课程设计--贪心算法解决活动安排问题

《算法分析与设计课程设计--贪心算法解决活动安排问题》由会员分享，可在线阅读，更多相关《算法分析与设计课程设计--贪心算法解决活动安排问题（12页珍藏版）》请在毕设资料网上搜索。

1、 算法分析与算法分析与设计设计 课课 程程 设设 计计 报报 告告 课程名称课程名称 算算 法法 分分 析析 与与 设设 计计 实验学期实验学期 20201 13 3 年至年至 2012014 4 年年 第第 1 1 学期学期 所在学院所在学院 理学院理学院 年年级级 专业班级专业班级 信息与计算科学信息与计算科学 3 3 班班 2 算法分析与算法分析与设计设计课程设计报告课程设计报告 设计题目 贪心算法解决活动安排问题 设计时间 年 月 日 设计性质 应用性 设计性 综合性 设计成绩 教师评阅： 设计目的明确 ； 操作步骤正确 ； 设计文稿（表 格、 程序 、 数据 库 、网 页 ）符 合

2、要求 ； 设计结果正确 ； 设计分析总结 全面 ； 设计报告规范 ； 课程设计答辩情况记录： 思路清晰；语 言表 达 准确 ， 概念 清 楚。 准备工作充分 , 具备必 要的 报 告资 料 ；报 告 在规 定 的时 间 内完成 。 回答问题有理 论依 据 ，基 本 概念 清 楚; 主要问题 回 答简 明 准确 ； 对前人工作有 改进 或 突破 ， 或有 独 特见 解。 评阅教师签名： 3 目 录 1 课程实验概述 4 1.1 问题概述 4 1.2 目的与任务 4 1.3 开发环境 4 1.4 参考资料 4 1.5 任务完成的一般过程 4 1.6 软件配置 5 2 个人的构思与创意 . 5 2.

3、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 不足 .11 4 1 1 课程实验概述课程实验概述 1.1 问题概述 设有 n 个活动的集合 E=

4、1,2，n，其中每个活动都要求使用同一资 源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi，且 si=fj 或者 sj=fi 时， 活动 i 与活动 j 相容。 活动安排问题就是要在所给的活动集合中选出最大的相容 活动子集合。 1.2 目的与任务 利用贪心算法的性质， 通过选择适当的贪心策略的贪心算法解决活动安排问 题，且能求得活动安排的最优解。 1.3 开发环境 平台：Windows 7； 编程语言：C 语言； 1.4 参考资料 1 算法设计与分析（第二版） 王晓东 编著 清华大学出版社 2011 2 标准

5、C语言基础教程 （第四版） 美Gary J.Bronson 电子工业出版社 2011 1.5 任务完成的一般过程 完成过程如下图 1 所示： 图 1 任务完成的一般过程 5 1.6 软件配置 编程工具：C-Free5.0 2 2 个人的构思与创意个人的构思与创意 2.1 构思 此次课程设计的构思过程的核心是：贪心算法并不总能求得问题的整体最优 解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定 的相容活动集合 A 的规模最大。因此，这个方向非常明确，就是用贪心算法解决 活动安排问题。 首先，贪心算法最大的难度在于选择贪心策略，只要选择正确的贪心策略就 能通过贪心算法求得最优

6、解，对于活动安排，以选择结束时间最早的活动为贪心 策略是可以得到最优解的。 其次，既然是按照一定的顺序来选择活动，那么必将先要对活动按结束时间 递增进行排序，因为排序后，编写贪心算法程序会变得十分简洁。 最后，在对所有活动进行选择完毕后，要程序中显示选择结果，以确实是否 正确。 2.2 特色 本次编程，个人觉得最大的特色就是把贪心选择算法程序和结果显示程序分 离开成单独的模块， 这样会使得贪心选择算法变得更加简洁易懂， 便于浏览阅读。 其次，在界面设计上，为了让前后衔接的更加美观，也设置的两个表格，以 便显示输入是的活动表和排序后的活动表， 这样可以很直观的看出此次设计的运 行过程。 再者，我是通过设置全局变量，一次赋值或者排序后都可以在所有函数中调 用， 这也使得个模块的连接更加简单， 没有复杂的地址调用， 是代码更具易读性。 3 3 用贪心算法解决活动安排的问题的实验及其结果分析用贪心算法解决活