1

我有一个图表，其中我所有的节点之间都有一个计算出的距离。

现在，我想从我的 startNode 开始，然后找到计算值最低的路径，只要该路径有 X 个唯一节点。把它想象成一张地图：我们从巴黎开始，想去 3 个城市旅行。我想找到距离巴黎总共 3 站的路径，计算值最低。

我正在考虑实施修改后的 Dijkstra 算法，这通常会给我到最终目的地的最短距离，然后我的最终目的地是所有 X_level_out 目的地，这应该给我一个类似 O(nodes^level) 的运行时间。

这有道理吗？还有其他建议吗？

4

1 回答 1

1

给定一个加权无向图 G(V,E)，以及 V 的一个集合 S 子集，找到跨越 S 中节点的最小成本树。这个问题在文献中被称为施泰纳树问题。这个问题是NP完全的，这意味着没有已知的多项式算法可以找到问题的精确解。但是，有些算法可以在指数时间内解决 Steiner 问题（O(2^N) 或 O(2^M)）。

朴素或最短路径算法。

Find the Shortest path tree from one participant node to the rest of the graph. 
Prune the parts of the tree that do not lead to a participant.

复杂度 O(N^2)，CR = O(M)。

贪心或最近参与者优先算法。（Takahashi，Matsuyama 1980）从一个参与者开始。

Find the participant that is closest to the current tree. 
Join the closest participant to the closest part of the tree. 
Repeat until you have connected all nodes.

复杂度 O(MN^2)，CR = O(1)，实际上 CR <= 2。

Kou、Markowsky 和 ​​Berman 算法（KMB 1981）。

1. Find the complete distance graph G' 
  (G' has V' = S , and  for each  pair of nodes (u,v) in VxV there is an edge with weight equal to the weight of the min-cost path between these nodes p_(u,v)  in G) 
2. Find a minimum spanning tree  T' in G' 
3. Translate tree T' to the  graph G: substitute every edge of T', which is an edge  of G' with the corresponding path of G. Let us call T the result of the translation. 
4. Remove any possible cycles from T.

复杂度 O(MN^2)，CR = O(1)，实际上 CR <= 2。

于 2013-05-18T09:46:51.043 回答