0

以下は、ハッシュ マップに保存したデータ セットです。2 つの値の間の最短パスを見つける必要があります。

9244, 4322, 4886, 5989, 8598, 9979, 1447, 9657
8598, 6752, 7146, 1951, 660, 1447, 7779
568, 1951, 4886, 2570, 9026, 9489, 7779
6752, 3424, 1977, 4746, 9657
77

ハッシュ マップのキー値は各行の最初の値で、残りは 9244 の想定される "友達" です (いずれの場合も同じ)。

私はこの形式でハッシュテーブルに保存しました: hashmap(key, array)、ここで:

  • キーは例えば 9244 です
  • 配列は[4322、4886、5989、8598、9979、1447、9657]を保持します

2 つのキー間の最短経路を見つける方法は?

4

2 に答える 2

1

私があなたの質問を正しく解釈するならば、あなたは有向グラフでの最短経路問題について話している。

  • 整数から始めて、マップする整数の配列を取得します。
  • これらの整数のそれぞれが、新しい配列の鍵になります。
  • それらのパスをたどって、最短のパスを見つけてください。

グーグル検索をしてウィキペディアのページを見ると、あなたを助けるたくさんのコードサンプルとアルゴリズムを見つけることができるでしょう。

Peter Smitが述べたように、A*アルゴリズムはこの問題の一般的なアルゴリズムです。その他には、ダイクストラ法とベルマンフォード法が含まれます。

于 2009-04-23T07:21:06.310 に答える
0

A*アルゴリズムを実装できます。最初にこれからグラフを作成してから、ウィキペディアページの擬似コードに従うことができます。

于 2009-04-23T07:19:37.280 に答える