Dynamic Programming-钢条切割问题

Dynamic Programming-钢条切割问题

2019, Mar 27    

前言

动态规划是算法中的一大类,是一个求解最优解的值的问题

本文内容主要来自于 《算法导论第三版第四部分第15章 动态规划》

四个基本步骤

我们通常需要四个步骤来设计一个动态规划算法:

  • 1.刻画一个最优解的结构特征
  • 2.递归地定义最优解的值。
  • 3.计算最优解的值,通常采用自定向上的算法
  • 4.利用计算出的信息构造一个最优解

钢条切割问题

问题描述

给定一段长度为n的英寸的钢条,和一个价格表pi(i=1,2,…,n),求切割钢条的切割方案,是的销售收益rn最大。(如果长度为n英寸的钢条价格pn足够大,最优解可能就是完全不需要切割)

问题处理

长度为n英寸的钢条共有2^(n-1)种不同的切割方案,因为在距离钢条左端i(i=1,2,…,n-1)英寸的地方,我们总是可以选择切割或者不切割。 这时候rn=max(pn,r1+r[n-1],r2+r[n-2],r[n-1]+r1),相当于,我们将问题分割了,首先将钢条切割了,切割成了长度为i和n-i的两端,然后求解这两端的ri和r[n-i]

这样,我们就能通过组合两个相关子问题的最优解,并在所有可能的两端切割方案中选取组合收益的最大者,构成原问题的最优解。 这样,我们称钢条切割问题满足最优子结构(optimal substructure)的性质:问题的最优解由相关问题的最优解组合而成,而这些子问题可以独立求解。

除此之外,我们可以将钢条从左边切割下长度为i的一段,然后只对右边剩下的长度为n-i的一段继续进行切割(递归求解),对左边的一段则不再进行切割,

而不做任何切割的方案,可以描述为:第一段的长度为n,收益为pn,剩余部分的长度为0,对应的收益为r0=0。

伪代码实现(自顶向下的方法)

	CUT-ROD(p,n)
	1	if n == 0
	2		return 0;
	3 	q = min_num
	4 	for i = 1 to n
	5 		q=max(q,p[i]+CUT-ROD(p,n-i))
	6 return q

CUT-ROD优化

上方的方法,在n变大的时候,程序运行时间会变得特别特别慢,原因是,它会反复的使用相同的参数值,对自身进行递归调用,等价于他在反复求解相同的子问题。如果将上面函数的递归调用树画出来,将会有2^(n-1)个叶节点。全部展开,必将成为一个指数级增长的趋势。上面的朴素递归算法,效率低,就是这个问题,反复求解了相同的子问题。

因此,动态规划要求仔细安排求解的顺序,对每个子问题,之求解一次,并将结果保存下来。因此,对于每个子问题的解,咱们只求一次,并且将结果保存下来,之后再遇到相同的子问题,就可以直接求出解,因此,动态规划方法,就是付出了额外的内存空间,来节省计算时间,这就是典型的时空权衡的例子。下面是两个优化算法的伪代码

带备忘的自顶向下法(top-down with memoization)

过程会保存每个子问题的解,通常保存在一个数组或者散列表当中。当需要一个子问题的解的时候,首先检查一下是否已经保存过此解。

	MEMOIZED-CUT-ROD(p,n)
	1 let r[0..n]be a new array
	2 for i = 0 to n
	3 	r[i] = min_num
	4 return MEMOIZED-CUT-ROD-AUX(p,n,r);

	MEMOIZED-CUT-ROD-AUX(p,n,r)
	1 if r[n]>=0
	2 	return r[n]
	3 if n == 0
	4 	q = 0
	5 else q = min_num
	6		for i = 1 to n 
	7 			q=max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
	8 r[n]=q
	9 return q
自底向上的方法
	BOTTOM-UP-CUT-ROD(p,n)
	1 let r[0..n] be a new array
	2 r[0] = 0
	3 for j = 1 to n 
	4 		q=min_num
	5		for i = 1 to j
	6  			q = max(q,p[i]+r[j-i])
	7 		r[j]=q
	8 return r[n]

结语

算法之大,博大精深,吾之所见,沧海一粟
路漫漫其修远兮,吾将上下而求索