Algorithms/SearchAlgorithm - tmura's note

深さ優先探索 (Depth First Search)

• 最大探索深さが予め決まっている場合のみ実用的だが、幅優先探索よりも早く解が見つかる
• 最短経路が見つかる保証はない
• アルゴリズムの実装にはスタックを使うとよい。すなわち、探索ツリーの走査において、現在ノードの子要素をスタックに積み（ただし訪問済みノードは除く）、次に探索するノードをスタックから取る。

幅優先探索 (Breadth First Search)

• 最短経路の発見が保証される
• アルゴリズムの実装にはキューを使うとよい。すなわち、探索ツリーの走査において、現在ノードの子要素をキューの末尾に積み（ただし訪問済みノードは除く）、次に探索するノードをキューの先頭から取る。

A*探索

• 次に調べる状態候補の各々について、評価関数を計算し、最も有利なものを選ぶ。
  • は、初期状態から候補状態を経て目標状態に至るまでの推定コスト
  • は、初期状態から候補状態に至るまでの推定コスト。通常は探索ツリーにおける候補状態の深さを取ればよいが、それが最小コストとは限らないことに注意せよ。（回り道をしているかもしれないので）
  • は、候補状態から目標状態に至るまでの推定コスト。コスト＝何らかの方法で定義された状態間の距離と考えればよい。この値が評価の要である。
• を真のコストとして、任意の状態についてが成り立っていれば、目標状態までの最短経路が見つかることが保証されている。
  • 従って、この条件を満たすをいかに作るかが重要になる。

---

Algorithms