バックトラッキング探索とは、問題を解くためのすべての選択肢を体系的に評価する探索アルゴリズムの一種です。解の候補を段階的に構築しながら進み、途中で条件を満たさない（行き止まりである）と判明した時点で直前の分岐点まで戻り（バックトラック）、別の可能性を試します。無駄な探索を減らす枝刈りを組み合わせることで、効率的に正解を見つけます。
バックトラッキング探索とは
バックトラッキング探索は、解の候補を一つずつ試して行き止まりにぶつかったら一つ前の状態に戻って別のルートを試す、試行錯誤型の探索アルゴリズムです。
詳しく解説
バックトラッキング探索は、基本的に深さ優先探索の考え方をベースにしています。問題の解をツリー構造のような選択肢の集まり（状態空間探索）として表現し、解の可能性を1つずつ深く掘り下げて検証していきます。その過程で、現在の状態が制約を満たしておらず正解に到達できないと判断された場合、それ以上深く進まずに手前の分岐点まで戻り、未検証の別の選択肢へと切り替えます。この「無駄と分かったパスを即座に破棄する」処理は枝刈りと呼ばれ、探索空間を大幅に削減して処理を高速化する重要な役割を果たします。特に人工知能における制約充足問題の解決や、パズル・ゲームの着手予測、論理プログラミングなどで広く活用されています。
具体例・使われ方
数独（ナンプレ）やNクイーン問題のようなパズルの解法が典型例です。マス目に数字を順番に入れていき、ルール違反が発生した時点で直前のマスに戻って別の数字を試します。また、AIの自動推論や計画立案システムにおいて、複数の制約条件を満たす解を見つける際にも利用されます。
似た用語との違い
全探索（総当り攻撃）との違いは、条件を満たさないと判明した時点で即座にその先の探索を中断する点にあります。全探索がすべての組み合わせを愚直に確認するのに対し、バックトラッキング探索は枝刈りを行うため大幅に効率的です。また、すべての階層を均等に調べる幅優先探索とは異なり、1つの選択肢を最後まで深く掘り下げるアプローチをとります。
注意点
問題の構造によっては、枝刈りが効果的に機能せず、最悪の場合には全探索と同等以上の計算時間がかかる可能性があります。特に状態空間探索の規模が膨大で、行き止まりの判定基準が曖昧な問題では、メモリ消費量や実行時間が劇的に増加する点に注意が必要です。