贪心算法
一、基本概念：
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本思路：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
六、例题分析
下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
动态规划和贪心算法的区别
动态规划和贪心算法都是一种递推算法
均有局部最优解来推导全局最优解
不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解
==============================================================================
贪心算法与动态规划
贪心法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1.
2.
3.
从问题的某一初始解出发；
while
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解
贪心算法最经典的例子，给钱问题。
比如中国的货币，只看元，有1元2元5元10元20、50、100
如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？
如果用贪心算，就是我每一次拿那张可能拿的最大的。
比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元
也就是3张
每次拿能拿的最大的，就是贪心。
但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解，而且贪心算法很好想得到。
再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了
比如某国的钱币分为
如果要拿6元钱
实际最优呢？
求最优解的问题，从根本上说是一种对解空间的遍历。最直接的暴力分析容易得到，最优解的解空间通常都是以指数阶增长，因此暴力穷举都是不可行的。
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，如上面的分析，这是不可行的。
贪心和动态规划本质上是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是“子问题最优性”。即，组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的。如果以自顶向下的方向看问题树（原问题作根），则，我们每次只需要向下遍历代表最优解的子树就可以保证会得到整体的最优解。形象一点说，可以简单的用一个值（最优值）代表整个子树，而不用去求出这个子树所可能代表的所有值。
动态规划方法代表了这一类问题的一般解法。我们自底向上（从叶子向根）构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。动态规划的代价就取决于可选择的数目（树的叉数）和子问题的的数目（树的节点数，或者是树的高度？）。
贪心算法是动态规划方法的一个特例。贪心特在，可以证明，每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。
No comments:
Post a Comment