递归、动规、分治、贪婪算法的一些总结

递归和动态规划的比较

动态规划(Dynamic Programming, DP)是一项虽简单但较难掌握的技术,一个容易识别和求解DP问题的方法时通过求解尽可能多的问题。
“Programming”一词并不是指编程,而是填充表格(类似线性规划)。

递归

尽管递归问题五花八门,但题型大都类似。
一个问题是不是递归的,就看它能不能分解成子问题进行求解。

当你听到问题是这么开头的:“设计一个算法,计算第n个……”,“编写代码列出前n个……”,“实现一个方法,计算所有……”等等,那么这个问题基本就是一个递归问题。

递归的解法,根据定义,就是从较小的子问题逐渐逼近原始问题。
很多时候,只要在f(n-1)的解法中 加入、移除某些东西或者稍作修改就能计算出f(n)。而在其他情况下,答案可能更为复杂。

你应该双管齐下,自下而上和自上而下两种递归解法都要考虑。简单构造法对递归问题就很奏效。

自下而上的递归

自下而上的递归往往最为直观。首先要知道如何解决简单情况下的问题,比如,只有一个元素的列表,找出有两个、三个元素的列表的解法,依此类推。这种接法的关键在于,如何从先前解出来的答案,构建出后续情况的答案。

自上而下的递归

自上而下的递归可能比较复杂,不过对某些问题很有必要。遇到此类问题时,我们要思考如何才能将情况N下的问题分解成多个子问题。同时注意子问题是否重叠了。

分治

分治(Divide and Conquer)法递归地将问题分解成两个或多个同类型的子问题,直到这些子问题简单到能够直接求解,然后将这些子问题的解合成为原始问题的解。

分治一般包括如下步骤:

  1. 分(divide): 将初始问题分割成多个子问题,这些子问题是与初始问题同类型的规模更小的实例。
  2. 递归(recursion): 递归求解子问题。
  3. 治(conquer):合理地组合子问题的解。

分治法递归地求解子问题,所有问题一般按照递归进行定义,用 主定理(Master theorem) 容易求得这些递归问题的时间复杂度。

分治法的应用

  • 二分查找
  • 归并排序
  • 快速排序
  • 中间值查找
  • 最大最小值查找
  • 矩阵乘法
  • 最近点对问题

动态规划

如果听到问题是求一个最优解(通常是求最大值或最小值),而且该问题能够分解成若干子问题,并且子问题之间还有重叠的更小的子问题,就可以考虑用动态规划来解决这个问题。

动态规划的四个特点(剑指Offer总结)

  1. 求一个问题的最优解;
  2. 整体问题的最优解是依赖各个子问题的最优解;
  3. 把大问题分解成若干小问题,这些小问题之间还有相互重叠的更小的子问题;
  4. 由于子问题在分解大问题的过程中重复出现,为了避免重复求解子问题,用从下往上的顺序先计算小问题的最优解并存储下来,再以此为基础求取大问题的最优解。 从上往下分析问题,从下往上求解问题。

动态规划的四个特点

  1. 最优子结构
  2. 子问题重叠
  3. 有边界
  4. 子问题独立

动态规划和分治法的主要区别

对于分治法,子问题是相互独立的,而在动态规划中子问题可能是重叠的,通过使用备忘录(用一个表来保存已解决子问题的答案),对于大部分问题,动态规划能够将待求解问题的复杂度由指数级降低为多项式级。

动态规划主要包含以下两个部分:

  • 递归: 递归求解子问题。
  • 备忘录: 将已计算的值存储在表中。

动态规划 = 递归 + 备忘录

动态规划算法例子

  • 许多字符串算法,如最长公共子序列、最长递增子序列、最长公共子串、编辑距离等
  • 关于图的有效求解算法,如寻找图中最短距离的Bellman-Ford算法、Floyd的所有定点间最短路径算法等
  • 链矩阵乘法
  • 子集和
  • 0/1背包问题
  • 旅行商问题等

贪婪算法

贪婪算法将问题分为多个阶段。在每一个阶段,选取当前状态下的最优决策,而不考虑对后续决策的影响。这意味着算法在执行过程中会选取某些 局部最优解。贪婪算法假设通过局部最优解可以获得全局最优解。

贪婪算法的要素

  1. 贪婪选择性质
  2. 最优子结构

贪婪选择性质

全局最优解可以通过寻找局部最优解获得(贪婪),局部最优解的选择可能依赖于之前的决策。通过迭代方式算法进行一个个贪婪选择,将原问题简化为规模更小的问题。

最优子结构

如果原问题的最优解包含子问题的最优解,则认为该问题具有最优子结构。这意味着可以对子问题求解并构建规模更大的解。

贪婪算法的优缺点

优点:
直观,易于理解和编程实现。当前的决策不会对已经计算出的结果有任何影响,因此不需要再对已有的局部解进行检查。

缺点:
选择局部最优不是对于所有问题都是用,所以贪婪算法并不总能得到最优解。在许多情况下,无法保证最优解能够产生局部最优解。

通常需要用数学的方式来证明贪婪选择是正确的。

贪婪算法的应用

  • 排序问题,选择排序、拓扑排序
  • 优先队列,堆排序
  • 哈夫曼编码
  • Prim和Kruskal算法
  • 加权图的最短路径算法(Dijkstra算法)
  • 硬币找零问题
  • 分数背包问题
  • 并查集的按大小或高度合并问题(或排名)
  • 任务调度算法
  • 求解复杂问题的近似算法

0%