0

パスの 2 次元空間 (実際には 2 次元配列) を設定する必要があります。すべてのインデックス [y][x] には、次のようなパスが含まれます。

+--  --+   +--  --+
|  ||  |   |  ||  |
|  | ==     ==++== 
|  ||  |   |      |
+--  --+   +------+

この空間をランダムに初期化できますが、他のすべての座標からすべての座標に確実に到達できる一連のパスを生成できるようにしたいと考えています。

これを解決するには、どのアルゴリズムを検討する必要がありますか?

Dijkstra や A* などの多くの経路検索アルゴリズムを学習しましたが、これらが私の問題に使用できるとは思いません。

4

1 に答える 1

0

あなたが抱えている問題は、深さ優先検索または幅優先検索のいずれかを使用して O(n) で実行できるスパニング ツリーを見つけることと本質的に同等です。

ヒント: A が B から到達可能であり、B が C から到達可能である場合、A は C から到達可能 (推移性) であることに注意してください。また、一方通行の廊下がない限り、A が B から到達可能であれば、B も A から到達可能です (再帰性)。

迷路を生成するために、スパンを生成したら、追加のエッジを追加していくつかのバリエーションを追加することができます (通常、エッジを追加すると迷路が解決しやすくなります)。スパンは接続を保証します。

于 2013-04-23T17:45:32.430 に答える