【动态规划】怎样从小问题出发，逐级解决大问题？

【动态规划】怎样从小问题出发，逐级解决大问题？

要确保问题可以分解成和原问题类似的子问题，并且这些子问题之间还相互独立，这时分治策略才能奏效。

算法分治策略的目的，不是要把一个不能解决的问题解决掉，而是要解决得更快。

咱举个例子，在计算机图形学中有个问题叫“碰撞检测”。 解决这个问题可不容易，尤其是模拟的空间中物体很多的时候。 100个球总共的计算次数是4950次。如果物体的个数更大些，计算次数会以平方的形式上升。 平方的形式，复杂度就挺高了。如果用这种算法，游戏在进行得枪林弹雨时，你的画面肯定会卡。 “分解”的时候计算成本的问题。 合并的时候，也有类似的问题。比如说你在分割空间的时候，可能会正好把某些球从中间割断。 合并的时候，你发现这些球不属于任何一个子空间，要判断它们有没有发生碰撞，还得额外计算。这是合并结果的成本。 分治中的两个重要操作，分解和合并，不是免费的。 如果它们自身就要耗费很多次计算，那很可能分治策略提升不了效率，也不算是奏效了。

分治算法，还可以通过巧妙地利用“硬件”，让效率进一步提升。这就是“并行计算”。 并行计算能让多个计算机的CPU同时为解决一个问题出力，但并不能减少总的操作数量。 并不是所有算法都可以用并行计算的。 迭代算法要求每一步以前一步的结果作为出发点，按步骤、按顺序进行计算。 顺序计算和并行计算有本质上的差异。 分治算法因为能把问题分解成独立的部分，所以和并行计算是天然的好朋友。 数据量越大，处理起来的所花的步骤也就多。那为了能快速地对数据进行分析处理，就必须用分治算法。 1 分治算法是通过回溯，不断分解同样的问题，直到问题小得可以直接解决，再把小问题的解合并成原来问题解的算法策略。 2 确保要解决的问题能分解成与原问题类似的子问题，并且这些子问题之间相互独立，这时分治策略才能奏效。 3 如果分解问题和合并结果计算不复杂，分治策略能减小算法的复杂度。 4 分治策略开启了并行计算的大门，利用多CPU硬件上的优势，可以减少算法的运行时间。 分治算法与生活中通常理解的分治不同，不是简单的将复杂大的问题分解成小的问题各个击破。 分治算法包括了分解和合并两步，将问题分解成用同样方法可以解决的独立小问题，再把这些小问题的解合并成原来问题的解，分解出来的小问题可以通过并行计算提高效率；所以，分解和合并本身的计算复杂度也决定了分治算法应用的可行性。 动态规划：怎样从小问题出发，逐级解决大问题？ “动态规划”是什么意思呢？“动态”指的是多个步骤，而“规划”指的就是决策。“动态规划”这个词既指多步骤的决策优化问题，也代表解决这类问题的算法方法。 问题的解决思路：以终为始，以小建大 要弄清楚动态规划，我们得从两方面入手，一个是它的内涵，它的解决思路；一个是它的外在，这个算法的结构。我们先来说它的解决思路，叫“以终为始，以小建大”。 这就是“以终为始，以小建大”的解决思路。也就是说，我们要先得到小问题的解，再构建出大问题的解。 火箭垂直软着陆的问题虽然更复杂，但解决的思路是类似的。 火箭科学家需要的，就是以终为始，从后往前解决问题。 每一步都施加正确的推进力，才能确保最后成功的软着陆。 动态规划算法的结构：最优子结构 “以终为始”的思想要能实现，还得通过特定的算法结构才能实现。这个结构，叫最优子结构。 如果将来的你总是遵守最优策略，那现在拿2颗糖就一定是现阶段最优的选择。 这也就是说，我们在面对一个多步骤的决策问题时，某一步决策的最优，包含且依赖于对更小规模问题的最优策略。 这就是最优子结构。 这个结构很重要。

如果一个问题满足了这个结构，那就说明我们可以从解决小问题开始，慢慢构建对大问题的解。 如果这个性质不满足，以终为始，以小建大的解决方案就不奏效。 这就出现了最优子结构不满足的情况。

你从北京，经东京到纽约的联程机票，虽然是两步问题中的最优解，但它并不包含从东京到纽约单步问题的最优解，因为联程机票不能分开使用。 即使你算出了北京到东京，和东京到纽约单步机票的价格，也不能构建出从北京到纽约的联程机票，大问题并不依赖于小问题的解。

所以这时候，最优子结构的条件就不满足，“以终为始”的思想就实现不了了。 动态规划算法，就是在多步骤的决策优化问题满足最优子结构的时候，用以终为始、以小建大的思想解决问题的算法策略。

动态规划在实际中出现的频率非常高。比如库存管理问题，每个周期是不是应该补货。工厂生产控制问题，每天应该生产哪拨订单。飞行器降落，每个时刻应该施加多少的加速度。股票交易，每天是应该买进还是卖出。这些问题的解决，都可以依赖动态规划的算法策略。 动态规划策略有效的条件 “维度爆炸”。 这个维度的大小，决定着我们要求解子问题的个数。

当问题的维度很大的时候，子问题的数量会呈指数形式上升。 即使最优子结构没有变化，但以终为始、以小建大的解决方向就会遇到计算瓶颈了。 选择算法策略最重要的考量就是在质量和效率之间寻求平衡。 算法工程师不一定会精确求解所有的子问题，很可能只求解其中的一部分，而且是非精确求解，对另外的子问题的解，只进行一个估计。 虽然不能得到完美的最优决策，得到的结果也是足够好的。

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

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

3 动态规划的效率会受“维度爆炸”的影响。 动态规划指解决多步骤决策优化问题的算法，限制条件是要满足最优子结构，然后以终为始、以小建大来解决整体问题 严格以来最优最结构，否则不成立 还会面对维度爆炸的问题。 分支定界：怎样决定谁是“被淘汰者”？