您所在位置：主题：[讨论]总结常见算法模型的原理，应用特点
sq宋强
[专家分：0] 发布于 2010-06-21 19:20:00
、总结常见算法模型的原理，应用特点。
常见算法:贪心法，分治法，回溯法，动态规划法，分支限界法。
（1）贪心法：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，
通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。
应用特点：贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，
因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的
选择之一。
（2）分治法：在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成
两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题
的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅
立叶变换)……
应用特点： 分治法所能解决的问题一般具有以下几个特征，
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
（3）回溯法：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进
则进，不能进则退回来，换一条路再试。
应用特点：（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
（4）动态规划法：是系统分析中一种常用的方法。在水资源规划中,往往涉及到地表水库调度、水资源量的合理分配、优化
调度等问题,而这些问题又可概化为多阶段决策过程问题。动态规划法是解决此类问题的有效方法。动态规划法是20世
纪50年代由贝尔曼（R. Bellman）等人提出,用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程,就
是把研究问题分成若干个相互联系的阶段,由每个阶段都作出决策,从而使整个过程达到最优化。许多实际问题利用动态
规划法处理,常比线性规划法更为有效,特别是对于那些离散型问题。实际上,动态规划法就是分多阶段进行决策,其基本
思路是：按时空特点将复杂问题划分为相互联系的若干个阶段,在选定系统行进方向之后,逆着这个行进方向,从终点向始
点计算,逐次对每个阶段寻找某种决策,使整个过程达到最优,故又称为逆序决策过程。
动态规划的基本思想：前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，适合用于理论上的分析。在实际应用中，许多问
题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并
且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子
问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问
题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。
因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此
一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖
子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，
重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，
而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。但是首先要保证该问题的无后效性,
即无论当前取哪个解,对后面的子问题都没有影响.在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，
动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，
并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，
只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
（5）分支限界算法：是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。
应用特点： 对于分支限界算法,上界是已求得的可行解的目标函数值中的最小者,分为初始上界和在探测过程中产生的动态上界.分支定界法在求最优解的迭代过程中, 若某结点估计的下界不小于已知的上界, 则不必从该节点往下继续搜索. 因此若能产生一个较好的上界, 可以消除许多不必要的列举计算.
2、写一个函数，删除表中所有重复的值，例如将（1，2，2，3，3，2，3，3，5）变成（1，2，3，5）注意：表中元素未必是排好序的，且每一个值的第一次出现应当保留。
解：
#include <stdio.h>
#define N 80
int fun(int a[],int n)
{ int i,j=1;
for(i=1;i<n;i++)
if(a[j-1]!=a[i])
a[j++]=a[i];
return j;
}
main()
{ int a[N]={1,2,2,3,3,2,3,3,5},i,n=9;
printf("The original data :\n");
for(i=o;i<n;i++) printf("%3d",a[i]);
n=fun(a,n);
printf("\n The data after deleted :\n");
for(i=o;i<n;i++) printf("%3d",a[i]);printf("\n\n");
}
3、例：（35，33，12，24，42），删除i=2的数据元素，依照顺序表插入操作完成。
1）分析边界条件；2）分别给出伪代码和C++描述算法。3）分析时间复杂度。
解：
truct SList //固定大小的顺序表结构
{
int array[20];
SList *Next;
};
struct SList //不固定大小的顺序表结构
{
int *array;
long int lenth;
SList *Next;
};
常见算法:贪心法，分治法，回溯法，动态规划法，分支限界法。
（1）贪心法：在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，
通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。
应用特点：贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，
因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的
选择之一。
（2）分治法：在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成
两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题
的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅
立叶变换)……
应用特点： 分治法所能解决的问题一般具有以下几个特征，
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
（3）回溯法：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进
则进，不能进则退回来，换一条路再试。
应用特点：（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
（4）动态规划法：是系统分析中一种常用的方法。在水资源规划中,往往涉及到地表水库调度、水资源量的合理分配、优化
调度等问题,而这些问题又可概化为多阶段决策过程问题。动态规划法是解决此类问题的有效方法。动态规划法是20世
纪50年代由贝尔曼（R. Bellman）等人提出,用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程,就
是把研究问题分成若干个相互联系的阶段,由每个阶段都作出决策,从而使整个过程达到最优化。许多实际问题利用动态
规划法处理,常比线性规划法更为有效,特别是对于那些离散型问题。实际上,动态规划法就是分多阶段进行决策,其基本
思路是：按时空特点将复杂问题划分为相互联系的若干个阶段,在选定系统行进方向之后,逆着这个行进方向,从终点向始
点计算,逐次对每个阶段寻找某种决策,使整个过程达到最优,故又称为逆序决策过程。
动态规划的基本思想：前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，适合用于理论上的分析。在实际应用中，许多问
题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并
且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子
问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问
题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。
因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此
一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖
子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，
重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，
而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。但是首先要保证该问题的无后效性,
即无论当前取哪个解,对后面的子问题都没有影响.在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，
动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，
并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，
只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
（5）分支限界算法：是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。分支限界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。
应用特点： 对于分支限界算法,上界是已求得的可行解的目标函数值中的最小者,分为初始上界和在探测过程中产生的动态上界.分支定界法在求最优解的迭代过程中, 若某结点估计的下界不小于已知的上界, 则不必从该节点往下继续搜索. 因此若能产生一个较好的上界, 可以消除许多不必要的列举计算.
2、写一个函数，删除表中所有重复的值，例如将（1，2，2，3，3，2，3，3，5）变成（1，2，3，5）注意：表中元素未必是排好序的，且每一个值的第一次出现应当保留。
解：
#include <stdio.h>
#define N 80
int fun(int a[],int n)
{ int i,j=1;
for(i=1;i<n;i++)
if(a[j-1]!=a[i])
a[j++]=a[i];
return j;
}
main()
{ int a[N]={1,2,2,3,3,2,3,3,5},i,n=9;
printf("The original data :\n");
for(i=o;i<n;i++) printf("%3d",a[i]);
n=fun(a,n);
printf("\n The data after deleted :\n");
for(i=o;i<n;i++) printf("%3d",a[i]);printf("\n\n");
}
3、例：（35，33，12，24，42），删除i=2的数据元素，依照顺序表插入操作完成。
1）分析边界条件；2）分别给出伪代码和C++描述算法。3）分析时间复杂度。
解：
truct SList //固定大小的顺序表结构
{
int array[20];
SList *Next;
};
struct SList //不固定大小的顺序表结构
{
int *array;
long int lenth;
SList *Next;
};