問題タブ [breadth-first-search]

DFS と BFS の違いは理解していますが、どちらを使用するのがより実用的か知りたいですか?

DFSがBFSを打ち負かし、その逆の例を誰か挙げてもらえますか?

まず、これはゴーストではなくパックマンの AI です。

アイコンの周りでパックマンを再生する Android ライブ壁紙を作成しています。画面タッチによるユーザーの提案をサポートしていますが、ゲームの大部分は AI によってプレイされます。ゲームのプログラミングはすべて 99% 完了しましたが、パックマン自身の AI はまだ非常に弱いです。パックマンの次の移動方向を判断するための優れた AI の開発について、助けを求めています。

私の最初の計画はこれでした：

1. 各方向のスコア カウンターをゼロの値で初期化します。
2. 現在の位置から開始し、BFS を使用して、可能な最初の 4 つの方向をキューに追加することで外側にトラバースします。

3. 要素をキューからポップし、まだ「見られていない」ことを確認し、それが有効なボード位置であることを確認し、対応する初期方向スコアに現在のセルの値を以下に基づいて追加します。

   1. ドットあり: プラス 10
   2. パワーアップあり：プラス50
   3. 果物がある: プラス果物の値 (レベルによって異なります)
   4. ゴーストがパックマンに向かって移動している: 200 を引く
   5. ゴーストがパックマンから離れていく: 何もしない
   6. ゴーストが垂直に移動している: 50 を引く
   7. セルまでのステップ数に基づくパーセンテージをセルの値に掛けます。最初の方向からのステップが多いほど、セルの値はゼロに近づきます。

   現在のセルから可能な 3 つの方向をキューに入れます。

4. キューが空になったら、4 つの可能な最初の方向のそれぞれについて最高スコアを見つけ、それを選択します。

紙の上ではいいように聞こえましたが、幽霊はパックマンを非常に急速に取り囲み、パックマンは同じ2つまたは3つのセルで前後にぴくぴく動き、1つが到達するまで. ゴーストの存在の値を調整しても役に立ちません。私の最も近いドット BFS は、ゲームが終了する前に、少なくともレベル 2 または 3 に到達できます。

適切な AI を開発するためのコード、考え、および/またはリソースへのリンクを探しています。できれば前者の 2 つです。今週末には市場に出したいので少し急いでいます。どんな助けでも大歓迎です。

参考までに、これは手動でGameDev.StackExchangeにクロスポストされました。

DAG（Direct Acyclic Graph）のBFSフォレストを生成したい。つまり、Treeクラスは、バイナリツリーではなく、一般的なツリーである必要があります（つまり、フォレストを生成するときに、ノードが持つ子の数を事前に知ることはできません）。ほとんどのコードは以下に記述されて示されていますが、私は一生の間、私を逃れる一行が欠けています！

My Treeクラスには、値パラメーター、親参照、および子のリストが格納されます。私の問題は、次のツリーノードを参照することです。未訪問のすべてのネイバーを現在のノードの子として追加したら、次のノードに移動するにはどうすればよいですか？

編集：

それで、それはこのように見えるでしょうか？

再帰呼び出しはどこに行きますか？

上記の投稿されたコードは、私のレベル オーダー トラバーサル コードです。このコードは私にとってはうまく機能しますが、私が気に入らないことの 1 つは、明示的に初期化temp_node = NULLしているか、ブレークを使用していることです。しかし、それは私には良いコードではないようです。

これよりもきちんとした実装はありますか、またはこのコードをより良くするにはどうすればよいですか?

私は8パズルの問題を解決するためにスキームでbfsを実装することを検討していました.これは私がこれまでに持っているコードです(デバッグできないエラーを与えます)::

両方を使用して、単一のソースから最短パスを見つけることができます。BFS は で実行されますO(E+V)が、ダイクストラは で実行されO((V+E)*log(V))ます。

また、ダイクストラがルーティング プロトコルとよく似た方法で使用されているのを見てきました。

では、BFS が同じことをより高速に実行できるのに、なぜダイクストラのアルゴリズムを使用するのでしょうか?

