动态规划算法

引言

  动态规划是求解多级决策过程最优化的一种数学方法。所谓多级决策过程，是指把一个过程分成若干阶段，每一阶段都作出决策，以使整个过程取得最优效果。通过对多级决策问题的讨论，可以初步了解动态规划的思想和方法[1]。通俗地讲，就是在当前状态的关口，如何做出下一步决策，就好比你处于迷茫状态的关口，下一步你有很多选择，如果你能够知道在当前状态下几个选择中收益最大的那个，选择了它之后在不久的将来能够当上CEO，赢取白富美，你肯定会毫不犹豫地作出选择。在众多动态规划问题中，最短路径问题是多级决策的一个典型例子，用这个阐述相信大家很快就能学会。

最短路径问题

  其实路径规划还是我上最优控制这门课的时候了解到的算法，所以引用考研朱伟老师的话“少一些功利主义的追求，多一些不为什么的坚持”，只要你觉得有意思或者是有那么一点点用的东西，趁年轻学它吧！在控制中动态规划是为了求解类似最优状态调节器问题而引入的算法，虽然我去上最优控制这门课的次数不多，但每次我觉得有意思的内容我都会搞懂，在此要感谢我校的陈晖老师！！接下来由一个书中的最短路径问题讲解动态规划的思想：



  引用书中的话，假设$N$N为多级决策过程中的级数，如图4-1中现处于C级还剩下3级决策则$N=3$N=3；$x$x表示任一级所处的位置，称为状态变量；$S_{N}(x)$SN​(x)为决策变量，表示状态$x$x以后还有$N$N级时，所选取的下一个点；$J_{N}(x)$JN​(x)表示状态$x$x到$N$N级决策的最短距离，$d(x,S_{N})$d(x,SN​)表示从状态$x$x到到$S_{N}$SN​的距离，对于图4-1的问题，用动态规划的方法是从后往前做决策，从$E$E级开始算起，这级有两个状态，$E_{1}$E1​和$E_{2}$E2​，则
第一步：
$J_{1}(E_1)=1$J1​(E1​)=1 $J_{1}(E_2)=2$J1​(E2​)=2 第二步：
$J_{2}(D_{1})=min\left\{ \begin{aligned} J_{1}(E_1)+d(D_1,E_1)=4+1 \\ J_{1}(E_2)+d(D_1,E_2)=2+2 \\ \end{aligned} \right\}=4$J2​(D1​)=min{J1​(E1​)+d(D1​,E1​)=4+1J1​(E2​)+d(D1​,E2​)=2+2​}=4则处于$D_{1}$D1​级时最优选择是$E_2$E2​，因此$S_{2}(D_{1})=E_2$S2​(D1​)=E2​
$J_{2}(D_{2})=min\left\{ \begin{aligned} J_{1}(E_1)+d(D_2,E_1)=6+1\\ J_{1}(E_2)+d(D_2,E_2)=9+2\\ \end{aligned} \right\}=7$J2​(D2​)=min{J1​(E1​)+d(D2​,E1​)=6+1J1​(E2​)+d(D2​,E2​)=9+2​}=7则$S_{2}(D_{2})=E_1$S2​(D2​)=E1​

第三步(具体计算省略，下同)：
$J_{3}(C_{1})=5 ,S_{3}(C_{1})=D_1$J3​(C1​)=5,S3​(C1​)=D1​ $J_{3}(C_{2})=11 ,S_{3}(C_{2})=D_2$J3​(C2​)=11,S3​(C2​)=D2​$J_{3}(C_{3})=8 ,S_{3}(C_{3})=D_1$J3​(C3​)=8,S3​(C3​)=D1​第四步：
$J_{4}(B_{1})=14 ,S_{4}(B_{1})=C_1$J4​(B1​)=14,S4​(B1​)=C1​$J_{4}(B_{2})=9 ,S_{4}(B_{2})=C_1$J4​(B2​)=9,S4​(B2​)=C1​$J_{4}(B_{3})=12 ,S_{4}(B_{3})=C_2$J4​(B3​)=12,S4​(B3​)=C2​  看到这里，你可能会感觉这也太无趣了吧，但是接下来奇迹就要发生了哦，现在到了开始的$A$A点要做决策的时候了，这就是之前讲的：你现在处于$A$A的关口，接下来怎么选择你会了么？

