深度最初の検索と幅優先探しの理解

Question

私はテトリスを面白いプロジェクト（宿題ではない）にしていて、コンピュータを再生できるようにAIを実装したいと考えています。私が聞いたことは、利用可能な場所を検索してから、最も賢明なドロップ位置の集計点を作成することです...

しかし、私はBFSとDFSのアルゴリズムを理解することができません。私が最もよく学ぶ方法は、それを描くことです...私の図面は正しいですか？

---

ありがとう！

Answer 1

最終的なトラバーサル結果は正しいですが、あなたはかなり近いです。しかし、あなたは細部に少し出ている。

深さの最初の検索では、ノードをポップし、訪問したとマークして未訪問の子を積み重ねます。その順番で。順序はツリーとは無関係に見えるかもしれませんが、サイクルを持つグラフがあれば、無限ループに陥る可能性がありますが、これは別の議論です。

ルートノードをスタックにプッシュした後、最初の反復を開始し、すぐにAをポップします。アルゴリズムの終了までスタックには残りません。 A、スタックD、C、Bを一度に（またはB、C、D、左から右または左から行うことができます。それはあなたの選択です）、Aを訪問したとマークします。今、あなたのスタックは、下部にD、中央にC、上部にBを持っています。

ポップされた次のノードはBです。あなたはFとEをスタックに押し込みます（私はあなたと同じ順序を保ちます）。スタックは上から下へE F C Dを持ちます。次に、Eがポップされ、新しいノードは追加されず、Eは訪問済みとしてマークされます。ループは、最終的な順序は、私はあなたと同じようにアルゴリズムを書き直してみますABEFC D.

であるF、C及びDに同じことをやって、続けます：

Push root into stack 
Loop until stack is empty 
    Pop node N on top of stack 
    Mark N as visited 
    For each children M of N 
     If M has not been visited (M.visited() == false) 
      Push M on top of stack 

私は勝ちました幅広い最初の検索のための詳細に行く、アルゴリズムはまったく同じです。違いは、データ構造とその動作にあります。キューはFIFO（先入れ先出し）であり、そのため、下位レベルのノードにアクセスする前に同じレベルのすべてのノードを参照します。

Answer 2

まず、あなたのトラバーサルは大丈夫だと思います（概要から）。私はあなたに以下のいくつかの有用なリンクを与えるつもりです。

これまで私はYouTubeでいくつかのまともな動画を見つけましたが、ここには1つ（これまでに見た中で最高のものではありません）が含まれています。http://www.youtube.com/watch?v=eXaaYoTKBlEあなたが楽しいためにそれをやっている場合は、DFSとBFSの2つのバージョンを作成し、その違いを観察するためのベンチマークを行います。また、グラフサーチャーや役に立つツールがあれば、http://www.aispace.org/downloads.shtmlからダウンロードしてください。最後にDFSとBFSのstackoverflowに関する質問http://www.stackoverflow.com/questions/687731/