各ノードが無向の方法で別のノードにリンクする何百万ものノードのグラフを保存したいと考えています (ポイント A から B、自動的に B は A をポイントします)。可能な解決策として Neo4j、OrientDB を検討しましたが、それらは有向グラフに向けられているようです。

他の NoSQL DB (Redis、CouchDB、MongoDB など) のどれがこのようなものに最適で、どのように実装できるか教えていただけますか? プロパティのない (リンクされた要素のみを提供する) 幅優先クエリを 2 つの深さレベルで作成したい (A<->B、B<->C、C<->D を持ち、A をクエリすると B が返されるはず)および C で、D ではありません)。

これは在宅ワークではありません。ツリートラバーサルでいくつかの新しい質問を考えていましたが、これは非常に明白であるように思われるので、解決することを考えました。

質問は、BFS のようなレベル オーダー トラバーサルに非常に似ています。BFS では通常、ツリーの各レベルで左から右に移動しますが、ここでレベル i で左から右に移動する場合、レベル (i-1) と (i+1) は右から左に移動する必要があります。

例えば：

通常の BFS では、2、7、5、2、6、9、5、11、4 を出力します。

しかし、私は出力するソリューションを探しています: 2, 5, 7, 2, 6, 9, 4, 11, 5

私は解決策を思いつくことができます。しかし、私は誰かが私のものよりも良い解決策を思いつくかどうかを見たい. 特に、スペースの複雑さ (スタック サイズ) の最適化も検討しています。

C++言語に合わせてロジックを入力してください。ソリューションでコンテナーや STL を使用していない場合は、非常にありがたいです。

ここのコメントに基づいて、2 つのスタックを使用したソリューションを考え出しました。私の解決策は以下の通りです。

• スタック S1 と S2 を作成し、キュー Q を作成します。キュー Q は最終的な ans を保持します。
• スタック (S1 または S2) をプッシュする前に、まずそれをキュー Q に入れることに注意してください。
• スタック s1 から何をポップしても、その (最初の) 右の子と (次に) 左の子を (この順序で) スタック s2 にプッシュします。（ポイント2を覚えておいてください）
• スタック s2 からポップするものは何でも、その (最初の) 左の子と (次に) 右の子を (この順序で) スタック s1 にプッシュします。（ポイント2を覚えておいてください）
• 1 つのスタックからポップし、両方のスタックが空になるまで別のスタックにプッシュします。Queue の最終エントリは ans になります。

私には問題ないようです（そうでない場合はお知らせください）。しかし、他に可能な解決策があるかどうかはまだ疑問です（これよりも優れています）。

Boost Graph Libraryに含まれている幅優先探索アルゴリズムを使用して、独自のバージョンの連結成分検出を作成しようとしています。祖先（現在の頂点の検出につながる頂点）頂点にアクセスする必要があります。現在の頂点のコンポーネント番号を設定するための訪問者のdiscover_vertexコールバック。とにかく簡単にできますか？

次のグラフについて考えてみます。

ソースノードからターゲットノードへのすべての可能なパスを列挙する方法を見つけようとしています。たとえば、AからEまで、次のパスが考えられます。

ACDEの場合、パスの1つはエッジF3を使用し、もう1つはエッジF5を使用するため、実際には2つのパスがあることに注意してください。また、AとCの間にサイクルがあるため、パスの数が無限になる可能性がありますが、この目的のために、ソースからターゲットへのパスでノードが繰り返されないパスにのみ関心があります。

深さ優先探索（DFS）アルゴリズムを作成しましたが、問題は、2つのノード間に複数のエッジがある場合（上記のエッジF3とF5など）、それを処理する方法がわからないことです。A C D E私のアルゴリズムはパスを戻すだけA C Eで、他のパスは返しません。の場合A B C E、理由は理解できます。Aから開始してCに移動し、それらのパスを構築しますが、DFSがノードBに戻ると、Cに移動しようとしますが、Cはすでにアクセスされているためです。止まります。

とにかく、これを行う方法があるのか​​、それともこれがNP完全であるのか疑問に思いました。

私のDFSをご覧になりたい場合は、以下のコードをご覧ください（マクロの乱用については申し訳ありませんが、コンテストプログラミングで使用しているので、少し習慣になっています）。

出力：