单位文秘网 2021-07-20 08:07:01 点击: 次
教师经常会提到“无记忆性”与“记忆性”两个看似完全矛盾的概念,不少学生也感到十分茫然。其实,这两个概念在动态规划中得到了完美的统一。
“无记忆性”指的是可用动态规划方法求解的多阶段决策问题,在划分阶段时,状态必须满足的一个特性,也称为无后效性或马尔科夫性。其实质是:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。即“未来与过去无关”,当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过程未来的演变。[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.
[责任编辑:王 品]
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-121-67412-1.html
上一篇:运筹学在安全决策中的应用
下一篇:四年级阅读训练材料
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用