凸完全單調(diào)性的一個(gè)加強(qiáng)與應(yīng)用

1、凸完全單調(diào)性的一個(gè)加強(qiáng)與應(yīng)用西安市第一中學(xué)楊哲第一部分四邊形不等式、凸完全單調(diào)性與決策單調(diào)性以及凸完全單調(diào)性的一個(gè)加強(qiáng)四邊形不等式、凸完全單調(diào)性與決策單調(diào)性對(duì)于一個(gè)權(quán)函數(shù)w(i, j)，如果它滿足w(x, i + 1) - w(x, i)隨x單調(diào)不增，亦即w(x, i + 1) + w(x + 1,i) w(x, i) + w(x+1,i + 1)，則稱這個(gè)權(quán)函數(shù)滿足凸完全單調(diào)性。容易證明，當(dāng)k 0 時(shí)，w(x, i + k) - w(x, i) 隨x單調(diào)不減，w(i + k, x)- w(i, x) 隨x單調(diào)不減。所以對(duì)任意的a b c d，有w(a, d) + w(b, c) w(a, c

2、)+ w(b, d)。稱此不等式為四邊形不等式。由四邊形不等式也可推出凸完全單調(diào)性，所以“w 滿足四邊形不等式”與“w具有凸完全單調(diào)性”這兩種說法是等價(jià)的。四邊形不等式、凸完全單調(diào)性與決策單調(diào)性n 在一類要求將一段序列劃分為若干子段，從i到j(luò)的一段的費(fèi)用為w(i, j)，要求出所有子段代價(jià)之和最小的劃分方案的動(dòng)態(tài)規(guī)劃問題中，通?？梢砸姷竭@樣的狀態(tài)轉(zhuǎn)移方程：f x = minf i + w(i, x) :1 i xn 設(shè)t(i, x) = fi + w(i, x)，如果對(duì)于某個(gè)x，t(i, x) t(j, x) (i x，有t(i, y) t(j, y)。此式說明，對(duì)于i j，一旦某個(gè)時(shí)刻決策i

3、沒有決策j好，以后決策i也不會(huì)比決策j好。這說明，fx 的決策是隨x單調(diào)不減的， 這就是決策的單調(diào)性。四邊形不等式、凸完全單調(diào)性與決策單調(diào)性n 解決這類問題時(shí)，通常用Bi記錄使決策i比所有之前的決策j (j i)要好的最小的x，即Bi = minx : t(i, x) t(j, x)對(duì)所有j i均成立。n 根據(jù)決策的單調(diào)性，決策i比所有之前的決策j (j i)要好等價(jià)于Bi x。n 如果對(duì)某個(gè)(i, j) (i j)，Bi Bj，則說明決策i是無用的。n 于是任何時(shí)刻，假設(shè)所有有用決策為 i1, i2, , ik，滿足i1 i2 ik，則Bi1 Bi2 Bik。四邊形不等式、凸完全單調(diào)性與決策

4、單調(diào)性n 求解fx時(shí)，如果j = maxj : Bij x, j k，則此時(shí)決策ij一定是最好的，即fx = t(ij,x)。利用決策的單調(diào)性，這個(gè)j可以接著上次查找，所以n次找j的時(shí)間復(fù)雜度為O(n + 決策序列長(zhǎng)度) = O(n)。n 在求出了fx 之后，x將成為一個(gè)有用決策，我們需要求出Bx，以及維護(hù)這個(gè)決策序列。四邊形不等式、凸完全單調(diào)性與決策單調(diào)性假設(shè)可以在T單位時(shí)間內(nèi)求出y = miny : t(x, y) t(ik,y)。那么如果y Bik，一定有Bx Bik。于是ik是無用決策，這時(shí)應(yīng)當(dāng)在決策序列中刪去這個(gè)ik（只需要讓k k - 1）。繼續(xù)這個(gè)過程，直到miny : t(x,

5、 y) Bik。此時(shí)，Bx = y（因?yàn)椴豢赡茉傩。?，并且x應(yīng)當(dāng)被添加到這個(gè)決策序列的末尾。容易發(fā)現(xiàn)，用?？梢院芎玫耐瓿蛇@個(gè)序列的維護(hù)，由于每個(gè)決策至多進(jìn)出棧一次，每個(gè)決策出棧至多消耗T單位時(shí)間，于是維護(hù)序列的時(shí)間復(fù)雜度是O(nT)。又因?yàn)闆Q策的單調(diào)性，查找合適決策的時(shí)間復(fù)雜度是O(n)的， 所以總的時(shí)間復(fù)雜度是O(nT)。四邊形不等式、凸完全單調(diào)性與決策單調(diào)性有時(shí)，因?yàn)楹瘮?shù)w的表達(dá)式便于求出miny : t(x, y) t(ik,y)，所以T = O(1)；一般情況下，根據(jù)w的凸性可以得到t(x, y) - t(ik,y) 關(guān)于y單調(diào)不增，于是可以在O(log n) 時(shí)間內(nèi)用二分的方法求出y

