贪婪算法
贪婪算法，也被称为“贪心算法”。贪婪算法分阶段地工作。在每一个阶段，都可以认为所作决定是好的，而不考虑将来的后果。一般来说，这意味着选择的是某个局部的最优。这种“眼下能够拿到的就拿”的策略即是这类算法的来源。当算法终止时，我们希望局部最优就是全局最优。如果是这样的话，那么算法就是正确的；否则，算法得到的就是一个次优解。如果不要求绝对最佳答案，那么有时会用简单的贪婪算法来生成近似的答案，而不是使用一般产生准确答案所需要的复杂算法。
分治算法
分治算法由两部分组成：
- 分(divide)：递归解决较小的问题（当然，基本情况除外）。
- 治(conquer)：然后，从子问题的解构建原问题的解。
传统上，在正文中至少含有两个递归调用的例程叫做分治算法，而正文中只含有一个递归调用的例程不是分治算法。我们一般坚持子问题是不相交的（即基本上不重叠）。
在分治算法中，所有有效的分治算法都是把问题分成一些子问题，每个子问题都是原问题的一部分，然后进行某些附加的工作以算出最后的答案。
回溯算法
在许多情况下，回溯算法相当于穷举搜索的巧妙实现，但性能一般不理性。不过，情况并不总是如此，即使如此，在某些情况下下它相比蛮力(brute force)穷举搜索，工作量也有显著的节省。当然，性能是相对的；对于排序而言，O(N^2)的算法是相当差的，但对旅行售货员（或任何 NP-完全）问题，O(N^2)算法则是里程碑式结果。
动态规划
任何数学递归共识都可以直接翻译成递归算法，但是基本现实是编译器常常不能正确对待递归算法，结果导致低效的算法。当我们怀疑很可能是这种情况时，我们必须再给编译器提供一些帮助，将递归算法重新写成非递归算法，让后者把那些子问题的答案系统地记录在一个表内。利用这种方法的一种技巧叫做动态规划(dynamic programming)。
区别和联系
如果我们将这四种算法思想分一下类，那贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类，因为它跟其他三个都不大一样。为什么这么说呢？前三个算法解决问题的模型，都可以抽象成我们今天讲的那个多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。
其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。
网友评论