01分數規劃算法 信息學競賽 OI ACM 二分 Dinkelbach 最優比率生成樹 最優比率環

01分數規劃

張天翔

blog.csdn.net/hzoi_ztxztx97@QQ.com

前置技能

問題模型1

基本01分數規劃問題

給定n$n$個二元組(valuei,costi)$(value_i,cost_i)$，valuei$value_i$是選擇此二元組獲得的價值（非負），costi$cost_i$是選擇此二元組付出的代價（非負），設xi(xi∈{0,1})$x_i(x_i/in /{0,1/})$代表第i$i$個二元組的選與不選，最大(小)化下式 maximize(or minimize)   r=∑valuei?xi∑costi?xi $$maximize(or/ minimize)/ / / r = /frac{/sum value_i /cdot x_i}{/sum cost_i/cdot x_i}$$

解決方法

二分法

設r$r$最大值為r?$r^*$， r?=∑valuei?xi∑costi?xi $$r^* = /frac{/sum value_i /cdot x_i}{/sum cost_i/cdot x_i}$$

∑valuei?xi?r??∑costi?xi=0 $$/sum value_i /cdot x_i - r^*/cdot /sum cost_i/cdot x_i = 0$$

設一個函數，自變量為r$r$值， f(r)=∑valuei?xi?r??∑costi?xi $$f(r) =/sum value_i /cdot x_i - r^*/cdot /sum cost_i/cdot x_i$$

觀察這個函數，假如{xi}$/{x_i/}$固定，則這個函數就是坐標系中一條直線(y=B?A?x$y = B - A/cdot x$)，每一組{xi}$/{x_i/}$對應著一條直線，這些直線斜率非正(因為?A=?∑costi?xi≤0$-A =- /sum cost_i/cdot x_i /le 0$)，縱截距非負(因為B=∑valuei?xi≥0$B =/sum value_i /cdot x_i /ge 0$ )，如圖1。 對于每一條直線，當f(r)=0$f(r)=0$時，橫截距就是這一組的r$r$，那么r?$r^*$就是每條直線橫截距的最大值（每組{xi}$/{x_i/}$對應r$r$的最大值）如圖2。 在圖中上任取一條垂直x$x$軸的豎線， 如果存在直線與這條豎線的交點縱坐標為正，那么最優值一定在當前豎線的右側； 如果所有直線與這條豎線交點縱坐標為負，那么最優值一定在當前豎線的左側； 如果所有直線與這條豎線交點縱坐標非正且存在直線與這條豎線交點縱坐標為0，那么當前豎線橫坐標即為最優值r?$r^*$。 按照這個思想，可以二分答案r$r$，那么二分時如何進行判斷呢？

選擇一個r$r$時需要判斷所有f(r)$f(r)$的最大值是否為0，如果max{f(r)}>0$max/{f(r)/} > 0$則r<r?$r < r^*$；如果max{f(r)}<0$max/{f(r)/} < 0$ 則 r>r?$r > r*$。 怎樣求max{f(r)}$max/{f(r)/}$? f(r)=∑valuei?xi?r?∑costi?xi=∑(valuei?r?costi)?xi $$/begin{aligned}f(r) &= /sum value_i /cdot x_i - r /cdot /sum cost_i/cdot x_i // &= /sum (value_i-r/cdot cost_i) /cdot x_i/end{aligned}$$

二分一個r$r$時，每個二元組的valuei?r?costi$value_i-r/cdot cost_i$ 都可以求出，設其為weighti$weight_i$，現在的目標就是找到一組{xi}$/{x_i/}$使得∑wighti?xi$/sum wight_i/cdot x_i$最大（即求max{f(r)}$max/{f(r)/}$）。怎么找到這一組{xi}$/{x_i/}$，或者直接求得max{f(r)}$max/{f(r)/}$呢？具體問題具體分析，經常借助最短路算法判斷是否存在負環。下面會有幾道例題。

01分數規劃還會與其他問題結合，如網絡流等。

Dinkelbach$Dinkelbach$算法

這個算法我是在寫這篇文章時才知道的。

