如何最小化最短路径树的总成本 [英] How to minimize total cost of shortest path tree

问题描述

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

I have a directed acyclic graph with positive edge-weights. It has a single source and a set of targets (vertices furthest from the source). I find the shortest paths from the source to each target. Some of these paths overlap. What I want is a shortest path tree which minimizes the total sum of weights over all edges.

例如，考虑两个目标.在所有边缘权重相等的情况下，如果它们在大部分长度上共享一条最短路径，那么它比两条大部分不重叠的最短路径(树中更少的边缘等于更低的总体成本)更好.

For example, consider two of the targets. Given all edge weights equal, if they share a single shortest path for most of their length, then that is preferable to two mostly non-overlapping shortest paths (fewer edges in the tree equals lower overall cost).

另一个示例:两个路径在其长度的一小部分之间是不重叠的，非重叠路径的成本较高，但是长共享路径的成本较低(组合成本较低).另一方面，两条路径在其大部分长度上都是不重叠的，非重叠路径的成本较低，而短共享路径的成本较高(而且组合成本较低).有很多组合.考虑到从源到目标的所有最短路径，我想找到总成本最低的解决方案.

Another example: two paths are non-overlapping for a small part of their length, with high cost for the non-overlapping paths, but low cost for the long shared path (low combined cost). On the other hand, two paths are non-overlapping for most of their length, with low costs for the non-overlapping paths, but high cost for the short shared path (also, low combined cost). There are many combinations. I want to find solutions with the lowest overall cost, given all the shortest paths from source to target.

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

In other words, I want the shortest, shortest-path-trees.

这会和任何人打铃吗?谁能指出我相关的算法或类似的应用程序?

Does this ring any bells with anyone? Can anyone point me to relevant algorithms or analogous applications?

干杯！

推荐答案

此问题( Steiner Tree )具有NP难点和最大SNP完全性，因此，除非P = NP，否则就没有多项式时间算法或PTAS(任意近似).

This problem (Steiner Tree) is NP-hard and max SNP-complete, so there are neither polynomial-time algorithms nor PTAS (arbitrarily close approximations) unless P = NP.

除非您知道图形的某些特殊功能(例如，图形是平面的，或者至少权重服从三角形不等式)，否则MST的权重可能会比最佳值更差.例如，如果您的K_1,000,000,001的所有边权重均为1，并且只有一个目标，那么最优解的权重为1，MST的权重为1,000,000,000.

The MST can give a weight arbitrarily worse than optimal, unless you know some special feature of your graph (e.g. the graph is planar, or at least that the weights obey the triangle inequality). For example, if you have K_1,000,000,001 with all edge weights 1 and only one target, the optimal solution has weight 1 and the MST has weight 1,000,000,000.

如果假设目标之间的所有边缘以及源与每个目标之间的所有边缘都存在，则仍然可以通过任意因素超调.考虑上面的示例，但是将目标和源之间的边缘权重更改为2,000,000,000,000,000,000(与最佳值相比，您仍然相差十亿).

If you assume that all edges between targets and all edges between the source and each target exist, you can still overshoot by an arbitrary factor. Consider the above example, but change the edge weight between the target and source to 2,000,000,000,000,000,000 (you're still off by a factor of a billion from optimal).

当然，您可以通过遍历图形将图形转换为去除"时间为O(E)较高的边缘权重.这加上目标和源集合的MST，得出的近似值为2.

Of course you can transform the graph to 'remove' edge weights that are high in time O(E) or so by traversing the graph. This plus a MST of the set of targets and source gives an approximation ratio of 2.

存在更好的近似比率.罗宾斯& Zelikovsky具有多项式时间算法，该算法不会比最优算法差54.94％: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Better approximation ratios exist. Robins & Zelikovsky have a polynomial-time algorithm that is never more than 54.94% worse than optimal: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik& Chlebikova表明，接近1.05％的点是NP难的:图上的Steiner树问题:不可近似结果 (doi 10.1.1.4.1339)

Chlebik & Chlebikova show that approximating closer than 1.05% is NP-hard: The Steiner tree problem on graphs: Inapproximability results (doi 10.1.1.4.1339)

如果图形是平面的，情况会更好.由于Borradaile，Kenyon-Mathieu和A. Klein(建立在Erickson，Monma和& Veinott的基础上):一种O(nlogn)近似方案平面图中的斯坦纳树 (doi 10.1.1.133.4154)

If your graph is planar, the situation is better. There's a fast algorithm that gives an arbitrarily-close approximation due to Borradaile, Kenyon-Mathieu & Klein (building on Erickson, Monma, & Veinott): An O(nlogn) approximation scheme for Steiner tree in planar graphs (doi 10.1.1.133.4154)

这篇关于如何最小化最短路径树的总成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！