[問題] Single-Source Multi-Target Network
目前遇到的問題,想了很久沒有適合的簡化方式想上來請教各位先進.
現在在一個平面上存在一個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
推
06/03 03:11, , 1F
06/03 03:11, 1F
→
06/03 03:11, , 2F
06/03 03:11, 2F
→
06/03 03:12, , 3F
06/03 03:12, 3F
→
06/03 03:13, , 4F
06/03 03:13, 4F