分类：
2009-12-09 22:17:50
正向思维法是指从初始状态或边界状态出发，利用某种规则不断到达新的状态，直到问题目标状态的方法。动态规划的正向思维法，正是从已知最优值的初始状态或边界状态开始，按照一定的次序遍历整个状态空间，递推出每个状态所对应问题的最优值。
提出动态规划的正向思维法的根本原因，是为了摆脱逆向思维法当中那种将大问题转化为子问题的思维框框，提供一种新的思维方式。在正向思维法中，我们不再区分原问题和子问题，将动态规划的过程看成是从状态到状态的转移。我们将所有的状态构造出一个状态空间，并在状态空间中设想一个状态网络，若对两个状态i,j，存在决策变量di使t(i，di)=j，则向状态网络添加有向边
因为正向思维法中不再区分原问题、子问题、子子问题，所以我们不再按照问题被递归调用求解的相反次序的方法确定状态最优值的计算次序。从上面我们知道可以按照状态的拓扑序列来计算每个状态的最优值，于是我们用一个新的名词“阶段”来描述在状态空间遍历的过程中，各个状态最优值的计算次序。我们将每个状态和一个阶段挂钩，前一个阶段的状态先计算，后一个阶段的状态后计算。有的时候我们甚至将一组状态和一个阶段挂钩，前一个阶段的那组状态先计算，后一个阶段的那组状态后计算，而在同一个阶段内，那些状态的计算次序可以是任意的。
动态规划的正向思维法的要点可归纳为以下三个步骤：
(1)构造状态网络；
(2)根据状态转移关系和状态转移方程建立最优值的递推计算式：
(3)按阶段的先后次序计算每个状态的最优值。
在下一节“最短路问题”当中，我们将结合最短路问题来示范动态规划的正向思维法。
动态规划的正向思维法带给我们什么启示呢?动态规划需要按阶段遍历整个状态空间，因此动态规划的效率取决于状态空间的大小和计算每个状态最优值的开销：如果状态空间的大小是多项式的，那么应用动态规划的算法就是多项式时间的；如果状态空间的大小是指数的，那么应用动态规划的算法也是指数时间的。因此，找一个好的状态划分对动态规划的效率是至关重要的。
将这个结论应用到逆向思维上，我们得出如下结果：一个问题的最优子结构常常暗示了动态规划的状态空间。典型的情况是，某一个特定问题可有几类“自然”的子问题，不同的子问题往往意味着不同的最优子结构，从而我们得到不同的状态划分方案。但是由这些不同的状态得到的算法的效率可能差异极大。例如，某个问题的输入是一个有序序列，有两类“自然”的子问题，一类子问题的输入是原问题输入序列的所有子序列，另一类子问题的输入是原问题输入序列的任意元素构成的新序列。显然若我们采用后者的最优子结构来建立状态，它的状态空间必然远远大于基于前者的状态空间。那末基于后者的状态空间的动态规划则要解许多不必要的问题，使得算法的效率骤然下降。
从动态规划的正向思维法的分析可以看出，我们从已知最优值的初始状态和边界状态出发，利用最优化原理，一步一步向未知的目标状态推进，直到目标状态的最优值解决。这种“从己知推广到未知”的思维，正是动态规划正向思维法的精髓。大家在运用动态规划的正向思维法时如果能掌握这一点，那么就能达到应用自如的境界。
在应用动态规划求解的问题的过程中，希望读者能够注意从题目的分析中领会：应用动态规划解题是富于技巧和创造性的，没有固定的模式可套；题目出现的形式多种多样，而且大部分表面上与动态规划看不出直接的联系。只有在充分把握其思想精髓的前提下大胆联想，才能达到得心应手，灵活运用的境界。
