PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Single-Source Multi-Target Network

看板Prob_Solve (計算數學 Problem Solving)作者summer08818 (........)時間12年前 (2012/06/02 16:30)推噓1(1推 0噓 3→)

留言4則, 1人參與討論串1/1

目前遇到的問題,想了很久沒有適合的簡化方式想上來請教各位先進. 現在在一個平面上存在一個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