浅析动态规划算法

Touch_2011

浏览: 290484 次
性别:
来自: 武汉

最近访客更多访客>>

mantis_qiang

lyshine66

Eliotry

Stack-

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Data Structures And Algorithms

矩阵连乘次数最少动态规划最长上升子序列最长公共子序列数字三角形

1、基本思想

将一个问题分解为子问题递归求解，且将中间结果保存以避免重复计算。通常用来求最优解，且最优解的局部也是最优的。求解过程产生多个决策序列，下一步总是依赖上一步的结果，自底向上的求解。

2、一般步骤

A． 寻找子问题，对问题进行划分。一般是分几种情况，有时是模拟现实中的情况

B． 定义状态。往往将和子问题相关的各个变量的一组取值定义为一个状态。某个状态的值就是这个子问题的解。

C． 找出状态转移方程。一般是从一个状态到另一个状态时变量值改变。

D．若有K个变量，一般用K维的数组存储各个状态下的解，并可根据这个数组记录打印求解过程。

E． 动态规划并没有具体的模式，应具体情况具体分析。

3、例题分析

（1）求从三角形顶部到底部和最大的路径，即最佳路径

3 4

5 7 4

5 6 7 8

分析：这题一看，可以用回溯法。子问题：从（i，j）开始，到底部的最佳路径。状态就是（i，j）坐标。比如数字1，要么从左边走，要么从右边走。所以状态转移方程：

maxSum(i,j)=max{ maxSum(i+1,j) , maxSum(i+1,j+1)} (i<3)

maxSum(i,j)=a[i][j] (i==3) 假设有从0行开始，且用a数组存储三角形。

代码：

//求（i，j）坐标到底部的最佳路径

int maxSum(int i,int j)

{

int sumLeft,sumRight;

if(i==N-1){

return triangle[i][j];

}

if(remarkSum[i+1][j]==-1)//没计算过，则计算

remarkSum[i+1][j]=maxSum(i+1,j);

if(remarkSum[i+1][j+1]==-1)

remarkSum[i+1][j+1]=maxSum(i+1,j+1);

sumLeft=remarkSum[i+1][j];

sumRight=remarkSum[i+1][j+1];

return sumLeft>sumRight?sumLeft+triangle[i][j]:sumRight+triangle[i][j];

}

//打印路径

void print(int i,int j)

{

if(i>=N)

return;

printf("%-4d",triangle[i][j]);

if(remarkSum[i+1][j]>remarkSum[i+1][j+1])

print(i+1,j);//左边的和比右边的大，则打印左边的数

else

print(i+1,j+1);//右边的和比左边的大，则打印右边的数

}

（2）最长上升子序列，如aghbcz的最长上升子序列长度是4：abcz

分析：子问题是以str[i]为终点的最长上升子序列。状态是str[i].要求出str[i]状态中对应的各个子问题的解的最大值。状态转移方程：要求某一个状态的最长上升子序列，先要求出在这个终点的左边各个点的最长上升子序列，选择其中的最大值且字符的值小于当前要求的点上的字符值。up(i)=max{ up(k) && str[i]>str[k]} 其中k为0到i.

代码：

int up(int n)

