动态规划运筹帷幄之中决胜千里之外什么是动态规划?动态规划是解决某一类问题的一种方法,是分析问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因此,在学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。动态规划三要素:阶段,状态,决策。1、阶段(stage)把所给问题恰当地划分为若干个相互联系又有区别的子问题,通常根据时间顺序或空间特征来划分,以便按阶段的次序逐段解决整个过程的优化问题。描述阶段的变量叫作阶段变量,阶段变量通常用k表示(k=1,2,3,…,n)。动态规划三要素:阶段,状态,决策。2、状态(state)用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。它应能描述过程的特征并具有“无后效性”,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。状态变量——sk(statevariable)状态集合——Sk(setofadmissiblestates)动态规划三要素:阶段,状态,决策。3、决策(decision)决策:确定系统过程发展的方案。决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量—uk(sk)(decisionvariable)决策集合—Dk(sk)(setofadmissibledecision)多阶段决策过程及实例状态s1阶段1决策u1状态s2决策u2阶段2状态s3...状态sk决策uk阶段k状态sk+1...状态xn决策un阶段n状态sn+1动态规划的适用范围动态规划用于解决多阶段决策最优化问题,但是不是所有的最优化问题都可以用动态规划解答呢?一般在题目中出现求最优解的问题就要考虑动态规划了,但是否可以用还要满足两个条件:最优子结构(最优化原理)当前状态是前面状态的完美总结无后效性什么是无后效性呢?就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N,而求状态N时有用到了状态i动态规划解决问题的一般思路(1)模型匹配法:最先考虑的就是这个方法了。挖掘问题的本质,如果发现问题是自己熟悉的某个基本的模型,就直接套用,但要小心其中的一些小的变动,现在考题办都是基本模型的变形套用时要小心条件,三思而后行。这些基本模型在先面的分类中将一一介绍。(2)三要素法仔细分析问题尝试着确定动态规划的三要素,不同问题的却定方向不同:先确定阶段的问题:数塔问题,和走路问题(详见解题报告)先确定状态的问题:大多数都是先确定状态的。先确定决策的问题:背包问题。(详见解题报告)(3)寻找规律法(4)边界条件法找到问题的边界条件,然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。(5)放宽约束和增加约束这个思想是在陈启锋的论文里看到的,具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。状态是一维的例1:拦截导弹某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。问题:输入导弹依次飞来的高度(389,207,155,300299,170,158,65),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统?
dp浙江大学周杨涛教授 来自淘豆网m.daumloan.com转载请标明出处.
