当前位置:网站首页>四边形不等式优化

四边形不等式优化

2021-07-20 22:25:06 水沐银橙

先占个坑,准备学习一把运筹学,好像里面很多最优化的内容都是和算法设计相关联的问题

Va10003 - Cutting Sticks 

题目链接

简介: 
给出一个长度为L的木棍,以及n个切割点 
要求切割成n+1段,每切一次花费都是原始的木棍长度 
求最小花费

分析: 
实际上我们可以看做是n+1个物品 
这和能量项链是一样的: 
设计状态:f[i][j]表示切割编号为(i~j)的木棍的花费

f[i][j]=min{f[i][k]+f[k+1][j]+a[j]-a[i-1]}

a[i]是前i段木棍的前缀和,实际上就是分割点 
唯一需要注意就是现在有n+1个物品了

这样的复杂度是O(n^3)

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=55;
int pre[N],nxt[N];
int a[N],n,L;
int f[N][N];

int main()
{
    while (scanf("%d",&L)!=EOF&&L)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        a[n+1]=L;
        int i,j,k;

        memset(f,0x33,sizeof(f));
        for (i=1;i<=n+1;i++) f[i][i]=0;
        for (i=n;i>=1;i--)
            for (j=i+1;j<=n+1;j++)
                for (k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);

        printf("The minimum cutting is ");
        printf("%d.\n",f[1][n+1]);
    }
    return 0;
}

很简单的题对吧,我为什么要做这么简单的题呢? 
闲的 
实际上,我们可以把复杂度降为O(n^2) 
这就需要一个新知识了(上面只是引入)

四边形不等式

在动态规划中,经常遇到如下的状态转移方程:

d[i,j]=min{d[i,k]+d[k+1,j]}+w[i,j]

其中i < k < j,w[i,j]是区间(i,j)的额外代价,时间复杂度为O(n^3) 
这种情况下,我们通常可以考虑用四边形不等式优化

首先我们需要明确一些概念

对于一个权函数w(i,j),如果ta满足w(x,i+1)-w(x+1,i)随x单调不增,亦即w(x,i+1)+w(x+1,i)>=w(x,i)+w(x+1,i+1),则称这个权函数满足凸完全单调性

易证明,当k>0时,w(x,i+k)-w(x,i)随x单调不增,w(i+k,x)-w(i,x)随x单调不增,

则对任意a<=b<=c<=d,有w(a,c)+w(b,d)<=w(a,d)+w(b,c)。

称此式为四边形不等式

(可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和)

通过四边形不等式也可推出凸完全单调性,所以这两种说法不严格来说是等价的

在一类要求将一段序列划分成若干子段,从i到j的一段费用为w(i,j),要求出所有子段代价之和最小划分方案的动态规划中,通常可以见到这样的状态转移方程: 
d(i)=min{d(j)+w(j+1,i) | j < i}

设t(i,x)=d(i)+w(i+1,x) ,如果对于某个x,t(i,x)>=t(j,x) (i < j) 
则对于任何y>x都有t(i,y)>=t(j,y) 
此式说明,对于i < j,一旦某个时刻决策i没有决策j好,以后决策i也不会比决策j好。 
这说明,f(x)的决策时随x单调不降的,这就是决策单调性

或许大家已经发现了,决策单调性的dp一个经典优化就是:斜率优化

如果函数w满足:w(i,j)<=w(i’,j’) ([i,j]属于[i’,j’]) 
则说w关于区间包含关系单调 
(可以形象理解为如果小区间包含于大区间中,那么小区间的w值不超过大区间的w值)


有了上面的知识铺垫,我们现在提出一些重要的定理:

定理一:如果上述的w函数同时满足区间包含单调性和四边形不等式性质,那么函数d也满足四边形不等式性质。

我们再定义s(i,j)表示d(i,j)取得最优值时对应的下标(即i≤k≤j时,k处的w值最大,则s(i,j)=k)。此时有如下定理

定理二:假如d(i,j)满足四边形不等式,那么s(i,j)单调,s(i,j)≤s(i,j+1)≤s(i+1,j+1)

那么我们怎么判断w是否符合四边形不等式呢?

定理三: w为凸当且仅当w(i,j)+w(i+1,j+1)<=w(i,j+1)+w(i+1,j)

这个定理说明了验证w是否为凸的方法: 
固定j算出w(i,j+1)-w(i,j)关于i的表达式,若i单调递减,那么w为凸 
固定i算出w(i+1,j)-w(i,j)关于j的表达式,若j单调递减,那么w为凸

我们发现如果w函数满足区间包含单调性和四边形不等式性质,那么有s(i,j-1)≤s(i,j)≤s(i+1,j)

原来的状态转移方程可以改写为下式:

d(i,j)=min{d(i,k)+d(k+1,j)}+w(i,j) (s(i,j-1)≤k≤s(i+1,j))(min也可以改为max)

由于这个状态转移方程枚举的是区间长度L=j-i, 
而s(i,j-1)和s(i+1,j)的长度为L-1,是之间已经计算过的,可以直接调用。 
不仅如此,区间的长度最多有n个,对于固定的长度L,不同的状态也有n个,故时间复杂度为O(N^2),而原来的时间复杂度为O(N^3),实现了优化

tip

说句实话,在dp的代码实现上,我们只是加了一个数组s(区间最优解的位置) 
每次循环的时候,只循环s[i,j-1]~s[i+1,j]

下面给出一开始引入问题的优化代码

//这里写代码片
#include <cstdio>
#include <cstring>

const int N=55; 
int s[N][N],f[N][N],a[N],n,L;

int main()
{
    while (scanf("%d",&L)!=EOF&&L)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        a[n+1]=L;
        n++;

        int i,j,k;
        memset(f,0x33,sizeof(f));
        for (i=1;i<=n;i++) 
            f[i][i]=0,s[i][i+1]=i;
        for (i=1;i<=n;i++)
            f[i][i+1]=a[i+1]-a[i-1];

        for (i=n-2;i>=1;i--)
            for (j=i+1;j<=n;j++)
                for (k=s[i][j-1];k<=s[i+1][j];k++)
                if (f[i][j]>f[i][k]+f[k+1][j]+a[j]-a[i-1])
                {
                    f[i][j]=f[i][k]+f[k+1][j]+a[j]-a[i-1];
                    s[i][j]=k;
                }

        printf("The minimum cutting is ");
        printf("%d.\n",f[1][n]);
    }
    return 0;
}

版权声明
本文为[水沐银橙]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_12136715/2954492