作者summer08818 (........)
看板Prob_Solve
標題[問題] Single-Source Multi-Target Network
時間Sat Jun 2 16:30:20 2012
目前遇到的問題,想了很久沒有適合的簡化方式想上來請教各位先進.
現在在一個平面上存在一個source S, 以及多個targets Ti, 以及其他不屬於source與target的其他中間點,
目標是將 S 與所有 Ti 透過其他中間點完成相連, 並且總和路徑為最短,
姑且將這問題稱作尋找Single-source Multi-target shortest path.
但目前查到的資料幾乎都是討論single-source single-target shortest path,
主要解法都是透過Network-Flow的方式去model,
將source流入流出總和設為1, target流入流出設為-1, 其他中間點流入流出為0,
路徑上的cost計算會等於 "流量f (此問題必為1) * edge長度"
如此一來必然可以找到source與target之間的最短連接方式.
但我現在遇到的問題是source流出流量不為1(因為有multi target需求),
也就是說source流出的量要等於target的總數才符合我的需求,
如此一來使用Network-Flow會遇到一個問題,
因為source流出的流量在所有edge上不保證為1,
會造成cost的計算與真實edge長度總和有誤差而導致求出的cost總和不為最短路徑.
ex: node A 與 node B 之間的 edge Xab 長度為100,
case1, 在source流出為1的情況下,且流經 Xab, cost = 1*100
case2, 在source流出為5的情況下, 有3單位流量經過 Xab, cost = 3*100
但在實際上, 因為路徑估算只看流量經過或沒經過,
也就是說case2 依然只使用了100的長度將A B相連,
在原始Netflow-work中他的cost卻將會是300, 與我的需求不符.
目前的解決方式是另外加入constraints,
一旦edge Xi 的flow大於1, 就將特定變數 Ai 設為1,
反之將 Ai 設為0,
最後計算總和cost採用 Ai * Xi長度, 如此一來這可以符合我的需求找到最短路徑解.
但付出的代價就是這問題變成ILP problem,
當target與中間點數量大的時候, 求解時間會很長,
所以來版上詢問看看各位先進有沒有其他見解, 謝謝.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.73.114
1F：推 seanwu:你的問題應該是 steiner tree，O(total*2^target) 06/03 03:11
2F：→ seanwu:approximate或heuristic的解法也有不少 06/03 03:11
3F：→ seanwu:然後，如果edge要重覆計算的話其實也不用什麼flow啦 06/03 03:12
4F：→ seanwu:就是source到每個target的shortest path加起來而已XD 06/03 03:13