《利用贪婪算法实现多种实际问题》由会员分享，可在线阅读，更多相关《利用贪婪算法实现多种实际问题（14页珍藏版）》请在金锄头文库上搜索。
1、利用贪婪法实现多种实际问题I算法设计与分析课程设计任务书学院名称： 数学与计算机学院 专业： 信息与计算科学专业 年级： 2007 一、设计题目题目十四：利用贪婪算法实现多种实际问题二、主要内容给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。三、具体要求（1）贪婪算法的基本思想；（2）给出背包问题的贪婪算法；（3）给出有限期计算机作业调度的贪婪算法；（4）给出上面两个算法的证明；（5）给出上面两个算法的程序。（6）给出时间复杂度。四、主要技术路线提示在用贪婪算法解决资源分配问题、布线问题、0-1 背包问题过程中，使用贪婪算法解决问题，通常需要做好以下几个方面的工作：1、明确问题的求解
2、目标。2、分析问题所包含的约束条件。3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。4、制定贪婪准则。五、进度安排 1、第一周:分析题目的需求，设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型并编写上机程序2、第二周 完成程序开发，进行测试并分析结果，最后撰写课程设计报告利用贪婪法解决实际问题II六、完成后应上交的材料上交的成果的内容必须由以下四个部分组成，缺一不可。1上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中） 。2上交程序的说明文件：（保存在.txt 中） ，在说明文档中应该写明上交程序所在的目录，上交程序的主程序
3、文件名，如果需要安装，要有程序的安装使用说明。3课程设计报告电子文档：（保存在 word 文档中，文件名要求 按照“学号姓名算法分析课设报告.doc”起名，如文件名为“200300109 张三算法分析课设报告.doc” ） ，按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成：其中包括：（1）需求分析：在该部分中叙述每个模块的功能要求等。（2）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图） ，每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。（3）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功
4、能模块采用不同的函数实现） 。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。（4）调试分析包括测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？） ，算法的改进设想。（5）课设总结总结可以包括 ：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对算法设计与分析这门课程的思考、在课程设计过程中对算法设计与分析课程的认识等内容。4课程设计报告打印稿。七、推荐参考资料教 材： 算法设计与分析 Anany Levitin 著 潘彦译 清华大学出版社，2007。算法设
5、计与分析 宋 文 等编 重庆大学出版社，2001。参考书：1 算法设计与分析 周培德 电子工业出版社，2000。2 算法设计与分析 王晓东 电子工业出版社，2004指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日 目 录1 引言 .12 贪婪算法的概述 .12.1 什么是贪婪算法 .12.2 贪婪算法的特性 .12.3 贪婪算法解决问题的步骤 .22.4 贪婪算法的优缺点 .23 贪婪算法的应用 .33.1 贪婪算法在资源分配问题中的应用 .33.2 贪婪算法在布线问题中的应用 .43.3 贪婪算法在 0/1 背包问题中的应用 .63.3.1 传统的贪婪算法解决方案 .63.3.
6、2 改进的贪婪算法策略 .74 总结与展望 .9参考文献 .10利用贪婪法实现多种实际问题- 1 -引言为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的
7、方法来求解该问题。 目前常用的算法设计技术有分治法、回溯法、贪婪法、动态规划算法、分支限界法等。其中分治法、回溯法主要用于设计非数值问题的算法,而贪婪法、动态规划算法、分支限界法则主要用于设计数值最优化问题的算法。贪婪法是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对许多问题可能产生整体最优解。2 贪婪算法的概述2.1 什么是贪婪算法贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用
8、自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解， 则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初
9、看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。2.2 贪婪算法的特性利用贪婪法解决实际问题2贪婪
10、算法及贪婪算法可解决的问题通常大部分都有如下的特性:（1） 有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合：比如不同面值的硬币。（2） 随着算法的进行,将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。（3） 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。（4） 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。（5） 选择函数可以指出哪一个剩余的候选对象最有希望构成问
11、题的解。（6） 最后,目标函数给出解的值。为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。2.3 贪婪算法解决问题的步骤贪婪算法的一般解题步骤:设计中一类非常重要的问题。每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解方案称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪婪算法是解
