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

Question

我有一个带正边权重的有向无环图。它有一个源和一组目标(离源最远的顶点)。我找到了从源到每个目标的最短路径。其中一些路径重叠。我想要的是一个最短路径树，它最小化所有边的权重总和。

例如，考虑两个目标。给定所有边权重相等，如果它们的大部分长度共享一条最短路径，那么这比两条大部分不重叠的最短路径更可取(树中的边越少，总成本越低)。

另一个例子:两条路径在它们的一小部分长度上是不重叠的，不重叠的路径成本高，但长共享路径的成本低(组合成本低)。另一方面，两条路径的大部分长度是非重叠的，非重叠路径的成本低，但短共享路径的成本高(组合成本也低)。有很多组合。鉴于从源到目标的所有最短路径，我想找到总成本最低的解决方案。

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

这是否对任何人敲响了警钟？谁能指点我相关的算法或类似的应用程序？

干杯!

Answer 1

这个问题 ( Steiner Tree ) 是 NP-hard 和最大 SNP 完全的，所以除非 P = NP，否则既没有多项式时间算法也没有 PTAS(任意接近的近似值)。

MST 可以给出比最佳值差的任意权重，除非您知道图形的某些特殊特征(例如图形是平面的，或者至少权重服从三角不等式)。例如，如果您有 K_1,000,000,001，所有边权重为 1，只有一个目标，则最优解的权重为 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 难的:The Steiner tree problem on graphs: Inapproximability results
(doi 10.1.1.4.1339)

如果您的图形是平面图，则情况会更好。由于 Borradaile、Kenyon-Mathieu 和 Klein(建立在 Erickson、Monma 和 Veinott 的基础上)，有一个快速算法可以给出任意接近的近似值:An O(nlogn) approximation scheme for Steiner tree in planar graphs
(doi 10.1.1.133.4154)