动态规划案例教学设计

总结，此前的历史只能通过当前的状态去影响过程未来的演变。[1]

“记性性”指的是用动态规划方法求解多阶段决策问题时（以逆序为例），为求得第K步最优子策略fk（Sk），必须先计算出从第K+1阶段的各状态出发所对应的最优子策略fk+1（Sk+1），并由第K+1步的最优子策略fk+1（Sk+1）去求取第K步最优子策略fk（Sk）。这些后续状态对应的最优子策略实际上构成了一张查找表（Lookup Table）。[3]为更好地理解无记忆性与记忆性，仍以最短路问题为例进行说明。

假设有一个可分为10个阶段的最短路问题，每阶段有10个状态可供选择。“无记忆性”指的是当游客在第k阶段处于状态Sk时，则该游客从Sk出发到终点的最短路径（K步最优子策略）只与Sk相关，而与Sk之前的状态、决策无任何关系。

“记忆性”指的是当用动态规划方法求解最短路问题时，第K步最优子策略是由第K步的决策和第K+1步的最优子策略共同决定的，而第K+1步的最优子策略已在之前求出并存放于内存之中，这就是记忆性。动态规划的记忆性可节省大量的计算时间，但会占用较多的计算机内存，即常用的“空间换时间”策略。

以上题为例，10个阶段每阶段10个状态的最短路问题，如果采用穷举法，则需要计算的路径条数（相当于动态规划中的全策略）为109条，每条路径需要进行10次加法运算;在109条路径中找出最短路径需要进行109-1次比较运算，则总的基本运算是11*109-1次。

而采用动态规划方法时，每阶段的每个状态需要进行10次加法运算和9次比较运算，则总的基本运算次数为1539次（其中加法运算810次，比较运算729次），和穷举法比较可节省大量的计算时间。

从该例题的分析可知，一个多阶段决策问题之所以可采用有“记忆性”的动态规划方法求解，恰恰是因为该问题在划分阶段时，各阶段的自然特征（即状态）满足“无记忆性”。因此，我们说，“记忆性”与“无记忆性”在动态规划中得到了完美的统一。

五、结束语

经教学实践证明，在动态规划教学中以最短路为引例，有利于学生对动态规划相关概念的理解，尤其有利于学生掌握最优性原理和无记忆性、记忆性这些晦涩难懂的原理与性质，为学生学好、用好动态规划打下了良好基础。

[ 参 考 文 献 ]

[1] 胡运权.运筹学教程（第四版）[M].北京：清华大学出版社，2012：191-232.

[2] Bellman R. E.Dynamical Programming[M].普林斯顿大学出版社，1957：58-92.

[3] Hamdy A. Taha. Operations Research：An introduction（第8版）[M].北京：人民邮电出版社，2008：744-754.

[4] 《运筹学》教材编写组.运筹学（第三版）[M].北京：清华大学出版社，2005：194-215.

[5] 韩伯棠.管理运筹学（第二版）[M].北京：高等教育出版社，2005：256-262.

[责任编辑：王 品]