详细实例说明+典型案例实现对动态规划法进行全面分析 | C++

简单的来说算法就是用计算机程序代码来实现数学思想的一种方法。学习算法就是为了了解它们在计算机中如何演算以及在当今的信息时代它们是如何在各个层面上影响我们的日常生活的从而提高我们的逻辑思维能力和处理实际问题的能力。善用算法、巧用算法是培养程序设计逻辑的重中之重许多实际的问题都可用多个可行的算法来解决但是要从中找出最优的解决算法却是一项挑战。

一、动态规划法是什么

1.简要介绍

20世纪50年代初动态规划法由美国数学家R.E.Bellman所创造它很类似于分治法并且用来研究多阶段决策问题的优化过程和对问题最优解的求法。动态规划法的核心做法如果一个问题的答案与子问题相关的话就能将这个大问题拆解成多个子问题并且将每个子问题的答案储存起来用于下一次求解时的直接使用。它与分治算法最大的不同点就是在于子问题能否去进行存储的问题。

2.生活实例

① 一个工程队需要从一个地方往另一个地方修建下水管道。他们的出发地是A目的地是B其中有三级中间站中转枢纽两地之间的连线表示即将要修建的下水管道并且每一级的枢纽只能与自己下一级所有的枢纽相连而不能跨级相连具体情况如图所示。工程队要从总的计划方案中找出最短的路径从而以较低的成本去完成此次任务。运用动态规划的思想对该次任务进行分析我们的总计划方案可以规划成多种子方案并且每种情况下的子方案还与原来总方案之间是具有相关的关系的是它的子问题。将每种情况下子方案的路径算出并记录下来最终进行方案的总体比较从而得出我们要找的最短路径。

二、动态规划法对斐波那契数列的优化

1.优化方法

从第二章http://t.csdn.cn/4OxrH我们讲解的斐波那契函数执行路径图中可知它递归调用了多次加法也运算了多次。这样的重复计算影响到了执行的性能和效率根据动态规划的思想已经计算过的数据就不需要再去重复计算也不必要再往下递归。从而我们将对它进行以下的优化

前面介绍中我们提到过动态规划法的核心就是将已经计算过的数据进行记录存储。为了达到这个目的我们可以先去设置一个用来记录值的数组countval该数组中的每一个值将会去记录已经被计算过的斐波那契数列中的各项值并且在记录前需要将该数组设为空。每当下一次要去计算斐波那契数列中的值时就先去从countval中去判断如果是空值就去继续进行计算再将计算所得结果保存到相应下标的数组中......具体过程如下

①第一次计算F1按照斐波那契数列定义其数值为1将此值存入暂存区countval[0]中

②第一次计算F2按照斐波那契数列定义其数值为1将此值存入暂存区countval[1]中

③第一次计算F3按照斐波那契数列定义其数值为F1+F2即countval[0]+countval[1]=2再将F3的值存入暂存区countval[2]中

④第一次计算F4按照斐波那契数列定义其数值为F2+F3即countval[1]+countval[2]=3在将F4的值存入暂存区countval[3]中

⑤第一次计算F5按照斐波那契数列定义其数值为F3+F4即countval[2]+countval[3]=5

再将F5的值存入暂存区countval[4]中结束执行。

2.优化核心代码片段

int countval[1000] = { 0 };   //暂存区
int Fib(int n)
{
	int result;
	result = countval[n-1];
	if (result == 0)
	{
		if (n == 1 || n == 2) {
			result = 1;
		}
		else {
			result = Fib(n - 2) + Fib(n - 1);
		}
		countval[n-1] = result;
	}
	return result;
}

3.代码实现以及结果展示

用优化后的方法去求解第五个斐波那契数的值并且输出暂存区中的存储数据。

 #include<iostream>
using namespace std;
int countval[1000] = { 0 };   //暂存区
int Fib(int n)
{
	int result;
	result = countval[n-1];
	if (result == 0)
	{
		if (n == 1 || n == 2) {
			result = 1;
		}
		else {
			result = Fib(n - 2) + Fib(n - 1);
		}
		countval[n-1] = result;
	}
	return result;
}
void text()
{
	int i = 0;
	cout << "请输入要求的第几个斐波那契数";
	int x; cin >> x;
	cout << "该数为" << Fib(x) << endl;
	cout << "暂存区中的数据" << endl;
	while (countval[i] != 0)
	{
		cout << "countval" << "[" << i << "]" << "=" << countval[i] << endl;
		i++;
	}
}
int main()
{
	text();
}

