作者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