动态规划思想入门 喻（2008 年 10 月 7 日）关键字：动态规划，最优子结构，记忆化搜索引言动态规划 (dynamic programming)是运筹学的一个分支，是求解决策过程(decisionprocess) 最 优 化 的 数 学 方 法 。 20 世 纪 50 年 代 初 美 国 数 学 家R.E.Bellman 等人在讨论多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957 年出版了他的名著 Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划的基本思想动态规划是：将待求的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它直接求解，并把答案保存起来，让以后再次遇到是直接引用答案，不必从新求解，其实质是分治思想和解决冗余。例 1：求 A—>B 的最短路径图 1这是一个利用动态规划思想的经典问题，通过直接观察图 1 我们可以枚举出 20 多条路径，并可以计算出其中最短的路径长度为 16用动态规划的思想来分析，我们可以把这个问题转换成下面这个模型阶段图 2阶段：根据问题的特点和需要，将问题按时间或空间特征分解为若干相互联系的阶段。在本例中，我们根据空间特性将问题分成了 6 个阶段。状态：各阶段的开始条件，本例中，A,B,C……P这些节点都属于状态，表示从该点到B的最短路径，在这里我们计做S(i)，表示从第i个节点（状态）到B的最短路径决策：某阶段状态确定后，从该状态到下阶段某状态的选择。比如S(A)，它可以选择通过C到达B，也可以选择通过D到达B。状态转移方程：系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移，体现转移规律的方程称状态转移方程。在本例中，我们不难推出S(A)=MIN{S(C)+4,S(D)+3},S(C)=MIN{S(E)+5,S(F)+3}…………S(B)=0，由...
