搜索
智能信息处理-----贪心算法贪心算法的定义贪心算法的基本思想贪心算法的实现思路贪心算法的基本要素贪心算法的特点贪心算法存在的问题•贪心算法•（又称贪婪算法）可以简单描述为：对一组数据进行排序，找出最小值，进行处理，再找出最小值，再处理，也就是说贪心算法是一种依据某种贪心标准，从问题的初始状态出发，在每一步选择中都直接去求每一步的最优解，最终通过若干次的贪心选择得出整个问题的最优解的算法。•贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好或最优的选择，即贪心选择，从而得到结果是最好或最优的算法。••贪心的基本思想•用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。•利用贪心策略解题，需要解决两个问题：•（1）该题是否适合于用贪心策略求解；•（2）如何选择贪心标准，以得到问题的最优/较优解。贪心算法的实现思路应用同一规则F，将原问题变为一个相似的、但规模更小的子问题；从问题的某一初始解出发：while能朝给定总目标前进一步Do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。贪心算法的基本要素•贪心选择性质•所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。（先做选择，再解问题的自顶向下的方式）最优子结构性质•当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。•在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做的贪心选择可以依赖于以往所做过的选择，但决不依赖于将来所做的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。•贪心算法的特点•贪心算法最大的特点就是快，但同时存在两大难点：•（1）如何贪心•具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。一般单纯的贪心算法是顺序处理问题的，而且每个结果是可以在处理完一个数据后即时输出的。•（2）贪心的正确性•要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。贪心算法存在的问题不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；贪心算法只能用来求某些最大或最小解的问题；贪心算法只能确定某些问题的可行性范围。汽车加油问题•问题的提出•一辆汽车加满油后，可行使N千米。旅途中有若干个加油站。若要使沿途加油次数最少，设计一个有效算法，对于给定的N和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。•编码分析•把两加油站的距离放在数组中，a[1..k]表示从起始位置开始跑，经过k个加油站，a[i]表示第i-1个加油站到第i个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n（1）始点到终点的距离小于N，则加油次数k=0；（2）始点到终点的距离大于N时：A加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n；B加油站间的距离相等，即ａ[i]=a[j]=LN，则不可能到达终点；C加油站间的距离相等，即ａ[i]=a[j]=LN，则加油次数k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；D加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过贪心算法求解。•贪心算法策略•由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。（提出问题）•提出问题是解决的开始。为了着手解决遇到的困难，取得最优方案。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。正确性证明•该题设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，因为m+Nn+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在B、C之间且在C的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质由于（b[1]，b[2]，……b[n]）是这段路程加油次数最少的一个满足贪心选择性质的最优解，则易知若在第一个加油站加油时，b[1]=1，则（b[2]，b[3]，……b[n]）是从a[2]到a[n]这段路程上加油次数最少且这段路程上的加油站个数为（a[2]，a[3]，……a[n]）的最优解，即每次汽车中剩下的油不能在行驶到下一个加油站时我们才在这个加油站加一次油，每个过程从加油开始行驶到再次加油满足贪心且每一次加油后相当于与起点具有相同的条件，每个过程都是相同且独立，也就是说加油次数最少具有最优子结构性质。总结•在对问题求解时，会选择当前看起来最有希望成功的边（任务）。一旦做出决定，它就不会再重新考虑，也不会关心后面会引发什么情况。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。•贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法，通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下某种意义的最好选择，即贪心选择。即希望通过问题的局部最优解来求出整个问题的最优解。这种策略是一种很简洁的方法，对许多问题它能产生整体最优解，但不能保证总是有效，因为它不是对所有问题都能得到整体最优解，只能说其解必然是最优解的很好近似值