动态规划(Dynamic Programming)之切割钢条问题(rod cutting problem)

  • Post author:
  • Post category:其他




问题描述

Seriling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。

假定我们知道Serling公司出售一段长为



i

i






i





英寸的钢条的价格为



p

i

p_i







p










i





















(



i

=

1

,

2

,

.

.

.

,

i=1, 2, … ,






i




=








1


,




2


,




.


.


.


,





单位为美元)。钢条的长度均为整英寸。下表给出一个价格表样例。

长度



i

i






i




1 2 3 4 5 6 7 8 9 10
价格



p

i

p_i







p










i




















1 5 8 9 10 17 17 20 24 30

正式的问题描述为:给定一段长度为n英寸的钢条和一个价格表



p

i

(

i

=

1

,

2

,

.

.

.

,

n

)

p_i(i=1, 2, …, n)







p










i


















(


i




=








1


,




2


,




.


.


.


,




n


)





,求切割方案,使得销售的收益



r

n

r_n







r










n





















最大。注意,如果长度为n英寸的钢条价格



p

n

p_n







p










n





















足够大,最优解可能就是完全不需要切割。

考虑n=3的情况,我们用一组数字来表示一种可能的切割情况,共有(3),(1, 2),(2, 1),(1, 1, 1)四种可能。卖出获得的收益分别是8,6,6,3美元。

对一个长度为n的钢条,在距离左端



i

i






i





英寸处我们可以选择切或不切,所以总共有



2

n

1

2^{n-1}







2











n





1













种切割方案。假设最优的方案是切为k段(



1

k

n

1 \leq k \leq n






1













k













n





),每段长为



i

k

i_k







i










k





















,那么最优切割方案可表示为





n

=

i

1

+

i

2

+

.

.

.

+

i

k

n=i_1 + i_2 + … + i_k






n




=









i










1




















+









i










2




















+








.


.


.




+









i










k





















该方案下的最大收益为





r

n

=

p

i

1

+

p

i

2

+

.

.

.

+

p

i

k

r_n = p_{i_1} + p_{i_2} + … + p_{i_k}







r










n




















=









p












i










1





































+









p












i










2





































+








.


.


.




+









p












i










k






































对于上述价格表样例,我们先给出长度10英寸以内所有钢条的最优切割方案及其对应收益:




r

1

=

1

,

1

=

1

r_1=1, 1=1







r










1




















=








1


,




1




=








1





(无切割)




r

2

=

5

,

2

=

2

r_2=5, 2=2







r










2




















=








5


,




2




=








2





(无切割)




r

3

=

8

,

3

=

3

r_3=8, 3=3







r










3




















=








8


,




3




=








3





(无切割)




r

4

=

10

,

4

=

2

+

2

r_4=10, 4=2+2







r










4




















=








1


0


,




4




=








2




+








2









r

5

=

13

,

5

=

2

+

3

r_5=13, 5=2+3







r










5




















=








1


3


,




5




=








2




+








3









r

6

=

17

,

6

=

6

r_6=17, 6=6







r










6




















=








1


7


,




6




=








6





(无切割)




r

7

=

18

,

7

=

1

+

6

7

=

2

+

2

+

3

r_7=18, 7=1+6或7=2+2+3







r










7




















=








1


8


,




7




=








1




+








6





7




=








2




+








2




+








3









r

8

=

22

,

8

=

2

+

6

r_8=22, 8=2+6







r










8




















=








2


2


,




8




=








2




+








6









r

9

=

25

,

9

=

3

+

6

r_9=25, 9=3+6







r










9




















=








2


5


,




9




=








3




+








6









r

1

0

=

30

,

10

=

10

r_10=30, 10=10







r










1


















0




=








3


0


,




1


0




=








1


0





(无切割)



问题求解

下面来求解切割钢条问题。首先我们注意到,对于



r

n

(

n

1

)

r_n(n\geq1)







r










n


















(


n













1


)





可以用更短的钢条的最优收益来描述它:





r

n

=

m

a

x

(

p

n

,

r

1

+

r

n

1

,

r

2

+

r

n

2

,

.

.

.

,

r

n

1

+

r

1

)

r_n=max(p_n, r_1+r_{n-1}, r_2+r_{n-2}, … , r_{n-1}+r_1)







r










n




















=








m


a


x


(



p










n


















,





r










1




















+









r











n





1



















,





r










2




















+









r











n





2



















,




.


.


.


,





r











n





1





















+









r










1


















)





即在只切一次后钢条被分成的两段的情况下,这两段钢条的最优收益之和的最大值,即为原钢条的最优收益。其中完全不切割的情况表示为



p

n

p_n







p










n





















更加一般概括的说,为了求解规模为n的原问题,我们先求解形式完全一样,但规模更小的自问题。这些子问题的最优解组合起来,就构成了原问题的解。

这种性质称为

最优子结构性质(optimal substructure)

:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。



递归求解

除了上述方法外,还有一种更为简洁的递归求解法。将钢条从左端起切下长为



i

i






i





的一段,这一段将不再被切割,只对右边剩下的长度为



n

