算法设计方法的分类及经典算法

黄友亮

简单来说，所谓算法就是定义良好的计算过程，他取一个或一组值作为输入，并产生一个或者一组值作为输出。亦即，算法就是一系列的计算步骤，用来将输入数据转换为输出结果。

我们还可以将算法看作一种工具，用来解决一个具有良好规格说明的计算问题。有关该问题的表述可以用通用语言，来规定所需要的输入/输出关系。与之对应的算法则描述了一个特定的计算过程，用于实现这一输入/输出关系。

计算机科学经过几十年的发展，孕育出许多算法设计的方法以及运用这些方法设计的算法，他们广泛运用于计算机研究领域以及计算机意外的现实生活中的各个领域。其中，算法设计的方法包含有一下几类：

一、分治法

有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。这些算法通常采用分治策略：将问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些iwenti，然后再合并其结果，就得到原问题的解。

分治模式在每一层递归上都有三个步骤：

分解（Divide）：将原问题分解成一系列子问题;

解决（Conquer）：递归地解决各子问题。若子问题足够小，则直接求解;

合并（Combine）：将子问题的结果合并成原问题的解。

﹒分治法的经典算法——合并排序（merge sort）。

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表

合并排序直观地操作如下：

分解：将n个元素分成n/2个元素的子序列;

解决：用合并排序法对两个子序列递归地排序;

合并：合并两个已排序的子序列以得到排序结果。

在对子序列排序时，其长度为1时递归结束。单个元素被视为是已排好序的。

合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过程MERGE（A，p，q，r），其中A是个数组，p、q和r是下标，满足p<=q

二、代换法

代换法常用于解递归式。为解释代换法，先引入递归式的概念。递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值來定义的。

用代换法解递归式需要两个步骤：

1）猜测解的形式。

2）用数学归纳法找出使解真正有效的常数。

“代换法“这一名称源于当归纳假设用较小值时，用所猜测的值代替函数的解。这种方法很有效，但是只能用于解的形式很容易猜的情形。

不幸的是，并不存在通用的方法来猜测递归式的正确解。这种猜测需要经验，有时甚至是创造性的。值得庆幸的是，还有一些试探法可以帮助做出好的猜测。

有时，我们或许能够猜出递归式解的渐进界，但却会在归纳证明时出现一些问题。通常，问题出在归纳假设不够强，无法证明其准确的界。遇到这种情况时，可以去掉一个低阶项来修改所猜的界，以使证明顺利进行。

代换法亦是一种经典的解决递归问题的算法。

三、随机化

随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。

首先引入概率分析（probabilistic analysis），概率分析是在问题的分析红应用概率技术。大多数情况下，我们使用概率分析来分析一个算法的运行时间。有时候用它分析其他的亮。为了进行概率分析，必须使用关于输入分布的知识或者对其做的假设。然后分析算法，计算出一个期望的运行时间。这个期望通过对所有可能的输入分布算出。因此实际上是将所有能输入的运行时间做平均。在确定输入的分布时必须非常小心。对于有些问题，我们队所有可能的输入集合可以做某种设定，也可以讲概率分析作为一种手段来设计高效的算法，并加深对问题的认识。对于其他的一些问题，可能无法描述一个合理的输入分布，此时就不能使用概率分析方法。

为了利用概率分析，需要了解关于输入分布的一些情况。在许多情况下，我们对输入分布知之甚少。即使知道关于输入分布的某些信息，从计算上来说，可能也无法对这红分布知识建立模型。然而，通过使一个算法中某些部分的行为随机化，就常常可以利用概率和随机性作为算法设计和分析的工具。

随机化的经典算法——随机算法（randomized algorithm）。

以经典的雇用问题为例，在雇用问题中，看起来应聘者好像是以随机的顺序出现的，但是我们无法知道这是否正确。因此，为了设计雇用问题的一个随机算法，必须对面试应聘者的次序有更大的控制。假设雇用代理有n个应聘者，而且实现给我们一份应聘者的名单，我们每天随机地选择其中一个来面试。虽然我们不了解任何关于应聘者的事项（除了他们名字），我们已经做了一个显著的改变。我们控制了应聘者的来到过程且加强了随机次序，而不是依赖于随机次序到达这个猜测。

四、动态规划（dynamic programming）

和分治法一样，动态规划是通过组合子问题的解而解决整个问题的。分治算法是将问题分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解，与此不同，动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共子子问题。动态规划算法对每个子子问题只求一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出一个具有最优（最大或最小）值得解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个最优值的解。

动态规划算法的设计可以分为以下4个步骤：

1）描述最优解的结构。

2）递归定义最优解的值。

3）按自底向上的方式计算最优解的值。

4）由计算出的结果构造一个最优解。

动态规划的经典算法——最优二叉树算法。

最优二叉树的实现目的是从已给出的目标带权结点（单独的结点）经过一种方式的组合形成一棵树.使树的权值最小。

（1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn};

（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和;

（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中;

（4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

（作者单位：武警警官学院训练基地信息技术教研室）