3

ですから、これはCSでMSCを取得している人にとっては古典的な質問だと思います。

N要素があり、距離もあります。次の距離の要素が3つあるとします。対称なので

A -> B == B -> A

マトリックスのように見えます：

   A,  B,  C,  
A  0, 10,  20 
B 10,  0,  30
C 20, 30,   0

私の質問は次のようになります：

  • これを効率的に保存するにはどうすればよいですか（どのデータ構造）
  • 距離の合計が最小であるリンクリストを取得するための最も効率的な方法は何ですか

この場合、最良は

B -> A -> C = 30 which equals to C -> A -> B

その他の場合：

A -> B -> C = 40 which equals to C -> B -> A

これにはBFSが適しているのではないかという印象を受けました。アマゾンの本でさえ、英語のドキュメントへのリンクは良いです...

4

2 に答える 2

4

データ構造の理想的なソリューションは、隣接リストです。

隣接リストは、単にオブジェクトのリストです（グラフ上の頂点を表します）。各オブジェクトには、隣接するエッジを持つすべての頂点と対応する重みを含むリストがあります。

ルビーでは、単純な実装は次のようになります。

vertices = {}
a = Vertex.new
b = Vertex.new

a.add(b, 10)
b.add(a, 10)

vertices[a] = a
vertices[b] = b

最短の重み付きパスを見つけるアルゴリズムは、ダイクストラ法と呼ばれます。

アルゴリズムの実行後に最短パスを取得したい場合は、トレースバックを実行できます。これは、各ノードに到達したときに、各ノードの（最適な）親を保存することによって行われます。これを行うために、訪問したノードごとにハッシュを作成して、最小のコストでそのノードにつながるノードにマップすることができます。

アルゴリズムを終了すると、再帰的なトレースバックは次のようになります。

def traceback(parent, start, node, path)
  if(start == node)
     (path + start.to_s).reverse
  else
     path += node.to_s + " "
     traceback(parent, start, parent[node], path)
  end
end
于 2010-12-24T01:28:08.023 に答える
-2

ダイクストラには、重み付きグラフをナビゲートするアルゴリズムがあると聞きました。

于 2010-12-22T23:27:18.913 に答える