一只无聊的柠檬

# 14.动态规划：最优结构解决复杂问题

分治法使用必须满足的4个条件

  • 1.问题的解决难度与数据规模有关
  • 2.原问题可被分解
  • 3.子问题的解可以合并为原问题的解
  • 4.所有子问题相互独立

但是在实际工作中，存在一种前三个条件的都满足，但是最后一个条件不满足的情况。这就是动态规划算法

# 14-1 什么是动态规划

从数学的视角来看，动态规划是一种运筹学方法，是在多轮决策过程中的最优方法
从分治法的视角来看，每个子问题必须相互独立，在多轮决策中，这个假设显然不成立，这也是动态规划方法产生的原因之一。

# 14-2 最短路径问题

图示

每个结点是一个位置，每条边是两个位置之间的距离，现在需要求解出一条由A到G的最短距离
不难发现，我们需要求解的路线是由A到G,这就意味着，路线为A-B-C-D-E-F，每一轮都有不同的决策，而每一次的决策又依赖上一轮的决策结果

例如，做D2 -> E 的决策时，D2 -> E2 的距离是1，最短。但这轮的决策，基于的假设是从D2出发，这就意味着，前面一轮的决策结果是D2。由此可见，相邻两轮的决策结果并不是相互独立的。

动态规划还有一个重要的概念叫作状态，在这个例子中，状态是一个变量，而且受决策动作的影响。例如，第一轮决策状态是S1,可选的值为A,第二轮决策的状态是S2,可选的值就是B1和B2，以此类推。

# 14-3 动态规划的基本方法

动态规划问题之所以难，是因为动态规划的解题方法并没有那么标准化，它需要你因题而异，仔细分析问题并寻找方案。虽然动态规划问题没有标准的解题方法，但它有一些宏观层面通用的方法轮：

  • 1.分阶段；将原问题划分成几个子问题，一个子问题就是多轮决策的一个阶段，它们可以是不满足独立性的
  • 2.找状态：选择合适的状态变量Sk,它需要具备描述多轮决策过程的演变，更像是决策可能的结果
  • 3.做决策；确定决策变量uk.每一轮的决策就是每一轮可能决策动作，例如D2的可能决策动作是D2 -> E2和D2 -> E3
  • 4.状态转移方程；这个步骤是动态规划最重要的核心，即是sk+1 = uk(sk)
  • 5.定目标；写出代表多轮决策目标的指标函数Vk,n
  • 6.寻找终止条件。

了解了方法轮、状态、多轮决策之后，我们再补充一些动态规划的基本概念

  • 策略，每轮的动作就是决策，多轮决策合在一起常常被称为策略
  • 策略集合，由于每轮的决策动作都是一个变量，这就导致合在一起的策略也是一个变量，我们通常会称所有可能的策略为策略集合。因此，动态规划的目标，也可以说是从策略集合中，找到最优的那个策略

一般而言，具有如下几个特征的问题，可以采用动态规划求解：

  • 1.最优子结构；它的含义是，原问题的最优解说包括的子问题的解也是最优的。例如，某个策略使A到G是最优的，假设它的途径了Fi,那么它从A到Fi也一定是最优的
  • 2.无后效性；某阶段的决策，无法影响先前的状态，可以理解为今天的动作改变不了历史
  • 3.有重叠子问题；子问题之间不独立。这个性质是动态规划区别于分治法的条件，如果原问题不满足这个特征，也是可以用动态规划求解的。

# 14-4 动态规划的案例

接下来，我们以最短路径问题看看动态规划的求解方法。这个问题，我们可以采用最暴力的方法，就是把所有的可能路径都遍历一遍，去看哪个路径最短。如果采用动态规划方法，那么我们按照方法论来执行。

# 14-4-1 动态规划的求解方法

  • 1.分阶段

很显然，从A到G,可以拆分为A -> B、B -> C、C -> D、D -> E、E -> F、F -> G，6 个阶段

  • 2.找状态

第一轮状态S1 = A，第二轮S2 = {B1,B2},第三轮S3 = {C1,C2，C3，C4}，第四轮 S4 = {D1,D2，D3}，第五轮S5 = {E1,E2，E3}，第六轮S6 = {F1,F2}，第七轮S7 = {G}。

  • 3.做决策

决策变量就是上面图中的每条边，我们以第四轮决策D->E为例来看，可以得到u4(D1),u4(D2),u4(D3),其中u4(D1)的可能结果是E1和E2

  • 4.写出状态转移方程

在这里，就是Sk+1 = uk(Sk)

  • 5.定目标

我们的目标是总距离最短。我们定义dk(sk,uk)是在Sk时，选择uk动作的距离，例如d5(E1,F1) = 3。那么此时n = 7,则有，

图示

  • 6.寻找最终条件
    • 很显然，这里的终止条件分别是，s1 = A 和 s7 = G
    • 接下来，我们把所有已知条件凝练为上面的符号之后，只需要借助最优子结构，就可以把问题解决可。最优子结构的含义是，原问题的最优解也是最优的
    • 套用这个例子的含义就是：如果A->...->F1->G，是全局A到G的最优路径，那么此处A->...->F1也就是A到F1的最优路径
    • 因此，此时的优化目标 min Vk,7(s1=A, s7=G)，等价于 min { Vk,6(s1=A, s6=F1)+4， Vk,6(s1=A, s6=F2)+3 }
    • 此时，优化目标的含义为，从 A 到 G 的最短路径，是 A 到 F1 到 G 的路径和 A 到 F2 到 G 的路径中更短的那个
    • 同样的，对于上面式子中，Vk,6(s1=A,s6=F1) 和 Vk,6(s1=A,s6=F2)，仍然可以递归地使用上面的分析方法

# 14-4-2 计算过程详解

我们把函数Vk,7(s1=A, s7=G) 精简为 V7(G)，含义为经过了 6 轮决策后，状态到达 G 后所使用的距离。我们把图片复制到这里一份，方便大家不用上下切换

我们的优化目标为 min Vk,7(s1=A, s7=G)，因此精简后原问题为，min V7(G)

# 14-4-3 第6轮决策

原问题等价于 min{V6(F1) + 4,V6(F2) +3}
利用最优子结构原理，需要求解min V6(F1) 和 min V6(F2)
路径候选为 A-> F1G和 A-> F2G

# 14-4-4 第5轮决策

...

因此，最终输出路径为 A -> B1 -> C2 -> D1 -> E2 -> F2 -> G，最短距离为 18。

# 14-5 总结

  • 动态规划并不简单，动态规划的适用范围也没那么广
  • 一般从事专门的运筹优化领域的工作，才会对其做深入学习和理解

← 第一题 →