五大常用算法之一：分治算法

基本概念：

把一个复杂的问题分成两个或更多的相同的或相似的子问题。再把子问题分成更小的子问题。直到最后子问题可以简单的解决。

分成的子问题与原问题形式相同，并且互相独立，递归的解决这些子问题。然后将子问题的解合并得到原问题的较小模式。这就为使用递归技术提供了方便。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中。

分治法适用范围情况：

1）该问题规模缩小到一定程度就可以轻易解决

2）该问题可以分解为若干个规模较小相同问题，即该问题具有最优子结构性质。

3）利用该问题分解出来的子问题的解可以合并为该问题的解。

4）该问题所分解出的各个子问题是相互独立的。不包含公共子问题。

如果第三条和第四条不满足，分治法要做许多不必要的方法，需要使用动态规划法较好。

分治法的基本步骤：

step1：分解问题：分成规模较小，相互独立，与原问题形式相同的子问题。

step2：若子问题规模较小容易解决直接解决，否则递归的解各个子问题。

一般设计模式：

Divider-and-Conquer(P)//表示问题的规模

1.if |p|<n  //当问题小于一个阈值，就可以直接解决了

2.then return (Adhoc(p))

3.将p分解为较小的子问题p1,p2,...pk//否则继续分解

4.for i- 1 to k//分解每一个问题带进方法去解

5.do yi Divide-and-Conquer(Pi)递归解决Pi

6.T - Merge(y1,y2,..yk)合并子问题

7.return （T）

分治法的复杂性分析

总结

1.一定是要找到最小规模的解决办法

2.找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

五大常用算法之二：动态规划算法

基本概念

每次决策依赖于当前状态，又随即引起状态的转移。一个决策的序列就是就是在变化的状态中产生出来的。所以，这种多阶段最优化决策解决问题的过程叫动态规划。

在思想上与分治法类似，将待求解问题分为若干个子问题，按顺序求解子阶段，前一子问题的解为后一子问题的求解提供了有用的休息。子啊求解任一子问题时，可以列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢其舍弃其它局部解。依次解决各子问题。最后一个子问题就是初始问题的解。

动态规划解决问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差异是：适合于动态规划法求解的问题，经分解后问题往往不是相互独立的

适用的情况

1）最优化原理：如果问题的最优解所包含的子问题也是最优的，也就称该问题具有最优子结构，即满足最优化原理。

2）无后效性：某个阶段一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前的状态有关。

动态规划算法最大的优势，就是解决子问题之间重叠的问题。

求解基本步骤

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

（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定是要有序的或者是可排序的。否则问题就无法求解。

（2）确定状态和状态变量：将问题发展到各个阶段时所处于的客观情况用不同的状态表示出来，当然状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但一般是根据前后的两个阶段的状态之间的关系来确定决策方法和状态转移方程的。

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

五大常用算法之三：回溯法

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

回溯法解题的一般步骤

（1）针对所有问题。确定问题的解空间。

首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

（2）确定结点的扩展搜索规则

以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

算法框架

（1）问题框架

设问题的解是一个n维向量（a1，a2。。an），约束条件是ai之间满足某种条件，记为f（ai）

非递归回溯框架

int a[n],i;

初始化数组a[];

i=1;

while(i>0有路可走，并且未达目标)

｛

        if(i>n){

           搜索到一个解，输出；

}else{

a[i]第一个可能得值

while（a[i]在不满足约束条件且在搜索空间内）｛

          a[i]下一个可能的值

｝

}

｝

递归的算法框架

一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度。

int a[n];

try(int i){

if(i>n)

输出结果；

else{

        for(j=下界；j<=上界；j=j+1)//枚举i所有可能得路径

｛

         if(fun(j)){

          a[i]=j;

}

｝

}

}

五大常用算法之四：分支限界法

分支限界法与回溯法类似，但是回溯法是求解目标中所有满足约束条件的解，而分支限界法是找出满足约束条件的一个解，最优。

（1）分支搜索算法

会有几种不同的分支搜索方式。

FIFO搜索，LIFO搜索，优先队列式算法搜索。

分支限界法的一般过程

在每一活结点出，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的节点作为扩展节点。

回溯法和分支限界法的一些区别

回溯法深度优先搜索堆栈活结点的所有可行子节点被遍历后，才被从栈中弹出找出满足约束条件的所有解。

分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解。

五大常用算法之贪心算法

基本概念

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择，不从整体最优考虑，做出的只是某种意义上的局部最优解。

它不具有固定的算法框架，算法设计的关键是贪心策略的选择，贪心算法不是对所有问题都能得到整体最优解。选择的贪心策略必须具备无后效性，即某个状态以后的状态不会影响到以前的状态。所以对采用的贪心策略一定要仔细分析是否满足无后效性。

建立数学模型来描述问题。

把求解的问题分成若干个子问题。

对每一子问题求解，得到子问题的局部最优解。

把子问题的解局部最优解合成原来解问题的一个解。

贪心策略使用的前提是，局部最优策略能导致产生全局最优解。

贪心算法的实现框架

从某一问题的初始解出发：

while（朝给定总目标前进一步）｛

利用可行的决策，求出可行解的一个解元素；

｝

由所有解元素组合成问题的一个可行解。

例子

[背包问题]有一个背包，背包容量是M=150.有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过容量。

A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30

分析：目标函数：E pi最大

约束条件：E wi<=M(M=150)

(1)根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优

(2)每次挑选所占重量最小的物品装入是否能的到最优

每次挑选单位重量价值最大的物品，称为解本题的策略。虽然贪心算法经过证明之后，很高效，并且简单易行，但是它必须经过证明才能真正运用到题目的算法中去。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由贪心策略中存在的子问题最优解得来的。对于例题中的几种贪心策略，都是无法成立的。

五大常用算法之三：回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不再满足求解条件时，就回溯返回，查找别的路径。

从根节点出发深度搜索解空间树，当探索到某一点时，先判断该节点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解