动态规划：状态变量与递推关系的构建

1.阶段

把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序来求解。描述阶段的变量称为阶段变量，常用k 表示。阶段的划分，一般是根据时间和空间的自然特征来划分的，但要便于把问题的过程能转化为多阶段决策的过程。如在例5-1中，可分为6个阶段来求解，k 分别等于1，2，3，4，5，6。

2.状态

状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称为不可控因素。如在例5-1中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路的终点。一个阶段通常有若干个状态，第一阶段有一个状态就是点A；第二阶段有两个状态，即点集合{ B1，B2}；一般地，第k 阶段的状态就是第k 阶段所有始点的集合。

描述过程状态的变量称为状态变量，它可用一个数、一组数或一向量（多维情形）来描述。常用 Sk表示第k 阶段的状态变量。如在例5-1中，第三阶段有4 个状态，则状态变量 Sk可取4 个值，即 C1，C2，C3，C4。点集合{C1，C2，C3，C4}就称为第三阶段的可达状态集合，记为S3={C1，C2，C3，C4}。有时为了方便起见，将该阶段的状态编上号码1，2…，这时也可记为S3={1，2，3，4}。第k 阶段的可达状态集合就记为Sk。

这里所说的状态应具有下面的性质：如果某阶段状态给定后，则在此阶段以后过程的发展不受此阶段以前各段状态的影响。换句话说，过程的过去历史只能通过当前的状态来影响它未来的发展，当前的状态是以往历史的一个总结。这个性质称为无后效性（即马尔科夫性）。

如果状态仅仅描述过程的具体特征，那么并不是任何实际过程都能满足无后效性的要 求。所以，在构造决策过程的动态规划模型时，不能仅从描述过程的具体特征这点着眼来规定状态变量，而要充分注意是否满足无后效性的要求。如果状态的某种规定方式可能导致不满足无后效性，应适当改变状态的规定方法，以达到能使它满足无后效性的要求。例如，研究物体（把它看作一个质点）受外力作用后其空间运动的轨迹问题。从描述轨迹这点着眼，可以只选坐标位置（xk，yk，zk）作为过程的状态，但这样不能满足无后效性，因为即使知道了外力的大小和方向，仍无法确定物体受力后的运动方向和轨迹，只有把位置（xk，yk，zk）和速度都作为过程的状态变量，才能确定物体下一步运动的方向和轨迹，实现无后效性的要求。

3.决策

决策表示当过程处于某一阶段的某个状态时，可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。描述决策的变量，称为决策变量，它可用一个数、一组数或一向量来描述。常用 uk（sk）表示第k 阶段当状态处于 sk时的决策变量，它是状态变量的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用 Dk（sk）表示第k 阶段从状态 sk出发的允许决策集合。显然有 uk（sk）∈Dk（sk）。

如在例5-1 第二阶段中，若从状态 B1出发，就可做出三种不同的决策，其允许决策集合D2（s1）={C1，C2，C3}；若选取的点为C2，则 C2就是状态 B1在决策 u2（B1）作用下的一个新的状态，记作 u2（B1）=C2。

4.策略

策略是一个按顺序排列的决策组成的集合。由过程的第k 阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k 子过程）。由每段的决策按顺序排列组成的决策函数序列{uk（sk），…，un（sn）}称为k 子过程策略，简称子策略，记为pk，n（sk）。即

当k=1时，此决策函数序列称为全过程的一个策略，简称策略，记为p1，n（s1）。即

在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P 表示。从允许策略集合中找出达到最优效果的策略称为最优策略。

5.状态转移方程(www.xing528.com)

状态转移方程是确定过程由一个状态到另一个状态的演变过程。若给定第k 阶段状态变量 sk的值，如果该段的决策变量 uk一经确定，则第k+1阶段的状态变量sk+1的值也就完全确定。即sk+1的值随 sk和 uk的值的变化而变化。这种确定的对应关系，记为

上式描述了由k 阶段到k+1阶段的状态转移规律，称为状态转移方程，Tk称为状态转移函数。如例5-1中，状态转移方程为sk+1=uk（sk）。

6.指标函数和最优值函数

用来衡量所实现过程优劣的一种数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数，常用Vk，n表示之。即

对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk，n可以表示为sk，uk，Vk+1，n的函数，记为

在实际问题中，很多指标函数都满足这个性质。

常见的指标函数的形式如下：

（1）过程和它的任一子过程的指标是它所包含的各阶段的指标的和。即

其中 vj（sj，uj）表示第j 阶段的阶段指标。这时上式可写成

（2）过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。即

这时可写成

指标函数的最优值，称为最优值函数，记为fk（sk）。它表示从第k 阶段的开始状态 sk到第n 阶段的终止状态的过程，采取最优策略所得到的指标函数值。即

其中“opt”是最优化（optimization）的缩写，可根据题意而取min 或max。

在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产品的产量或资源消耗等。例如，在最短路线问题中，指标函数Vk，n就表示在第k 阶段由点 sk至终点G的距离。用 dk（sk，uk）=vk（sk，uk）表示在第k 阶段由点 sk到点sk+1=uk（sk）的距离，如 d5（E1，F1）=3，就表示在第五阶段中由点 E1到点 F1的距离为3。 fk（sk）表示从第k 阶段点 sk到终点G的最短距离，如 f4（D1）就表示从第四阶段中的点 D1到点G的最短距离。