动态规划

动态规划:根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。即使是一些静态模型,只要人为的引进“时间”因素,分成时段,就可以转化为多阶段的动态模型,用动态规划去处理。

动态规划求解的问题需要满足一定的条件:

  • 最优化原理
  • 无后效应

最优化原理

最优化原理:不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简单来说就是一个最优策略的子策略也是必须是最优的,所有子问题的局部最优解将导致整个问题的全局最优解。
最优化原理是动态规划的基础,任何一个问题,如果失去最优化原理的额支持,就不可能用动态规划解决

举个的例子说明:



如上图,求从A点到E点的最短距离,假如最短距离的路线经过图中的B点,那么子问题就是求从A点到B点之间的最短距离。

那么这个问题里,怎么证明最优化原理呢?

我们假设从A点到E点的最短距离为d,其最优策略的子策略假设经过B点,记该策略中B点到E点的距离为d1,A点到B点的距离为d2。我们可以使用反证法,假设存在B点到E点的最短距离d3,并且d3 < d1,那么 d3 + d2 < d1 + d2 = d,这与d是最短距离相矛盾,所以,d1是B点到E点的最短距离。

为了增加理解,这里再举一个反例:



图中有四个点,A、B、C、D,相邻两点有两条连线,代表两条通道,d1,d2,d3,d4,d5,d6代表的是道路的长度,求A到D的所有通道中,总长度除以4得到的余数最小的路径为最优路径,求一条最优路径。

按照最优化原理,A的最优取值应该可以由B的最优取值来确定,而B的最优取值为(3+5)mod 4 = 0,所以应该选d2和d6这两条道路。而实际上,全局最优解是d4+d5+d6或者d1+d5+d3。所以这里子问题的最优解并不是原问题的最优解,即不满足最优化原理。所以就不适合使用动态规划来求解了

无后效应

无后效应:下一时刻的状态只与当前状态有关,而与当前状态之前的状态无关,当前状态是对以往策略的总结。换句话说,过去做的选择不会影响现在能做的最优选择,现在能做的最优选择只与当前的状态有关,与经过如何复杂的决策到达该状态的方式无关。


在上面的最短路径问题上,加上一个限制条件:同一个格子只能通过一次。
那么, 这个题就不符合无后效性了,因为前一个子问题的解会对后面子问题的选择策略有影响,比如说,如果从A到B选择了一条如下图中绿色表示的路线,那么从B点出发到达E点的路线就只有一条了。也就是说从A点到B点的路径选择会影响B点到E点的路径选择

问题解决思路

动态规划的理论设计都有一定的模式,一般需要经历一下几个步骤:
初始状态 -> |决策1| -> |决策2| -> |决策3|...-> |决策n| -> 结束状态

  1. 划分阶段:按照问题的时间或空间特征,把问题分为若干阶段
  2. 确定状态或者状态变量:将问题发展到各个阶段所处于的各种客观情况用不同的状态标识出来
  3. 确定决策并写出状态转移方程:如果确定了决策,状态转移方程也可写出,但事实上常常是反过来做,根据相邻两段个状态之间的关系来确定决策。
  4. 寻找边界条件:给出的状态转移方程是一个递归式,需要一个递推的终止条件或边界条件

使用动态规划求解问题,最重要的就是确定动态规划三要素

  • 问题的阶段
  • 每个阶段的状态
  • 从前一个阶段转化为后一个阶段之间的递推关系

其中递推关系必须是从次小的问题开始到较大的问题之间的转化
从这个角度来讲,动态规划往往可以用递归程序实现,不给过递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势。

设计算法实现步骤:
  1. 问题抽象化
  2. 建模
  3. 寻找约束条件
  4. 寻找递推关系式
  5. 确定初始值

参考:http://www.doc88.com/p-7983313595935.html

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,340评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,762评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,329评论 0 329
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,678评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,583评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 47,995评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,493评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,145评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,293评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,250评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,267评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,973评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,556评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,648评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,873评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,257评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,809评论 2 339