凸完全单调性的一个加强与应用.ppt

凸完全单调性的一个加强与应用,西安市第一中学杨哲,四边形不等式、凸完全单调性与决策单调性以及凸完全单调性的一个加强,第一部分,四边形不等式、凸完全单调性与决策单调性,对于一个权函数w(i,j)，如果它满足w(x,i+1)-w(x,i)随x单调不增，亦即w(x,i+1)+w(x+1,i)w(x,i)+w(x+1,i+1)，则称这个权函数满足凸完全单调性。容易证明，当k0时，w(x,i+k)-w(x,i)随x单调不减，w(i+k,x)-w(i,x)随x单调不减。所以对任意的abcd，有w(a,d)+w(b,c)w(a,c)+w(b,d)。称此不等式为四边形不等式。由四边形不等式也可推出凸完全单调性，所以“w满足四边形不等式”与“w具有凸完全单调性”这两种说法是等价的。,四边形不等式、凸完全单调性与决策单调性,在一类要求将一段序列划分为若干子段，从i到j的一段的费用为w(i,j)，要求出所有子段代价之和最小的划分方案的动态规划问题中，通常可以见到这样的状态转移方程：设t(i,x)=fi+w(i,x)，如果对于某个x，t(i,x)t(j,x)(ix，有t(i,y)t(j,y)。此式说明，对于ij，一旦某个时刻决策i没有决策j好，以后决策i也不会比决策j好。这说明，fx的决策是随x单调不减的，这就是决策的单调性。,四边形不等式、凸完全单调性与决策单调性,解决这类问题时，通常用Bi记录使决策i比所有之前的决策j(ji)要好的最小的x，即Bi=minx:t(i,x)t(j,x)对所有ji均成立。根据决策的单调性，决策i比所有之前的决策j(ji)要好等价于Bix。如果对某个(i,j)(ij)，BiBj，则说明决策i是无用的。于是任何时刻，假设所有有用决策为i1,i2,ik，满足i1i2ik，则Bi1Bi2Bik。,四边形不等式、凸完全单调性与决策单调性,求解fx时，如果j=maxj:Bijx,jk，则此时决策ij一定是最好的，即fx=t(ij,x)。利用决策的单调性，这个j可以接着上次查找，所以n次找j的时间复杂度为O(n+决策序列长度)=O(n)。在求出了fx之后，x将成为一个有用决策，我们需要求出Bx，以及维护这个决策序列。,四边形不等式、凸完全单调性与决策单调性,假设可以在T单位时间内求出y=miny:t(x,y)Bik。此时，Bx=y（因为不可能再小），并且x应当被添加到这个决策序列的末尾。容易发现，用栈可以很好的完成这个序列的维护，由于每个决策至多进出栈一次，每个决策出栈至多消耗T单位时间，于是维护序列的时间复杂度是O(nT)。又因为决策的单调性，查找合适决策的时间复杂度是O(n)的，所以总的时间复杂度是O(nT)。,四边形不等式、凸完全单调性与决策单调性,有时，因为函数w的表达式便于求出miny:t(x,y)t(ik,y)，所以T=O(1)；一般情况下，根据w的凸性可以得到t(x,y)-t(ik,y)关于y单调不增，于是可以在O(logn)时间内用二分的方法求出y，此时T=O(logn)。所以如果函数w是凸的，那么这种动态规划问题最坏可以在O(nlogn)时间内求解；最好时，可以在O(n)时间内求解，可见这种方法是非常高效的。然而，此种动态规划模型单一，对w的限制有时又难以满足，所以应用范围也较为狭窄。但其思想是值得借鉴的。,凸完全单调性的一个加强,假设我们要维护一个广义（不局限于动态规划问题）决策序列i1,i2,ik，满足i1i2ik，存在函数g和h，满足在选取有关x的最优决策时，决策i不如决策j(ij)等价于g(i,j)h(x)。此时，决策仍然具有单调性，不过这不是关于x单调，而是关于h(x)单调。类比上面的知识，容易知道，这里维护的决策序列满足为了方便，我们记i0=nil。则g(ik-1,ik)il，g(i0,i1)g(i1,i2)i2il，此时要将x(ilx)添加到决策序列中。我们比较g(il1,il)与g(il,x)的大小，如果g(il,x)g(il1,il)，就删去决策il（令ll1），继续这样的比较直到g(il1,il)g(il,x)，最后再将x放到决策序列的末尾。,选取适当的h(x)加速算法,容易看出，这是一个栈维护的问题。因为g的计算是O(1)的，所以整个过程的时间复杂度是O(n)。综上，每个阶段的计算是O(n)的，一共有k个阶段，故总的时间复杂度为O(kn)。对比这个方法与直接利用凸完全单调性的方法可以发现，直接利用凸完全单调性的方法实际上是在求出了g(i,j)之后，用二分的方法求出了最小的满足g(i,j)Sx的x。而这是完全没有必要的。如果w本身是凸的，通过选择合适的h(x)（这里h(x)=Sx），那么这个h(x)与x一定具有相同的单调性，这不会影响查找的总时间，而计算g的复杂度由O(logn)降到了O(1)，这就将维护决策序列时间复杂度从O(nlogn)降到了O(n)，从而提高的算法的效率。,用于解决一些权函数不具有凸完全单调性的问题,在刚才的例题中，这个方法只是扮演着优化的角色，并没有质的改变。下面，我们将利用这个方法解决一个权函数不满足四边形不等式的题目。例2(石阶)水平面上有个高度为h的高台，你需要用n(n1000)块石块修建一个石阶，从这个高台通往地面。第i个石阶的高度为hi。由于一些限制，你从高台出发，并且只能顺次处理每块石块，你要么将当前的石块摞在你前方的那一列，要么走到前方的那一列。在修建石阶的过程中你不能向回走。为了让这个石阶不至于太单调，你希望这个石阶有所起伏，所以你希望将这n个石块都用上。为了让这个石阶安全可用，你希望相邻两列高度之差的最大值（视高台为第0列，地面为最后一列）尽可能小。也就是说，你需要将这n个石块分成若干段，假设你将他们分成了k段，则每段的高度为这段所有石块的高度总和。假设第i段的高度为ti，t0=h，tk+1=0。你的目标就是选择一个合适的分段，来最小化。,用于解决一些权函数不具有凸完全单调性的问题,设h0=h,hn+1=0,dk,x为将石块0到石块x分成若干段，最后一段为石块k到石块x的方案中，相邻两段高度差的最小值。设si=h0+hi，diffi,k,x=|sx2sk1+si1|，则dn+1,n+1就是所求答案。,用于解决一些权函数不具有凸完全单调性的问题,这里，我们按照k从小到大,x从小到大的顺序计算dk,x。我们需要维护n+1个决策序列，第k个决策序列存储di,k1，其中i作为决策量。我们考察决策i比决策j更好的条件，以确定决策序列的各决策的序以及维护方法。设h(x)=sx2sk1，则决策i比决策j(ij)好等价于,用于解决一些权函数不具有凸完全单调性的问题,容易发现，如果h(x)足够大，那么此式一定不成立。我们考察这类不等式的解集。考虑函数f1(x)=max(|x+a1|,b1)，f2(x)=max(|x+a2|,b2)。这里a1a2，但b1、b2间没有必然的大小关系。则这两个函数间可能有以下几种关系：,用于解决一些权函数不具有凸完全单调性的问题,用于解决一些权函数不具有凸完全单调性的问题,在图中我们可以看到，f1(x)f2(x)的解集一定是xg(a2,b2,a1,b1)。故决策i比决策j(ij)好等价于简写为h(x)g(j,i)。这里g是可以在O(1)时间内求出的。,用于解决一些权函数不具有凸完全单调性的问题,所以我们维护的每个决策序列中的决策应当满足：查找决策时，应当找到最大的j，满足h(x)g(ij1,ij)。因为h(x)=sx2sk1关于x单调增，我们可以接着上次向前查找，所以总的查找时间为O(n)。维护序列时，由于dk,x是按照k从小到大计算的，新的决策一定是被追加到决策序列的末尾，所以只需要反复比较g(il1,il)与g(il,k)，删去序列的末尾决策直到满足g(il1,il)g(il,k)，最后将k追加到决策序列的末尾。,用于解决一些权函数不具有凸完全单调性的问题,这样，我们就得到了这个题目的O(n2)时间复杂度的解法。这个题目中，f2(x)-f1(x)并不一定是单调增的，也就是权函数并不具有凸完全单调性，但我们还是利用这个方法解决了这个问题。其原因在于，我们利用的只是决策的单调性，并不需要在意是哪个具体的性质造成的这种单调性。对权函数要求过高，这便是凸完全单调性的局限，为一个不难达到的目的付出了过多的代价。,合理的序与维护方向,上面两个例子，尤其是例2，向我们展示了这种方法的灵活性。动态规划的方程并不像第一节中的那么死板，也并不只有一个决策序列，决策的添加顺序也没有固定的要求。一个决策甚至可以被加入多个决策序列！（但不能太多，否则就与动态规划的本质与维护决策的最终目的背道而驰；当然，在例2中并未出现此情况）然而，解决动态规划问题只是此类方法的一部分，此类方法还可以解决更为宽泛的问题。,合理的序与维护方向,例3(经典问题)要求维护一些不与y轴平行的直线，为了方便，初始时只有一条直线y=。每次要么添加一条直线y=kx+b，要么询问x=k与这些直线的最低交点的坐标。假设询问的次数为q，直线的条数为n，请给出一个O(n+q)logn)的算法。假设第i条直线为y=kix+bi。考虑何时直线i不如直线j好。显然，这等价于但由于ki-kj的正负不确定，所以无法继续变形下去。,合理的序与维护方向,回顾决策序列的维护过程，可以发现，此方法并没有对决策的顺序作任何显式的要求，只要求决策满足：回顾前两个例题可以发现，决策的顺序恰恰是暗含在函数g中的。,合理的序与维护方向,在本题中为了得到g(i,j)h(x)，我们可以要求kikj。这样就得到了一个合适的序。有了这个序，我们就可以得到：即h(x)=x，,合理的序与维护方向,假如我们维护了一个决策序列i1,i2,il，满足ki_1ki_2ki_l，-=g(nil,ki_1)g(ki_1,ki_2)g(ki_(l-1),ki_l)回答询问时，只要在这个序列中找最大的j，满足g(ij-1,ij)x。则所求交点一定在直线ij上。插入新直线时，由于这条直线并不一定是斜率最小的直线，所以我们不能在决策序列的末尾添加这个决策，而是要根据这条直线的斜率来决定是在开头还是中间还是末尾来维护这个序列。为了使算法描述尽可能地简洁，我们视序列的开头和结尾为一种退化了的中间。假设ki_j0)，求出一个权和最大的划分。设di为从第1个数到第i个数的权值最大的划分。则决策i不如决策j(isi_(k+1)。于是刚才的方法实际上只用在序列的末尾进行维护，于是程序的时间复杂度就降到了O(N)。,第三部分总结,从上面的讨论可以看出，凸完全单调性的这个加强中函数g和h的出现带来了很大的灵活性，不仅可以用来加速求解权函数本身就凸的情形，还可以解决权函数并不凸的形式，而且其应用也不仅限于动态规划问题。维护决策序列，更应当被看作一种思考问题的方法。,谢谢大家！,