6、，此時(shí)T = O(log n)。所以如果函數(shù)w是凸的，那么這種動(dòng)態(tài)規(guī)劃問題最壞可以在O(nlogn) 時(shí)間內(nèi)求解；最好時(shí)，可以在O(n) 時(shí)間內(nèi)求解，可見這種方法是非常高效的。然而，此種動(dòng)態(tài)規(guī)劃模型單一，對(duì)w的限制有時(shí)又難以滿足，所以應(yīng)用范圍也較為狹窄。但其思想是值得借鑒的。凸完全單調(diào)性的一個(gè)加強(qiáng)n 假設(shè)我們要維護(hù)一個(gè)廣義（不局限于動(dòng)態(tài)規(guī)劃問題）決策序列i1, i2, , ik，滿足i1 i2 ik，存在函數(shù)g和h，滿足在選取有關(guān)x的最優(yōu)決策時(shí)，決策i不如決策j (i j)等價(jià)于g(i, j) h(x)。n 此時(shí)，決策仍然具有單調(diào)性，不過這不是關(guān)于x單調(diào)，而是關(guān)于h(x)單調(diào)。類比上面的知識(shí)，

7、容易知道，這里維護(hù)的決策序列滿足- = g(nil ,i1 ) g(i1,i2 ) L g(ik -1,ik )n 為了方便，我們記i0 = nil。則g(ik - 1,ik) g(ik,ik+1)。凸完全單調(diào)性的一個(gè)加強(qiáng)n 我們需要在這個(gè)序列上進(jìn)行查找最小的j，滿足h(x) 0 時(shí)dk, x = min dk -1, i + Tx- Ti - Pi-1 (Sx - Si ) : x 0時(shí)Txdk, x =min Ui + Tx- Pi-1Sx: x i2 il，g(i0, i1) g(i1, i2) Sx，則 dk, x = Ui+ Txj- Pi -1Sx。由于S 在的計(jì)算過程中是單調(diào)jx

8、增的（按照x從大到小的順序計(jì)算），我們只需要接著上次向后查找，于是這n次查找的總時(shí)間復(fù)雜度為O(n)。 計(jì)算出dk之后，我們需要建立一個(gè)決策序列供下一階段選擇。我們按照從大到小的順序?qū)⑦@些候選決策加入決策序列。假設(shè)某個(gè)時(shí)刻決策序列為i1, i2, , ik，i1 i2 il，此時(shí)要將x (il x) 添加到?jīng)Q策序列中。我們比較g(il1, il)與g(il, x)的大小，如果g(il, x) g(il1, il)，就刪去決策il（令l l 1），繼續(xù)這樣的比較直到g(il1, il) g(il, x)，最后再將x 放到?jīng)Q策序列的末尾。選取適當(dāng)?shù)膆(x)加速算法容易看出，這是一個(gè)棧維護(hù)的問題。因

