-1

迷路を示すためにポンドとスペースの配列を返す深さ優先検索を使用して、迷路ジェネレーターを作成しました。例：

char maze[height][width] =
{
    "#########",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "#########",
};

エージェントは常に左上隅 (maze[1][1]) から開始し、右下隅 (maze[7][7]) で終了します。

Depth First Searchを使用してソルバーを作成しようとしています。

問題は、私がかなりの初心者から中級プログラマーであるため、C++ で深さ優先検索を実装する方法を理解するのに苦労しており、迷路に実装するのにさらに苦労していることです。

私はスタック、キューなどの基本的な知識を持っています。また、DFS がツリーでどのように機能するか (理論的にはほとんど) も知っていますが、主な問題は、2D 配列に格納されている迷路でこれを実装する方法です。

特に DFS を学びたいので、始めてから、他の検索戦術 (BFS など) を実装して AI を使い始めます。

編集:準備ができたコードは必要ありません!!! 迷路の疑似コードを C++ に転送する方法を理解するのを手伝ってほしい!

4

1 に答える 1

2

したがって、深さ優先検索の基本的な操作は次のとおりです。

深さ優先検索のフローチャート

これは、任意のグラフとツリーの場合と同じように機能します。ツリーは単なる特殊なケースです。迷路をツリーとして視覚化することもできます。

#########
#123#   #
#4### # #
#5#   # #
# # # ###
#   # # #
# ### # #
#   #   #
#########

木

このアルゴリズムをツリーで使用する場合と任意のグラフで使用する場合の唯一の違いは、ツリーの階層構造により、ツリー内のどのノードが訪問されたかが暗黙のうちにわかっていることです。任意のグラフを使用すると、次のような構造を持つ可能性があります。

#####
#187#
#2#6#
#345#
#####

そして、ノード 8 を調べるとき、ノード 1 を新しい訪問先として扱いたくありません。

迷路で、どのノードが訪問されたかを覚えておく 1 つの方法は、それらに'#'遭遇したらすぐにそれらを埋めることです。

エージェントの位置を表す方法、エージェントを移動する方法などはほぼ理解できましたが、主な問題は、スタックを使用してエージェントがどの場所にいたかを追跡する方法にあります。私がグーグルで見つけたものによると、訪問した場所のスタックを保持している人もいますが、スタックから位置を削除するタイミングが本当にわかりませんでした。それが私の最大の混乱です

スタック自体は、訪問した場所を追跡するために使用されません。迷路を通過した現在の「パス」のみを追跡します。行き止まりに達すると、ノードはスタックから削除されます。これらのノードは、スタックから削除されても、アクセス済みとしてマークされたままにする必要があります。これらのノードを削除すると、それらのノードも「未訪問」になる場合、検索は継続的に試行され、行き止まりを再試行する可能性があります。

最初にいくつかの小さな迷路を描き、上記のフロー チャートを使用して手作業で通り抜けることをお勧めします。これにより、アルゴリズムの理解が深まります。迷路の例を次に示します。

Start at O, finish at X

####    #####      #####     #####
#OX#    #O X#      #O#X#     #O  #
####    #####      #####     # #X#
                             #####

次に、フローチャートの各ボックスを検討し、使用するデータ、そのデータを表す方法、およびそのデータを使用してコードでボックスのアクションを実装する方法について考えます。

于 2013-11-06T19:09:19.530 に答える