本文主要是介绍算法导论（八）——动态规划贪婪算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法导论（八）——动态规划&贪婪算法
【主要参考资料：MIT算法导论视频，《数据结构，算法与应用，c++语言描述》】
动态规划方法通常用来求解最优化问题，从可行解中寻找具有最优值的解，得到的是问题的一个最优解(an optimal solution)。
求解的问题需具备要素：最优子结构和子问题重叠。算法对每个子问题只求解一次，将其解保存在一个表格，从而无需每次求解一个子问题时都重新计算，避免了这种不必要的计算工作。是付出额外的内存空间来节省计算空间。
动态规划是基于递推公式或初始状态，当前子问题的解由上一次子问题的解推出，只需要多项式时间复杂度。它的本质，是对问题状态的定义和状态转移方程的定义。
我们通常按如下4个步骤来设计一个动态规划算法：
•1.刻画一个最优解的结构特征。
•2.递归地定义最优解的值。
•3.计算最优解的值，通常采用自底向上的方法。
•4.利用计算出的信息构造一个最优解。
1. 最长公共子序列（LCS）。
背景;x序列有m个元素，y序列有n个元素，最坏情况下，找到一个lcs需要指数时间
理论：动态规划的特征
①（最优子结构的性质）一个问题的最优解包含了其子问题的最优解
——令z为LCS(x,y)，则z的前缀为x的前缀和y的前缀的LCS。
②重叠子问题：递归法解决时有少量的子问题重复出现
——画出递归树，树高m+n，指数时间，有很多重复，LCS有m*n个独立子空间。
解决方案：
①备忘法（自顶而下，对已经计算过的内容，及时记录）
2. 数塔问题：
http://blog.csdn.net/baidu_28312631/article/details/47418773
数字三角形中寻找一条从顶部到底边的路径（每一步都只能往左下或右下走），使得路径上所经过的数字之和最大。
3. 钢条切割
http://blog.csdn.net/nxiangbo/article/details/51111391
给一段钢条，对其进行切割，每一段钢条都有不同的价值。要找到最优的切割方案，使切割成的钢条价值最大。
①带备忘录的自顶而下法：记录每个计算过的值 【记录中间解】
②自底而上法：将子问题按照规模排序，按照有小到大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存。【通过对问题求解顺序的合理安排，达到避免重复】
两种方法具有相同的复杂度，自顶而下的方法并没有解决所有可能的子问题，由于没有频繁的递归函数的调用开销，自底而上的方法复杂度通常会比自顶而下的方法复杂度小
4. 矩阵连乘(钢条问题的升级版)
http://blog.sina.com.cn/s/blog_5d1f04810100x4qe.html
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
m[i][j]=m[i][k]+m[k+1][j]+pipk+1pj+1
5. 最优二叉搜索树
http://blog.csdn.net/xiajun07061225/article/details/8088784
给定一个由n个互异的关键字组成的有序序列K={k1<k2<k3<,……,<kn}和它们被查询的概率P={p1,p2,p3,……,pn}，要求构造一棵二叉查找树T，使得查询所有元素的总的代价最小。
代价可以定义为：比如从根节点到目标节点的路径上节点数目，即所发现的节点的深度加1。
n+1个“虚拟键”d0,d1,...,dn，他们代表不在K内的值。
定义e[i,j]为包含关键字ki,...,kj的最优二叉查找树的期望代价，最终要计算的是e[1,n]。
可以说贪心问题是DP问题的特例。
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。贪婪算法：每一步的最优解一定包含上一步的最优解。（硬币问题可用DP,但不一定能用贪婪算法）
贪婪算法：作出在当前看来最好的选择
逐步构造最优解。每一步都在一定的标准下，做出一个最优决策。
不能保证得到最优解，但所得的结果通常非常接近最优解，这种算法称为启发式方法。
适用的前提：局部最优策略能导致产生全局最优解。
应用：
背包问题（价值密度，k阶优化）；
拓扑排序：【从剩余顶点中选择一个点j，它没有入边（i,j），其中i不在序列中】
用栈保存候选顶点，用一维数组表示各顶点的入度（入度为0即是候选点，否则要及时更新）
//生成拓扑序列
booltopologicalOeder(int *theOrder){
//若能生成拓扑序列，则结果保存在theOrder
//否则返回false,说明有向图中含有环
//点的下标从1开始，1~n
int n=numberofVertices();
//计算每个顶点的入度
int *inDegree=new int[n+1];
fill(inDegree,inDegree+n+1,0);
for(int i=1;i<=n;i++){
vertexIterator<T> *ii=iterator(i);
int u;//其邻接点
while((u=ii->next())!=0)
inDegree[u]++;
}
//入度为0的点入栈
arrayStack<int> stack;
for(int i=1;i<=n;i++){
if(inDegree[i]==0)
stack.push(i);
}
//生成拓扑序列
int j=0;
while(!stack.empty()){
int nextVertex=stack.top();
stack.pop();
theOrder[j++]=nextVertex;
vertexIterator<T> *inextVertex=iterator(nextVertex);
int u;
while((u=inextVertex->next())!=0){
inDegree[u]--;
if(inDegree[u]==0)
stack.push(u);
}
}
return (j==n);
}
二分覆盖（寻找最小覆盖）；【从一个集合中选择一个顶点，它最大数量地覆盖了另一个集合中还未被覆盖的元素】
单源最短路径；【从还没到达的定点中，选择可以产生最短路径的顶点】——Dijkstra
voidshortestPaths(int sourceVertex,T* distanceFromSource,int* predecessor){
//distanceFromSource保存从sourceVertex开始的最短路径
//predecessor表示某点从源开始的路径中的前驱节点
//节点1~n
if(sourceVertex<1||sourceVertex>n)
return;
graphChain<int> newRechableVertices;
//初始化
for(int i=1;i<=n;i++){
distanceFromSource[i]=a[sourceVertex][i];//邻接矩形
if(distanceFromSource[i]==noEdge)
predecessor[i]=-1;
else{
predecessor[i]=sourceVertex;
newRechableVertices.insert(0,i);
}
}
distanceFromSource[sourceVertex]=0;
predecessor[sourceVertex]=0;
//更新
while(!newRechableVertices.empty()){
//从还没到达的定点中，选择可以产生最短路径的顶点
chain<int>::iteratorinewRechableVertices=newRechableVertices.begin();
int v=*inewRechableVertices;
while(inewRechableVertices!=newRechableVertices.end()){
int w=*inewRechableVertices;
inewRechableVertices++;
if(distanceFromSource[v]>distanceFromSource[w])
v=w;
}//找到了最小值v
//接着找到达v的最短路径
newRechableVertices.eraseElement(v);
for(int j=1;j<=n;j++){
if(a[v][j]!=noEdge&&(predecessor[j]==-1||distanceFromSource[j]>distanceFromSource[v]+a[v][j])){
distanceFromSource[j]=distanceFromSource[v]+a[v][j];
if(predecessor[j]==-1)
newRechableVertices.insert(0,j);
predecessor[j]=v;
}
}
}
}
最小成本生成树:选择n-1条边，使成本最小
代码参考：https://github.com/lymcool/Introduction-to-Algorithms-Data-Structures/blob/master/MiniSpanTree.cpp
①Kruskal算法:【“加边”，选择成本最小且不会产生环路的边加入】
boolkruskal(weightEdge<T> *spanningTreeEdges){
// 加权无向图不联通时，返回false
//否则，最小成本生成树的边存储在spanningTreeEdges0~n-2中
int n=numberifVertices();
int e=numberofEdges();
weightEdge<T> *edges=newweightEdge<T> [e+1];//存储边
int k=0;
for(int i=1;i<=n;i++){
vertexIterator<T> *ii=iterator(i);
int j;
T w;
while((j=ii->next(w))!=0){
if(i<j)
edge[++k]=weightEdge<int>(i,j,w);
}
}
//把边插入小根堆
minHeap<weightEdge<T>> heap(1);
heap.initialize(edge,e);
//union/find结构
fastUnionFind uf(n);
//按照权重递增顺序提取边，然后决定舍弃或选入
k=0;
while(e>0&&k<n-1){
weightEdge<T> x=heap.top();
heap.pop();
e--;
int a=uf.find(x.vertex1());
int b=uf.find(x.vertex2());
if(a!=b){
spanningTreeEdges[k++]=x;
uf.unite(a,b);
}
}
return (k==n-1)
}
② Prim算法:【“加点”，选择成本最小且加入后能形成树的边——有一个顶点相连】
③Sollin算法：【对所有顶点选择最小成本边(有重复)，再对各个子树选择最小成本边，将其连接】
这篇关于算法导论（八）——动态规划贪婪算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