9、為g的計(jì)算是O(1) 的，所以整個(gè)過程的時(shí)間復(fù)雜度是O(n)。綜上，每個(gè)階段的計(jì)算是O(n)的，一共有k個(gè)階段，故總的時(shí)間復(fù)雜度為O(kn)。對(duì)比這個(gè)方法與直接利用凸完全單調(diào)性的方法可以發(fā)現(xiàn)， 直接利用凸完全單調(diào)性的方法實(shí)際上是在求出了g(i, j)之后，用二分的方法求出了最小的滿足g(i, j) Sx的x。而這是完全沒有必要的。如果w 本身是凸的，通過選擇合適的h(x)（這里h(x) = Sx），那么這個(gè)h(x)與x一定具有相同的單調(diào)性，這不會(huì)影響查找的總時(shí)間，而計(jì)算g的復(fù)雜度由O(log n)降到了O(1)，這就將維護(hù)決策序列時(shí)間復(fù)雜度從O(n log n)降到了O(n)，從而提高的算法的

10、效率。用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問題在剛才的例題中，這個(gè)方法只是扮演著優(yōu)化的角色，并沒有質(zhì)的改變。下面， 我們將利用這個(gè)方法解決一個(gè)權(quán)函數(shù)不滿足四邊形不等式的題目。例2 (石階)水平面上有個(gè)高度為h 的高臺(tái)，你需要用n (n 1000) 塊石塊修建一個(gè)石階，從這個(gè)高臺(tái)通往地面。第i 個(gè)石階的高度為hi。由于一些限制， 你從高臺(tái)出發(fā)，并且只能順次處理每塊石塊，你要么將當(dāng)前的石塊摞在你前方的那一列，要么走到前方的那一列。在修建石階的過程中你不能向回走。為了讓這個(gè)石階不至于太單調(diào)，你希望這個(gè)石階有所起伏，所以你希望將這n個(gè)石塊都用上。為了讓這個(gè)石階安全可用，你希望相鄰兩列高度之差的最大值

11、（視高臺(tái)為第0列，地面為最后一列）盡可能小。也就是說，你需要將這n個(gè)石塊分成若干段，假設(shè)你將他們分成了k段，則每段的高度為這段所有石塊的高度總和。假設(shè)第i 段的高度為ti，t0 = h，tk+1 = 0。你的目標(biāo)就是選擇一個(gè)合適的分段，來最小化max k| t - t|。i=0ii+1用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問題n 設(shè)h0 = h, hn+1 = 0, dk, x為將石塊0到石塊x分成若干段，最后一段為石塊k到石塊x的方案中，相鄰兩段高度差的最小值。設(shè)si = h0 + x = |sx 2sk1 + si1|，則0+ hi，diff i, k,當(dāng)k = x = 0時(shí)當(dāng)0 = k

12、x時(shí)當(dāng)1 k x n +1時(shí)dk, x = minmax(di, k -1, diff i, k, x) : 0 i j)好等價(jià)于max(| h(x) + si-1 |, di, k -1) max(| h(x) + s j-1 |, d j, k -1)用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問題n 容易發(fā)現(xiàn)，如果h(x)足夠大，那么此式一定不成立。我們考察這類不等式的解集。考慮函數(shù)f1(x)= max(|x + a1|, b1)， f2(x) = max(|x + a2|, b2) 。這里a1 a2，但b1、b2 間沒有必然的大小關(guān)系。則這兩個(gè)函數(shù)間可能有以下幾種關(guān)系：用于解決一些權(quán)函數(shù)不具

13、有凸完全單調(diào)性的問題用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問題n 在圖中我們可以看到，f1(x) f2(x)的解集一定是x g(a2, b2, a1, b1)。故決策i比決策j (i j)好等價(jià)于h(x) g(sj-1, d j, k -1, si-1, di, k -1)n 簡(jiǎn)寫為h(x) g(j, i)。這里g是可以在O(1) 時(shí)間內(nèi)求出的。用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問題n 所以我們維護(hù)的每個(gè)決策序列中的決策應(yīng)當(dāng)滿足：nil= i0 i1 i2 L g(i1 , i2 ) L g(il -1 , il )n 查找決策時(shí)，應(yīng)當(dāng)找到最大的j，滿足h(x) g(ij1, ij)。因?yàn)?/p>