第五步：$J_{5}(A)=min\left\{ \begin{aligned} J_{4}(B_{1})+d(A,B_1)=3+14=17 \\ J_{4}(B_2)+d(A,B_2)=9+5=14 \\ J_{4}(B_3)+d(A,B_3)=4+12=16 \end{aligned} \right\}=14$J5​(A)=min⎩⎪⎨⎪⎧​J4​(B1​)+d(A,B1​)=3+14=17J4​(B2​)+d(A,B2​)=9+5=14J4​(B3​)+d(A,B3​)=4+12=16​⎭⎪⎬⎪⎫​=14 $S_{5}(A)=B_2$S5​(A)=B2​  最终我们发现我们需要的最短路径和就是14，而其所经路径就是$A\rightarrow$A→$B_2\rightarrow$B2​→$C_1\rightarrow$C1​→$D_1\rightarrow$D1​→$E_2\rightarrow$E2​→$F$F，终于码完了，好森虎！现在你对动态规划有所感觉了么？精华就是如果你知道下一步走某个状态的最优，那肯定能通过简单的加减计算求出此次应该走哪一步，前提是你知道下一步某个状态后面的最优值。想一下：如果预知下前一步的函数值是不是和递归的想法有点不谋而合，接下来就以一个简单的编程题作为动态规划算法的升华

动态规划例题(C++实现)

  问题描述：给定一个矩阵$M(m,n)$M(m,n)，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的$M$M如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.
$\begin{matrix} 1 & 3 & 5&9 \\ 8 &1 & 3 &4 \\ 5 &0 & 6 &1\\ 8 &8 & 4 &0 \end{matrix}$1858​3108​5364​9410​  试想：在矩阵的开头1如果要做决策往右还是往下，如果你知道了3作为决策点后面的最短路径(设为$J(0,1)$J(0,1))和8作为决策点的最短路径(设为$J(1,0)$J(1,0))你一定会做出正确选择。设以1为决策点到达右下0的最短路径为$J(0,0)$J(0,0)
$if\quad J(0,1)>J(1,0),\quad then\quad J(0,0)=1+ J(1,0)$ifJ(0,1)>J(1,0),thenJ(0,0)=1+J(1,0)$else\quad J(0,0)=1+ J(0,1)$elseJ(0,0)=1+J(0,1)而以3作为决策点则形成了以下面的矩阵
$\begin{matrix} 3 & 5&9 \\ 1 & 3 &4 \\ 0 & 6 &1\\ 8 & 4 &0 \end{matrix}$3108​5364​9410​此时处于3的位置又要决策是往右还是往下，据此归纳上述问题：假设现处于决策点$M(m,n)$M(m,n)在有右和下元素的情况下右边到达终点的最短路径为$J(m,n+1)$J(m,n+1)，而下边到达终点的最短路径为$J(m+1,n)$J(m+1,n)
$if\quad J(m,n+1)>J(m+1,n) ,\quad then\quad J(m,n)=M(m,n)+J(m+1,n)$ifJ(m,n+1)>J(m+1,n),thenJ(m,n)=M(m,n)+J(m+1,n)$else\quad J(m,n)=M(m,n)+ J(m,n+1)$elseJ(m,n)=M(m,n)+J(m,n+1)至此你是不是很兴奋，感觉终于要做出来了？别高兴太早！还需要验证边界条件：如果此时到了最后一列，不能再下和右之间做抉择，你只能选择向下；如果到了最后一行，你只能选择向右，当到达最后一个矩阵的元素时，恭喜你，你跑完了，即最终return的条件是
$m=row\quad of\quad\ M-1$m=rowof M−1 $n=coloum\quad of\quad\ N-1$n=coloumof N−1 然而获取$J(m,n+1)$J(m,n+1)和$J(m+1,n)$J(m+1,n)却有两个方法，第一个是从后往前每次都将变量保存，这时候牺牲了空间，但是节省了时间，称为动态规划的算法；而另一种则是每次都需要计算，例如你要计算$J(0,0)$J(0,0)时候在迭代过程中要得到$J(1,1)$J(1,1)的值，而计算$J(0,1)$J(0,1)同样也要得到$J(1,1)$J(1,1)的值，这是暴力迭代的算法，但是同一个$J(1,1)$J(1,1)何必需要迭代计算多次呢？这样效率不是很低？因此动态规划算法是有很大优势的，可以减少运算，将每次从后往前计算的结果保存住就行了，至此写出两种代码的对比：

