1

すべてのノードが互いに計算された距離を持っているグラフがあります。

ここで、startNode から開始し、パスに X 個の一意のノードがある限り、計算値が最も低いパスを見つけたいと考えています。これを地図と考えてください。パリから始めて、3 つの都市を旅したいと考えています。計算値が最も低く、パリから合計 3 駅離れた経路を見つけたいと考えています。

通常、最終目的地までの最短距離を提供する修正されたダイクストラのアルゴリズムを実装することを考えています。その後、最終目的地はすべて X_level_out の目的地であり、 O(nodes^level) のような実行時間が得られます。

これは意味がありますか？他の提案はありますか？

4

1 に答える 1

1

重み付き無向グラフ G(V,E) と、V のセット S サブセットが与えられた場合、S のノードにまたがる最小コスト ツリーが見つかります。この問題は、文献ではシュタイナー ツリー問題として知られています。問題は NP 完全です。つまり、問題の正確な解を見つける既知の多項式アルゴリズムはありません。ただし、シュタイナー問題を指数時間 (O(2^N) または O(2^M)) で解くアルゴリズムがあります。

Naive または Shortest Paths アルゴリズム。

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)。

貪欲または最も近い参加者優先アルゴリズム。(高橋、松山 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 に答える