{

int i,temp=0;

if(n==0){

return remark[0]=1;

}

//选择a[0]到a[n]中比n小且最长子序列最大的那个值

for(i=n;i>=0;i--){

if(a[i]<a[n]){

if(remark[i]==0)

remark[i]=up(i);

if(remark[i]>temp)

temp=remark[i];

}

return remark[n]=1+temp;

}

（3）最长公共子序列

分析：顺次比较两个序列的各个值，有三种情况。

递归方程：

当 i = 0 , j = 0 时 , c[i][j] = 0
当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1
当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

代码：

//返回最长公共子序列的长度

int sub(int i,int j)

{

if(str1[i]=='\0' || str2[j]=='\0')

return 0;

if(str1[i] == str2[j]){

if(remark[i+1][j+1]<0)

remark[i+1][j+1]=sub(i+1,j+1);

return remark[i+1][j+1]+1;

}

else{

if(remark[i][j+1]<0)

remark[i][j+1]=sub(i,j+1);

if(remark[i+1][j]<0)

remark[i+1][j]=sub(i+1,j);

return remark[i+1][j] > remark[i][j+1] ?

remark[i+1][j] : remark[i][j+1];

}

（4）矩阵连乘

分析：A[i]* ...*A[j]，以A[k]为分界点，分为A[i]*...*A[k]和A[k+1]*...*A[j]两部分。这两个字部分也要是最优解。用remark[i][j]记录各个状态的值。

代码：

//Ai到Aj连乘乘法计算的最少次数

int matrixMul(int i,int j)

{

int k,min=0;

if(i==j){

return 0;

}

//以A[k]为分界点，分为A[i]*...*A[k]和A[k+1]*...*A[j]两部分

for(k=i;k<j;k++){

if(remark[i][j]==0)

remark[i][j]=matrixMul(i,k)+matrixMul(k+1,j)

+A[j].column*A[i].row*A[k].column;

if(min==0){

min=remark[i][j];

}

else if(remark[i][j]<min){

min=remark[i][j];

}

return min;

}

（5）旅行商问题:从一个城市出发，遍历所有城市（每个城市只走一次），最后回到原点。求花费的最小代价。

分析：min{下一个结点到始点的最短路径+这个点到下一个结点的路径}

代码：

//从顶点i开始遍历canUseVertex里的城市最终到达0（开始点）的最短路径

int shortestPath(int i,int* canUseVertex,int length)

{

int temp,tempMin;

int min=INFINITE,j,k;

if(length==0)

return graph[i][0];

for(j=0;j<length;j++){

temp=canUseVertex[j];

for(k=j;k<length-1;k++){

canUseVertex[k]=canUseVertex[k+1];

}

tempMin=shortestPath(temp,canUseVertex,length-1)

+graph[i][canUseVertex[j]];

for(k=length-1;k>j;k--)

canUseVertex[k]=canUseVertex[k-1];

canUseVertex[j]=temp;

if(tempMin<min)

min=tempMin;

}

return min;

}

（6）图中两点的最短路径。

分析：min{下一个结点到终点的最短路径+这个结点到下一个结点的路径}

（7）0/1背包问题

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

4、总结

动态规划和贪心算法相同与不同：

相同点：

动态规划和贪心算法都是一种递推算法；

均有局部最优解来推导全局最优解 ；

不同点：

贪心算法：

1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。

2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法：

1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。（如背包问题）

2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优。

3.边界条件：即最简单的，可以直接得出的局部最优解。

/*
 * 矩阵连乘计算次数最少
 */

#include<stdio.h>

typedef struct 
{
	int row; //矩阵行数
	int column;//矩阵列数
}Matrix;

Matrix A[20];//存储要相乘的矩阵
int remark[20][20]={0};//存储Ai到Aj连乘乘法计算的最少次数


//Ai到Aj连乘乘法计算的最少次数
int matrixMul(int i,int j)
{
	int k,min=0;
    if(i==j){
		return 0;
	}
	//以A[k]为分界点，分为A[i]*...*A[k]和A[k+1]*...*A[j]两部分
    for(k=i;k<j;k++){
		if(remark[i][j]==0)
    		remark[i][j]=matrixMul(i,k)+matrixMul(k+1,j)
		    	+A[j].column*A[i].row*A[k].column;
		if(min==0){
			min=remark[i][j];
		}
		else if(remark[i][j]<min){
			min=remark[i][j];
		}
	}
	return min;
}

void print(int i,int j)
{
	int k,temp;
	for(k=i;k<j;k++){
		temp=matrixMul(i,k)+matrixMul(k+1,j)
		    	+A[j].column*A[i].row*A[k].column;
		if(temp==remark[i][j])
			break;
	}
	if(k<j && i<k<j){
	//	printf("A[%d]*...*A[%d]\n",i,k);
	//	printf("A[%d]*...*A[%d]\n",k,j);
		printf("A[%d]  ",k);
		print(i,k);
		print(k+1,j);
	}
}

void main()
{
	int i,n;
	printf("请输入要相乘的矩阵个数,然后输入每个矩阵的行数和列数\n");
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d%d",&A[i].row,&A[i].column);
	printf("\n这些矩阵相乘乘法计算的最少次数是：%d\n",matrixMul(0,n-1));
	print(0,n-1);
	printf("\n");
}

/*求从三角形顶部到底部和最大的路径，即最佳路径（动态规划）
 *   1
 *  3 4
 * 5 7 4
 *5 6 7 8
 */

#include<stdio.h>
#define N 4

int triangle[N][N]={//三角形
	{1},
	{3,4},
	{5,7,4},
	{5,6,7,8}
};

int remarkSum[N][N];//记录maxSum(i,j)的值,避免重复计算

//求（i，j）坐标到底部的最佳路径
int maxSum(int i,int j)
{
	int sumLeft,sumRight;
	if(i==N-1){
		return triangle[i][j];
	}
	if(remarkSum[i+1][j]==-1)//没计算过，则计算
		remarkSum[i+1][j]=maxSum(i+1,j);
    if(remarkSum[i+1][j+1]==-1)
		remarkSum[i+1][j+1]=maxSum(i+1,j+1);
	sumLeft=remarkSum[i+1][j];
	sumRight=remarkSum[i+1][j+1];
	return sumLeft>sumRight?sumLeft+triangle[i][j]:sumRight+triangle[i][j];
}

//打印路径
void print(int i,int j)
{
	if(i>=N)
		return;
	printf("%-4d",triangle[i][j]);
	if(remarkSum[i+1][j]>remarkSum[i+1][j+1])
		print(i+1,j);//左边的和比右边的大，则打印左边的数
	else
		print(i+1,j+1);//右边的和比左边的大，则打印右边的数
}

void main()
{
	int i;
	for(i=0;i<N*N;i++)
		*(*remarkSum+i)=-1;
	printf("%d\n",maxSum(0,0));
	print(0,0);
	printf("\n");
}

/*
 * 最长公共子序列
 */

#include<stdio.h>
#include<string.h>

#define M 20
#define N 20

int remark[M][N];

char *str1="programming";
char *str2="contest";

//返回最长公共子序列的长度
int sub(int i,int j)
{
	if(str1[i]=='\0' || str2[j]=='\0')
		return 0;
	if(str1[i] == str2[j]){
		if(remark[i+1][j+1]<0)
              remark[i+1][j+1]=sub(i+1,j+1);
		return remark[i+1][j+1]+1;
	}
	else{
		if(remark[i][j+1]<0)
           remark[i][j+1]=sub(i,j+1);
		if(remark[i+1][j]<0)
           remark[i+1][j]=sub(i+1,j);
		return remark[i+1][j] > remark[i][j+1] ? 
			remark[i+1][j] : remark[i][j+1];
	}
}

//打印
void print(int i,int j)
{
	if(str1[i]=='\0' || str2[j]=='\0')
		return;
	if(str1[i]==str2[j]){
		putchar(str1[i]);
		print(i+1,j+1);
	}
	else if(remark[i][j+1]>remark[i+1][j])
		print(i,j+1);
	else
    	print(i+1,j);
}

void main()
{
	int i,j,maxLength=0;
	for(i=0;i<N*M;i++)
		*(*remark+i)=-1;
	for(i=0;i<strlen(str1);i++)
		for(j=0;j<strlen(str2);j++)
			if(maxLength<sub(i,j))
				maxLength=sub(i,j);
	printf("%d\n",maxLength);
	print(0,0);
	printf("\n");
}

/*
 * 最长上升子序列
 */

#include<stdio.h>

int a[50];//输入的序列
int len;//长度
int remark[50]={0};//记录a中各个数的最长上升子序列

//求序列中下标为n的上升子序列
int up(int n)
{
	int i,temp=0;
	if(n==0){
		return remark[0]=1;
	}
	//选择a[0]到a[n]中比n小且最长子序列最大的那个值
	for(i=n;i>=0;i--){
		if(a[i]<a[n]){
			if(remark[i]==0)
		     	remark[i]=up(i);		
	        if(remark[i]>temp)
				temp=remark[i];
		}
	}
	return remark[n]=1+temp;
}

void main()
{
	int i,indexMax=0,j,index;
	printf("input length:\n");
	scanf("%d",&len);

    for(i=0;i<len;i++)
		scanf("%d",&a[i]);

	//求每个值的最长升序子序列
	for(i=0;i<len;i++)
    	if(up(i)>remark[indexMax])
			indexMax=i;
	printf("%d\n",remark[indexMax]);
	index=indexMax;

	//打印
	for(i=0;i<remark[indexMax];i++){
	    printf("%-4d",a[index]);
		for(j=index;j>=0;j--)
			if(remark[j]==remark[index]-1 && a[j]<a[index]){
				index=j;
				break;
			}
	}
	printf("\n");
}

/*
 * 旅行商问题
 */

#include<stdio.h>
#define INFINITE 1000

int m,n;

int graph[5][5]={//邻接矩阵存储图
	{INFINITE,3,INFINITE,4,3},
	{3,INFINITE,1,5,8},
	{INFINITE,1,INFINITE,6,INFINITE},
	{4,5,6,INFINITE,2},
	{3,8,INFINITE,2,INFINITE}
};
//未走过的城市，既未遍历的图的顶点，默认出发点已经遍历过
int canUseVertex[5]={1,2,3,4};
int length=4;//没遍历的城市个数

int remark[5][5]={0};//存储中间状态的最优解

//从顶点i开始遍历canUseVertex里的城市最终到达0（开始点）的最短路径
int shortestPath(int i,int* canUseVertex,int length)
{
	int temp,tempMin;
	int min=INFINITE,j,k;
	if(length==0)
		return graph[i][0];
	for(j=0;j<length;j++){
  		temp=canUseVertex[j];
		for(k=j;k<length-1;k++){
			canUseVertex[k]=canUseVertex[k+1];
		}

		tempMin=shortestPath(temp,canUseVertex,length-1)
			+graph[i][canUseVertex[j]];

		for(k=length-1;k>j;k--)
			canUseVertex[k]=canUseVertex[k-1];
		canUseVertex[j]=temp;

		if(tempMin<min)
			min=tempMin;
	}
	return min;
}

void main()
{
	printf("%d\n",shortestPath(0,canUseVertex,4));

}

例题源代码.rar (4 KB)
下载次数: 7

动态规划浅析.rar (12.1 KB)
下载次数: 4

分享到：

浅析贪心算法 | 浅析递归

2011-07-05 15:30
浏览 1859
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论