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 小果子 閱讀(211) |
評論 (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 小果子 閱讀(1839) |
評論 (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 小果子 閱讀(211) |
評論 (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 小果子 閱讀(5117) |
評論 (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 小果子 閱讀(958) |
評論 (1) |
編輯 收藏