1

私の単純なプロジェクトで使用するために、私は少し封鎖しました。

グリッドには、「壁」と「オープンスペース」という一連のポイントがあります。グリッドの外側のスペースは壁と見なされます。このグリッドには任意の数の開いているポイントがあり、グリッド内の1つの特定のブロックをオープンスペースから壁に変更した場合に、接続されているポイントが変わるかどうかを判断する必要があります。

これを行うための効率的な方法は何ですか？

例 。

例：緑の正方形が壁またはオープンスペースの場合、赤い正方形の間のパスの有無が変わるかどうかを判断します。（追記：ひどいグリッドについて心からお詫び申し上げます）

今のところ、ある種のセルオートマトンが最適だと思いますが、よくわかりません。私は以前にパスファインディングを見たことがありますが、この種の問題に巻き込まれたものは実際には見たことがありません。

注意：パスの長さは関係ありません（最大長はわかっています）。パスは存在する必要があります。したがって、ポイント間の最適なパスを見つける必要はありません。

ああ、それは問題ではないはずですが、私はこのプロジェクトをJavaで書いていますが、任意の言語（または擬似コード）またはアルゴリズムの英語の説明で十分です。（私はほとんどのCurly Bracket言語を知っていますが、HaskellとLISPは限られていますが、すべて知っています。）

4

1 に答える 1

1

これは最善の解決策ではないかもしれませんが、解決策は次のとおりです。

  • 接続されているすべてのポイントに同じ番号が割り当てられるまで、グリッドを塗りつぶすことから始めます (接続されているとは、隣接または同じ番号の「島」を意味します)。これを行うには多くの方法がありますが、どれも複雑すぎる必要はありません。最初のノードから最後のノードまでグリッドを単純に実行し、まだ満たされていない場合はそれを埋めることがオプションです。
  • 隣接するノードまたは同じ番号のノード間のパスは、島を 2 つに分割する壁を配置した場合にのみ切断できます。したがって、壁を追加するときは、そうであるかどうかを確認してください。これは、A* を使用して合理的に効率的に確認できます。新しい壁に隣接する 4 つのノードすべてから、それらが同じ番号を持っている場合でも、互いに到達できることを確認します。
  • 壁が原因で分割が発生しなかった場合: パスが壊れていない場合は、すべて同じです。
  • 壁が原因で分割が発生した場合: グリッドを再度塗りつぶし、2 つのノードが隣接しているか、同じ番号にあるかどうかをもう一度確認します (チェックしているブロックが常に開いている場合は、常に隣接しています)。

この方法ですべてのノードをチェックすることはかなり効率的です (n*n/2-n/2 パスをチェックするには O(n^2) かかると思います)、必要な島だけが作成されれば、新しい壁を追加することはより効率的になるかもしれませんフラッド フィルを使用しませんが、実装がより困難になる可能性があります。

于 2010-10-04T22:09:43.993 に答える