多阶段决策过程问题的动态规划算法

多阶段决策过程（ multistep decision process ）是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。在计算机算法设计方法中，动态规划技术是比较基本，但又比较抽象，难于理解的一种。它建立在最优原则的基础上，动态规划 （ dynamic programming ）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。因此，动态规划技术越来越成为解决许多重要的应用问题的关键技术。例如，用动态规划解决0-1背包问题、图像数据压缩、矩阵连乘、有向图最短路径、无交叉子集、元件折叠以及最长公共子序列等应用问题。另外，在语音识别领域，应用动态规划技术的动态时间伸缩算法DTW取得了很大成功，当词汇表较小以及各个词条不易于混淆时，DTW可以有效的解决孤立词识别时说话速度不均匀的难题，从而自20世纪60年代末期掀起了语音识别研究的热潮。