动态规划的斜率优化

《动态规划的斜率优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、獻形锫合的达用我锬幼态规刻十的斜率优化【摘要】随着动态规划在01中的广泛运用，动态规划问题已经不再停滞于能够写出方程就能得到完美解答。如今考察我们的对于动态规划的运用往往是考察动态规划的优化，也就是降维。我们己经知道维护方程中的决策可以选择用数据结构进行优化，比如：Splay、线段树，等等。这样的优化仅能将方程的时间复杂度下降一个LogN的级别。如果N的范围相当大，即使下降一个LogN的级别也依然超时呢？我们引进一种更强的优化一一斜率优化。【关键字】动态规划决策变量单调性斜率优化【正文】斜率优化，亦就是说把决策与决

2、策之间表示成一个类似斜率的式子，进一步分析其中的单调性，并用队列维护其有用决策。因此斜率优化乂称为队列优化。这样笼统的介绍过于抽象，下面我们用几道例题，来体会斜率优化的运用。【例1】锯木场选址(TwoCE0I2004)［题目描述］从山顶上到山底下沿着一条直线种植了77棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材，树被砍倒后要运送到锯木厂。木材只能按照一个方向运输：朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂，使得传输的费用总和最小。假定运输每公斤木材每米

3、需要一分钱。任务你的任务是写一个程序：从标准输入读入树的个数和他们的重量与位置计算最小运输费用将计算结果输出到标准输出输入输入的第一行为一个正整数n—一树的个数（2^77^20000）。树从山顶到山脚按照1,2……标号。接下来/7行，每行有两个正整数（用空格分开）。第/+1行含有：%一一第/棵树的重量（公斤为单位）和d,一一第7棵树和第/+1棵树之间的距离，1彡％<10000，0彡4<10000。最后一个数忒，表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000000000分。输出输

4、出只有一行一个数：最小的运输费用。样例输入912213311321621样例输出26算法分析]初步分析：我们明确题目的核心：最优值问题。再加上树木只能往K传送,满足无后效性。那么此题用动态规划解决是十分明显。进一步分析：题目中说明第n棵树下面还有一个锯木厂，不妨把它当作第H4-1个位置来考虑。为了分析的方便，我们增设儿组变量：Sw[i]表示1〜i棵树的总重量,表达式为=,吋间复杂度为0⑻。7=1Sd[i]表示1〜i棵树的距离，表达式为&/[/]=5>/[./]，时间复杂度为00）。7=1Cost[i]表示把第一鋸木

5、场设在第i棵树的位置上，1〜i棵树到i所需的费用。表达式为（?如[/]=<7仍巾-1]+5冲—1]*卯-1]，时间复杂度为0⑻。All[i,j]表示把第i〜j棵木头都运送到第j棵树的位置上所需要的费用。表达式为A/収刀=[刀-C如[Z-l]-Svv[Z-对于求每一项所需的吋间复杂度为0（1）。接下来，设状态列方程。设F[i]表示第二个鋸木厂设在i处所需的总费用。那么状态转移方程为：F[i]=Min{Cost[j]+AU[j+1,/]+AU[i+1,n+1]}1<=j

6、题S的要求ns20000。因此我们必须对其进行优化。优化：提出这样一个设想：假设当前第二鋸木厂设置在i，而它的最优决策为k,也就是说求出的F[i]值是当j取k时得到的，而对于F[i+1]的最优决策kl必然大于等于k。下面我们对其进行证明。证明：设jl，j2分别为F[i]的两个决策，且G[i，jl],G[i，j2]分别为jl，j2得出的F[i]值，即:G[iJ]=Cost[j]+A//[yl+l,Z]+All[i+1，n+1]G[z,j2]=Cost[j2]^A//[/2+l,zl+All[i+1，n+1]那么，

7、G[iJl]-G[iJ2}=Svvt72jx(Sd[i]~Sd[j2])-Svvlyljx(Sd[i]~Sd[jl])若GU，yi]—G[z;j2]<0，贝ljS^j2]x(Sd[i]-Sd[j2})-S^ji]x(Sd[i]-Sd[jl])<0整理妬设Slope[jl，j2]=不等式左边因为r/[Z]20，所以对于所有的々S/都满足Slope[ji，j2]>Sd[i]>Sd[k]证毕。由此我们可以得知，决策j是满足单调性的。如何来维护这种单调性呢？不难发现Slope[jl,j2](jl

8、一个斜率的式子，其中ShU]xS6/[>]为Y坐标，Sw[j]为X坐标。当它能满足的不等式①，亦就是说明jl优于j2,反之则是j2优于jl。又由于Sd[i]是递增的，所以当前最优的决策jl始终会被次优的决策j2所替代，至此决策jl就再无用武之地可以完全忽略从决策集合屮删除。另一方面，当前求出F[i]之后，i也能够成为之后的决策，所以应该将其并入集合中。维护决