动态规划算法百百科.doc

动态规划算法百度百科
2

———————————————————————————————— 作者：
———————————————————————————————— 日期：

个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
动态规划
百科名片
  
动态规划
动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）(multistep decision process)的优化问题时，提出了著名的最优化原理（principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法-—动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
目录
简介
概念及意义
基本模型
基本思想
基本结构
基本模型
适用条件
作用
简介
概念及意义
基本模型
基本思想
基本结构
基本模型
适用条件
作用
应用
动态规划练习题
3

个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
《Dynamic Programming》
展开
编辑本段
简介
　　
  
  
是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱。
　　动态规划首次进入信息学奥赛是在IOI94（数字三角形），在国内首次出现是在NOI95。此后动态规划成为信息学奥赛的必考算法之一.
编辑本段
概念及意义
　　动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
　　虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解.
　　动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同,确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题,有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，、讨论，逐渐学会并掌握这一设计方法。
4

个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
个人收集整理 勿做商业用途
编辑本段
基本模型
　　多阶段决策过程的最优化问题。
　　含有递推的思想以及各种数学原理（加法原理，乘法原理等等）.
　　在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）
  
多阶段决策问题
这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策