知识库

知识库资源

当前位置:首页>知识库
全部 14 商业 3

动态规划:怎样从小问题出发,逐级解决大问题?

时间:2021-04-24   访问量:1060

欢迎来到我的《算法通识课》

上一讲我们讲了分治的算法策略。用的是把一个问题分解,子问题逐个解决,然后合并的思想。

但不是所有问题都能一分为二。碰到这个情况,我们得换个思路,有时候“化大为小”也能有效解决问题。动态规划就是这么一种算法。

“动态规划”是什么意思呢? 

“动态”指的是多个步骤,而“规划”指的就是决策。“动态规划”这个词既指多步骤的决策优化问题,也代表解决这类问题的算法方法。

举个例子来说。2015年的时候,航空航天界发生了一件大事。美国的两家民营公司,蓝色起源Blue Origin和太空探索技术公司SpaceX,相继实现了火箭的垂直软着陆,把太空旅行和卫星发射的成本大大降低了。

垂直软着陆是什么样的呢?想象一下,推力装置会让火箭慢慢减速,调整姿态,最后速度几乎为0,垂直降落在指定的位置。

火箭降落时,每时每刻的速度和姿态都在变化,它是怎么实现安全着陆的呢?

这复杂的过程背后隐藏着一个重要的算法策略,就是动态规划。我们这一讲,就来说说动态规划算法是怎么解决问题的。

1 问题的解决思路:以终为始,以小建大

要弄清楚动态规划,我们得从两方面入手,一个是它的内涵,它的解决思路;一个是它的外在,这个算法的结构。

我们先来说它的解决思路,叫“以终为始,以小建大”

比如说咱俩现在要做一个游戏。桌上有一堆糖果,你我轮流从当中取走几颗。每次至少取一颗,最多取三颗。谁拿到最后一颗糖果谁赢。假设这时候桌上还有50颗糖果,轮到你来取了,你会取几颗呢?

你可以试着想想,如果取一颗会怎样,两颗、三颗又会怎样。是不是想不清楚?

因为问题里面的糖果个数太多了。我们从前往后思考,考虑很多步,也不会知道最终的结果会怎样。

那如果反过来呢?咱们一起试试。

糖果最终会有拿完的时候,如果从最少的糖果数来考虑,就容易多了。

假如现在桌上还有1颗糖果,你想都不用想,直接拿走,赢得游戏。如果有2颗或者3颗,你也可以都拿走。

但如果有4颗糖,就危险了。无论你拿几颗,都会至少剩1个,最多剩3个。我会把剩下的都拿走,赢得游戏。所以说,谁面对4颗糖,谁就要输。

那如果有5颗、6颗、7颗糖呢?你都可以选择拿1颗、2颗或者3颗,给我剩下4颗,让我陷入必输的境地。用同样的方法,你可以不断向上推演,得到一个最优策略。

最优策略是这样的:50颗糖,你拿走2颗,给我剩下48颗。正好是4的倍数。接下来你可以一直遵照这个最优策略,无论我拿几颗,你都让剩下糖的个数是4的倍数。这样你就一定可以赢得游戏。

这就是“以终为始,以小建大”的解决思路。也就是说,我们要先得到小问题的解,再构建出大问题的解。

火箭垂直软着陆的问题虽然更复杂,但解决的思路是类似的。

我们知道,火箭着陆的那一刻,位置必须离指定位置非常近,同时,火箭与地面的角度必须非常接近90度,着陆的速度必须非常接近零才行。满足这些条件,我们就赢了,否则就输了。

往回推一点,如果火箭离最终的着陆点还有一点距离,速度也还不是零,角度也不够垂直,那就需要对火箭在正确的方向上进行推动,才能实现软着陆。这就像是我们要拿正确数目的糖果一样。

但如果这时候火箭已经远远偏离着陆地点,再怎么推进都不能正确着陆。这就像是你必须从4个糖果里面取1到3个糖果,你已经输了,再怎么做都无济于事了。

火箭科学家需要的,就是以终为始,从后往前解决问题。每一步都施加正确的推进力,才能确保最后成功的软着陆。

2 动态规划算法的结构:最优子结构

好,动态规划的思想你已经知道了。但“以终为始”的思想要能实现,还得通过特定的算法结构才能实现。这个结构,叫最优子结构。

什么是最优子结构呢?咱们还用拿糖果的游戏来举例。

我们刚才说到,如果现在桌上有50颗糖果,你的最优策略应该是拿2颗糖。但拿2颗糖就一定能赢吗?

不一定。如果将来的你,在面对更少糖果的时候,不遵守最优策略,那你现在拿2颗糖也不会赢。反过来说,如果将来的你总是遵守最优策略,那现在拿2颗糖就一定是现阶段最优的选择。

