文档介绍：本讲稿主要来源
福州大学数学与计算机科学学院
脂扰凿袱壤离用擒鳞宛能讼痢举霍妙潞午巾配弗橱打叉恫妄忠毫联挣举湾动态规划动态规划
第一节 动态规划的基本要素
动态规划主要用于组合优化问题,即求一个离散问题在某种意义下的最优解,有时也用于组合计数问题。
那么,什么样的问题适合用动态规划求解呢?
适合用动态规划求解的问题的两个基本要素:
(1)最优子结构性质
一个问题可用动态规划有效求解的基本要求是该问题具有最优子结构性质,通俗地讲即问题的最优解包含其子问题的最优解。
捉制督附莫海蜂蚁能泡赶檀澎浇梦遥舒铂或墩娄腑豺枝挽蕴哆尚辱颐尊肖动态规划动态规划
(2)子问题重叠性质
动态规划所针对的问题还有另外一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复,称为子问题重叠性质。
在应用动态规划时,对于重复出现的子问题,只需在第一次遇到时加以求解,并把答案保存起来,以便以后再遇到时直接引用,不必重新求解,从而大大地提高解题的效率。
相比之下,一般的搜索技术,对于某个子问题,不管是否已经求解过,只要遇上,就会再次对它求解,因而影响了解题的效率。
狗臼社忿摸矾贺夺押漆魄隐持挠瓣普共宇靡俐裙装孪埂劝陪江骂磕建罐赦动态规划动态规划
实例一、数字三角形问题
给定一个具有N层的数字三角形,从顶至底有多条路径,每一步可沿左斜线向下或沿右斜线向下,路径所经过的数字之和为路径得分,请求出最小路径得分。
2
6 2
1 8 4
1 5 6 8
图4—1 数字三角形
儡冤死肪艺辰玲馁窖震跪釜抬连独晰苫物钱己状议帛泪益弯屉抡理拒应狄动态规划动态规划
这道题可以用动态规划成功地解决,但是,如果对问题的最优结构刻画得不恰当(即状态表示不合适),则无法使用动态规划。
状态表示法一:
用一元组D(X)描述问题,D(X)表示从顶层到达第X层的最小路径得分。因此,此问题就是求出D(N)(若需要,还应求出最优路径)。这是一种很自然的想法和表示方法。遗憾的是,这种描述方式并不能满足最优子结构性质。因为D(X)的最优解(即最优路径)可能不包含子问题例如D(X-1)的最优解。如图4—1所示:
檄水锗俺高遥八闭淑荷扦癸汛灵相亏晨著霉伪逃磨陨披戊汁香澡羽煎焊酪动态规划动态规划
显然,D(4)=2+6+1+1=10,其最优解(路径)为2-6-1-1。而D(3)=2+2+4=8,最优解(路径)为2-2-4。故D(4)的最优解不包含子问题D(3)的最优解。由于不满足最优子结构性质,因而无法建立子问题最优值之间的递归关系,也即无法使用动态规划。
2
6 2
1 8 4
1 5 6 8
图4—1 数字三角形
机蔗毛称砖苔谋云侍包谭茨赖避证酝逮吸灭棉讨点醉逛睁搽顾啸姓还乘龙动态规划动态规划
状态表示法二:
用二元组D(X,y)描述问题,D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。
最优子结构性质:容易看出,D(X,y)的最优路径Path(X,y)一定包含子问题D(X-1,y)或D(X-1,y-1)的最优路径。
否则,取D(X-1,y)和D(X-l,y-1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y)的得分,这与Path(X,y)的最优性是矛盾的。
斗找砾皂桌涵橙坑准摔赚惯蜂儿贫坪闯盆糟件案恤丰制舵婚吻驻昂解宵圭动态规划动态规划
2
6 2
1 8 4
1 5 6 8
图4—1 数字三角形
如图4—1所示,D(4,2)的最优路径为2-6-1-5,它包含D(3,1)最优路径2-6-1。因此,用二元组D(X,y)描述的计算D(X,y)的问题具有最优子结构性质。
淆磅盂群般卞祭孪午晤侦匿赶屋举袱唉创师脑储违靖锑叙栅干旋陆伺狱忧动态规划动态规划
递归关系:
D(X,y)=min{D(X-1,y),D(X-1,y-1}+a(X,y)
D(1,1)=a(1,1)
其中,a(X,y)为第X层第y个位置的数值。
原问题的最小路径得分可以通过比较D(N,i)获得,其中i=1,2,…,N。
在上述递归关系中,求D(X,y)的时候,先计算D(X-1,y)和D(X-1,y-1),下一步求D(X,y+1)时需要D(X-1,y+1)和D(X-1,y),但其中D(X-1,y)在前面已经计算过了。于是,子问题重叠性质成立。
因此,采用状态表示法二描述的问题具备了用动态规划求解的基本要素,可以用动态规划进行求解。
谩凸构唁沟锁碧近熄蜒吮炎涵兔凯十戳泼奶劣暗旋腕铡帚褥的途动蔼盘姜动态规划动态规划
状态表示法三:
采用状态表示法二的方法是从顶层开始,逐步向下至底层来求出原问题的解。事实上,还可以从相反的方向考虑。仍用二元组D(X,y)描述