文档介绍：动态规划动态规划目录[ 隐藏] 概念及意义基本模型记忆化搜索状态决策动态规划算法的应用动态规划练习题《 Dynamic Programming 》是信息学竞赛中选手必须熟练掌握的一种算法, 他以其多元性广受出题者的喜爱. 动态规划首次进入信息学奥赛是在 IOI94 (数字三角形) ,在国内首次出现是在 NOI95 。此后动态规划成为信息学奥赛的必考算法之一。[ 编辑本段] 概念及意义动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process) 最优化的数学方法。 20 世纪 50 年代初美国数学家 等人在研究多阶段决策过程(multistep decision process) 的优化问题时,提出了著名的最优化原理(principle of optimality) ,把多阶段过程转化为一系列单阶段问题, 利用各阶段之间的关系, 逐个求解, 创立了解决这类过程优化问题的新方法——动态规划。 1957 年出版了他的名著 Dynamic Programming ,这是该领域的第一本著作。动态规划问世以来, 在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题, 用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划( 如线性规划、非线性规划), 只要人为地引进时间因素, 把它视为多阶段决策过程, 也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样, 具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题, 由于各种问题的性质不同, 确定最优解的条件也互不相同, 因而动态规划的设计方法对不同的问题, 有各具特色的解题方法, 而不存在一种万能的动态规划算法, 可以解决各类最优化问题。因此读者在学习时, 除了要对基本概念和方法正确理解外, 必须具体问题具体分析处理, 以丰富的想象力去建立模型, 用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。[ 编辑本段] 基本模型多阶段决策过程的最优化问题。在现实生活中, 有一类活动的过程, 由于它的特殊性, 可将过程分成若干个互相联系的阶段, 在它的每一阶段都需要作出决策, 从而使整个过程达到最好的活动效果。当然, 各个阶段决策的选取不是任意确定的, 它依赖于当前面临的状态, 又影响以后的发展, 当各个阶段决策确定后, 就组成一个决策序列, 因而也就确定了整个过程的一条活动路线,如图所示: (看词条图) 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题就称为多阶段决策问题。[ 编辑本段] 记忆化搜索给你一个数字三角形, 形式如下: 123456789 10 找出从第一层到最后一层的一条路, 使得所经过的权值之和最小或者最大. 无论对与新手还是老手,这都是再熟悉不过的题了,很容易地, 我们写出状态转移方程: f(i, j)=a[i, j]+ min{f(i+1, j), f(