Steiner Tree是一個(gè)經(jīng)典的NP-hard問(wèn)題，問(wèn)題定義不在這里重復(fù)了，主要介紹幾種近年來(lái)典型的解法思路。
Steiner Forest擴(kuò)展了Tree的定義，設(shè)置一組起始點(diǎn)集，一組終點(diǎn)集，要求任意一對(duì)起點(diǎn)-終點(diǎn)在Steiner Forest上有路徑。
Steiner Forest并不真的是一個(gè)森林的形態(tài)，應(yīng)該稱之為一個(gè)子圖。
最簡(jiǎn)單的啟發(fā)式解法是遍歷所有起點(diǎn)算Steiner Tree做合并（結(jié)果像是一個(gè)森林因此得名），但這顯然是啟發(fā)式貪婪算法，并非最優(yōu)解。
1. Directed Steiner Tree Problem
1.1 精確解
1.1.1 整數(shù)線性規(guī)劃ILP
- 線性規(guī)劃有一個(gè)優(yōu)化目標(biāo)，同時(shí)有若干關(guān)于決策變量的限制條件，求解最優(yōu)的決策變量（一個(gè)或多個(gè)）。
- 整數(shù)線性規(guī)劃要求決策變量均為整數(shù)，沒(méi)有高效的解法，但可以借用一些LP solver。
1.1.1.1 基于流的模型
- 圖中的每一條邊（即
），都對(duì)應(yīng)一個(gè)決策變量
，1代表選進(jìn)斯坦納樹，0代表未選進(jìn)。
a. 優(yōu)化目標(biāo)即為總邊權(quán)重最小，因?yàn)榻Y(jié)果是樹，所以如果是無(wú)權(quán)圖，這也等價(jià)于樹中點(diǎn)的數(shù)量最少。
b.代表邊a是否在root到終點(diǎn)x的路上。對(duì)于每一個(gè)終點(diǎn)x，有且只有一條邊從root出發(fā)，且在到達(dá)x的路上。
c. 對(duì)于每一個(gè)終點(diǎn)x，有且只有一條入邊是在root到x的路上的。
d. 從x出發(fā)的所有邊，不能再返回x。（但可以去其他終點(diǎn)）
e. 給定一個(gè)終點(diǎn)x，對(duì)于某一個(gè)中間點(diǎn)q，入邊攜帶的到x的流和出邊攜帶的到x的流總是相等的。【這里的流是說(shuō)邊是不是在root到x的路上】
然而實(shí)際上這個(gè)流的值要么是1，要么是0。這樣來(lái)保證沒(méi)有環(huán)。
f. 任意一個(gè)中間點(diǎn)，對(duì)于一個(gè)終點(diǎn)x來(lái)說(shuō)，要么是一個(gè)root到x路徑上的點(diǎn)，要么不是。
到此為止的這些限制條件可以滿足root到x一定有且僅有一條路徑。
g. 限制
h. 如果一個(gè)邊被選入Tree，那一定要負(fù)載流
1.1.1.2 基于路徑的模型
此模型需要首先把從root到所有終點(diǎn)的所有路徑全部找出來(lái)，然后建立規(guī)劃模型。
a. 總權(quán)重最小。
b. 每個(gè)終點(diǎn)至少有一條路。
c. 如果一條邊沒(méi)有被選，那么不能有通過(guò)這條邊的路徑被選。
1.1.2 Dreyfus-Wagner算法
速度較差，暫略過(guò)。
1.2 近似解
1.2.1 基于最短路的算法
當(dāng)終點(diǎn)只有一個(gè)的時(shí)候，Steiner Tree問(wèn)題變成最短路問(wèn)題，因此可從最短路算法補(bǔ)充邊
1.2.1.1 最短路合并
找所有的最短路，合并之。
很簡(jiǎn)單，但是存在一個(gè)問(wèn)題，如下圖，過(guò)于貪婪導(dǎo)致不會(huì)使用已有樹中邊。
1.2.1.2 最短束
一個(gè)束是root到某一個(gè)中間節(jié)點(diǎn)v，然后v到所有的終點(diǎn)的最短路。
中間節(jié)點(diǎn)v需要遍歷去尋找，只要root到v有路徑，v到所有終點(diǎn)有路徑，就可以嘗試構(gòu)造束。
然后選最短束即可。
-
如下圖，解決了最短路方法的一些問(wèn)題，可以利用一些中間信息，當(dāng)然代價(jià)是復(fù)雜度增加了。
image.png -
最短束也有問(wèn)題，如下圖，如果沒(méi)有合適的可達(dá)所有終點(diǎn)的中間節(jié)點(diǎn)，仍然無(wú)法利用中間信息。
image.png
1.2.2 基于最小生成樹的算法
當(dāng)整個(gè)圖的點(diǎn)全都是終點(diǎn)的時(shí)候，Steiner Tree問(wèn)題變成最小生成樹問(wèn)題（有向，從root可達(dá)其它所有點(diǎn)），因此可從最小生成樹刪除邊得到近似解。
1.2.2.1 貪婪算法
從root開始使用Prim算法， 逐一加入與已加入點(diǎn)距離最近的點(diǎn)，直到所有終點(diǎn)都加入進(jìn)來(lái)。
然后只保留到終點(diǎn)的路徑其它點(diǎn)和邊全部去掉。
1.2.3 近似算法的總結(jié)
- 最短路算法雖然簡(jiǎn)單，但是快，在小圖上表現(xiàn)已經(jīng)很不錯(cuò)了；
- 其它最短路算法復(fù)雜度提高較多，但是近似系數(shù)上沒(méi)有提升，實(shí)際近似質(zhì)量上有時(shí)不比最短路強(qiáng)很多；
- 最小生成樹速度不慢，但是近似系數(shù)是最大的，代表沒(méi)有近似比例保證，但實(shí)際近似質(zhì)量居中。
