对动态规划的再认识

本文分两部分:第一部分,回顾规划论简史之后,讨论动态规划的最优性原理与递推公式。认为原理本身存在多方面不严密之处,并举出了反例;还证明了(定理1)当第一、第二两类最优策略集合相等时,原理与公式等价。第二部分,作者抛开上述原理与公式,另行建立嘉量原理以及与之等价的求解代数公式。它们不仅可以用来求解常义的最优策略,而且可以用来求解N阶最优策略,多目标非劣解以及其他问题,而这些是最优性原理不能概括、递推公式解决不了的。从代数的观点,作者讨论了摹方阵乘幂问题,得到了定理3。它说明可以代数地构造任意多个有效的算法求解网络上两类最优路问题;还讨论了摹多项式及其应用。本文目的是概述作者对动态规划的某些基本看法以及作者长期从事研究上述问题的基本思路与主要结果。