贪心算法的分析与实际应用

天津师范大学计算机与信息工程学院算法设计与分析期末论文话题贪婪算法的分析及实际应用专业计算机科学与技术1402级学校编号第一个名字叫王刘阳老师竣工日期2015-1-18贪婪算法的分析及实际应用王摘要：贪婪算法是指在解决问题时，总是做出目前最好的选择。也就是说，从某种意义上说，他所做的只是局部最优解，而没有考虑整体最优解。贪婪算法不能获得所有问题的全局最优解，但它能为广泛的问题产生全局最优解或全局最优解的近似解。本文主要介绍贪婪算法的核心、特点和存在的问题。关键词：贪婪算法；最佳解决方案；背包问题；那匹马踩在棋盘上。贪婪算法分析及实际应用王天津师范大学计算机与信息工程学院摘要：贪婪算法是指，在解决问题时，总是做出在当前看来是最好的选择。也就是说，不作为一个整体来考虑，他只作出了某种意义上的局部最优解。贪婪算法不能获得所有问题的全局最优解，但对于广泛的问题，他可以产生全局最优解或全局最优解的近似解。本文主要介绍gr eedy算法的核心，算法本身的特点和存在的问题.关键词：贪婪算法；最佳解决方案；背包问题；介绍研究背景：为了满足人们对大数据量信息处理的需求和解决各种实际问题，计算机算法得到了迅速发展。线性规划、动态规划和贪婪策略等一系列运筹学模型被应用到计算机算法中，产生了解决各种实际问题的有效算法。虽然设计一个好的算法更像是一门艺术，而不是一项技术，但是仍然有一些有效的算法设计方法可以用来解决许多问题。当问题具有最优子结构性质和贪婪选择性质时，贪婪算法通常给出一个简单、直观和有效的解。贪婪算法通过一系列选择获得问题的解。在当前状态下，它做出的每一个选择都是有一定意义的最佳选择，即贪婪的选择。每一个贪婪的选择都可以将问题简化成一个与原问题形式相同的小问题。虽然贪婪算法不能总是对许多问题产生全局最优解，但它对诸如最短路径问题、最小生成树问题、哈夫曼编码问题等问题有最优子结点。然而，对于构造和贪婪选择问题，可以获得全局最优解。此外，该算法通常比动态编程算法更简单、更直观和更有效。贪婪算法1.1贪婪算法概述贪婪算法是解决一些优化问题的一种更简单、更快速的设计技术。贪婪方法的特征在于算法是逐步设计的，并且通常根据基于当前情况的优化措施进行最优选择，而不考虑各种可能的总体情况。为了找到最佳解决方案，它节省了用尽所有可能性所需的大量时间。它采用自上而下的迭代方法进行连续的贪婪选择。每个贪婪的选择都将期望的问题简化成一个更小的子问题。通过每个贪婪的选择，可以得到问题的最优解。尽管每一步都必须获得局部最优解，但最终的全局解可能并不总是最优的，所以贪婪方法不应该后退。贪婪算法是一种改进的分层处理方法。核心是根据主题选择测量标准。然后，以测量标准要求的顺序排列多个输入，并且以该顺序一次输入一个量。如果这个输入和当前在这个度量的意义上形成的一些最佳解决方案不能被加在一起产生一个可行的解决方案，那么这个输入不会被加到这个分解中。这种能在一定程度上获得最优解的层次化处理方法称为贪婪算法。对于给定的问题，通常有几种度量方法。乍一看，这些度量似乎是可取的，但实际上，在这个度量意义上，通过贪婪处理获得的最优解不是问题的最优解，而是次优解。因此，贪婪算法的核心是选择能够产生问题最优解的最优度量。一般来说，选择最佳测量标准并不容易，但是当可以选择最佳测量标准时，使用贪婪算法来解决问题尤其有效。最优解可以通过一系列局部最优的选择来实现，即贪婪的选择。根据当前状态，做出最佳选择，即局部最优解选择，然后求解做出该选择后生成的相应子问题。每一个贪婪的选择都会将问题归结为一个更小的子问题，最终得到一个整体最优解。1.2贪婪算法的基本思想全局解由局部解构成，即问题的某个初始解逐渐逼近给定的目标，以尽快获得更好的解。当算法中的一个步骤不能继续时，算法停止。贪婪算法的本质是分而治之，或者说分而治之是贪婪的基础。每次都形成局部最优解，换句话说，每次都处理最佳解。1.3贪婪算法的核心贪婪算法的核心问题是选择能够产生最佳解的最佳度量，即具体的贪婪策略。贪婪策略是指一种解决问题的方法，它通过从问题的初始状态开始的几个贪婪的选择来获得最优值(或更好的解决方案)。事实上，从“贪婪策略”一词中，我们可以看出，在目前看来，贪婪策略总是做出最好的选择，也就是说，贪婪策略不是作为一个整体来考虑的，它做出的选择在某种意义上只是一个局部最优解，而许多问题的特征决定论可以用来获得最优解或更好的解。1.4贪婪算法特征贪婪算法可以解决大多数问题，通常有以下特点：(1)有一个问题需要以最佳方式解决。为了构造该问题的解决方案，存在一组候选对象：例如不同面额的硬币。(2)随着算法的进行，另外两个集合：将被累积，一个包含已经被考虑和选择的候选，另一个包含已经被考虑和丢弃的候选。(3)有一个功能来检查一组候选对象是否提供了问题的解决方案。该函数不考虑此时的解决方案是否最优。(4)还有一个检查一组候选对象是否可行的功能，也就是说，是否可能向该组添加更多的候选对象以获得解决方案。像前面的函数一样，此时不考虑解的最优性。(5)选择功能可以指示剩余候选中的哪一个最有可能形成问题的解决方案。(6)最后，目标函数给出解的值。为了解决这个问题，有必要找到构成解决方案的候选对象集。它可以优化目标函数，贪婪算法是逐步进行的。首先，算法选择的候选对象集是空的。在下一步中，根据选择函数，算法从剩余的候选对象中选择最有可能形成解的对象。如果将对象添加到集合中是不可行的，那么该对象将被丢弃并且不再被考虑。否则，它将被添加到集合中。每次集合被扩展时，检查该集合是否构成一个解。如果贪婪算法工作正常，找到的第一个解通常是最优的。1.5贪婪算法的理论基础拟阵贪婪策略是最接近人类认知思维的解决问题策略。然而，这种方法越明显，就越难证明。“拟阵”理论是一种可以确定贪婪策略何时能产生最优解的理论。拟阵M被定义为满足以下三个条件的有序对(S，I):(1) S是非空有限集合；(2)I是具有遗传性质的独立子集族，即如果BI，B是S的独立子集，并且B的任何子集也是S的独立子集。空集比是I的子集；(3)满足交换性质，即如果AI，BI，和|A|B|，则有一个元素xB-A，使Ax I；定理2.1拟阵M中的所有最大独立子集都具有相同的大小。引理2.1(拟阵的贪婪选择性质)设M=(S，I)是一个带权函数M的加权拟阵，S中的元素按权值由大到小排列，设xS是S中的第一个元素，使得x是一个独立的子元素，那么就有一个S的最优子集A，使得xA.引理2.2让M=(S，I)是拟阵。如果S中的元素X不是空集的可展开元素，那么X也不能是S中任何独立子集A的可展开元素。引理2.3(拟阵的最优子结构性质)设X是S中的第一个元素，它是一种寻找加权拟阵的最优子集的贪婪算法。然后，将原问题简化，得到加权拟阵M=(S ，I )的最优子集。定理2.4(加权拟阵的贪婪算法的正确性)高M=(S，I)是一个带权函数W的加权拟阵，算法贪婪返回M的最优子集许多适用于贪婪策略的问题可以归结为在加权拟阵中寻找一个总权重最大的独立子集的问题，即给定一个加权拟阵M=(S，I)，如果可以找到一个具有最大可能权重的独立子集a，并且a没有被大于它的独立子集M所包含，那么a就是最优子集，也是最大独立子集。我们认为，只要拟阵的结构是可用的，贪婪策略就可以用来解决大多数信息学问题。拟阵理论对于我们判断贪婪策略是否适用于复杂问题是非常有效的。1.6贪婪算法的优缺点贪婪算法是一种重要的算法设计策略，其效率很高。贪婪算法不考虑整体最优选择，而只考虑局部最优选择，从某种意义上说，就是目前的最佳选择。人们希望每一个贪婪的选择都会导致问题的最佳解决方案。贪婪算法具有良好的爬山能力。一般来说，该算法可以快速找到满足计算精度要求的近似最优解。当算法在有限时间内无法找到满足问题要求的近似最优解时，给出可行解及其计算误差作为决策参考。然而，随着问题规模和复杂性的不断增加，单一算法在收敛和求解速度方面都表现出了局限性。即使贪婪算法是高效的，它也只能应用于少量的实例。用贪婪算法解决问题2.1背包问题2.1.1问题描述0-1背包问题有一个容量为M=150的背包。有7个项目，不能分成任何大小。要求背包中物品的总价值最大化，但不能超过总容量。因为每次有东西装入背包，我们只考虑它是否能被装入，以及在当前状态下它是否是最好的选择，也就是说，我们需要设计一个有背包容量的数组，以及每个单位容量的最大值是多少，等等，以获得背包容量的最大值。2.1.2贪婪算法策略目标函数：pi最大值约束条件是装载物品的总重量不超过背包容量：wi=M(M=150)，每次选择单位重量值最大的物品作为解决问题的策略。值得注意的是，贪婪算法并非完全不可用。一旦贪婪策略被证明是有效的，它就是一个有效的算法。贪婪算法仍然是常见的算法之一，因为它简单且易于实现，并且构造贪婪策略并不十分困难。一般来说，贪婪算法的证明集中在：整个问题的最优解必须从贪婪策略中存在的子问题的最优解中获得。对于例子中的三种贪婪策略，它们都是站不住脚的(无法证明)。解释如下：(1)贪婪策略：选择价值最大的策略。反例：W=30项目：甲、乙、丙重量：28 12 12价值：30 20 20根据策略，首先选择项目A，然后不能选择项目A，但最好选择项目B和项目c(2)贪婪策略：选择最小权重。它的反例与第一种策略相似。(3)贪婪策略：选择单位重量价值最大的物品。反例：W=30项目：甲、乙、丙重量：28 20 10价值：28 20 10根据策略，这三个项目的单位重量和价值是相同的。程序无法根据现有策略做出判断。如果选择A，答案是错误的。注：如果文章可以分成任何大小，那么最佳解决方案可以通过策略3获得对于选择单位重量值最大的项目的策略，可以添加一个优化规则：对于单位重量值相同的项目，优先选择重量较小的项目。这样，上述反例就解决了。然而，如果主题如下，这个策略也不会起作用。W=40项目：甲、乙、丙重量：25 20 15价值：25 20 152.1.3求解背包问题的贪婪算法代码如下：#包括struct goodinfo浮动p；/商品利益浮动w；/项目重量浮动X；/要放的物品数量int标志；/项目编号；/项目信息结构国际货物公司/插入排序，按pi/wi值收入排序国际j，I；对于(j=2；j=n。j)货物0=货物j；I=j-1；而(商品