算法设计的5种通用方法 _算法

从广义上讲，很多算法解决问题的思路是相同的。因此，为了方便，通常按照算法采用的方法和思路来给它们分类。这样给算法分类的一个原因是：如果我们理解了它采用的一般思路我们常常就能够对该算法获得一些深入的了解。在解决一些没有现成算法求解，但与现有问题类似的问题时，我们从中可以得到一些启发和灵感。当然，有些算法有悖于分类原则，而另一些则是多种方法相结合的产物。这一节将介绍一些常用的方法。
1 随机法

文章插图

随机法依赖于随机数的统计特性。一个应用随机法的例子是快速排序。
快速排序按如下方式工作：设想要对一堆作废的支票排序，首先将无序的一整堆分成两部分。其中一堆里使所有的支票号码都小于等于所设定的一个中间值，另一堆里保证所有的支票号码都大于这个中间值。一旦有了这样的两堆支票后，就再以同样的方式对这两堆支票重复刚才的划分过程，直到每一堆里都只有一张支票为止。这个时候所有的支票就都排好序了。
为了获得较高的性能，快速排序依赖于每一次要如何划分支票，我们需要让划分出的两堆支票数量几乎相同。为了实现这一步，理想的方法是在划分支票之前首先找到支票号码的中间值。可是为了确定这个中间值需要遍历所有的支票，因此我们并不打算这么做。作为替代的方法，随机选择一个支票号码作为划分的依据。快速排序的平均性能很不错，因为随机数的正态分布使得划分的结果是相对平衡的。
2 分治法

文章插图

分治法包含3个步骤：分解、求解与合并。在分解阶段，将数据分解为更小、更容易管理的部分。在求解阶段，对每个分解出的部分进行处理。在合并阶段，将每部分处理的结果进行合并。一个分治法的例子是归并排序。
归并排序按照如下方式工作。如前所述，同样假设要排序一堆作废的支票。首先将无序的一整堆分成两半，下一步分别将两堆支票再各自分成两半，一直持续这个步骤直到每一堆中都只有一张支票为止。一旦所有堆中都只有一张支票时，就将其两两合并且保证每一个合并后的新堆都是有序的。一直做两两合并直到重新得到一大堆，此时所有的支票就都已经排好序了。
在所有的分治算法中都有相同的三个步骤。归并排序能以以下方式来描述，首先，在分解阶段将数据划分为两份。接下来，按照递归的方式对分解出的两部分应用归并排序。最后，在合并阶段将两部分合并成一个排好序的集合。
3 动态规划

文章插图

【算法设计的5种通用方法】动态规划同分治法类似，都是将较大的问题分解为子问题最后再将结果合并。然而，它们处理问题的方式与子问题之间的关系有关。在分治法中，每一个子问题都是独立的。为此，我们以递归（见第3章）的方式解决每一个子问题，然后将结果与其他子问题的结果合并。在动态规划中，子问题之间并不是独立的。换句话说，子问题之间可能有关联。这类问题采用动态规划法比分治法更合适。因为若用分治法来解决这类问题会多做很多不必要的工作，有些子问题会重复计算多次。尽管动态规划法是一种重要的思想且很多算法都利用了这种思想，但本书介绍的算法中都没有使用到它。
4 贪心法

文章插图

贪心法在求解问题时总能够做出在当前的最佳选择。换句话说，不是从整体最优上考虑，而仅仅是在某种意义上的局部最优解。遗憾的是，当前的最优解长远来看却未必是最优的。因此，贪心法并不会一直产生最优结果。然而，在某些方面来说，贪心法确是最佳选择。一个采用贪心法的例子是霍夫曼编码（见第14章），这是一个数据压缩算法。
霍夫曼编码中最重要的部分是构建一棵霍夫曼树（又称最优二叉树）。为了构建一棵霍夫曼树，从它的叶子节点自底向上处理。将每个要压缩的符号和它们在数据中出现的次数（频率）一起作为二叉树的根节点保存。接下来，选择两棵拥有最小频率值的根节点作为左右子树节点，构造一棵新的二叉树，且保证新的二叉树根节点的频率值为左右子树节点的频率值之和。然后重复这个步骤，直到得到唯一的一棵树，这就是最终的霍夫曼树。霍夫曼树的根节点包含数据中符号的总数，叶子节点包含原始的符号以及它们出现的频率。霍夫曼编码是一种贪心算法，因为每次它都会挑选出当前最合适的两棵树来合并。