14、h(x) = sx 2sk1關(guān)于x單調(diào)增，我們可以接著上次向前查找，所以總的查找時(shí)間為O(n)。n 維護(hù)序列時(shí)，由于dk, x是按照k從小到大計(jì)算的，新的決策一定是被追加到?jīng)Q策序列的末尾，所以只需要反復(fù)比較g(il1, il) 與g(il, k)，刪去序列的末尾決策直到滿足g(il1, il) g(il, k)，最后將k追加到?jīng)Q策序列的末尾。用于解決一些權(quán)函數(shù)不具有凸完全單調(diào)性的問題n 這樣，我們就得到了這個(gè)題目的O(n2)時(shí)間復(fù)雜度的解法。n 這個(gè)題目中，f2(x) -f1(x)并不一定是單調(diào)增的，也就是權(quán)函數(shù)并不具有凸完全單調(diào)性，但我們還是利用這個(gè)方法解決了這個(gè)問題。其原因在于， 我們利用

15、的只是決策的單調(diào)性，并不需要在意是哪個(gè)具體的性質(zhì)造成的這種單調(diào)性。對(duì)權(quán)函數(shù)要求過高，這便是凸完全單調(diào)性的局限，為一個(gè)不難達(dá)到的目的付出了過多的代價(jià)。合理的序與維護(hù)方向n 上面兩個(gè)例子，尤其是例2，向我們展示了這種 方法的靈活性。動(dòng)態(tài)規(guī)劃的方程并不像第一節(jié)中 的那么死板，也并不只有一個(gè)決策序列，決策的 添加順序也沒有固定的要求。一個(gè)決策甚至可以 被加入多個(gè)決策序列?。ǖ荒芴?，否則就與 動(dòng)態(tài)規(guī)劃的本質(zhì)與維護(hù)決策的最終目的背道而馳； 當(dāng)然，在例2中并未出現(xiàn)此情況）然而，解決動(dòng) 態(tài)規(guī)劃問題只是此類方法的一部分，此類方法還 可以解決更為寬泛的問題。合理的序與維護(hù)方向n 例3 (經(jīng)典問題) 要求維護(hù)一

16、些不與y軸平行的直線，為了方便，初始時(shí)只有一條直線y = 。每次要么添加一條直線y = kx + b，要么詢問x = k 與這些直線的最低交點(diǎn)的坐標(biāo)。假設(shè)詢問的次數(shù)為q，直線的條數(shù)為n，請(qǐng)給出一個(gè)O(n + q) log n) 的算法。n 假設(shè)第i條直線為y = kix + bi?？紤]何時(shí)直線i不如直線j好。顯然，這等價(jià)于ki x + bi k j x + bj bi - bj (ki - k j )x但由于ki - kj的正負(fù)不確定，所以無法繼續(xù)變形下去。合理的序與維護(hù)方向n 回顧決策序列的維護(hù)過程，可以發(fā)現(xiàn)，此方法并沒有對(duì)決策的順序作任何顯式的要求，只要求決策滿足：決策i不如決策j g(i

17、, j) h(x)n 回顧前兩個(gè)例題可以發(fā)現(xiàn)，決策的順序恰恰是暗含在函數(shù)g中的。合理的序與維護(hù)方向n 在本題中為了得到g(i, j) h(x)，我們可以要求ki kj。這樣就得到了一個(gè)合適的序。有了這個(gè)序，我們就可以得到： bj - bi x當(dāng)k k 時(shí) k- kijij決策i不如決策j - x當(dāng) k = k , b b時(shí)ijji x當(dāng) k = k , b b時(shí) bj - biijjin 即h(x) = x， k 時(shí)當(dāng)k kij- kijg(i, j) = - 當(dāng) k = k , b b時(shí)ijji當(dāng) k = k , b b時(shí)ijji合理的序與維護(hù)方向假如我們維護(hù)了一個(gè)決策序列i1, i2, ,

18、 il，滿足ki_1 ki_2 ki_l ，-= g(nil, ki_1) g(ki_1, ki_2) g(ki_(l-1), ki_l)回答詢問時(shí)，只要在這個(gè)序列中找最大的j，滿足g(ij-1,ij) x。則所求交點(diǎn)一定在直線ij上。插入新直線時(shí)，由于這條直線并不一定是斜率最小的直線，所以我們不能在決策序列的末尾添加這個(gè)決策，而是要根據(jù)這條直線的斜率來決定是在開頭還是中間還是末尾來維護(hù)這個(gè)序列。為了使算法描述盡可能地簡(jiǎn)潔，我們視序列的開頭和結(jié)尾為一種了的中間。假設(shè)ki_j kn ki_(j-1) ，我們可以用類似棧維護(hù)的方法刪去前面不需要保留的決策。假設(shè)這個(gè)時(shí)候n前方的決策變成了ij，我們比