1、暴力迭代法

/*
Function:The violence Iterative algorithm
Writer:WenQing Huang
Filename:13-01
Date and time:2020/05/04 21:20
*/
#include<iostream>
using namespace std;
#include<stdlib.h>
int Min_matrix(int **Matrix, int Row, int Coloum, int M_row, int M_coloum);//M_row是输入的矩阵的行，M_coloum是输入矩阵的列，Row是当前行，Coloum是当前列
int main()
{
	int M_row;
	int M_coloum;

	cout << "输入矩阵的大小:" << endl;
	cin >> M_row >> M_coloum;

	//--------------动态开辟内存---------------//
	int **Matrix = new int*[M_row];
	for (int i = 0; i < M_row; i++)
	{
		Matrix[i] = new int[M_coloum];
	}
	//--------------动态开辟内存---------------//

	cout << "输入矩阵:" << endl;
	//输入矩阵
	for (int i = 0; i < M_row; i++)
	{
		for (int j = 0; j < M_coloum; j++)
		{
			cin >> Matrix[i][j];
		}
	}
	cout << endl;
	int Result = Min_matrix(Matrix,0,0, M_row,M_coloum);
	cout << "最短路径为:" << endl;
	cout << Result;
	//不要忘了删除动态开辟的内存，养成好习惯
	if (Matrix != NULL)
	{
		for (int i = 0; i < M_row; i++)
		{
			delete[] Matrix[i];
		}
		delete Matrix;
	}

	system("pause");
	return 0;
}

int Min_matrix(int **Matrix, int Row, int Coloum, int M_row, int M_coloum)
{
	//判断是否到达终点
	if ((Row == M_row - 1) && (Coloum == M_coloum - 1))
	{
		return Matrix[Row][Coloum];
	}
	//判断是否到达最下面的行
	if (Row == M_row - 1)
	{
		return Matrix[Row][Coloum] + Min_matrix(Matrix, Row, Coloum + 1, M_row, M_coloum);
	}
	//判断是否到达最右面的列
	if (Coloum == M_coloum - 1)
	{
		return Matrix[Row][Coloum] + Min_matrix(Matrix, Row + 1, Coloum, M_row, M_coloum);
	}
	//判断决策往右和往左
	if (Min_matrix(Matrix, Row + 1, Coloum, M_row, M_coloum) > Min_matrix(Matrix, Row, Coloum + 1, M_row, M_coloum))
	{
		return Matrix[Row][Coloum] + Min_matrix(Matrix, Row, Coloum + 1, M_row, M_coloum);
	}
	else
	{
		return Matrix[Row][Coloum] + Min_matrix(Matrix, Row + 1, Coloum, M_row, M_coloum);
	}

}

2、动态规划算法

