如何最小化最短路径树的总成本

2018-05-29 06:06:05

我有一个具有正边权重的有向无环图。它有一个单一来源和一组目标（离源头最远的顶点）。我发现从源到每个目标的最短路径。其中一些路径重叠。我想要的是使所有边上的权重总和最小的最短路径树。

例如，考虑两个目标。如果所有边权重相等，如果他们在大多数长度上共享单一最短路径，那么优于两个大多不重叠的最短路径（树中较少的边等于较低的总成本）。

另一个例子：两条路径在它们的一小部分长度上不重叠，非重叠路径的成本很高，但长共享路径的成本较低（低综合成本）。另一方面，两条路径的大部分长度都不重叠，非重叠路径的成本较低，但短共享路径的成本较高（组合成本较低）。有很多组合。我希望找到具有最低总体成本的解决方案，给出从源到目标的所有最短路径。

换句话说，我想要最短的，最短路径的树。

这是否与任何人发出任何响铃？任何人都可以指向相关算法或类似的应用程序吗？

干杯!

这个问题（斯坦纳树）是NP-hard和最大SNP完备的，因此除非P = NP，否则既没有多项式时间算法也没有PTAS（任意接近的近似值）。

除非你知道图的一些特殊特征（例如，图是平面的，或者至少权重服从三角不等式），否则MST可以给出任意一个权重，而不是最优的权重。例如，如果您拥有所有边权为1且仅有一个目标的K_1,000,000,001，则最优解为权重1，MST权重为1,000,000,000。

如果您假定目标和源与每个目标之间的所有边缘之间的所有边缘都存在，则仍然可以通过任意因子超调。考虑上面的例子，但是将目标和源之间的边缘权重更改为2,000,000,000,000,000,000（您仍然偏离最优的十亿倍）。

当然，您可以通过遍历图来将图转换为“去除”时间O（E）左右的高权重的边权重。这加上一组目标和源的MST给出的近似比为2。

存在更好的近似比率。 Robins＆Zelikovsky有一个多项式时间算法，它的优化程度从未超过54.94％：http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik＆Chlebikova表明近似接近1.05％是NP-hard：图中的Steiner树问题：不可约性结果（doi 10.1.1.4.1339）

如果你的图是平面的，情况会更好。由于Borradaile，Kenyon-Mathieu＆Klein（建立在Erickson，Monma和Veinott之上），有一种快速算法给出了任意近似的逼近：平面图中Steiner树的O（nlogn）近似方案（doi 10.1.1.133。 4154）

如果您只有正的成本，而且您正在最小化，那么只需使用Dijkstra的算法即可。

链接地址: http://www.djcxy.com/p/907.html