19、較g(ij, x) 與g(x, ij+1)來判斷決策n是否需要保留。如果需要保留，這時(shí)有可能g(n, ij+1) g(ij+1, ij+2)，那么決策ij+1不需要被保留，刪去決策ij+1，再判斷決策ij+2是否不需要被保留。如此操作直到不需要?jiǎng)h除決策為止。合理的序與維護(hù)方向容易知道，平衡樹可以在O(log n)的時(shí)間內(nèi)求前驅(qū)、后繼， 查找最大的不超過h(x)的元素。因?yàn)槊看尾迦胄碌臎Q策只需要進(jìn)行均攤O(1)次操作（可用類似于棧維護(hù)的方法證明），所以維護(hù)序列的總時(shí)間是O(nlogn) 的?；卮鹪儐柕目倳r(shí)間是O(qlogn) 的。所以總時(shí)間復(fù)雜度就是O(n+q)logn)的。值得一提的是，只要對(duì)

20、這個(gè)算法稍加改變，就可以在O(nlogn + 輸出規(guī)模)的時(shí)間內(nèi)解決在線半平面交的問題， 因?yàn)槲覀冇?jì)算出的g恰好就是這些直線組成的最低折線上的轉(zhuǎn)折點(diǎn)。雖然這種方法可以高效處理從中間維護(hù)決策序列的情況， 但畢竟平衡樹操作的常數(shù)因子不小，如果可以只在兩頭 維護(hù)序列，就只需要用棧來維護(hù)，程序效率會(huì)大大提高。合理的序與維護(hù)方向考慮離線半平面交問題，給出n個(gè)二元一次方程Ax + By C，求出可行域。我們只考慮這個(gè)問題的關(guān)鍵步驟：給出一些直線y = kx + b， 求出最低的一條折線（顯然這是上凸的）。由于最終的結(jié)果與處理直線的順序無關(guān)，我們先將這些直線按照k從大到小排序，然后應(yīng)用上面的方法。這時(shí)，這些

21、“決策”的插入過 程中，只需要從序列的尾部維護(hù)，這個(gè)操作用棧就可以高效的完成。最后剩下的“決策”就是按照從左到右順序的最低折線，而相鄰兩“決策”間的g，就是這些折線交點(diǎn)的橫坐標(biāo)。排序之后的這些操作，其時(shí)間復(fù)雜度總計(jì)O(n)。這個(gè)幾何問題，我們甚至沒有畫一張圖，就用這種方法在O(nlogn)的時(shí)間內(nèi)高效的解決了。而算法效率的瓶頸是一開始的排序，如果排序可以在O(n)時(shí)間內(nèi)完成，或者直線就是按斜率從大到小或斜率從小到大的順序給出，那么此方法的時(shí)間復(fù)雜度就是O(n)。這足以說明此方法更應(yīng)該被作為一種思想來看待。合理的序與維護(hù)方向例4 (USACO JAN07 schul) 要求維護(hù)一些不與y軸平行的

