0

そのため、それぞれが異なる重みを持つ複数のターゲット エンドポイントへの最短ルートを事前に計算する単純なパスファインディング アルゴリズムがあります。これは、エッジの重みが異なりますが、1 つのエンドポイントと各エンドポイントの間にノードを持つことと多少同じです。使用するアルゴリズムは単純な拡散アルゴリズムで、1 次元では次のようになります (| は壁を意味し、- は空間を意味します)。

  • 5 - - - 3 | - - - 2 - - - - 2
  • 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
  • 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
  • 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
  • 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
  • Done. Any remaining rooms are unreachable.

したがって、次のような事前計算されたパスファインディング ソリューションがあるとします。5 のみがターゲットです。

- - - - | 5 4 3 2 1 -

壁を部屋に変えたら。再計算は簡単です。すべての距離ノードを再処理するだけです (ただし、既に存在するノードは無視します)。ただし、4が壁になった場合の効率的な処理方法がわかりません。明らかに結果は次のとおりです。

- - - - | 5 | - - - -

ただし、2d ソリューションでは、4 を効率的に処理する方法がわかりません。4 が 5 に依存しているため、再計算が必要であることを簡単に保存できますが、新しい依存関係と値を安全に判断するにはどうすればよいですか? 配列全体を再計算するのは避けたいと思います。

何もないよりはましな解決策の 1 つは、(大まかに) 5 から 5 のマンハッタン距離を持つ配列要素のみを再計算し、ソース情報を維持することです。これは基本的に、選択した領域にアルゴリズムを再適用することを意味します。

4

1 に答える 1

0

うーん。私が思いついた 1 つの解決策は次のとおりです。各ノードから最も速く到達できるノードのリストを保持します。ノードが壁になった場合は、到達可能なノードを確認し、対応するリストを取得します。次に、標準アルゴリズムを使用してそれらすべてのノードを再チェックします。新しい距離が小さいノードに到達したら、再テストが必要であるとマークします。

マークされていないマークされたノードのすべての隣接ノードを取得し、それらにアルゴリズムを再適用します。この手法がヒットするマークされたノードは無視します。再適用されたアルゴリズムによってマークされたノードの値が増加する場合は、新しい値を使用します。

于 2009-04-02T15:48:01.693 に答える