引言

承接前文，介绍完基本概念后，我们来学习动态规划的基本思想，用上一篇文章的最短路问题来配合说明。

2.2 动态规划的基本思想

最短路问题中的网络如下图所示，从 A 到 E 可以分成 4 段，第一段从 A 到 B ，有两条路，如果选择去 B2 作为此阶段的决策，则下一阶段的起点就是 B2 ，此时又有两种选择，以此类推，可以求出一个决策序列。每一段选择不同，得到的序列便不同，我们希望求出一个最优决策，此决策对应的路线为 A 到 E 的最短路线。

在这里插入图片描述
显然，通过求出所有路线的距离进行比较，找出最短路对于本例是可行的，但是当路径数增加，这种穷举法的计算量会大大增加。下面介绍动态规划方法，可以帮助我们更好地求解该问题。

动态规划方法基于贝尔曼（R. Bellman）等人提出的最优化原理，这个最优化原理指出：一个过程的最优策略具有这样的性质，即无论初始状态或初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策须构成最优策略。

将该原理应用到最短路问题中，即从 A 到 E 的最短路线若经过 $s_k$ 点，则此路线由 $s_k$ 点到 E 的部分，必是由 $s_k$ 点到 E 点的最短路线。

如此，我们便可以从最后一个状态，即 $s_4$ 开始，向最初状态不断递推求解，最终得到从 A 到 E 的最短路线。

第一步： $k = 4$ ，此时状态变量集合为 $S_4=\{D1,D2,D3\}$ ，那么每个取值对应的指标函数分别为 $f_4(D1)=3,f_4(D2)=4,f_4(D3)=3$ 。

第二步： $k = 3$ ，此时状态变量可取值为 $S_3=\{C1,C2,C3,C4\}$ ，如果取 $C 1$ ，则其到终点有两条路线，需加以比较，有 $f_3(C1)=min\begin{Bmatrix} d(C1,D1)+f_4(D1) \\ d(C1,D2)+f_4(D2)\end{Bmatrix}=min\begin{Bmatrix} 5+3 \\ 6+4\end{Bmatrix}=8$ 说明从 C1 到 E 最短距离为 8 ，路径为 $C1\to D1 \to E$ ，此阶段决策为 $u^*_3(C_1)=D1$ 。

若取 $C 2$ ，只有一条路径，即 $C_2\to D1\to E$ ，则 $f_3(C2)=d(C2,D1)+f_4(D1)=8$ ，相应决策为 $u^*_3(C2)=D1$ 。同理，可求出 $f_3(C3)=d(C3,D3)+f_4(D3)=11,u^*_3(C3)=D3$ $f_3(C4)=d(C3,D3)+f_4(D3)=6,u^*_3(C4)=D3$ 第三步： $k = 2$ ，此时状态变量集合 $S_2=\{B1,B2\}$ ，有 $f_2(B1)=min\begin{Bmatrix} d(B1,C1)+f_3(C1) \\ d(B1,C2)+f_3(C2) \\ d(B1,C3)+f_3(C3) \end{Bmatrix}=min\begin{Bmatrix} 1+8 \\ 6+8 \\ 3+11 \end{Bmatrix}=9,u^*_2(B1)=C1$ $f_2(B_2)=min\begin{Bmatrix} d(B2,C2)+f_3(C2) \\ d(B2,C4)+f_3(C4)\end{Bmatrix}=min\begin{Bmatrix} 8+8 \\ 4+6\end{Bmatrix}=10,u^*_2(B_2)=C4$ 第四步： $k = 1$ ，此时只有一个状态 A ，有 $f_1(A)=min\begin{Bmatrix} d(A,B1)+f_2(B1) \\ d(A,B2)+f_2(B2)\end{Bmatrix}=min\begin{Bmatrix} 5+9 \\ 3+10 \end{Bmatrix}=13,u^*_1(A)=B2$ 即 A 到 E 的最短距离为 13 ，按照计算顺序反推可得到最优决策序列 ${u^*_k\}$ ，为 $u^*_1(A)=B2,u^*_2(B_2)=C4,u^*_3(C4)=D3,u^*_4(D3)=E$ ，则最优路线为 $A\to B2 \to C4 \to D3 \to E$ 从上述求解过程中可以看出，第 $k$ 阶段和第 $k + 1$ 段都利用了如下关系 $\begin{cases} \ f_k(s_k)=min\{d_k(s_k,u_k)+f_{k+1}(s_{k+1})\}, & k=4,3,2,1（1.1）\\ \ f_5(s_5)=0 （1.2） \end{cases}$ 注：状态转移方程为 $s_{k+1}=u_k$ 。