1

グラフ上の 2 つのノードが指定された場合に、指定されたホップ数を使用するそれらの間のルートを見つけるアルゴリズムはありますか? どのノードも他のノードに接続できます。

現時点でのポイントは 2D 空間にあるため、グラフが最適なアプローチかどうかはわかりません。

4

3 に答える 3

2

反復深化 DFSを試しましたか?

于 2009-10-21T20:41:26.560 に答える
1

ばかげたアプローチ:(データ構造はスタックの配列です）。これは基本的に幅優先探索（BFS）を深さNまで実行しますが、ループが許可されている場合（明確にしなかったが、そうだと思います）、訪問したノードをそれ以上の検索から除外しません。

  1. インデックス0（インデックス=深さ）で配列に格納されているスタックの開始ノードをプッシュします

  2. レベル/インデックス「l」ごとに0-N：

    レベル「l」に格納されているスタック上の各ノードについて、そのすべての隣接ノードを見つけて、レベル「l+1」に格納されているスタックにプッシュします。

    重要：タスクでループを含むパスを検索できる場合は、追加したノードに既にアクセスしたかどうかを確認しないでください。ループが許可されていない場合は、訪問したノードのハッシュを使用して、ノードを2回追加しないようにします**

  3. レベル「N-1」を終了したら停止します。

  4. インデックス「N」でスタックするために追加したすべてのノードをループして、宛先ノードを見つけます。見つかった場合：成功、そうでない場合、そのようなパスはありません。

「すべてのノードを接続できる」とは、完全接続グラフを意味する場合、実際にノードにアクセスすることを含まない数学的な答えが存在することに注意してください。

（ただし、数式が長すぎてStackOverflowのテキスト入力フィールドに書き込むことができません）

于 2009-10-21T20:49:06.637 に答える
1

ノードがホップの観点からルートを見つけようとしている場合、グラフはおそらく正しいアプローチです。ただし、特に「任意のノードを他のノードに接続できる」に関して、あなたが何をしようとしているのか、および制約が何であるかを理解しているかどうかはわかりません..これは少しオープンエンドのようです。

ただし、それを無視します。いくつかのグラフ表現で：

最初のノードから開始し、そこから深さ優先検索を実行し、(a) 取得したホップ数が指定した数よりも大きい場合、または (b) 2 番目のノードに到達した場合に検索を終了するように見えます。これにより、2 つのノードを (最大で) その数のホップで接続する最初の (唯一ではない) パスが決定されます。

正確に指定されたホップである必要がある場合、ホップを超えた場合は検索の分岐を終了し、2 番目のノードにも到達した場合は成功して終了します。

于 2009-10-21T20:30:58.083 に答える