/*
Function:The third Dynamic Programming algorithm
Writer:WenQing Huang
Filename:13-01
Date and time:2020/05/04 21:20
*/
#include<iostream>
using namespace std;
#include<stdlib.h>
void Min_matrix(int **Result_matrix, int **Matrix, int M_row, int M_coloum);
int main()
{
	int M_row;
	int M_coloum;

	cout << "输入矩阵的大小:" << endl;
	cin >> M_row >> M_coloum;

	//--------------动态开辟内存(输入矩阵)---------------//
	int **Matrix = new int*[M_row];
	for (int i = 0; i < M_row; i++)
	{
		Matrix[i] = new int[M_coloum];
	}
	//--------------动态开辟内存(输入矩阵)---------------//
	
	//--------------动态开辟内存(结果矩阵)---------------//
	int **Result_matrix = new int*[M_row];
	for (int i = 0; i < M_row; i++)
	{
		Result_matrix[i] = new int[M_coloum];
	}
	//--------------动态开辟内存(结果矩阵)---------------//


	cout << "输入矩阵:" << endl;
	//输入矩阵
	for (int i = 0; i < M_row; i++)
	{
		for (int j = 0; j < M_coloum; j++)
		{
			cin >> Matrix[i][j];
		}
	}
	cout << endl;

	//初始化结果矩阵
	for (int i = 0; i < M_row; i++)
	{
		for (int j = 0; j < M_coloum; j++)
		{
			Result_matrix[i][j] =0;
		}
	}
	Min_matrix(Result_matrix, Matrix, M_row, M_coloum);

	int Result = Result_matrix[0][0];
	cout << "最短路径为:" << endl;
	cout << Result<<endl;
	
	//不要忘了删除动态开辟的内存，养成好习惯
	if (Matrix != NULL)
	{
		for (int i = 0; i < M_row; i++)
		{
			delete[] Matrix[i];
		}
		delete Matrix;
	}

	//不要忘了删除动态开辟的内存，养成好习惯
	if (Result_matrix != NULL)
	{
		for (int i = 0; i < M_row; i++)
		{
			delete[] Result_matrix[i];
		}
		delete Result_matrix;
	}

	system("pause");
	return 0;
}

void Min_matrix(int **Result_matrix, int **Matrix,int M_row, int M_coloum)
{
	//循环写出每一级每一个点的最优(行循环)
	for (int i = M_row - 1; i >= 0; i--)
	{
		//(列循环)
		for (int j = M_coloum - 1; j >= 0; j--)
		{
			//在终点则最优值为原矩阵中的数值
			if (i == M_row - 1 && j == M_coloum - 1)
			{
				Result_matrix[i][j] = Matrix[i][j];
			}
			//在最后一行则最优值别无选择，只能往右
			else if (i == M_row - 1 && j != M_coloum - 1)
			{
				Result_matrix[i][j] = Result_matrix[i][j + 1] + Matrix[i][j];

			}
			//在最后一列则最优值别无选择，只能往下
			else if (i != M_row - 1 && j == M_coloum - 1)
			{
				Result_matrix[i][j] = Result_matrix[i+1][j] + Matrix[i][j];
			}
			//其他地方需要做选择，比较向右和向下的代价哪个最优
			else
			{
				if (Result_matrix[i + 1][j] > Result_matrix[i][j + 1])
				{
					Result_matrix[i][j] = Result_matrix[i][j + 1] + Matrix[i][j];

				}
				else
				{
					Result_matrix[i][j] = Result_matrix[i + 1][j] + Matrix[i][j];
				}
			}
		}
	}
}

最终输出结果均为

有感而发

  至此动态规划算法就算讲到这里了(紧张的复习工作之余来写这篇文章真的很解压)，动态规划算法真的很有用。最后再讲点故事吧，步入研究生阶段前我真的是一个小孩的心态，以为看上去最好的就是最适合自己的，最终在现实面前给了自己几个大大的教训。
  她很漂亮，我们最开始认识的一段时间很快乐，我推荐她选了那门最优控制(分手之后才上的，哈哈，这也就是我经常不去上课的原因之一)。由于自己经验不足再加上比较直男就很快对她示意了，本来没答应在一起后来在我的死缠烂打下在一起了，最终发现好像我很多方面不能理解她(也就是不合适)，后来。。。也就不欢而散了，当时都说了恶心对方的话，其实恶语相向中伤曾经喜欢的人是很不成熟的表现，但也正是我的不成熟，她对我说的话深深打击到了我，从此开始了自己繁忙科研和业务能力快速发掘的成长之路。
  在此不管曾经的她是如何想的，也不管她当时究竟喜欢我多少，我一点都不在乎，当时分手后的一段时间真的处于抑郁的状态，还好过了几个月走过来了。马铭洁，如果你能看到，我真的想对她说一句：感谢曾经那段经历，给了我一记人生最大的教训，成为我快速成长的历程之一。现在我也有了自己中意的人，我会好好地去把握，好好地经营。

[1] 胡寿松, 王执铨, 胡维礼. 最优控制理论与系统.第2版[M]. 科学出版社, 2005.