利用动态规划,求数值矩阵左上角至右下角最小路径

  • Post author:
  • Post category:其他



问题描述:

随机产生一个n行m列的整数矩阵,如图所示即随机产生的一个7行5列的数值矩阵,在整数矩阵中寻找从左上角至右下角,每步可向下(D)或向右(R)或斜向右下(O)的一条数值和最小的路径。

27 28 29 18 26

16 13 19 14 27

32 22 39 26 21

10 30 23 20 18

13 11 30 29 20

10 13 21 17 36

34 37 15 22 36


设计要点:

应用动态规划设计,即从右下角逐行反推左上角。确定n、m后,随机产生的整数二维数组a(n,m)作矩阵输出,同时赋给部分和数组b(n, m)。


这里数组b(i,j)为点(i,j)到右下角的最小数值和,stm(i,j)是点(i,j)向右(R)或向下(D)或向右下(O)的路标字符数组。

注意到最后一行与最后一列各数只有一个出口,于是由b(n,m)开始向左逐个推出同行的b(n,j)(j=m-1,…,2,1);向上逐个推出同列的b(i,m)(i=n-1,…,2,1)。

b(i,j)与stm(i,j) (i=n-1,…,2,1; j=m-1,…,2,1)的值由同一列其下面的整数b(i+1,j)与同一行其右边的整数b(i,j+1)或其右下方的b(i+1,j+1)的值决定:


设min=min(b(i+1,j+1),b(i,j+1),b(i+1,j);


首先,作赋值min=b(i+1,j+1),stm(i,j)=”O”;


若b(i,j+1)<min,则min=b(i,j+1),stm(i,j)=”R”;


若b(i+1,j)<min,  则min=b(i+1,j),stm(i,j)=”D”。


然后赋值:b(i,j)=b(i,j)+min。

这样反推所得b(1,1)即为所求的最小路径数字和。

为了打印最小路径,利用c数组从上而下操作:

先打印a(1,1), i=1, j=1.


①若stm(i,j)=”R”,则j++,然后打印”-R-“与右边的整数a(i,j)。


②若stm(i,j)=”D”,则i++,然后打印”-D-“与下面的整数a(i,j)。


③若stm(i,j)=”O”,则i++,j++,然后打印”-O-“与斜右下的整数a(i,j)。

依次类推,直到打印到点a(n,m)。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
	int m,n;
	printf("请输入行数(n)和列数(m):");
	scanf("%d%d",&n,&m);
	int i=0;
	int **randomArray = new int*[n];//随机数
	for (i=0;i<n;i++)
	{
		randomArray[i] = new int[m];
	}

	int **weightData = new int*[n];
	for (i=0;i<n;i++)
	{
		weightData[i] = new int[m];
	}
	char **storm = new char*[n];//存储方向
	for (i=0;i<n;i++)
	{
		storm[i] = new char[m];
	}
	srand(time(NULL));

	int row,col;
	for (row=0;row<n;row++)
	{
		for (col=0;col<m;col++)
		{
			randomArray[row][col] = rand()%50+1;
			weightData[row][col] = randomArray[row][col];
			printf("%4d",randomArray[row][col]);
		}
		printf("\n");
	}

	// 第n行递推为边界条件
	for (col=m-2;col>=0;col--)
	{
		weightData[n-1][col] = weightData[n-1][col] +weightData[n-1][col+1];
		storm[n-1][col] = 'R';
	}

	// 第m列递推为边界条件
	for (row=n-2;row>=0;row--)
	{
		weightData[row][m-1] = weightData[row][m-1] +weightData[row+1][m-1];
		storm[row][m-1] = 'D';
	}

	//逆推求取最大值b(0,0) 
	int min;
	for (row= n-2;row>=0;row--)
	{
		for (col = m-2;col>=0;col--)
		{
			min = weightData[row+1][col+1];
			storm[row][col] = 'O';
			if (min > weightData[row][col+1])
			{
				min = weightData[row][col+1];
				storm[row][col] = 'R';
			}

			if (min > weightData[row+1][col])
			{
				min = weightData[row+1][col];
				storm[row][col] = 'D';
			}
			weightData[row][col] = weightData[row][col] + min;
		}
	}

	printf("\n最优路径数值和为:%d",weightData[0][0]);
	printf("\n最优路径为:%2d",randomArray[0][0]);
	row=0,col=0;
	while((row < n-1 )||(col < m-1))
	{
		switch(storm[row][col])
		{
		case 'R':
			{
				col++;
				printf("-(R-%d)",randomArray[row][col]);
			}
			break;
		case 'D':
			{
				row++;
				printf("-(D-%d)",randomArray[row][col]);
			}
			break;
		case 'O':
			{
				col++;
				row++;
				printf("-(O-%d)",randomArray[row][col]);
			}
			break;
		}
	}
	printf("\n");

	for (i=0;i<n;i++)
	{
		delete []randomArray[i];
		delete []weightData[i];
		delete []storm[i];
	}
	delete []randomArray;
	delete []weightData;
	delete []storm;
	randomArray = NULL;
	weightData = NULL;
	storm = NULL;

	return 0;
}