分治 动态规划 贪婪
Mobius Wang
标准分治、动态规划和贪婪选择可以说是孙子兵法里面的上、中、下三策。 标准分治虽然将大问题分解为小问题，但每个小问题都需要一个一个解决，相当于逢城必攻，属于下策；动态规划则聪明的发现很多子问题相同，并不需要重新解 决，就是不对每个城市都进行攻城，从而节省兵力和精力，但仍然需要攻克子问题中的相当部分，属于中策；而贪婪策略则将子问题限于一个，即将攻城数量减少到 了最低，从而最大限度上节省了精力和兵力，属于上策。 不过就像兵法里所云，上策运用得不好，就有失策的时候。贪婪思想运用得不当，或者在条件不充分或不明朗的情况下运用，则会大败而归。 从另一个方面看，三种策略都为了在求解问题的时候是成本尽量低。因此，从这个方面看，三种策略的目标一致。但是，标准分治策略的目标只是获得问题的解，动态规划和贪婪选择则不仅要获得一个解，而且应该是个最优解。因此，贪婪选择和动态规划之间的相似性更多。 虽然动态规划和贪婪策略有许多相似的地方，但是有时候并不是很容易看出来。 贪婪选择和动态规划 贪婪选择属性指的是一个全局最优解决方案可以解决通过一个局部最优的选择（贪婪选择）获得。对于贪婪算法来说，容易看出来其做出的选择具有贪婪的性质。但对于动态规划来说，这一点不太容易。动态规划进行贪婪选择了吗？ 如果仔细察看动态规划就可以发现，动态规划的每一步都需要做出一个选择，动态规划的每一步都做出一个选择，例如，在最长公共子序列问题中，我们需要选择在 什么地方那个将序列断开。但这个选择都是贪婪选择吗？答案是肯定的。只不过此时我们的选择不是在不知道子问题解的情况下做出的，而是在子问题已经解出来的 基础上进行的。而我们选择的是最好的分解，因此当然是贪婪选择。 动态规划是先解决子问题，自底向上，因此，每次选择我们都知道是正确的。贪婪策略是在解决子问题前做出选择，然后希望做出的选择是正确的，是自顶向下。但不管是先做出选择还是在子问题解决后再做出选择，都是试图做出最好的选择！ 贪心算法是动态规划方法的一个特例。贪心特在，可以证明，每一个子树的根的值不取决于下面叶 子的值，而只取决于当前问题的状况。换句话说，不需 要知道一个节点所有子树的情况，就可以求出这个节点的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的 本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代 价只取决于子问题的数目，而选择数目总为1。 背包问题 以背包问题为例。贪心算法的思路是，直接选择当前价格／重量比最大的物品放入背包，力图保持 背包内的物品的总的价格／重量比总是最大的，以得到 最优的值。动态规划的思路是，对于每一种物品，都要考虑“放它”和“不放它”两种情况，并取最优的一种作为解。动态规划对解空间的遍历要比贪心完全。 显然，如果能保证背包总是满的，则贪心算法是正确的。但0-1背包问题不能保证背包总是满的，这样就降低了整体背包的价格／重量比。这种情况，就只能用动态规划来解。 感觉背包问题似乎是个特例，问题当前的状况（剩余的物品）就可以决定当前的选择，但其它的限制（背包的总重量）使得贪心是错误的。
其余的问题，如矩阵连乘，子串匹配等，则显然不具备贪心的要求，只能用动态规划来解。 |