第一次AIブームの時代を代表する研究分野。
最初に与えられた状態から目的の状態に至るまでの道筋を、場合分けや試行錯誤をしながら探っていくこと。
迷路を解くイメージ。
ノードを動線で繋いだ、木のような構造で表現される（探索木）。
ノードを進める順番が、道筋のパターンを表現する。
言いかえると、場合分けを通じて最も効率的な道筋を見つけるための手段。

●幅優先探索
同じ階層をしらみつぶしに当たってから、次の階層に進む方法。
最短距離の解が必ず見つかるが、一層ずつ進み、途中のノードの情報をすべて記憶に保持するため、メモリ消費が大きく記憶容量を超えてしまう危険性がある。


●深さ優先探索
出発点から深さ方向に行けるところまで掘り下げて、ゴールが見つからない場合は引き返して次の枝に移る方法。
深さ方向に進み、ダメなら戻って次の分岐を試すため、メモリを節約しやすい。
運が良ければ、枝を何本も試さずにゴールにたどり着ける。
運が悪ければ、遠回りになって時間がかかる。