探索木の手法のひとつ。
一旦、深さ方向に行けるところまで掘り下げてから、うまくいかないなら引き返して次の枝に移る方法。
出発点から深さ方向に進み、最下段でゴールが見つからない場合は引き返すよう探索を行う。
メリットは、深さ方面(ゴールの方面)に進んでダメなら戻って次の分岐を試すので、メモリを節約しやすいこと。
運がよければ、枝を何本も試す前にゴールにつける。
デメリットは、運が悪いと遠回りになって時間がかかることがあること。