Backtracking バックトラック

とてつもない数の"見込みのある解"の中から、解を探さなければならないというような問題は数多く存在します。これらの問題を解くアルゴリズムは、ある起点から出発し、特定の経路を探索することによって、解を見つけます。

しかし、多くの問題では、どのような経路が解へと導くかが不明です。このような問題を解くためには、可能な経路をすべて探索（総当り）する方法が考えられますが、探索しなければならない空間が膨大な場合には、無駄な探索を避けるためのテクニックが必須となります。

バックトラッキング Backtracking は、見込みのあるすべての探索空間を体系的（計画的）に探索する方法です。バックトラッキングでは、今いる地点からこれ以上探索が不可能と分かった時、または問題の定義によってこれ以上探索しても無駄であると断定できる時に、そこで探索を打ち切り、前の地点に戻って探索を続行します。

グラフにおける Depth First Search が、バックトラックアルゴリズムの良い例となります。

バックトラックが適用できる問題の例

• 8クイーン問題