川山甲 阅读(22) 评论(0)

 

 
 
概述
 
  动态规划我们在工作中会经常用到,有时候你会有这个意识,而且我相信你在项目中肯定使用过,只是你不了解这种方式是“动态规划”而已。它最大的特点就是“空间换时间“。
 
  如果你想大致了解下,你可以直接略过细节,直接看“使用动态规划方法求解最优钢条切割问题”这一部分。细节部分,只是使用案例和数学公式教大家怎么去思考问题。
 
 
举例
  
 
  A公司购买长钢条,将其切割为短钢条出售(切割工序本身没有成本支出),A公司想知道最佳的切割方案。
  假定:给定一段长度为n米的钢条。长度与价格的关系为:i米的钢铁价格为pi(i=1, 2, ...)元。
  求:切割钢条方案,使得销售收益γn最大。
  价格表的样例如下:
 
      

 

 
问题分析

   思路:通过假设法,寻找数据间的关系,进行建模。 

 

寻找数据间的关系1:

假设n=4,穷举所有的切割方式,找到最佳的切割方案。

不切(0刀):最高9元

1刀:最高10元

 

2刀:最高7元

 

3刀:最高4元

 

 
 从上面的图分析得出
  1) n米的钢条共有2n-1种切割方案。
  2)最优策略方案为:将钢条切割为两段长度均为2米的钢条,总价值为10。
 
用数学符号开始演练:(我们用加法符号表示切割,如  7 = 2 + 2 + 3,表示为长度7米的钢条切割段数为3段,每段分别为:2米、2米、3米。)
 
k为最优切割钢条方案中的段数,pi为i米钢条的价格,钢条切割的最大收益为γn
 
 
寻找数据间的关系2:
 
根据价格表样例,寻找到所有最优收益值及对应的最优切个方案:
 
 
总长n 段数k 最优收益值γ 切割方案
1 1 1 1
2 1 5 2
3 1 8 3
4 2 10 2+2
5 2 13 2+3
6 1 17 6
7 2或3 18 1+6或2+2+3
8 2 22 2+6
9 2 25 3+6
10 1 30 10

 

观察数据:(总长为5米的钢材最优收益是:2米刚才最优收益+3米钢材最优收益加和。)

 

 

 

从上述表,我们可以得出:对于γn(n>= 1),我们可以用更短的钢条的最优切割收益来描述它:

 

对于每个i=1、2、...、n-1,方案步骤如下:

  1)将钢条切割为长度为i和n-i的两段;

  2)求解这两段的最优切割收益γi和γn-i。——每种方案的最优收益为两段的最优收益之和。

由于无法预知那种方案会获得最优收益,我们必须考察所有可能的i,选取其中收益最大者。

 
  最优子结构:为了求解规模为n的原问题,我们先求解形式完全一样,规模更小的子问题。通过组合两个相关子问题的最优解,并在所有可能的两段切割方案中选取组合收益最大者,构成原问题的最优解。
 
  我们称钢条切割问题满足最优子结构性质:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。
 
 
求解简化版本

 

原有方式:

简化版本:钢条从左边切割下长度为i的一段,对左边的一段i不再进行切割,只对右边剩下的长度为n-i的一段继续进行切割(采用了一种自顶向下的递归方式)

 

递归方法CUT-ROD如下:
 

 

分析CUT-ROD:实际运行中,你会发现CUT-ROD的效率很差。因为CUT-ROD反复地用相同的参数值对自身进行递归调用,即它反复求解相同的子问题,如下图所示:

 

CUT-ROD的运行时间为n的指数,时间复杂度如下:

 


 
使用动态规划方法求解最优钢条切割问题

 

  动态规划方法的核心思想是:对每个子问题只求解一次,并将结果保存下来。如果随后再次需要此子问题的解,只需查找保存的结果,而不必重新计算。因此,动态规划方法是付出额外的内存空间来节省计算时间,是典型的时空权衡的例子。

 

  方法1:带备忘的自顶向下法。此方法扔按自然的递归形式编写,但过程会保存每个子问题的解(通常保存在数组或散列中)。当需要一个子问题解时,过程首先检查是否已保存过此解,无则计算,有则返回。

 

  方法2:自底向上法。将子问题按规模排序,按由小至大顺序求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已保存。每个子问题只需求解一次,当我们求解它时,它的所有前提子问题都已经求解完成。

 

 

 


 
子问题图

 

   当思考一个动态规划问题时,我们应该弄清所涉及的子问题及子问题之间的依赖关系。

  

  上面举得n=4时,钢条切割问题的子问题图如下:这是递归调用树的简化版,树中标号相同的节点收缩为图中的单一顶点,所有边均从父节点指向子节点。

  

上面的图中,我们可以把每个顶点向量化,标记为(x,y)。这个表示求解x的问题时候,我们需要子问题y的解。

 

 
推荐