当前位置:首页>> >>


基于java的贪婪算法研究与设计.rar

收藏

资源目录
    文档预览:
    编号:20180913143531169    类型:共享资源    大小:16.13MB    格式:RAR    上传时间:2018-09-13
    尺寸:148x200像素    分辨率:72dpi   颜色:RGB    工具:   
    40
    金币
    关 键 词:
    基于 java 贪婪 算法 研究 设计
    资源描述:
    太原理工大学毕业设计(论文)用纸i贪婪算法摘要在求最优解问题的过程中,依据某种贪婪标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪婪算法。从贪婪算法的定义可以看出,贪婪法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪婪算法可以得到最优解。贪婪算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,因此贪婪算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪婪算法应该是好的选择之一。本文讲述了贪婪算法的含义、基本思路及实现过程,贪婪算法的核心、基本性质、特点及其存在的问题。并通过贪婪算法的特点举例列出了以往研究过的几个问题,也针对了解的贪婪算法运用到了普通问题中,在实际应用中,使用贪婪算法的特点来解决并得以运用。关键词 最优化问题;贪婪算法;贪心选择;最优解太原理工大学毕业设计(论文)用纸iigreedy algorithmAbstractIn the process of optimal solution problem, according to certain standards of greed,starting from the initial state of the problem, go directly to every step of the optimal solution,through several times of greedy selection, finally it is concluded that the optimum solution oftheproblem, thesolvingmethod is thegreedy algorithm.Can be seen from the definition of the greedy algorithm, the greedy method does notconsider a problem from the whole, the choices it is only in a certain sense of local optimalsolution, but is decided by the nature of the problem of the topic using the greedy algorithmcan get the optimal solution. The choices made by the greedy algorithm can depend on thechoices made by the previous, but should not depend on the choice in the future, also doesnot depend on the solutions to the subproblems, so greedy algorithm have certain speedadvantage compared with other algorithms.if a problem can solve with several methods, at the same time should be greedyalgorithm is one of the best choice. This article tells the story of the definition of the greedyalgorithm, thebasicthought and the implementation process, thecore of thegreedy algorithm,basic nature, features and problems. By greedy algorithm and the characteristics of thestudied several problems, for example, lists the past, also to understand the greedy algorithmis applied to the common problems in the practical applications, the use of the characteristicsofthe greedy algorithmto solveand tobe ableto use.Key words optimization problems; greedy algorithm;greedy select;optimal solution太原理工大学毕业设计(论文)用纸目 录摘要.............................................................................................................................................iAbstract......................................................................................................................................ii1 绪论......................................................................................................................................11.1 研究背景..................................................................................................................11.2 贪婪算法特点及其存在的问题..............................................................................11.2.1 贪婪算法的特点..........................................................................................11.2.2 贪婪算法存在的问题..................................................................................21.3 本课题研究的内容及其目标..................................................................................21.4 本文组织..................................................................................................................32 贪婪算法的知识概述..........................................................................................................42.1 贪婪算法的概念......................................................................................................42.2 贪婪算法的思路及实现过程..................................................................................42.2.1 贪婪算法思路..............................................................................................42.2.2 实现过程......................................................................................................42.3 贪婪算法的核心......................................................................................................52.4 贪婪算法的基本要素..............................................................................................52.4.1 最优量度标准..............................................................................................52.4.2 最优子结构性质..........................................................................................52.5 贪婪算法的理论基础..............................................................................................52.5.1 目标函数......................................................................................................52.5.2 贪婪算法解向量..........................................................................................62.5.3 贪婪算法框架描述......................................................................................62.6 经典问题的讨论......................................................................................................62.6.1 哈夫曼编码..................................................................................................62.6.2 最小生成树问题(Prim算法、Kruskal算法).............................................82.7 Java语言的概述......................................................................................................92.7.1 Java语言基本概念......................................................................................92.7.2 历史起源......................................................................................................92.7.3 基本组成....................................................................................................102.7.4 主要特性....................................................................................................102.7.5 与C/C++的差异........................................................................................113 会场活动安排的问题........................................................................................................133.1 问题的提出....................................................................................................................133.2 编码原理................................................................................................................133.3 贪婪算法................................................................................................................133.3.1 贪婪思想....................................................................................................133.3.2 贪婪策略....................................................................................................13太原理工大学毕业设计(论文)用纸3.3.3 贪婪算法核心部分....................................................................................133.3.4 算法流程图................................................................................................153.4 最优解的体现.........................................................................................................153.4.1 顺序递增的结束时间................................................................................153.4.2 无序的结束时间........................................................................................163.4.3 算法分析....................................................................................................164 找零钱问题........................................................................................................................174.1 问题的提出............................................................................................................174.2 编码的原理............................................................................................................174.3 贪婪算法................................................................................................................174.3.1 贪婪思想....................................................................................................174.3.2 贪婪策略....................................................................................................174.4 最优解的体现........................................................................................................174.4.1 最优解的说明............................................................................................174.4.2 最优解的证明............................................................................................184.4.3 找零问题的核心代码................................................................................184.4.4 找零问题算法流程图................................................................................185 一般背包问题....................................................................................................................195.1 问题的提出............................................................................................................195.2 编码的原理............................................................................................................195.3 贪婪算法................................................................................................................195.3.1 贪婪策略....................................................................................................195.3.2 贪婪策略实现思想....................................................................................195.3.3 算法流程图................................................................................................205.3.4 背包问题的核心算法................................................................................205.4 最优解的证明........................................................................................................216 五子棋游戏........................................................................................................................236.1 可行性研究............................................................................................................236.1.1 经济可行性................................................................................................236.1.2 技术可行性................................................................................................236.2 系统设计................................................................................................................236.2.1 概要设计....................................................................................................236.2.2 详细设计....................................................................................................246.3 五子棋游戏贪婪算法............................................................................................266.3.1 贪婪策略....................................................................................................266.3.2 贪婪算法的体现........................................................................................266.3.4 五子棋游戏核心算法................................................................................267 贪婪算法实现语言及结果................................................................................................27太原理工大学毕业设计(论文)用纸7.1 语言实现的算法部分............................................................................................277.1.1 贪婪算法主界面........................................................................................277.1.2 主界面展示................................................................................................287.1.3 贪婪算法实例界面的实现........................................................................287.1.4 贪婪算法实例界面的展示........................................................................297.1.5 贪婪算法五子棋游戏主界面....................................................................297.2 实例代码结果展示................................................................................................307.2.1 会场活动安排............................................................................................307.2.2 背包问题....................................................................................................307.2.3 找零问题....................................................................................................317.2.4 五子棋游戏................................................................................................31结 论......................................................................................................................32参考文献..................................................................................................................................33致 谢......................................................................................................................................34外文原文..................................................................................................................................35中文翻译..................................................................................................................................39太原理工大学毕业设计(论文)用纸11 绪论1.1 研究背景为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。当一个问题具有最优子结构性质和贪心选择性质时,贪婪算法通常会给出一个简单、直观和高效的解法。贪婪算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是在当前状态下具有某种意义的最好选择,即贪心选择;并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。尽管贪婪算法对许多问题不能总是产生整体最优解,但对诸如最短路径问题、最小生成树问题,以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且所给出的算法一般比动态规划算法更加简单、直观和高效。贪婪算法是计算机算法策略中常用的一个,往往在需要解决一些最优性问题时,都可以应用贪婪算法。贪婪算法的用法特点有:一是明显的贪心,一般此类应用问题本身就是贪心;二是贪心数据结构,如:堆,最小树;三是可证明贪婪策略的贪心,这是我们最常见的;四是博弈、游戏策略,这些策略大多是贪心;五是求较优解或多次逼近最优解。通过用贪婪算法求解以上问题,可以找到解决这些问题的最优算法,为其它的类似问题的解决有示范和例证作用。1.2 贪婪算法特点及其存在的问题1.2.1 贪婪算法的特点贪婪算法的最大特点也及其优点在于求解问题的每一步都是选择最优解,这样算法就容易实现,也易于理解,同时也提高了效率并节省了时间。然而每一个算法也存在其缺点,故贪婪算法的缺点也是不容小觑的。由于它每次都是逐步获得算法最优解的方法,而不是从整体来考虑最优解,因此它得出的结果仅仅是从某种意义上的局部最有解,但对范围相当广泛的许多问题它都是能得出整体最优解或者是整体最优解的近似解。贪婪算法可解决的问题通常大部分都有如下的特性:⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合:比如不同面值的硬币。⑵ 随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。⑷ 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合太原理工大学毕业设计(论文)用纸2上添加更多的候选对象以获得一个解,和上一个函数一样,此时不考虑解决方法的最优性。⑸选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。⑹最后,目标函数给出解的值。在解决问题中,会选择合适的候选解来优化目标函数,使得贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。1.2.2 贪婪算法存在的问题(1)不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择,因此并不从整体上加以考虑;(2)贪心算法只能用来求某些最大或最小解的问题;(3)贪心算法只能确定某些问题的可行性范围。1.3 本课题研究的内容及其目标贪婪算法的定义(是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法),贪心算法的基本要素(最优子结构性质、贪心选择性质)、贪心算法的思路及过程,贪心算法的核心(贪心策略)及特性(无回溯)、探讨贪心算法存在的问题。然后分析已有成果运用贪心策略的解法(会场活动安排、找零问题、背包问题等),结合所学习到的例子,对上述问题做研究和实现,并根据知道的贪婪算法的知识,对贪婪算法在游戏中的应用,对贪婪算法进行分析与实现。通过资料收集、实际调查分析,最终形成自己的观点和见解,拟定以下内容进行探析:(1)基本知识1)贪心算法的含义2)贪心算法的基本思路及实现过程3)贪心算法的核心4)贪心算法的基本性质5)贪心算法的特点6)贪心算法存在的问题(2)问题的解决以及实现1)会场活动安排2)找零问题3)背包问题(3)贪心算法的实际应用1)在五子棋中的运用2)会场活动安排3)背包问题4)找零问题通过本课题的研究来探讨贪婪算法理论基础以及对贪心策略在更多实例中的运用太原理工大学毕业设计(论文)用纸3做可行的研究,为贪婪算法能够运用到更多的实际中的问题作示范。从学到的贪婪算法的知识中学习到如何运用贪婪算法,在哪些情况下可以优先考虑贪婪算法。1.4 本文组织本文从如下方面进行组织:先提出贪婪算法的基本知识,对贪婪算法有所了解后,再从贪婪算法运用到实例中来解决,主要实例是背包问题,找零钱问题,活动安排问题,最后还将贪婪算法运用到了五子棋游戏中实现了人机对弈。对于用到贪婪算法的实例,有了其具体实现的代码过程,并有了结果。太原理工大学毕业设计(论文)用纸42 贪婪算法的知识概述2.1 贪婪算法的概念贪婪算法的定义(是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法),贪心算法的基本要素(最优子结构性质、贪心选择性质)、贪心算法的思路及过程,贪心算法的核心(贪心策略)及特性(无回溯)、探讨贪心算法存在的问题。然后分析已有成果运用贪心策略的解法(会场活动安排、找零问题、背包问题等),结合所学习到的例子,对上述问题做研究和实现,并根据知道的贪婪算法的知识,对贪婪算法在游戏中的应用,对贪婪算法进行分析与实现。贪婪算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得
    展开阅读全文
    1
      金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    0条评论

    还可以输入200字符

    暂无评论,赶快抢占沙发吧。

    关于本文
    本文标题:基于java的贪婪算法研究与设计.rar
    链接地址:http://www.gold-doc.com/p-116471.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们
    copyright@ 2014-2018 金牌文库网站版权所有
    经营许可证编号:浙ICP备15046084号-3
    收起
    展开