2.5　常用算法介绍

2.5.1　递归算法与分治算法

递归算法是直接或者间接地不断反复调用自身来解决问题的方法，要求原始问题可以分解成相同问题的子问题，如阶乘、斐波纳契数列、汉诺塔问题。其中斐波纳契数列又称“黄金分割数列”，指的是数列1，1，2，3，5，8，13，21，…在数学上，斐波纳契数列以递归方法定义，即F1=1，F2=1，Fn=F(n-1)+F(n-2)(n>2,n∈N*)。

分治算法中待解决的复杂问题能够简化为多个若干个小规模相同的问题，然后逐步划分达到易于解决的程度，说明如下。

（1）将原问题分解为n个规模较小的子问题，各子问题间独立存在，并且与原问题形式相同。

（2）递归解决各个子问题。

（3）将各个子问题的解合并得到原问题的解。

例如，棋盘覆盖、找出伪币、求最值问题。其中的棋盘覆盖问题为在一个(2^k)*(2^k)个方格组成的棋盘上有一个特殊方格与其他方格不同，称为“特殊方格”。这样的棋盘称为“特殊棋盘”，要求用L型方块填满棋盘的其余部分。

2.5.2　动态规划

动态规划与分治算法相似，都是用组合子问题的解来解决原问题的解；不同之处在于分治算法的子问题是相互独立存在的，而动态规划应用于子问题重叠的情况。

动态规划方法通常用来求解最优化问题，这类问题可以有很多可行解，每个解都有一个值。找到具有最优值的解为问题的一个最优解，而不是所有的最优解，可能有多个解都达到最优值。

设计动态规划算法的步骤如下。

（1）刻画一个最优解的结构特征。

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

（3）计算最优解的值，通常采用自底向上的方法。

（4）利用算出的信息构造一个最优解。

例如，0～1背包问题和钢条切割问题等。

2.5.3　贪心算法

贪心算法根据问题选择当下最好的选择，而不是从整体上最优考虑，通过局部最优希望导致全局最优。

贪心算法的要素如下。

（1）性质：可以通过局部最优选择来构造全局最优解，即直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。

（2）最优子结构：一个问题的最优解包含其子问题的最优解。

贪心算法的设计步骤如下。

（1）将最优化问题转换为对其做出一次选择后只剩一个子问题需要求解。

（2）证明做出贪心选择后原问题总是存在最优解，即贪心选择总是安全的。

（3）证明做出贪心选择后剩余的子问题满足性质，其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

例如，背包、均分纸牌和最大整数问题。

2.5.4　回溯法

回溯法是一种搜索算法，从根节点出发按照深度优先搜索的策略搜索，到达某一节点后探索该节点是否包含该问题的解。如果包含，则进入下一个节点搜索；否则回溯到父节点选择其他支路搜索。

回溯法的设计步骤如下。

（1）针对所给的原问题定义问题的解空间。

（2）确定易于搜索的解空间结构。

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数除去无效搜索。

例如，0～背包、旅行商和八皇后问题。

2.5.5　分支限界法

和回溯法相似，分支限界法也是一种搜索算法。但回溯法是找出问题的许多解，而分支限界法是找出原问题的一个解。或是在满足约束条件的解中找出使某一目标函数值达到极大值或极小值的解，即在某种意义下的最优解。

在当前节点（扩展节点）处先生成其所有的儿子节点（分支），从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处计算一个函数值（限界）。然后根据函数值从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间中有最优解的分支推进，以便尽快地找出一个最优解。

有两种分支限界法，一是FIFO分支限界法；二是优先队列分支限界法，即按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。