i

n-i






n













i





的一段继续进行切割。这样一来,长度为



n

n






n





的钢条的收益就被分解为长度为



i

i






i





的钢条按照价格表上的收益与长度为



n

i

n-i






n













i





的钢条继续切割得到的最优收益之和。而原钢条的最优收益就等于所有可能的



i

i






i





之中收益和最大的那个值。即





r

n

=

max

1

i

n

(

p

i

+

r

n

i

)

r_n=\mathop{\max}_{1\leq i \leq n}(p_i + r_{n-i})







r










n




















=










max












1





i





n



















(



p










i




















+









r











n





i



















)





该方法的python实现如下:

import sys
sys.setrecursionlimit(100) #增大递归次数限制
p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30] #价格表
def cut_rod(p, n): 
    if n == 0: #递归终止条件
        return 0  
    q = -1
    for i in range(n):
        q = max(q, p[i] + cut_rod(p, n-i-1)) #递归比对所有i的收益,求最大值
    return q

该方法看似简单有效,然而在递归过程中执行了很多重复运算。对于一个子问题,在求解所有规模比它大的问题的时候都会重新被计算一遍,这使其效率大大被降低。具体过程中,对



i

=

1

,

2

,

.

.

.

,

n

i=1, 2, …, n






i




=








1


,




2


,




.


.


.


,




n





调用



c

u

t

_

r

o

d

(

p

,

n

i

)

cut\_rod(p, n-i)






c


u


t


_


r


o


d


(


p


,




n













i


)





等价于对



j

=

0

,

1

,

.

.

.

,

n

1

j=0,1, …, n-1






j




=








0


,




1


,




.


.


.


,




n













1





调用



c

u

t

_

r

o

d

(

p

,

j

)

cut\_rod(p, j)






c


u


t


_


r


o


d


(


p


,




j


)





。可见在递归过程中重复调用的次数会指数增长。令



T

(

n

)

T(n)






T


(


n


)





表示第二个参数值为



n

n






n









c

u

t

_

r

o

d

cut\_rod






c


u


t


_


r


o


d





的调用次数。因为



c

u

t

_

r

o

d

(

p

,

n

)

cut\_rod(p, n)






c


u


t


_


r


o


d


(


p


,




n


)





本身也算作一次调用,故



T

(

0

)

=

1

T(0)=1






T


(


0


)




=








1





,且





T

(

n

)

=

1

+

k

=

1

n

1

T

(

k

)

T(n)=1+\sum_{k=1}^{n-1}T(k)






T


(


n


)




=








1




+

















k


=


1



















n





1




















T


(


k


)





第一项的1表示调用



c

u

t

_

r

o

d

(

p

,

n

)

cut\_rod(p, n)






c


u


t


_


r


o


d


(


p


,




n


)





函数本身,



T

(

k

)

T(k)






T


(


k


)





为函数内部调用



c

u

t

_

r

o

d

(

p

,

n

i

)

cut\_rod(p, n-i)






c


u


t


_


r


o


d


(


p


,




n













i


)





时产生的所有调用次数(包括递归调用)。证明略,结论为



T

(

n

)

=

2

n

T(n)=2^n






T


(


n


)




=









2










n












,即对于长为



n

n






n





的钢条,调用次数为



2

n

2^n







2










n














使用动态规划求解

前述问题暴露的缺陷是递归过程中反复求解相同的子问题。为了避免这样的浪费,动态规划方法合理安排求解的顺序,对每个子问题只求解一次,并将结果保存下来。如果之后需要再次求解该问题,则直接使用已保存的结果。因此,动态规划是典型的用空间换时间的方法。以切割钢条问题为例,动态规划可以有两种等价的实现方法。第一种称为

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

,第二种称为

自底向上法(bottom-up method)



带备忘的自顶向下法

此方法仍然按照正常的递归形式实现过程,但在过程中每求解一个新的子问题就会将其结果保存下来。当重复需要某个子问题的解时,则直接读取保存的值即可。

p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
memo = [ -1 for _ in range(n) ]
def cut_rod(p, n): 
    if n == 0:
        return 0
    if memo[n-1] > 0: #memo的下标从0开始,而n是自然下标需要变换
        return memo[n-1]   
    q = -1
    for i in range(n):
        q = max(q, p[i] + cut_rod(p, n-i-1))
    memo[n-1] = q
    return q



自底向上法

此方法需要恰当定义子问题的规模,使得任何子问题的求解都只依赖于”更小的“子问题的解,然后按照从小到达的顺序求解问题。这样一来,在求解某个子问题时,它所依赖的那些更小的问题都已经求解完毕,结果已经保存。

p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
r = [ 0 for _ in range(n+1) ] #此处使用自然下标,0即为长度为0的钢条
def bottom_up_cut_rod(p, n):
    for j in range(1, n+1): #规模从小到大求解所有子问题
        #此处的求解方法与自顶向下相同
        q = -1
        for i in range(1, j+1):
            q = max(q, p[i-1] + r[j-i])
        r[j] = q
    return r[n]



版权声明:本文为csdnLeoMa原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。