传统算法

传统算法

1.枚举法，即穷举法，从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

采用枚举算法解题的基本思路：

（1） 确定枚举对象、枚举范围和判定条件；

（2） 一一枚举可能的解，验证是否是问题的解

2.回溯法，是一种既带有系统性又带有跳跃性的搜索法，它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。

3.递归法：即一个对象的描述中包含它本身。

能采用递归描述的算法通常有这样的特征：

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

4.递推法，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。

可用递推算法求解的题目一般有以下二个特点：

（1） 问题可以划分成多个状态；

（2） 除初始状态外，其它各个状态都可以用固定的递推关系式来表示。

在实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。

5.分治法，即将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

分治法所能解决的问题一般具有以下几个特征：
（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小相互独立的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

6.贪婪法，是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，它所做出的选择只是在某种意义上的局部最优解，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。所以贪婪法不要回溯。

7.迭代法，用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：
（1）选一个方程的近似根，赋给变量x0；
（2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；
（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。
若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。

8.动态规划法，即在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。

动态规划算法的基本思想是将待求解问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，动态规划法经分解得到的子问题往往不是相互独立的，前一子问题的解为后一子问题的解提供有用的信息，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

适合于用动态规划法求解的问题具有以下特点：

（1）可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过程。

（2）每个阶段有若干个可能状态

（3）一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。

（4）在任一个阶段，最佳的决策序列和该阶段以前的决策无关。

（5）各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系（即动态转移方程）。

动态规划法所处理的问题是一个多阶段最优化决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线。如下图：

动态规划设计都有着一定的模式，一般要经历以下几个步骤：

1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。

2、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。

3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。

4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

5、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。

根据以上的步骤设计，可以得到动态规划设计的一般模式：

for k:=阶段最小值to阶段最大值do {顺推每一个阶段}

for I:=状态最小值to 状态最大值do {枚举阶段k的每一个状态}

for j:=决策最小值to 决策最大值do {枚举阶段k中状态i可选择的每一种决策}

f[ik]:=min（max）{f[ik-1]+a[ik-1，jk-1]|ik-1通过决策jk-1可达ik}

有了以上的设计模式，对于简单的动态规划问题，就可以按部就班地进行动态规划设计。