三、动态规划法的典型案例——最短总距离

1.具体情况

要在某地区5个城市之间去修路将这5座城市构成一幅交通图并且要使修的路的总距离要最短。因此对总体方案进行如下分析

从上面各种情况中我们分析可知情况一和情况二中子图的顶点和总体方案原图完全相同。子图的分支也是总体方案原图的子集这些子分支刚好将图中所有城市连接起来形成一张交通图。

2.代码展示C++

使用程序代码去构建以上的具体情况并且求解出最短路径的具体长度。

#include<iostream>
using namespace std;
#define maxnum 20   //自定义图的最大的顶点数
#define maxvalue 65535
#define yes 0    //已选用顶点
#define no -1	//非邻接顶点
typedef struct {
	char vertex[maxnum];    //顶点信息
	int g_type;      //图的类型
	int vertex_num;		//顶点的数量
	int edge_num;		//边的数量
	int edge_weight[maxnum][maxnum];	//边的权
}graphmatrix;   
void creategraph(graphmatrix& gm)
{
	int weight;  //权重
	char start_vertex, end_vertex;   //起始两顶点
	int i,j,k;
	cout << "###请输入图中各顶点信息###" << endl;
	for (i = 0; i < gm.vertex_num; i++)
	{
		cout << "第" << i + 1 << "个城市:";
		cin >> gm.vertex[i];
	}
	cout << "###请输入图中构成各边的左右顶点以及该边的权值###" << endl;
	for (k = 0; k < gm.edge_num; k++)
	{
		cout << "第" << k + 1 << "条边:";
		cin >> start_vertex >> end_vertex >> weight;
		for (i = 0; start_vertex != gm.vertex[i]; i++)     //查找始点
		{
			for (j = 0; end_vertex != gm.vertex[j]; j++)   //查找终点
			{
				gm.edge_weight[i][j] = weight;                 //找到后将权值保存
			}
		}
		if (gm.g_type == 0)
		{
			gm.edge_weight[j][i] = weight;
		}
	}
}
void clear_graph(graphmatrix& gm)
{
	for (int i = 0; i < gm.vertex_num; i++)
		for (int j = 0; j < gm.vertex_num; j++)
			gm.edge_weight[i][j] = maxvalue;
}
void min_graph(graphmatrix &gm)
{
	int min, sum=0;
	int weight[maxnum];
	char vertex_[maxnum];
	int k;

	for (int i = 1;i< gm.vertex_num; i++)
	{
		weight[i] = gm.edge_weight[0][i];       //保存邻接矩阵中的一行数据
		if (weight[i] == maxvalue)
			vertex_[i] = no;
		else
			vertex_[i] = gm.vertex[0];
	}
	vertex_[0] = yes;
	weight[0] = maxvalue;
	for (int i = 1; i < gm.vertex_num; i++)
	{
		min = weight[0];
		k = i;
		for (int j = 1; j < gm.vertex_num; j++)
		{
			if (weight[j] < min && vertex_[j]>0)   //寻找具有更小权值的边
			{
				min = weight[j];
				k = j;
			}
		}
		sum += min;    //将权值进行累加
		vertex_[k] = yes; 
		weight[k] = maxvalue;
		for (int j = 0; j < gm.vertex_num; j++)
		{
			if (gm.edge_weight[k][j] < weight[j] && vertex_ != 0)
			{
				weight[j] = gm.edge_weight[k][j];
				vertex_[j] = gm.vertex[k];
			}
		}
	}
	cout << endl;
	cout << "最短路径的总长度为" << sum << endl;
}
void text()
{
	graphmatrix gm;

	cout << "###创建图###" << endl;
	cout << "输入图的类型0:无向图 1:有向图:";
	cin >> gm.g_type;
	cout << "输入图中城市的数量:";
	cin >> gm.vertex_num;
	cout << "输入图中城市间路径的数量:";
	cin >> gm.edge_num;

	clear_graph(gm);
	creategraph(gm);   //构建图
	min_graph(gm);   //最小生成树算法 ,动态规划的使用块
}
int main()
{
	text();
}