斜率优化的具体操作和证明[信息学资料]

这里是斜率优化的具体操作和证明,恩,顺便附上一个例子,APIO2010第一题commando/特别行动队的解题思路。

 

前言:
对于一个动态规划模型f[i]=max{f[j]+g(j,i)}(这里只讨论max,min的可以想成-max{什么什么})。
我们称对于阶段i决策x的价值为value(x)=f[x]+g(x,i)。
那么如果value(j)-value(k)>0,我们就说j比k优。
如果j<k时,value(j)-value(k)>0可以化成K(j,k)>H(i)的形式(这时K(j,k)>H(i)等价于j比k优),且H(i)是单调递增的,我们就可以用斜率优化了。
我们需要维护一个单调队列使得K(队中相邻的两个决策)递增。

具体操作:
Line
0   |Type f[XX..YY];
1   |Deque q;
2   |f[边界]:=边界值;
3   |q.push_back(边界);
4   |
5   |for i:=XX to YY do
6   |begin
7   |    while q中至少有两个决策 and K(队首,队首的后一个)<=H(i) do q.pop_front();
8   |    f[i]=value(队首);
9   |    while q中至少有两个决策 and K(队尾的前一个,队尾)>=K(队尾,i) do q.pop_back();
10  |    q.push_back(i);
11  |end;

 

证明(我用《算法导论》中的循环不变式来证明):
初始化:在0到3行的代码执行后,f[边界]=边界值,队中没有相邻的两个决策,所以显然是正确的。
保持:
/*开始*/
在5到11行代码中,涉及到三个操作,除去队首无用决策(第7行),计算f[i](第8行),除去队尾无用决策并加入决策i(第9到10行),我们分别证明。
1.除去队首无用决策
由于K(队中相邻的两个决策)在这次操作前是递增的,所以执行第7行代码后,K(队中相邻的两个决策)>H(i),即队中前一个元素比后一个元素优,或者q中只有一个决策(而它显然最优),又因为H(i)递增,所以被pop掉的决策总是前一个没有后一个优,并且都没有新的队首优,所以pop他们是正确的。
综上所述,这一步是正确的。
2.计算f[i]
由于除去队首无用决策后,队中前一个元素比后一个元素优,所以最优的决策显然在队首,所以f[i]:=value(队首)这个操作显然正确。
3.除去队尾无用决策并加入决策i
如果q中只有一个决策,那么我们将i直接加入队尾,显然K(队中相邻的两个决策)是递增的。
如果q中有多于一个决策,那么如果K(队尾的前一个,队尾)>=K(队尾,i),那么在某个阶段i’:
1)如果K(队尾的前一个,队尾)>=H(i’)>=K(队尾,i),那么”队尾”没有”队尾的前一个”优,也没有”i”优,所以”队尾”不可能成为最优的决策,我们pop它,显然正确;
2)如果K(队尾的前一个,队尾)>=K(队尾,i)>=H(i’),那么”队尾”没有”队尾的前一个”优,只是比”i”优,所以”队尾”不可能成为最优的决策,我们pop它,显然正确;
3)如果H(i’)>=K(队尾的前一个,队尾)>=K(队尾,i),那么”队尾”没有”i”优,只是比”队尾的前一个”优,所以”队尾”不可能成为最优的决策,我们pop它,显然正确。
综上所述,如果K(队尾的前一个,队尾)>=K(队尾,i),pop队尾是一个正确的举动。
如果K(队尾的前一个,队尾)<K(队尾,i),那么我们停止while,然后q.push_back(i),这时保持了K(队中相邻的两个决策)的单调性,是我们想要的,所以正确。
/*结束*/
终止:当算法结束后,f[YY]已经求出,即我们需要的最优值已经求出,这意味这算法是正确的。

例子(APIO2010第一题commando/特别行动队):
恩,输入n,a,b,c,x[1..n]。
预处理sum[0]:=0,sum[i]:=sum[i-1]+x[i]。
动规方程是f[i]=max{f[j]+g(j,i)},这里g(j,i)=a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c。
然后value(x)=f[x]+g(x,i)=f[x]+a*(sum[i]-sum[x])*(sum[i]-sum[x])+b*(sum[i]-sum[x])+c。
如果j<k时,value(j)-value(k)>0可以化成K(j,k)>H(i)的形式(这时K(j,k)>H(i)等价于j比k优),且H(i)是单调递增的,我们就可以用斜率优化了。
当j<k时,对value(j)-value(k)>0变形,得:
2*a*sum[i]*(sum[k]-sum[j])>f[k]-f[j]+b*(sum[j]-sim[k])+a*(sum[k]*sum[k]-sum[j]*sum[j])
sum[i]<(f[k]-f[j]+b*(sum[j]-sim[k])+a*(sum[k]*sum[k]-sum[j]*sum[j]))  /  (2*a*(sum[k]-sum[j])) /*因为a<0,sum[k]-sum[j]>0,所以反号*/
这时,我们看到了曙光!!
K(j,k)=(f[k]-f[j]+b*(sum[j]-sim[k])+a*(sum[k]*sum[k]-sum[j]*sum[j]))  /  (2*a*(sum[k]-sum[j]))
H(i)=sum[i]
满足K(j,k)>H(i),H(i)递增,所以我们可以斜率优化了,恩,就是这样,代码见这里

留下评论

电子邮件地址不会被公开。