这也就是说,我们在面对一个多步骤的决策问题时,某一步决策的最优,包含且依赖于对更小规模问题的最优策略。这就是最优子结构。

这个结构很重要。如果一个问题满足了这个结构,那就说明我们可以从解决小问题开始,慢慢构建对大问题的解。

但如果这个性质不满足,以终为始,以小建大的解决方案就不奏效。我来举个例子。

假设你要从北京坐飞机去纽约,但却没有直达飞机。中间必须在某一站转机。中转站的选择有很多。东京、夏威夷、首尔、西雅图都可以转机。那你应该在哪里转机才能买到价格最低的机票呢?

我们试着用以终为始的方法来解决。先算算每个中转站到纽约的航班价格,然后再算算北京到不同中转站的航班价格,分别相加,看看哪个路线的总价格最低。

这样得到的价格是最低的吗?

不一定。因为航空公司经常会有联程机票。很可能在东京转机的联程机票最便宜,而且比你分开买北京到东京,和东京到纽约的机票要便宜得多。

这就出现了最优子结构不满足的情况。你看,你从北京,经东京到纽约的联程机票,虽然是两步问题中的最优解,但它并不包含从东京到纽约单步问题的最优解,因为联程机票不能分开使用。

反过来,即使你算出了北京到东京,和东京到纽约单步机票的价格,也不能构建出从北京到纽约的联程机票,大问题并不依赖于小问题的解。

所以这时候,最优子结构的条件就不满足,“以终为始”的思想就实现不了了。

好了,到这里,我们介绍了动态规划的思想和结构,那我们一句话来总结一下,动态规划算法到底是什么。

动态规划算法,就是在多步骤的决策优化问题满足最优子结构的时候,用以终为始、以小建大的思想解决问题的算法策略。

动态规划在实际中出现的频率非常高。

比如库存管理问题,每个周期是不是应该补货。工厂生产控制问题,每天应该生产哪拨订单。飞行器降落,每个时刻应该施加多少的加速度。股票交易,每天是应该买进还是卖出。这些问题的解决,都可以依赖动态规划的算法策略。

3 动态规划策略有效的条件

那是不是遇到有最优子结构的多步骤决策问题,我们都能用动态规划算法有效解决呢?

肯定不是。这一讲的最后,我来说说动态规划算法经常遇到的一个问题,碰上了很可能就失效了。这个问题叫“维度爆炸”。

我们刚才讲的抓糖游戏里有两个描述游戏状态的变量,糖还有几颗,以及下一个抓糖的人是谁,所以维度是2。火箭软着陆的维度可能是十个或十个以上。这个维度的大小,决定着我们要求解子问题的个数。

当问题的维度很大的时候,子问题的数量会呈指数形式上升。这时候,即使最优子结构没有变化,但以终为始、以小建大的解决方向就会遇到计算瓶颈了。

拿围棋问题举个例子。

在棋局进行的任何一个时刻,当我们要下一个子的时候,面临着很多不同的选择,每一个选择都对应着一个子问题。可能落子的地方有几百个,对应的就是几百个子问题。如果再下一个子,就又会衍生出几百个子问题。

这个维度就太大了。围棋棋盘有361个格点,每个格点有黑棋、白棋、空位三种可能性,那整个子问题的数量就有3的361次方那么多。太多了,动态规划算法再强大也不能完美解决。

这时候怎么办呢?算法工程师的智慧就又显现出来了。

我们说过,选择算法策略最重要的考量就是在质量和效率之间寻求平衡。

所以算法工程师不一定会精确求解所有的子问题,很可能只求解其中的一部分,而且是非精确求解,对另外的子问题的解,只进行一个估计。这样虽然不能得到完美的最优决策,得到的结果也是足够好的。

 划重点

1 动态规划指的既是多步骤的决策优化问题,也是解决这类问题的算法方法。 

2 动态规划算法是在多步骤的决策优化问题满足最优子结构的时候,用以终为始、以小建大的方向解决问题的算法策略。

3 动态规划的效率会受“维度爆炸”的影响。

最后,给你留一道思考题。你在工作中有没有遇到需要先解决小规模问题,然后构建大规模问题解的情况呢?这个问题有没有“最优子结构”呢?欢迎留言,说说你的思考。

使用动态规划算法,需要问题满足最优子结构,那如果问题不满足这个要求,有没有算法可以应对呢?当然有,下一讲的分支定界法就可以应对。


上一篇:分治:怎样拆解问题,逐个击破?

下一篇:分支定界:怎样决定谁是“被淘汰者”?

发表评论:

评论记录:

未查询到任何数据!
点击这里给我发消息

在线咨询

咨询专员 点击这里给我发消息

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部