传统算法小结

传统算法小结

传统算法小结：

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

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

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

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

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

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

为求解规模为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） 矩阵乘法

动态规划法可以保证找到最优解而非满意解，与贪心法、局部搜索法只能找到满意解不同。