vlambda博客
学习文章列表

常用的算法设计技术主要有迭代法、穷举搜索法、递推法、递归法、回溯法、贪心法、分治法、动态规划法等。递归法、回溯法及贪心法极为重要，要重点掌握。

迭代法

迭代法是用于数值计算近似求解的一种常用的算法，确定一合适的迭代公式，选一初始近似值及解的误差，循环处理实行迭代过程，终止条件是前后两次得到的近似值之差的绝对值小于给定的误差。设方程为f（x）=0，用某种属性方法导出其等价形式x=g（x），然后按以下步骤进行。

1. 选取一个方程的近似根，赋给变量x0。
2. 将x0的值保存于变量x1，然后计算g（x1），并将结果保存于变量x0中。
3. 当x0与x1的差的绝对值还小于给定的精度要求时，重复步骤（2）的计算。

若方程有根，并且上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。

C语言形式如下：具体使用迭代法求根时应注意以下两种可能的情况：如方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成"死循环"，因此在使用迭代算法前应先考查方程是否有解，并在程序中对迭代的次数给予限制；方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。

穷举搜索法

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

要解决的问题只有有限种可能，在没有更好的算法时，总可用穷举搜索的办法解决，即逐个检查所有可能的情况。

递推法

1. 基本思想

递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1, 2,…, i-1的一系列解构造出问题规模为i的解。这样，程序可从i=0或i=1出发，重复地，由已知i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。

2. 典型应用：Fibonacci级数

Fibonacci级数数列为0, 1, 1, 2, 3, 5, 8, 13, …, 即F（0）=0，F（1）=1，…，F（n）=F（n-1）+F（n-2）（n>1）。递推法实现算法如下：

递归法

1. 基本思想

递归是设计和描述算法的一种有力的工具。

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

递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较复杂的问题的求解推到比原问题简单一些的问题的求解；在回归阶段，当获得最简单情况的解后，逐级返回，依次获得稍复杂问题的解。

2. 典型应用：Fibonacci数列和背包问题

• Fibonacci数列

Fibonacci数列的递归算法实现如下（注意与递推实现比较）。

• 背包问题

所谓背包问题，是指有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

典型做法是逐个考查每一件物品，对于第i件物品的选择考虑有两种可能。

(1) 考虑物品i被选择，这种可能仅当包含它不会超过方案总重量限制时才是可行的。选中后继续递归考虑其余物品的选择。

(2) 考虑物品i不被选择，这种可能仅当不包含物品i也有可能找到价值更大的方案时才是可行的。

按上述思想可得递归算法如下：

回溯法

1. 基本思想

回溯法也称试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；如果当前候选解除了不满足问题规模要求外，满足所有其他要求，继续扩大当前候选解的规模，并继续试探；如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解、寻找下一个候选解的过程称为回溯；扩大当前候选解的规模并继续试探的过程称为向前试探。

2. 典型应用：n皇后问题

n皇后问题是源于国际象棋的一个问题，n皇后问题要求在一个n×n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之在同一行或同一列或同一条斜线上的其他任何棋子。因此n皇后问题等价于要求在一个n×n格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。

求解算法如下：

贪心法

1. 基本思想

贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解，因为省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础做出最优选择，而不考虑各种可能的整体情况，所有贪心法不需要回溯。

2. 典型应用：装箱问题

装箱问题可简述如下：设有编号为0, 1, …, n-1的n种物品，体积分别为v1, v2, …, vn-1，将这n种物品装到容量都为V的若干箱子里，约定这n种物品的体积均不超过V。不同的装箱方案所需要的箱子数目可能不同，装箱问题要求使装尽这n种物品的箱子数最少。

算法描述如下：

分治法

1. 基本思想

分治法也许是最广泛使用的算法设计方法，其基本思想是把大问题的解分解成一些较小的问题，然后由小问题的解方便地构造出大问题的解。

2. 典型应用：Hanoi塔问题

Hanoi塔问题描述如下：有n个盘子在A处，盘子从大到小，最上面的盘子最小。现在要把这n个盘子从A处搬到C处，可以在B处暂存，但任何时候都不能出现大的盘子压在小的盘子上面的情况。

当只有一个盘子时，直接从A移到C即可；如果已知n-1个盘子的移动方案，那么n个盘子的移动方案如下：先把前n-1个盘子从A借助C移动到B处，再把第n个盘子从A处直接移动到C处，然后再将B处的n-1个盘子从B处借助A处移动到C处，至此就完成了全部盘子的移动。

具体C代码实现如下：

动态规划法

动态规划法的基本思想是：将大问题分解成小问题，为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中。