\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年12月7日 星期三

[ 0-1 Fractional Programming Dinkelbach algorithm ] 0-1分數規劃

【定義】

給你兩個數組,$benefit[i]$表示選$i$的利潤、$cost[i]$表示選$i$的花費。
如果選$i$,定義$x[i]=1$否則$x[i]=0$,通常題目會給你選擇的限制條件,像是必須是一顆生成樹之類的,這裡就把它忽略掉
我們的目標是要求$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}$的最大值。

【分析】

先不管最大化問題,令$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}=L$
可以把式子改寫成$(\sum{benefit[i] \times x[i]})-L \times (\sum{cost[i] \times x[i]})=0$
分離參數得到$\sum{(benefit[i]-L \times  cost[i]) \times x[i]}=0$
只要知道$L$,$(benefit[i]-L \times  cost[i])$是直接可以求出來的,先記他為$d(i,L)$吧
那可以設$f(L)=\sum{d(i,L) \times x[i]}$

我們的目標變成是要最大化$L$
那若存在一種$x$的選法使得$f(L)>0$能夠證明什麼呢?
$f(L)>0 \to \frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}>L$那表示存在另一個$L$會比現在的$L$還要好
那 $f(L)<0$?很明顯這種情況完全沒有意義,因為找不到這種$L$

最佳的$L$會讓所有$x$的選法都$f(L)\leq0$,只要找到這樣的$L$就說明他是最佳解了
也可以用類似的想法求最小化$L$,這裡就不贅述了。

【解法】

根據剛剛找出來的性質$f(L)$是單調性的,我們可以二分搜$L$,然後驗證是否存在一組解使得$f(L)>0$,這很簡單就不附code了。
另一個有效率的算法是Dinkelbach,他跟二分搜不一樣的地方是他要去求解,在驗證解跟求解的複雜度一樣的時候Dinkelbach是會比較快的,但有時候求解的複雜度會比驗證解的複雜度還要高,因此要看情況使用
以下附上虛擬碼:

常見的題型有:最優比率環、最優比率生成樹、最大密度子圖(有flow解)等

2016年12月6日 星期二

[ dominator tree ] 有向圖的支配樹

dominator tree,中文名稱叫支配樹
給一張有向圖$G$,我們從其中一個點$r$出發到$y$的所有路徑中,一定會經過點$x$,就稱$x$是$y$的必經點;我們把距離$y$最近的必經點稱為最近必經點,記為$idom(y)$。
支配樹上的有向邊$(u,v)$滿足$idom(v)=u$,那對於一個點$y$,$y$的所有必經點就會是支配樹上$r$到$y$路徑上的所有點。
這個東西可以求有向圖的割點、橋(在每個邊加入虛擬點)等等。
注意code裡的$idom$跟我定義的不一樣
我是看這份講義的偽代碼寫出來的: