【摘要】：设计最短路径问题，是为了在介绍动态规划方法时给读者一个具体的概念。由于动态规划文献中大都采用逆序解法，因此，下面先来介绍采用逆序解法求解最短路径问题时建立动态规划模型所要用到的基本概念。在定义动态规划模型中的状态变量时，要求状态变量应具有如下性质。如果所选定的变量不具备无后效性，就不能作为动态规划模型的状态变量。动态规划中本阶段的状态往往是上一阶段的状态和决策的共同结果。
设计最短路径问题，是为了在介绍动态规划方法时给读者一个具体的概念。尽管逆序解法和顺序解法本质上是一样的，但是采用逆序解法和顺序解法在建立动态规划模型时，有些符号所表示的含义是不一样的。有关这一点，通过上面的例子就可以看出。由于动态规划文献中大都采用逆序解法，因此，下面先来介绍采用逆序解法求解最短路径问题时建立动态规划模型所要用到的基本概念。
1.阶段
若想采用动态规划求解的问题，首先要求该问题可以按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。一般将描述阶段的变量称为阶段变量，常用n表示。在例4-1中，从A地到H地可分为三个阶段，即n = 1，2，3。
2.状态
在定义动态规划模型中的状态变量时，要求状态变量应具有如下性质。当某阶段状态给定后，该阶段以后的发展不受该阶段以前各阶段状态的影响。也就是说，当前状态是过去的一个完整总结，系统的过去只能通过当前状态去影响它的未来发展。这个性质被称为无后效性。如果所选定的变量不具备无后效性，就不能作为动态规划模型的状态变量。
3.决策和策略
4.状态转移方程
动态规划中本阶段的状态往往是上一阶段的状态和决策的共同结果。如果给定第n阶段的状态sn，本阶段的决策为xn （sn ），那么第n+1阶段的状态sn+1也就完全确定了。它们的关系用公式表示如下：
5.指标函数
（2）过程指标函数值是阶段指标连乘的形式，即
对于一般问题，如果过程指标函数是阶段指标和的形式，最优指标函数可写为：
类似的，如果过程指标函数是阶段指标连乘的形式，最优指标函数可写为：
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
