算法设计的方法

1.算法简介

作用：要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。

定义：简单的说，算法（Algorithm）是由有穷规则构成的为解决某一类问题的运算序列（方法或过程）。

算法的性质：算法可以有若干输入，这些输入是在算法开始时给出的初始值或条件；算法通常又有若干输出，是对输入进行加工后的计算结果。另外算法的性质有： （1）有穷性。一个算法必须在执行了有穷步之后结束。当然也有例外，在某些领域也需要研究不终止的算法。 （2）确定性。算法的每一步，必须具有确切的定义。也就是说，对于每步需要执行的动作必须严格和清楚地给出规定。 （3）可行性。算法的每一步必须要求是可行的，能够由机器或人准确完成。整个算法好像是解决问题的工作序列，其中的每一步都是我们力所能及的一个动作。 （4）正确性。这是算法最基本最重要的性质。正确性指如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且在终止时得到满足要求的输出结果。

2.算法的常用设计方法

实际应用的算法千变万化，种类繁多。设计一个好的算法需要设计者根据实际要解决的问题，充分发挥自己的分析和综合能力，经过认真构思、仔细设计和耐心调整。

在算法的设计过程中，最重要的是创新精神。经过数千年无数前人的创新，人类不近积累了大量精妙的算法，同时在算法的设计方法上也进行了深入的探讨，发现许多不同问题的解决算法，它们的设计思想有相似之处。经过科学的总结，找到了一些行之有效的能够用于设计算法的一般方法。下面列举最常用的算法设计的方法。

2.1穷举法

穷举法（Exhaustion）是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。

如将A、B、C、D、E、F这六个变量排成如图所示的三角形，这六个变量分别 取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。这个问题的求解就可以使用穷举法，列出所有可能的三角形的边的组合，求出最大值。

2.2贪婪法

贪婪法（Greedy），其基本设计思想是当追求的目标是一个问题的最优解时，设法把对整个问题的求解工作分成若干步骤来完成。在其中的每一个步骤都选择从局部看是最优的方案，以期望通过各阶段的局部最优选择来达到整体的最优。

贪婪法的特点是一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

如装箱问题和和着色问题都可以采用贪婪法来求解。

2.3递归法

递归（Recursion）是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。

能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。 斐波那契数列为：0、1、1、2、3、…，即：

fib(0)=0;  
fib(1)=1; 
fib(n)=fib(n-1)+fib(n-2) （当n>1时）

2.4分治法

分治法（DIvide and Conquer），其基本思想是把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题，首先对子问题进行求解，然后再把各个子问题的解合并起来，得出整个问题的解，即对问题分而治之。

如果原问题可分割成k个子问题（1<k≤n1<k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

如二路归并排序就用到分治法。二路归并的具体实现可参见本人blog:归并排序及其并行化。

2.5回溯法

回溯法（Backtracking）也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。

回溯法的基本思想是采用深度优先策略，一步一步向前试探的方法，当某一步有多种选择时，可以先任意选择一种，继续向前试探。一旦发现到达某步后无法再前进，说明上一步做的选择有问题，就后退到上一步重新选择（这就称为回溯）。

回溯法的特点是可以避免穷举式的盲目搜索，从而可能减少问题求解的搜索时间。

如迷宫问题和八皇后问题都可以采用回溯方法来设计求解算法。

2.6动态规划法

动态规划(Dynamic Programming)是运筹学的一个分支，是求解决策过程(Decision Process)最优化的数学方法。

动态规划与分治法相似，都是把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。不同的是分治法每次分解的子问题数目较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；而动态规划法分解子问题可能较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果保存起来，动态规划法通常是自底向上进行。

带权图中，求解所有结点之间最短路径Floyd算法就属于动态规划法。

2.7分枝界限法

分枝界限法（Branch and Bound）与回溯法相似，也是一种在全部问题解的空间中进行系统搜索的方法。所不同的是，回溯法使用深度优先策略，而分支界限法可以采用广度优先策略。与此同时，分支界限法在搜索过程中，还利用最优解属性的上下界来控制搜索的分支，剪去不必再花时间搜索的部分，从而提高搜索的效率。

该方法在人工智能中使用比较广泛。利用分支界限法，可以设计背包问题的算法。

参考文献

[1]算法与数据结构——C语言描述（第二版）.张乃孝