22、直線。每次要么添加一條直線y = kx + b，要么詢問當(dāng)x = p與這些直線的所有交點(diǎn)中的縱坐標(biāo)的最小的點(diǎn)。保證每條直線的斜率大于0，并且新加直線的橫截距-b/k比原來的直線的橫截距都大。并且保證每次詢問的p總比最大橫截距大。由于直線并不是按照斜率遞增或遞減的順序添加的，使用上面的方法只能得到O(n+q)logn)的算法，而對(duì)于本題的數(shù)據(jù)，這個(gè)算法雖然比O(qn)的方法快了很多，但還是很慢。我們不妨再仔細(xì)分析一下題目特點(diǎn)，按順序?qū)⒚織l直線假如決策序列會(huì)怎樣呢？直線i比直線j (i ki時(shí)，這等價(jià)于k j - kik j - ki而由于左邊不大于最大橫截距，而這個(gè)問題又保證每次詢問的x大于最大

23、橫截距，所以這個(gè)條件等價(jià)于 x ！合理的序與維護(hù)方向這樣，我們就得到了一個(gè)合適的函數(shù)g(i, j)，以及一個(gè)便于處理的序，這個(gè)序恰好就是直線插入的順序。所以這個(gè)問題就被轉(zhuǎn)化為一個(gè)普通的棧維護(hù)問題， 由于這個(gè)序列的維護(hù)方法已經(jīng)在例2中給出，這里不再贅述。這樣，我們就在O(n + q)的時(shí)間解決了這個(gè)問題。而解決這個(gè)問題的關(guān)鍵是：有些結(jié)論雖然在全局并不成立，但在某個(gè)具有更多限制的局部?jī)?nèi)卻可以滿足。所以我們要充分利用題目特點(diǎn)，找到最適合的序，這個(gè)序有時(shí)就是以這個(gè)特殊的局部?jī)?nèi)的某些性質(zhì)為基礎(chǔ)的。最優(yōu)決策的查找方式n 當(dāng)這個(gè)決策序列是使用棧在兩頭維護(hù)時(shí)： 如果h(x)單調(diào)增或單調(diào)減，則可以利用這個(gè)單調(diào)性

24、接著上次查找，在O(n + q)時(shí)間內(nèi)回答所有詢問，如果這個(gè)h(x)的反復(fù)次數(shù)不多（例如凸等），也可以用接著上次查找的方法，其時(shí)間復(fù)雜度為O(|ans1 -ans2| + |ans1 -ans2| + + |ansq-1 -ansq|)。 如果這個(gè)h(x)的變化很不規(guī)律，則可以用二分查找的方法在O(q log n)時(shí)間內(nèi)回答所有詢問。n 當(dāng)這個(gè)決策序列是從中間維護(hù)時(shí)，由于使用了平衡樹，我們也只能用平衡樹上的查找方法。n 相比之下，從中間維護(hù)決策序列無論是從決策的維護(hù)還是最優(yōu)決策的查找，都有很大劣勢(shì)，我們應(yīng)當(dāng)盡量避免（尋找適合的序）。選擇合適的規(guī)劃方向例5(旅行) 一條鐵路線上有N個(gè)城市，順序編

25、號(hào)為1, 2, , N，TT希望從城市1到城市N。從城市i出發(fā)只能到達(dá)后面的某個(gè)點(diǎn)j，需要花費(fèi)(j-i)Ai的車票費(fèi)與Bj元的檢票費(fèi)。TT想知道從城市1出發(fā)到城市N所需要的最少花費(fèi)。假設(shè)di為從城市1到城市i所需的最小費(fèi)用，則dx = min di + (x - i) Ai + Bx : 0 i x決策i不比決策j (i j)等價(jià)于di + (x - i)Ai + Bx d j + (x - j)Aj + Bx d j - jAj - di + iAi x(Ai - Aj )于是選擇Ai作為決策的序，就轉(zhuǎn)化為使用平衡樹從中間維護(hù)決策序列的問題。根據(jù)上面的討論，這個(gè)算法的時(shí)間復(fù)雜度是O(nlog

26、n)的。但由于使用平衡樹來維護(hù)，這個(gè)算法的常數(shù)因子不小。選擇合適的規(guī)劃方向n 但是，如果定義di為從車站i到車站N所花的最少代價(jià)，則dx = min di + (i - x) Ax + Bi : x j)等價(jià)于di + (i - x)Ax + Bi d j + ( j - x)Ax + Bj d j + Bj - di - Bi Axi - jn 這時(shí)，我們可以按處理順序在決策序列末尾維護(hù)決策，這樣只需要用棧就可以維護(hù)決策序列。在查找最優(yōu)決策的時(shí)候，只需要使用二分查找的方法，就可以在O(nlogn)時(shí)間內(nèi)解決此問題。n 雖然這個(gè)方法與上個(gè)方法具有一樣的理論時(shí)間復(fù)雜度，但由于棧維護(hù)和二分查找相對(duì)于平衡樹的常數(shù)因子