动态规划：基本思想与方程解析

如图5-2 所示的线路网络，求A 到G的最短路线问题是动态规划中一个较为直观的典型例子。现通过其解法的讨论，来说明动态规划方法的基本思想，并阐述它的基本概念。

由图5-2 可知，从A 点到G 点可以分为6 个阶段，其中，从A 到B 为第一阶段，从B 到C 为第二阶段……从F 到G 为第六阶段。在第一阶段，A 为起点，终点有 B1，B2两个，因而这时有两种线路可以选择：一种是走到 B1，另一种是走到 B2；若选择走到 B2这一决策，则B2就是第一阶段在我们决策之下的结果，它既是第一阶段线路的终点，又是第二阶段线路的始点。在第二阶段，再从 B2点出发，对应于 B2点就有一个可供选择的终点集合{C2，C3，C4}；若选择由 B2走至 C2为第二阶段的决策，则 C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到：各个阶段的决策不同，铺管线路就不同。很明显，当某阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个线路的长短，而后面各阶段的线路的发展又不受这点以前各阶段线路的影响。因此，此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条线路，其总路程最短。

如何解决这个问题呢？可以采取穷举法。即把由A 到G 所有可能的每一条线路的距离都算出来，然后互相比较找出最短者，即得出了最短线路。这样，由A 到G的6 个阶段中，一共有2×3×2×2×2×1=48 条不同线路，比较这48 条不同线路的距离值，再找出最短线路为(www.xing528.com)

即最短距离为18。显然，这样做计算是相当繁杂的。如果当段数很多，各段的不同选择也很多时，这种解法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的。因此，为了减少计算工作量，需要寻求更好的算法，即下面要介绍的动态规划方法。为了讨论方便，先介绍动态规划的基本概念和符号。