还有其他的资源（人力，物力）分配问题、生产贮存问题、最优装载问题、水库优化问题、最优控 制问题等等，都具有多阶段决策问题的特性，均可用动态规划方法去求解。 §4.2动态规划的基本概念和基本方程（书§8.2） 下面通过讨论例1.1(P192图8-2)的解法来说明动态规划的基本思想，并阐述基本概念。 从A到G分6个阶段：A到B,B到C,C到D,D到E,E到F,F到G。 在第1阶段，A为起点，有2个选择：→B1,→B2。若选择→B1,则得到下阶段的起点B1,若选择 →B2,则得到下阶段的起点B2。如果所做的决策是→B2,则得到下阶段的起点为B2。 在第2阶段，对起点B2,有3个选择：→C2,→C3,C4。若选择→C2,则得到下阶段的起点C2, 若选择→C3,则得到下阶段的起点C3,若选择→C4,则得到下阶段的起点C4。如果所做的决策是→C2, 则得到下阶段的起点为C2。 依次类推，可看到各个阶段所做的选择不同，则得到的路线就不同。 很明显，当某阶段的起点给定时，它直接影响后面各阶段的行进路线和整个路线的长短，而后面各 阶段路线的发展不受这点以前各阶段路线的影响。 故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的 一条路线为最短其路线。 方法一：枚举法，即把由A到G的所有可能的路线的距离都算出来，互相比较得最短者。 可能的路线个数：2×3×2x2×2×1=48。 显然此方法计算相当繁，计算量大，当段数很多时，不现实。 方法二：动态规划方法。 4.2.1动态规划的基本概念 (1)阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。 阶段的划分一般根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策过程。 用k表示第k个阶段。 如在例4.1.1中，根据空间位置把问题的过程划分为6个阶段，分别用=1,23,4,5,6表示。 (2)状态：表示每个阶段开始时所处的自然状况或客观条件，它描述了研究问题过程的状况，又 称不可控因素，用$4表示第k个阶段的状态。通常，一个阶段可有若干个状态，这些状态的集合称为允 许状态集，用S表示第k个阶段的允许状态集，显然S4∈S4。 如在例41.1中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路 的终点。第一阶段有1个状态就是A,第二阶段有2个状态，即B1,B2,因此s1∈S={A},S2∈S2={B1, B2} 状态必须具有如下性质。 无后效性（马尔科夫性）：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各 段状态的影响。换句话说：过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以 往历史的一个总结。 (3)决策：表示当过程处于某一阶段的某个状态时，可以作出的不同决定（或选择），从而确定 下一阶段的状态。用，(s)表示第k个阶段状态为s%时所做的决策以得到第什1阶段的状态。通常，在 状态S联处有若干个决策可供选择，这些决策的集合称为允许决策集，U(s)表示，显然(s)∈U4(S)。 如在例4.1.1，h(B2)∈U2(B2)={→C2,→C3,→C4}。2 还有其他的资源（人力，物力）分配问题、生产贮存问题、最优装载问题、水库优化问题、最优控 制问题等等，都具有多阶段决策问题的特性，均可用动态规划方法去求解。 §4.2 动态规划的基本概念和基本方程(书§8.2) 下面通过讨论例 1.1（P192 图 8-2）的解法来说明动态规划的基本思想，并阐述基本概念。 从 A 到 G 分 6 个阶段：A 到 B，B 到 C，C 到 D，D 到 E，E 到 F，F 到 G。 在第 1 阶段，A 为起点，有 2 个选择：→B1，→B2。若选择→B1，则得到下阶段的起点 B1，若选择 →B2，则得到下阶段的起点 B2。如果所做的决策是→B2，则得到下阶段的起点为 B2。 在第 2 阶段，对起点 B2，有 3 个选择：→C2，→C3，→C4。若选择→C2，则得到下阶段的起点 C2， 若选择→C3，则得到下阶段的起点 C3，若选择→C4，则得到下阶段的起点 C4。如果所做的决策是→C2， 则得到下阶段的起点为 C2。 依次类推，可看到各个阶段所做的选择不同，则得到的路线就不同。 很明显，当某阶段的起点给定时，它直接影响后面各阶段的行进路线和整个路线的长短，而后面各 阶段路线的发展不受这点以前各阶段路线的影响。 故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的 一条路线为最短其路线。 方法一：枚举法，即把由 A 到 G 的所有可能的路线的距离都算出来，互相比较得最短者。 可能的路线个数：2×3×2×2×2×1=48。 显然此方法计算相当繁，计算量大，当段数很多时，不现实。 方法二：动态规划方法。 4.2.1 动态规划的基本概念 （1）阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。 阶段的划分一般根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策过程。 用 k 表示第 k 个阶段。 如在例 4.1.1 中，根据空间位置把问题的过程划分为 6 个阶段，分别用 k=1,2,3,4,5,6 表示。 （2）状态：表示每个阶段开始时所处的自然状况或客观条件，它描述了研究问题过程的状况，又 称不可控因素，用 sk表示第 k 个阶段的状态。通常，一个阶段可有若干个状态，这些状态的集合称为允 许状态集，用 Sk表示第 k 个阶段的允许状态集，显然 sk∈Sk。 如在例 4.1.1 中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路 的终点。第一阶段有 1 个状态就是 A，第二阶段有 2 个状态，即 B1，B2，因此 s1∈S1={A}，s2∈S2={B1， B2}。 状态必须具有如下性质。 无后效性（马尔科夫性）：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各 段状态的影响。换句话说：过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以 往历史的一个总结。 （3）决策： 表示当过程处于某一阶段的某个状态时，可以作出的不同决定（或选择），从而确定 下一阶段的状态。用 uk(sk)表示第 k 个阶段状态为 sk时所做的决策以得到第 k+1 阶段的状态。通常，在 状态 sk处有若干个决策可供选择，这些决策的集合称为允许决策集，Uk(sk)表示，显然 uk(sk)∈Uk(sk)。 如在例 4.1.1，u2(B2)∈U2(B2)={→C2，→C3，→C4}