思考上述二分算法的思路，設二分過程中某一個二分值為r$r$，二分時的判斷條件是max{f(r)}$max/{f(r)/}$的正負性，而這個r$r$除了讓L$L$右移或者R$R$左移就沒有用了。現在思考某一過程中r$r$與max{f(r)}$max/{f(r)/}$能否再被利用。 二分時，假如max{f(r)}>0$max/{f(r)/}>0$這說明最優解在當前r$r$的右側，于是讓L=r$L=r$，但是，如果將L$L$移動到max{f(r)}$max/{f(r)/}$對應直線的橫截距呢？顯然，算法會變得更快。這個思想就是Dinkelbach$Dinkelbach$算法的內涵。 Dinkelbach$Dinkelbach$實質上是一種迭代算法，基于這樣的思想：不去二分答案，而是先隨便給定一個答案，然后根據更優的解（max{f(r)}$max/{f(r)/}$對應直線的橫截距）不斷移動答案，逼近最優解。理論上它比二分快些。 在這個算法中，一般將r$r$初始化為0$0$。

兩種算法的比較

Dinkelbach$Dinkelbach$算法的弊端就是需要保存解。這兩個算法解決統一問題實際上都有可能快些。 我覺著我一般還是用二分。。。。

例題

只先寫了文章，還差相關題目的分析，代碼等。得等個一兩天再。2017-02-06留。

Poj2976Dropping tests

問題模型2

最優比率生成樹

帶權無向圖G$G$， 對于圖中每條邊ei$e_i$， 都有valuei$value_i$和costi$cost_i$，現在求一棵生成樹T$T$，最大（小）化∑valuei∑costi,ei∈T$/frac{/sum value_i}{/sum cost_i},e_i/in T$

解決方法

套用01分數規劃模型，如果ei∈T$e_i/in T$則xi=1$x_i=1$否則xi=0$x_i=0$。

二分法

二分答案r$r$，邊賦值weighti=valuei?r?costi$weight_i = value_i-r/cdot cost_i$，因為是生成樹，邊的數量確定，那么max{f(r)}$max/{f(r)/}$需要選取前|G|?1$|G|-1$大的weighti$weight_i$，也就是求最大生成樹，按最大生成樹權值的正負性就可以二分了。

Dinkelbach$Dinkelbach$算法

當前答案r$r$，邊賦值weighti=valuei?r?costi$weight_i = value_i-r/cdot cost_i$，同樣求最大生成樹，找到max{f(r)}$max /{f(r)/}$對應的邊集{xi}$/{x_i/}$，也就是最大生成樹的邊集。對這個邊集找橫截距當做下一次答案。橫截距是啥呢？ f(r)=B?A?rrr=0=B/A=∑valuei?xi∑costi?xi $$/begin{aligned}f(r)=B-A/cdot r &= 0 // r&=B/A //r &=/frac{/sum value_i /cdot x_i}{ /sum cost_i/cdot x_i} /end{aligned}$$

例題

poj2728Desert King(最優比率生成樹)

問題模型3

最優比率環

給定有點權和邊權的圖，求一個環，使得環的點權和與邊權和的比值最大。

解決方法

套用01分數規劃模型，點權為valuei$value_i$，邊權為costi$cost_i$，一個環為C$C$ 問題要求最大化∑valuei∑costi,(i∈C)$/frac{/sum value_i }{/sum cost_i},(i/in C)$ 邊數和點數是相同的，但上述式子表述不是很正確，意會即可。 若答案為r?$r^*$，那么任意一個環 ∑valuei∑costi∑valueir??∑costi?∑valuei≤r?≤r??∑costi≥0 $$/begin{aligned}/frac{/sum value_i }{/sum cost_i}&/le r^* ///sum value_i&/le r^*/cdot /sum cost_i //r^*/cdot /sum cost_i -/sum value_i &/ge 0/end{aligned}$$

二分法

設當前答案r$r$， r<r?$r < r^*$，至少存在一個環，r?∑costi?∑valuei<0$r /cdot /sum cost_i -/sum value_i < 0$，即存在負權回路（將邊權設為r?costi?valuei$r/cdot cost_i-value_i$，不是提前算出，而是在更新路徑的時候從哪個點訪問到這條邊的就將這條邊設為相應點權與邊權的對應值）； r≥r?$r/ge r^*$，則不存在負環。

求負環可以用Bellman-Ford，但是比較慢，一般用spfa算法求負環 具體判斷方法為，一個點不能入隊n$n$次，否則有負環；一條最短路徑長度不能到n$n$，否則有負環。兩個判斷方法可以同時使用。

Dinkelbach$Dinkelbach$算法

如果用這個算法需要記錄下來一個負環，實現還是能實現的，但是沒有二分+spfa好寫。

例題

poj 3621(最優比率環)

問題模型4

最大密度子圖

這個問題會寫在網絡流總結中。

參考資料

【1】KirisameMarisa - NYIST 914Yougth的最大化【二分搜索/Dinkelbach算法】 【2】PerSeAwe - ［Algorithm］01分數規劃