1.完全加括号,Catalan(n-1)
2.不完全加括号:s1=1,s2=1,Sn=(3*(2*n-3)Sn-1-(n-3)Sn-2)/n;
posted @
2008-08-07 12:23 小果子 阅读(199) |
评论 (0) |
编辑 收藏对于0-1分数规划的Dinkelbach算法的分析
武钢三中 吴豪[译]
摘要:
0-1分数规划问题是指求出解集{xi|xi=0或1}使目标(c1x1+c2x2+
+cnxn) /(d1x1+d2x2+…+dnxn)=cx/dx达到最大。对于分数规划问题，Dinkelbach提出了一个算法，它通过解决一个子问题Q(L)来得到原文题的解。这里Q是一个线性的最小化目标函数cx-Ldx，且满足x等于0或1。在本文中，我们证明了Dinkelbach算法在最坏情况下可以在O(log(nM))的时间内解决子问题，这里M=max{max|ci|,max|di|,1}。
1．0-1分数规划问题
要使两个线性函数的比值最大或最小的问题，我们称作分数规划问题或双曲线问题。分数规划问题在许多领域都可以找到[22]。它在经济学中的应用有些常见的例子，如寻找最优收入比率或者在效益约束下的最佳物资调配问题。另外，系统效率也常常用比率来衡量，如收益/时间、利润/风险和消费/时间。有大量的文章对这类问题做了分析[3，5，12，20，24]。
有几类分数规划问题已被广泛地研究。如0-1分数规划问题[1],它包含最优比率生成树问题[4]，最优比率环问题[8，6，19]，分数背包问题[15]，以及分数剪枝问题[10]。在本文中，我们研究0-1分数规划问题，它的描述如下：
令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)为n维整数向量，那么一个0-1分数规划问题用公式描述如下:
FP: 最小化
(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx
xi∈{0,1}
这里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω称作可行域，而x则是Ω的一个元素，我们称x为可行解。贯穿全文，我们假定对于任意可行解x,dx都是正数。这里我们记C=max{max|ci|,1},D=max{max|di|,1}。那么，显然问题的最优解在区间[-nC,nC]内。
对于分数规划问题，有许多算法都能利用下面的线性目标函数解决问题。
Q(L): 最小化 cx-Ldx
xi∈{0,1}
记z(L)为Q(L)的最值。令x*为分数规划的最优解，并且令L*=(cx*)/(dx*)(注：分数规划的最值)。那么下面就容易知道了：
z(L) > 0
当且仅当
L<L*
z(L) = 0
当且仅当
L=L*
z(L) < 0
当且仅当
L>L*
此外，Q(L*)的最优解也能使分数规划最优化[7,16,17]。因此，解决分数规划问题在本质上等同于寻找L=L*使z(L)=0。出于这个目的，关于L的函数z(L)具有很多不错的性质：分段线性，凹函数，严格递减，z(-nC)<0，且z(nC)>0。根据上面的性质，显然当我们确定参量L，我们可以检验最值L*是否大于小于或等于当前的L。
有一些方法能够产生一系列收敛于L*的参量。其中一种借助于二分搜索[17,21,13]。在两个不同的可行解的目标值不相同的情况下，他们的差距将大于等于1/(nD)^2。这暗示我们，当我们采用二分搜索时，最优值L*可以通过解决子问题Q(L)在最多O(log(2nC/(1/nD)^2))<=O(log(nCD))的时间内得到。
在1979年，Megiddo[18]提出了一个巧妙的方法来系统地产生参量序列。他证明了如果子问题Q(L)能够通过O(p(n))的比较和O(q(n))的累加被解决，那么分数规划问题就能用O(p(n)+q(n))的时间被解决。
另一种方法理论上类似于牛顿迭代法，他被Isbell、Marlow[14]和Dinkelbach[7]提出（也被称作Dinkelbach算法）。这个算法在[17,21,11]中被讨论（也可能是其他文献）。下一节将对它进行正式的论述。Schaible[21]证明了对于非线性分数规划问题，二分搜索的方法的收敛速度仅仅是线性的，而Dinkelbach的收敛速度却是超线性的。另外，据说Dinkelbach算法在实际应用中强力而有效（参见[13,23]的例子）。然而，Dinkelbach算法对于0-1分数规划问题的最坏时间复杂度却没有被证明。在本文中，我们证明了,Dinkelbach算法最多会在O(log(nCD))的时间内解决子问题。注意它的时间复杂度与普通的二分搜索相同。我们的结论暗示了，如果对于子问题Q(L)存在多项式算法，Dinkelbach算法也能够在多项式时间内解决分数规划问题。另外，即使子问题Q(L)是NP-完全或NP-难的，对于特殊的分数规划我们也能够在多项式时间内出解。
2．Dinkelbach算法的论述
它本质上是观察直线
z=cx’-Ldx’
于函数z(L)在L=L’处相切，这里x’是子问题Q(L’)的最优解。因此，-dx’是z(L)在L’处的斜率。而且很容易看出上面的直线与L轴相交与L=cx’/dx’.
现在我们来描述Dinkelbach对于分数规划的算法。Dinkelbach算法产生了收敛于L*的参量序列，如图1中细线所示的方式。
Dinkelbach算法：
步骤1：设L=L1,使 L*<=L1<=nC
步骤2：解决子问题Q(L)并得到最优解x
步骤3：如果z(L)=0，那么输出x并终止。否则，设L=cx/dx跳到步骤2
为了初始化L1,将用到nC，因此充分挖掘拓展问题的结构将能做出更好的选择。
3．Dinkelbach算法的分析
在这一节中，我们假定Dinkelbach算法终止于第k次。我们可以得到一个参量序列(L1,L2…Lk)和一个0-1值的向量(x1,x2…xk).z(L)的凸度暗示了下面的不等式：
dx1>dx2>…>dxk-1>=dxk>0
cx1+nCdx1>cx2+nCdx2>>cxk-1+nCdxk-1>=cxk+nCxk>=0
由于函数z(L)是严格递减的，也很容易发现
z(L1)<z(L2)<<z(Lk) = 0 并且 L1>L2>>Lk
引理1
如果0>=z(Lr)>-1/nD (2<=r<=k) 那么 z(Lr)=0
证明 由于Lr=cxr-1/dxr-1
z(Lr)=cxr- Lr dxr=cxr-(cxr-1dxr)/(dxr-1)=(cxrdxr-1 – cxr-1dxr)/(dxr-1)
假定z(Lr)<0，那么(cxrdxr-1 – cxr-1dxr)<=-1。
因此不等式0<dxr-1<=nD暗示了z(Lr)<=-1/nD。它是矛盾的！
上面的引理来源于权向量c和d的完整性。这个引理暗示了如果z(Lr)>=-1/nD那么z(Lr)=0，因此该算法会中止于第r次。
引理2 如果0<=cxr+nCdxr<1,那么z(cxr/dxr)=0
证明 由于cxr+nCdxr是整数，如果0<=cxr+nCdxr<1，那么cxr+nCdxr=0并且cxr/dxr=-nC。由于最值L*>=-nC, xr是分数规划的最优解并且L*=cxr/dxr=-nC。那么显然有z(cxr/dxr)=z(L*)=0
上面的引理证明了如果cxr+nCdxr < 1，那么算法就在r或者r+1次终止。
现在给出主要引理：
引理3
如果1<=r<=k-1那么|z(Lr+1)|<=(1/2)|z(Lr)|或cxr+1+nCdxr+1 <=(1/2)(cxr+nCdxr)将满足。
证明 如果Lr+nC<=0 那么Lr=L*=-nC 并且它暗示着z(Lr)b=(1/2)z(Lr+1)=0
现在假定Lr+nC>0。就出现了两种情况：
情况(i) 首先我们来考虑z(Lr+1)( Lr+nC)<=z(Lr)/2*(Lr+1+nC)。这个情形如图２所示。在这个图中，直线z=cxr-Ldxr被记作lr。这里我们将用到图２的符号。令M为线段PR的中点。那么点M的坐标为( Lr+1 , z(Lr)( Lr+1+nC)/2/ Lr+nC )。因此条件z(Lr+1)( Lr+nC)<=z(Lr)*( Lr+1+nC)/2暗示着点Q=( Lr+1,z(Lr+1))在线段MR上。在这个条件下，我们证明不等式cxr+1+nC dxr+1<=(1/2)( cxr+nC, dxr)成立。这意味着直线lr+1与线段MR相交，lr+1也与线段M’R’相交，这里M’是线段P’R’的中点。现在我们证明这个不等式：
(Lr-Lr+1)( cxr+1+nC dxr+1)
=( cxr+1-Lr+1 dxr+1) (Lr+nC)- ( cxr+1-Lr dxr+1) (Lr+1+nC)
=z(Lr+1) (Lr+nC) - ( cxr+1-Lr dxr+1) (Lr+1+nC)
<= z(Lr) (Lr+1+nC)/2- ( cxr-Lr dxr) (Lr+1+nC)
=-(1/2) ( cxr-Lr dxr) (Lr+1+nC)=-(1/2)( cxr/ dxr - Lr) dxr( cxr/ dxr+nC)
=-(1/2)( Lr+1-Lr) ( cxr+nC dxr)=(1/2) (Lr-Lr+1) ( cxr+nC dxr)
由于Lr>Lr+1,那么不等式cxr+1+nC dxr+1<= (1/2) ( cxr+nC dxr)已经被证明。
情况(ii) 接着，考虑z(Lr+1)( Lr+nC)>z(Lr)/2*(Lr+1+nC)
|z(Lr+1)|=- z(Lr+1)< - z(Lr)(nC+ Lr+1)/2/(nC+ Lr)
=|z(Lr)|(1-(Lr- Lr+1)/ (nC+Lr))/2<=1/2 * |z(Lr)|
注意无论|z(L)|还是cx+nCdx在过程中都是不增长的。
在第一次，|z(L)|的值小于等于2n^2*CD。通过引理１，显然如果存在O(log(2n^2CD/(1/nD)))<=O(log(nCD))次，他们每个都能至少将z(L)减少50%那么，然后就能得到最优解。同样，引理２暗示了将cx+nCdx减少50%的次数O (log(2n^2CD))<=O(log(nCD))是最坏情况。引理３证明了每次将|z(L)|或cx+nCdx减少50%。因此，重复总次数的界限是O(log(nCD))。
定理４ Dinkelbanch算法最坏情况的运行次数是O(log(nCD))<=O(log(nM))，这里M=max{C,D}。
上面的定理证明了Dinkelbanch算法最坏运行次数是O(log(nCD))。它暗示了，如果对于Q(L)存在强多项式算法，Dinkelbach算法就能在多项式时间内解决分数规划问题。然而，当我们用多项式算法解决了子问题后，我们需要估计目标函数Q(L)的系数的输入规模。在下一节，我们将通过分析最优比率生成树和分数调配问题来讨论这一点。
4．讨论
Chandrasekaran[4]提出了最优比率生成树的算法，它是基于二分搜索的。Dinkelbach算法可以在O(T(v,e)log(vCD))的时间解决该问题，这里v是点的个数，e是边的个数，并且用T(v,e)表示计算普通最小生成树的强多项式算法。很容易将Chandrasekaran的算法延伸到一般带有分数目标函数的矩阵胚规划问题。在这种情况下，在这种情形下，函数z(L)的断点数最大为n(n-1)/2（参见[4]）因此，当可行域Ω是矩阵胚基础特征向量的集合。Dinkelbach算法就会在O(min{n^2,log(nCD)})后终止。
对于调配问题，已经研制了许多算法。大概最有名的算法就是Hungarian方法，并且它在最坏情况下的复杂度是O(v(v log v+e)) [9]。使用Hungarian方法，Dinkelbach算法可以用O(v(v log v+e)log(vCD))的时间解决分数调配问题。在[19]中，Orlin和Ahuja提出了一个O(sqrt(v)e*log(vW))的算法来解决调配问题而且据说他们的算法因为强多项式算法而具有竞争性（参见[2]也可）。在他们的算法中，它假定边权为整数，并且W代表边权的最大绝对值。为了将这个算法与Dinkelbach算法相结合，我们需要将在运行第r次解决的的子问题Q(L)用下面式子代替
(dxr-1) cx-( cxr-1) dx
这里xr-1表示代表运行第i次得到的最优解。因此，在每次运行中，Dinkelbach算法解决边权绝对值小于等于2v^2CD的调配问题。它暗示了Dinkelbach算法对于调配问题的最坏情况下的时间复杂度为
O(sqrt(v)e(log(2v^3CD))(log(eCD)))<=O(sqrt(v)e(log(vCD))^2)
我们说，如果一个具有线性目标函数的0-1整数规划问题存在多项式算法，我们可以利用上述目标函数在多项式时间内解决它的0-1分数规划问题。
posted @
2008-08-05 14:58 小果子 阅读(1812) |
评论 (3) |
编辑 收藏http://acm.pku.edu.cn/JudgeOnline/problem?id=3480
http://acm.zju.edu.cn/show_problem.php?pid=2507
posted @
2008-08-05 14:56 小果子 阅读(201) |
评论 (0) |
编辑 收藏最小费用最大流 修改的dijkstra + Ford-Fulksonff算法
修改的dijkstra其实和Johnson算法的思想是一致的。
一个求最小费用最大流的朴素算法是这样的：
1 求最小费用增广路
2 判断是否存在增广路，否的话算法终止。
3 增加增广路上边的流量
4 在增广路上添加必要的逆向负权边
5 goto 1
因为负权边的存在，求最小费用增广路就不可以用dijkstra算法。当然，我们可以用bellman-ford算法，可是这样的话求一次最短路的时间代价就是O(e*n)，e是边数，n是顶点数。代价大了点，如果能用dijkstra算法就好了。利用Johnson算法的思想，这是可以做到的。
第一次求最短路可以用dijkstra算法（如果一开始就有负权边，那就用bellman-ford算法，这没关系），求出源点到所有点的距离，嗯，我说的距离是指路径上边的费用之和的最小值。注意，要求出到所有点的距离，而不是求出到汇点的距离就完事了。
假设有一条边u->v，源点到u的距离是d[u]，到v的距离是d[v]，边的费用（权值）是w(u，v)。很显然，d[u]+w(u,v)>=d[v]，不然的话，你会发现一条更好的路径从源点到v。问题是，什么时候取等呢？当u->v在v的最优路径上，范围说小一点，当u->v在从源点到汇点的最优路径，即最小费用增广路上。
好的，如果u->v被你增载了，你要开始添负权边v->u了，权值取负，就是-w(u,v)。负权就是讨厌，是正的就好了，dijkstra算法就可以再用了。怎么办呢，把负权边加个权值，让它非负。要加多少呢，d[v]-d[u]。当然不能只加一条边，对所有边，无论原有的还是新添的，按这个规则加，构造一个新的图：
对边a->b，新的边权w'(a,b)=w(a,b)+d[a]-d[b]
现在来看看你的杰作：
对原来的边u->v, w'(u,v)=w(u,v)+d[u]-d[v]: 记得么d[u]+w(u,v)>=d[v], 所以 w'(u,v) >= 0
对新加的负权边v->u, w'(v,u)=w(v,u)+d[v]-d[u]=-w(u,v)+d[v]-d[u]: 记得么d[u]+w(u,v)==d[v]，这里可是取等号的，所以w'(v,u) == 0
哈哈，这下所有边又是非负的了。
可是，问题是，为啥不每个边加个足够大的正数，这样不是所有边也都是正的了么。仔细想想，边权为啥要为正，不就是为了求源点到汇点的最短路方便么，可是，都加大正数的话，你求出的最短路和原来图的最短路能一致么，不能，为啥，画个三角形，自己想想。可是，我的方法就能一致么，能。我证明给你看。
假设从源点s到汇点t有一条路径s->a->b->c->d.->t,在原图中的路径长度为
w(s,a)+w(a,b)+w(b,c)++w(x,t)
在新图中的路径为
w'(s,a)+w'(a,b)+w'(b,c)+w'(x,t)
展开来就是
w(s,a)+d[a]-d[s]+w(a,b)+d[b]-d[a]+w(c,d)+d[d]-d[b]+.+w(x,t)+d[t]-d[x]
消阿消，d[a]和-d[a]，d[b]和-d[b]d[x]和-d[x]，剩下什么呢：
w(s,a)+w(a,b)+w(b,c)++w(x,t)+d[t]-d[s]
噢，不就比原图中多d[t]-d[s]么（其实d[s]==0）。这可是对所有s到t的路径都成立的，既然所有路径，在新图中的权值都比在原图中的权值多了d[t]，那么，新图的最短路，也就对应原图的最短路，只不过路径长度多了d[t]，这不仅对t成立，对所有节点u都成立，只不过新图中到u的最短路长度比原图多了d[u]。
好，用dijkstra算法，第二次求出最短路。然后求出新的d’[u]，然后添加新的边，然后准备第三次的dijkstra算法。。。为什么第二次可以这样做，第三次还可以这样做，第三次的原图可能有很多负权边啊？我可没说过w(u,v)>=0这样的限制，所以，即使原图有负权边还是可以这样做的。
好了，第一次dijkstra算法（或者bellman-ford算法，如果有负权边的话，只用一次，不会成为瓶颈的），然后每次求最小增广路用一次修改的dijkstra算法。这个算法求最小费用最大流复杂度是O(m*n*n), m是最大流量，或者是求增广路次数的上界。最后，如果用这个算法来求最优匹配问题，复杂度是O(n^3)的。
posted @
2008-08-03 20:49 小果子 阅读(5060) |
评论 (9) |
编辑 收藏混合图欧拉回路
原来混合图欧拉回路用的是网络流。
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
今天碰到一题是求这的...写下笔记......
http://acm.pku.edu.cn/JudgeOnline/problem?id=1637
posted @
2008-08-02 22:09 小果子 阅读(941) |
评论 (1) |
编辑 收藏