利用贪婪算法实现多种实际问题..doc

《算法设计与分析》课程设计任务书 学院名称： 数学与计算机学院 专业： 信息与计算科学专业 年级： 2007 一、设计题目 题目十四：利用贪婪算法实现多种实际问题 二、主要内容 给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。 三、具体要求 （1）贪婪算法的基本思想； （2）给出背包问题的贪婪算法； （3）给出有限期计算机作业调度的贪婪算法； （4）给出上面两个算法的证明； （5）给出上面两个算法的程序。 （6）给出时间复杂度。 四、主要技术路线提示 在用贪婪算法解决资源分配问题、布线问题、0-1背包问题过程中，使用贪婪算法解决问题，通常需要做好以下几个方面的工作： 1、明确问题的求解目标。 2、分析问题所包含的约束条件。 3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。 4、制定贪婪准则。上交的成果的内容必须由以下四个部分组成，缺一不可1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）2．上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明3．课程设计报告：（保存在word 文档中，文件名要求 按照学号姓名课设报告起名，如文件名为张三.doc” ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成其中包括需求分析：在该部分中叙述每个模块的功能要求概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。课设总结总结可以包括 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对这门课程的思考、在课程设计过程中对《》课程的认识等内容2007。 《算法设计与分析》 宋 文 等编 重庆大学出版社，2001。 参考书：[1] 《算法设计与分析》 周培德 电子工业出版社，2000。 [2] 《算法设计与分析》 王晓东 电子工业出版社，2004 指导教师 签名日期 年 月 日 系 主 任 审核日期 年 月 日 目 录 1引言 1 2贪婪算法的概述 1 2.1 什么是贪婪算法 1 2.2贪婪算法的特性 1 2.3贪婪算法解决问题的步骤 2 2.4贪婪算法的优缺点 2 3贪婪算法的应用 3 3.1贪婪算法在资源分配问题中的应用 3 3.2贪婪算法在布线问题中的应用 4 3.3 贪婪算法在0/1背包问题中的应用 6 3.3.1 传统的贪婪算法解决方案 6 3.3.2 改进的贪婪算法策略 7 4 总结与展望 9 参考文献 10 引言 为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。 目前常用的算法设计技术有分治法、回溯法、贪婪法、动态规划算法、分支限界法等。其中分治法、回溯法主要用于设计非数值问题的算法,而贪婪法、动态规划算法、分支限界法则主要用于设计数值最优化问题的算法。贪婪法是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对许多问题可能产生整体最优解。 2贪婪算法的概述 2.1 什么是贪婪算法 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步