南开大学ACM暑期集训之动态规划.ppt

南开大学ACM暑期集训之

动态规划;本讲稿主要来源;第一节

动态规划的根本要素;;实例一、数字三角形问题;2．解题思路

这道题可以用动态规划成功地解决，但是，如果对问题的最优结构刻画得不恰当(即状态表示不适宜)，那么无法使用动态规划。

状态表示法一：

用一元组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)的最优解。由于不满足最优子结构性质，因而无法建立子问题最优值之间的递归关系，也即无法使用动态规划。;???态表示法二：

用二元组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

62

184

1568

图4—1数字三角形;递归关系：

D(X,y)＝min{D(X-1,y)，D(X-1,y-1}+a(X,y)

D(1,1)＝a(1,1);状态表示法三：

采用状态表示法二的方法是从顶层开始，逐步向下至底层来求出原问题的解。事实上，还可以从相反的方向考虑。仍用二元组D(X,y)描述问题，D(X,y)表示从第X层第y个位置到达底层的最小路径得分。原问题的最小路径得分即为D(1,1)。

最优子结构性质：显然，D(X,y)的最优路径Path(X,y)一定包含子问题D(X+1,y)或D(X+1,y+1)的最优路径，否那么，取D(X+1,y)和D(X+1,y+1)的最优路径中得分小的那条路径加上第X层第y个位置构成的路径得分必然小于Path(X,y)的得分，这与Path(X,y)的最优性矛盾。;2

62

184

1568

图4—1数字三角形;递归关系：

D(X,y)＝min{D(X+1,y),D(X+1,y+1)}+a(X,y)

D(N,k)＝a(N,k)，k＝1，…，N;算法设计

采用状态表示法三的算法的主要过程如下：

for(i=n-2;i=0;--i)

{

for(j=0;j=i;++j)

{

tmp=sou[i+1][j];

if(sou[i+1][j+1]tmp)

{

tmp=sou[i+1][j+1];

}

sou[i][j]+=tmp;

}

}

printf(%d\n,sou[0][0]);;第二节

动态规划算法步骤;步骤(1)～(3)是动态规划的根本步骤。在只需要求出最优值的情形，步骤(4)可以省略。

假设需要求出问题的一个最优解，那么必须执行步骤(4)。此时，在步骤(3)中计算

最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。

本卷须知:

在进一步探讨动态规划设计方法及应用之前，有两点需要注意：;(1)问题的状态表示对能否用动态规划进行求解是至关重要的，不恰当的状态表示将使问题的描述不具有最优子结构性质，从而无法建立最优值的递归关系，动态规划的应用也就无从谈起。因此，上面步骤(1)，即状态表示和最优子结构性质的分析，是最关键的一步。

(2)在算法的程序设计中，应充分利用子问题重叠性质来提高解题效率。更具体地说，应采用递推(迭代)的方法来编程计算由递归式定义的最优值，而不采用直接递归的方法。;实例二、花束摆放问题;;;最优子结构性质：对满足F≤k≤V的k，设T(F,k)是到达最优值S(F,k)的一种最正确摆放方式，其中，第F-1种花束摆在第j个花瓶中(jk)，那么T(F,k)中前F-1种花束的摆放方式获得的美学值为S(F-1,j)。故对每个满足F≤k≤V的k，计算S(F,k)的问题具有最优子结构性质。