毕业设计（论文）-贪婪算法系统设计.docx

太原理工大学毕业设计(论文)用纸贪婪算法摘要在求最优解问题的过程中，依据某种贪婪标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪婪算法。从贪婪算法的定义可以看出，贪婪法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪婪算法可以得到最优解。贪婪算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪婪算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪婪算法应该是好的选择之一。本文讲述了贪婪算法的含义、基本思路及实现过程，贪婪算法的核心、基本性质、特点及其存在的问题。并通过贪婪算法的特点举例列出了以往研究过的几个问题，也针对了解的贪婪算法运用到了普通问题中，在实际应用中，使用贪婪算法的特点来解决并得以运用。关键词 最优化问题；贪婪算法；贪心选择；最优解全套设计加扣 3012250582i太原理工大学毕业设计(论文)用纸greedy 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 of the problem, the solving method is the greedy algorithm.Can be seen from the definition of the greedy algorithm, the greedy method does not consider a problem from the whole, the choices it is only in a certain sense of local optimal solution, but is decided by the nature of the problem of the topic using the greedy algorithm can get the optimal solution. The choices made by the greedy algorithm can depend on the choices made by the previous, but should not depend on the choice in the future, also does not depend on the solutions to the subproblems, so greedy algorithm have certain speed advantage compared with other algorithms.if a problem can solve with several methods, at the same time should be greedy algorithm is one of the best choice. This article tells the story of the definition of the greedy algorithm, the basic thought and the implementation process, the core of the greedy algorithm, basic nature, features and problems. By greedy algorithm and the characteristics of the studied several problems, for example, lists the past, also to understand the greedy algorithm is applied to the common problems in the practical applications, the use of the characteristics of the greedy algorithm to solve and to be able to use.Key wordsoptimization problems; greedy algorithm;greedy select;optimal solutionii太原理工大学毕业设计(论文)用纸目录摘要.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.7Java 语言的概述.92.7.1Java 语言基本概念.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太原理工大学毕业设计(论文)用纸1 绪论1.1 研究背景为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。当一个问题具有最优子结构性质和贪心选择性质时，贪婪算法通常会给出一个简单、直观和高效的解法。贪婪算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是在当前状态下具有某种意义的最好选择，即贪心选择；并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。尽管贪婪算法对许多问题不能总是产生整体最优解，但对诸如最短路径问题、最小生成树问题，以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。而且所给出的算法一般比动态规划算法更加简单、直观和高效。贪婪算法是计算机算法策略中常用的一个，往往在需要解决一些最优性问题时，都可以应用贪婪算法。贪婪算法的用法特点有：一是明显的贪心，一般此类应用问题本身就是贪心；二是贪心数据结构，如：堆，最小树；三是可证明贪婪策略的贪心，这是我们最常见的；四是博弈、游戏策略，这些策略大多是贪心；五是求较优解或多次逼近最优解。通过用贪婪算法求解以上问题，可以找到解决这些问题的最优算法，为其它的类似问题的解决有示范和例证作用。1.2 贪婪算法特点及其存在的问题1.2.1 贪婪算法的特点贪婪算法的最大特点也及其优点在于求解问题的每一步都是选择最优解，这样算法就容易实现，也易于理解，同时也提高了效率并节省了时间。然而每一个算法也存在其缺点，故贪婪算法的缺点也是不容小觑的。由于它每次都是逐步获得算法最优解的方法，而不是从整体来考虑最优解，因此它得出的结果仅仅是从某种意义上的局部最有解，但对范围相当广泛的许多问题它都是能得出整体最优解或者是整体最优解的近似解。贪婪算法可解决的问题通常大部分都有如下的特性： 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合1太原理工大学毕业设计(论文)用纸上添加更多的候选对象以获得一个解，和上一个函数一样，此时不考虑解决方法的最优性。 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 最后，目标函数给出解的值。在解决问题中，会选择合适的候选解来优化目标函数，使得贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。1.2.2 贪婪算法存在的问题（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；（2）贪心算法只能用来求某些最大或最小解的问题；（3）贪心算法只能确定某些问题的可行性范围。1.3 本课题研究的内容及其目标贪婪算法的定义（是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法），贪心算法的基本要素（最优子结构性质、贪心选择性质）、贪心算法的思路及过程，贪心算法的核心（贪心策略）及特性（无回溯）、探讨贪心算法存在的问题。然后分析已有成果运用贪心策略的解法（会场活动安排、找零问题、背包问题等），结合所学习到的例子，对上述问题做研究和实现，并根据知道的贪婪算法的知识，对贪婪算法在游戏中的应用，对贪婪算法进行分析与实现。通过资料收集、实际调查分析，最终形成自己的观点和见解，拟定以下内容进行探析：（1）基本知识1）贪心算法的含义2）贪心算法的基本思路及实现过程3）贪心算法的核心4）贪心算法的基本性质5）贪心算法的特点6）贪心算法存在的问题（2）问题的解决以及实现1）会场活动安排2）找零问题3）背包问题（3）贪心算法的实际应用1）在五子棋中的运用2）会场活动安排3）背包问题4）找零问题通过本课题的研究来探讨贪婪算法理论基础以及对贪心策略在更多实例中的运用2太原理工大学毕业设计(论文)用纸做可行的研究，为贪婪算法能够运用到更多的实际中的问题作示范。从学到的贪婪算法的知识中学习到如何运用贪婪算法，在哪些情况下可以优先考虑贪婪算法。1.4 本文组织本文从如下方面进行组织：先提出贪婪算法的基本知识，对贪婪算法有所了解后，再从贪婪算法运用到实例中来解决，主要实例是背包问题，找零钱问题，活动安排问题，最后还将贪婪算法运用到了五子棋游戏中实现了人机对弈。对于用到贪婪算法的实例，有了其具体实现的代码过程，并有了结果。3太原理工大学毕业设计(论文)用纸2 贪婪算法的知识概述2.1 贪婪算法的概念贪婪算法的定义（是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法），贪心算法的基本要素（最优子结构性质、贪心选择性质）、贪心算法的思路及过程，贪心算法的核心（贪心策略）及特性（无回溯）、探讨贪心算法存在的问题。然后分析已有成果运用贪心策略的解法（会场活动安排、找零问题、背包问题等），结合所学习到的例子，对上述问题做研究和实现，并根据知道的贪婪算法的知识，对贪婪算法在游戏中的应用，对贪婪算法进行分析与实现。贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。贪婪算法选取一个量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，有很多量度标准，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。2.2 贪婪算法的思路及实现过程2.2.1 贪婪算法思路用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪婪算法思想的本质就是分治，或者说：分治是贪心利用贪心策略解题，需要解决两个问题：（1）该题是否适合于用贪心策略求解；（2）如何选择贪心标准，以得到问题的最优/较优解的基础。每次都形成局部最优解，换一种方法说，把局部子结构的最优解合成问题的最优解。2.2.2 实现过程（1）应用同一规则，将原问题变为一个相似的、但规模更小的子问题；4太原理工大学毕业设计(论文)用纸（2）从问题的某一初始解出发：While（能朝给定目标前进一步）do求出可行解的一个解元素；（3）由所有解元素组合成问题的一个可行解。2.3 贪婪算法的核心贪婪算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。2.4 贪婪算法的基本要素2.4.1 最优量度标准所谓贪婪算法的最优量度标准，是指可以根据该量度标准，实行多步决策进行求解，虽然在该量度意义下所做的这些选择都是局部最优的，但最终得到的解却是全局最优的。选择最优量度标准是贪婪法的求解的核心问题，值得注意的是，贪婪算法每一步做出的选择可以依赖以前做出的选择，但决不依赖将来的选择，也不依赖于子问题的解。虽然贪婪算法的每次选择也将问题简化成一个规模更小的子问题，但由于贪婪算法某一步选择并不依赖于子问题的解，每一步选择只按照最有量度标准进行。所以对于一个贪心算法，必须证明所采用的量度标准能够导致一个整体的最优解。每一个问题都有它的最优量度的标准，比如背包问题的最优量度标准就是按照 pi/wi 的非递增次序选取物品，装入背包。人机对弈问题的最优量度标准就是在人与电脑下棋后棋子的位置，用到一个函数来找出计算机下棋的最大值，并下子，同样最短路径和生成树的量度标准也是最优量度标准。2.4.2 最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪婪算法或动态规划算法求解的关键特征。贪婪算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪婪算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。2.5 贪婪算法的理论基础2.5.1 目标函数所谓最优化问题是指这样一类问题，问题给定某些约束条件，满足这些条件的问题解可称为可行解。通常满足约束条件的解不是惟一的，为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数，使目标函数取得最大（或者最小）值的可行解称为最优解。5太原理工大学毕业设计(论文)用纸当所选定可行解的候选集是有限时，从理论上讲可以使用穷举法，一一考察候选解集中的每一个，检查是否满足约束条件。若某个候选解集能够满足约束条件，则它便是一个可行解。此外，还可以同时用目标函数衡量每个可行解，从中找出最优解。显然当候选集很庞大的时候，这种方法是费时而不经济的。如果候选集是无限集，将无法实施穷举法求解。2.5.2 贪婪算法解向量一般来讲，如果一个问题适合贪婪算法求解，问题的解应该可以表示成一个 n-元组（x0,x1.xn），其中每一个分量 xi 取自某个值集 S，所有允许的 n-元组组成一个候选集，问题中应给出用于判定一个候选解是否可行的约束条件，满足判定方法的候选解称为可行解。同时还给定一个数值函数称为目标函数，用于衡量每个可行解的优劣，使目标函数取得最大（或最小）值的可行解为最优解。贪婪法在求解问题的每一步上做出某种决策，产生 n-元组解的一个分量。贪婪发要求根据题意，选定一种最优的量度标准，做为选择当前分量值的依据。这种在贪婪法每一步上用做决策依据的选择准则则被称为最优量度标准或者贪心准则，也称贪心选择性质。这种量度标准通常只考虑局部最优。解向量 solution=空集，其中未包含任何分量，在使用最优量度标准，一次选择一个分量，逐步形成解向量（x1,x2.xn）。算法过程中生成的向量（x1,x2.xk）,kn,称为部分解向量，也称部分向量。在跟据最有量度标准选择分量的过程中，还需要使用一个可行解判定