贪心算法的证明方法？什么是贪心算法

本文目录

• 贪心算法的证明方法
• 什么是贪心算法
• 贪心算法
• 简述贪心，递归，动态规划，及分治算法之间的区别和联系
• 贪心算法的本质
• 贪心算法的特性
• Python贪心算法
• 贪心算法的基本思路
• 贪心算法的例题分析

贪心算法的证明方法

贪心算法的基本思路如下：　　1.建立数学模型来描述问题。　　2.把求解的问题分成若干个子问题。　　3.对每一子问题求解，得到子问题的局部最优解。　　4.把子问题的解局部最优解合成原来解问题的一个解。----------------------------------------------其实归纳起来也就一个类。其他的都是分支

什么是贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。

3.2.2.1 贪心算法1

第一步:设置一个记录三角剖分中边的数组T。

第二步:计算点集S中所有点对之间的距离d(p_i，p_j)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d₁，d₂，…，d_n(n-1)/2，相应的线段记为e₁，e₂，…，e_n(n-1)/2，将这些线段存储在数组E中。

第三步:从线段集E中取出长度最短的边e₁存到T中作为三角剖分的第一条边，此时k=1。

第四步:依次从E中取出长度最短的边e_k，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除e_k。这一步运行到S中没有边为止，即至k=n(n-1)/2。

第五步:输出T。

该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n)

简述贪心，递归，动态规划，及分治算法之间的区别和联系

联系：都是问题求解之时的一种算法。

区别：

一、作用不同

1、贪心算法：把子问题的解局部最优解合成原来解问题的一个解。

2、递归算法：问题解法按递归算法实现。如Hanoi问题；数据的结构形式是按递归定义的。如二叉树、广义表等。

3、动态规划：动态规划算法通常用于求解具有某种最优性质的问题。

4、分治算法：可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。

二、方法不同

1、贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

2、递归算法：通过重复将问题分解为同类的子问题而解决问题。

3、动态规划：将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。

4、分治算法：将一个规模为N的问题分解为K个规模较小的子问题。

三、特点不同

1、贪心算法：根据题意选取一种量度标准。

2、递归算法：递归就是在过程或函数里调用自身。

3、动态规划：虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

4、分治算法：原问题可以分解为多个子问题；原问题在分解过程中，递归地求解子问题；在求解并得到各个子问题的解后。

贪心算法的本质

1. 贪心法（Greedy Algorithm）定义 求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择； 贪心法就是这样的算法：它在每个决策点作出在当时看来最佳的选择，即总是遵循某种规则，做出局部最优的选择，以推导出全局最优解（局部最优解-》全局最优解）2. 对贪心法的深入理解 （1）原理：一种启发式策略，在每个决策点作出在当时看来最佳的选择 （2）求解最优化问题的两个关键要素：贪心选择性质+最优子结构 ①贪心选择性质：进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解； ②最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质 （3）解题关键：贪心策略的选择 贪心算法不是对所有问题都能得到整体最优解的，因此选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 （4）一般步骤： ①建立数学模型来描述最优化问题； ②把求解的最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解； ③证明做出贪心选择后： 1°原问题总是存在全局最优解，即贪心选择始终安全； 2°剩余子问题的局部最优解与贪心选择组合，即可得到原问题的全局最优解。 并完成2°3. 贪心法与动态规划 最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

贪心算法的特性

贪婪算法可解决的问题通常大部分都有如下的特性：⑴随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。⑵有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。⑶还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。⑷选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。⑸最后，目标函数给出解的值。⑹为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

Python贪心算法

所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优加以考虑，它所做出的仅仅是在某种意义上的局部最优解。下面让我们来看一个经典的例题。假设超市的收银柜中有1分、2分、5分、1角、2角、5角、1元的硬币。顾客结账如果需要找零钱时，收银员希望将最少的硬币数找出给顾客，那么，给定需要找的零钱数目，如何求得最少的硬币数呢？这个找零钱的基本思路：每次都选择面值不超过需要找给顾客的钱最大面值的硬币。我们可以从面值最大的硬币开始，然后依次递减（图1）。首先定义列表d存储已有币值。并且定义d_num存储每种币值的数量。通过循环遍历的方法计算出收银员拥有钱的总金额并保存在变量S中，要找的零钱变量为sum。当找零的金_比收银员的总金额多时，无法进行找零，提示报错。要想用的钱币数量最少，我们从面值最大的币值开始遍历。这里也就是我们贪心算法的核心步骤。计算出每种硬币所需要的数量，不断地更新硬币个数与硬币面值，最终获得一个符合要求的组合（图2）。贪心算法在对问题求解时，不是对所有问题都能得到整体最优解，也不是从整体上去考虑，做出的只是在某种意义上的局部最优解。从面值最大的硬币开始依次递减，寻找可用的方法。一般贪心算法并不能保证是最佳的解决方法，这是因为：总是从局部出发没有从整体考虑，只能确定某些问题是有解的，优点是算法简单。常用来解决求最大值或最小值的问题。来源：电脑报

贪心算法的基本思路

1.建立数学模型来描述问题⒉把求解的问题分成若干个子问题。⒊对每一子问题求解，得到子问题的局部最优解。⒋把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。

贪心算法的例题分析

例题1、:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x》10）or(y》10）or(x1》10）or(y1》10）Thenwriteln(’Error’){判断是否越界}ElseFind(x,y);Writeln(’Total:’,total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。怎么才能快速地得到部分解呢？【贪心算法】其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。