2

迷路用の DFS および BFS ソルバーを作成しています。

C ++でグラフを実装する方法と、隣接するセルがいくつ空であるかに応じて複数の子を持つノードを実装する方法について、私は知識がありません(かなりひどい知識です)。

C++ でグラフを実装する初心者に優しい方法を何日も探していました。文字通り。日々。

私が見つけたものはすべて私には複雑すぎました。理解できない高度なものしか見つかりませんでした。私が見つけた最も初心者に優しいサイトはこれですが、このサイトでは C を使用しており、C++ には既に Stack クラスがあると私が信じているスタックを実装しています。このサイトでさえ、理解に苦しむ。

既に作成されたライブラリを使用することに関する私の問題は、グラフとノードを実際に実装する方法を決して学べないことであり、それは主題に関する私の知識を大きく損なうと思います.

これを入力するときにブースト ライブラリをダウンロードしているので、ライブラリを使用する場合は、おそらくこれを使用します。

したがって、グラフとノードの作成方法を決して学習せず、boost ライブラリ (またはその他のライブラリ) を使用するだけでよいでしょうか。それとも、DFS アルゴリズム、特に迷路のグラフとノードを構築する方法を学習するための実際の初心者に優しい方法はありますか?

4

2 に答える 2

2

DFS と BFS は単純なアルゴリズムであるため、ライブラリから取得する必要はありません。はい、それらはBGLで実装されていますが、このライブラリは主に、より複雑なアルゴリズム用です。また、BGL はいくつかのグラフ表現を提供しますが、実際には、独自のグラフ データ構造を使用しながら BGL のアルゴリズムを適用できるように実装されています。ただし、別の方法として、グラフとアルゴリズムを自分で実装してください。

DFS および BFS の場合、別のエッジ タイプを必要としないため、グラフの実装はかなり簡単です (エッジが指す場所以外にエッジ用に追加のデータが保存されることはありません)。グラフを実装するには、(ノードが訪問されたかどうかを示す) フラグを格納するノードタイプと、ターゲット ノードのインジケーターを含むコンテナーが必要です。ほとんどの場合、コンテナーはターゲット ノードへのポインターを格納するだけです。これは、もちろん、指しているノードがメモリに置かれたままであることを意味します。

std::deque<Node>端の 1 つでのみノードを追加/削除する場合、またはグラフstd::list<Node>内の任意の場所にノードを追加/削除できる場合 (DFS および BFS を実装するために、最後に実行できるノードのみを追加する場合、つまり、私は一緒に行きますstd::deque<Node>）。ノードの内部では、std::vector<Node*>. 2 つのノード間にエッジを挿入するときは、2 つのノードを見つけて、ソース ノードへのポインターをstd::vector<Node*>ターゲットに追加するだけNodeです。グラフが無向の場合はstd::vector<Node*>、両方のノードにポインターを追加します。

ところで、私は DFS や BFS を「人工知能」とは呼びません。また、C++ ソリューションを探しているようです。つまり、C タグの場所も間違っているようです。

于 2013-11-10T13:22:09.587 に答える
0

Node を複雑な構造として実装する必要はないようです。ノードが迷路の単なるセルを表す場合、特定のセルを識別するために整数を使用できます。

迷路が MxN サイズの場合、長さ MxN のノードの配列があります。

ノード間の隣接関係を表すには、隣接行列 (十分に小さいグラフの場合は問題ありません) または隣接リスト (各ノードが 4 つ以下の隣接ノードを持つことができるため、この場合はより効率的です) を使用できます。

Google で隣接表現について簡単に検索できます。

したがって、これは、これらのアルゴリズムを実装するために複雑なものを本当に必要としない場合です。必要なのは配列のみです (ただし、STL のベクター コンテナーを使用する方が実際には優れています)。BFS には STL のキュー コンテナーを使用します (DFS はスタックを使用しますが、スタックを明示的に使用する再帰を使用できます)。

于 2013-11-10T13:40:20.880 に答える