算法设计常用的三种方法（算法设计的5种通用方法）

算法设计常用的三种方法（算法设计的5种通用方法）贪心法在求解问题时总能够做出在当前的最佳选择。换句话说，不是从整体最优上考虑，而仅仅是在某种意义上的局部最优解。遗憾的是，当前的最优解长远来看却未必是最优的。因此，贪心法并不会一直产生最优结果。然而，在某些方面来说，贪心法确是最佳选择。一个采用贪心法的例子是霍夫曼编码（见第14章），这是一个数据压缩算法。动态规划同分治法类似，都是将较大的问题分解为子问题最后再将结果合并。然而，它们处理问题的方式与子问题之间的关系有关。在分治法中，每一个子问题都是独立的。为此，我们以递归（见第3章）的方式解决每一个子问题，然后将结果与其他子问题的结果合并。在动态规划中，子问题之间并不是独立的。换句话说，子问题之间可能有关联。这类问题采用动态规划法比分治法更合适。因为若用分治法来解决这类问题会多做很多不必要的工作，有些子问题会重复计算多次。尽管动态规划法是一种重要的思想且很多算法都利用了这种思想，但本书介绍的

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

1 随机法

随机法依赖于随机数的统计特性。一个应用随机法的例子是快速排序。

快速排序按如下方式工作：设想要对一堆作废的支票排序，首先将无序的一整堆分成两部分。其中一堆里使所有的支票号码都小于等于所设定的一个中间值，另一堆里保证所有的支票号码都大于这个中间值。一旦有了这样的两堆支票后，就再以同样的方式对这两堆支票重复刚才的划分过程，直到每一堆里都只有一张支票为止。这个时候所有的支票就都排好序了。

为了获得较高的性能，快速排序依赖于每一次要如何划分支票，我们需要让划分出的两堆支票数量几乎相同。为了实现这一步，理想的方法是在划分支票之前首先找到支票号码的中间值。可是为了确定这个中间值需要遍历所有的支票，因此我们并不打算这么做。作为替代的方法，随机选择一个支票号码作为划分的依据。快速排序的平均性能很不错，因为随机数的正态分布使得划分的结果是相对平衡的。

2 分治法

分治法包含3个步骤：分解、求解与合并。在分解阶段，将数据分解为更小、更容易管理的部分。在求解阶段，对每个分解出的部分进行处理。在合并阶段，将每部分处理的结果进行合并。一个分治法的例子是归并排序。

归并排序按照如下方式工作。如前所述，同样假设要排序一堆作废的支票。首先将无序的一整堆分成两半，下一步分别将两堆支票再各自分成两半，一直持续这个步骤直到每一堆中都只有一张支票为止。一旦所有堆中都只有一张支票时，就将其两两合并且保证每一个合并后的新堆都是有序的。一直做两两合并直到重新得到一大堆，此时所有的支票就都已经排好序了。

在所有的分治算法中都有相同的三个步骤。归并排序能以以下方式来描述，首先，在分解阶段将数据划分为两份。接下来，按照递归的方式对分解出的两部分应用归并排序。最后，在合并阶段将两部分合并成一个排好序的集合。

3 动态规划

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

4 贪心法

贪心法在求解问题时总能够做出在当前的最佳选择。换句话说，不是从整体最优上考虑，而仅仅是在某种意义上的局部最优解。遗憾的是，当前的最优解长远来看却未必是最优的。因此，贪心法并不会一直产生最优结果。然而，在某些方面来说，贪心法确是最佳选择。一个采用贪心法的例子是霍夫曼编码（见第14章），这是一个数据压缩算法。

霍夫曼编码中最重要的部分是构建一棵霍夫曼树（又称最优二叉树）。为了构建一棵霍夫曼树，从它的叶子节点自底向上处理。将每个要压缩的符号和它们在数据中出现的次数（频率）一起作为二叉树的根节点保存。接下来，选择两棵拥有最小频率值的根节点作为左右子树节点，构造一棵新的二叉树，且保证新的二叉树根节点的频率值为左右子树节点的频率值之和。然后重复这个步骤，直到得到唯一的一棵树，这就是最终的霍夫曼树。霍夫曼树的根节点包含数据中符号的总数，叶子节点包含原始的符号以及它们出现的频率。霍夫曼编码是一种贪心算法，因为每次它都会挑选出当前最合适的两棵树来合并。

5 近似法

并不计算出最优解，相反，它只计算出“足够好”的解。通常利用近似法解决那些计算成本很高又因为其本身十分有价值而不愿放弃的问题。推销员问题（见第16章）是一个通常会用近似法去解决的问题。

设想一位推销员需要设计一条去往好几个城市工作的路线。推销员问题的目的是找到最短的可能路径，以便推销员能够在回到出发点前恰好每座城市都只去过一次。由于推销员问题可能存在一种最优的策略，但计算的代价很高，因此可以采用启发式的方法得到一个近似解。当最优策略行不通时，启发式的方法是我们能够接受的一种比最优策略稍逊一些的策略。

推销员问题可以用图表的方式来描绘。把推销员必须前往的城市在格子中用点标记出来。然后按照如下启发式的方法来寻找这些点之间的最短路径。从推销员出发的位置开始只有一个点，将这个点涂黑。所有其他的点在加入路线图之前都是白色的，当它们加入时也同样涂黑。接下来，对于每一个还没有加入到路线图中的点v，计算最后一个加入到路线图中的点u和v之间的距离。通过这种方法，选择离u最近的那个点，将其涂黑并加入路线图中。重复这个过程直到所有的点都已经涂黑。最后，再次将出发点加入路线图使其闭合，这样就完成了整个路线图。