バックトラッキングとは？

バックトラッキングとは、解の候補を順に構成していき、途中で条件を満たさないと分かった時点でその先を打ち切って直前の分岐へ戻る探索法。深さ優先探索に「枝刈り」を組み合わせた形で、組合せ問題の全解列挙や充足解の発見に使う。

ばっくとらっきんぐ

高度試験・午前I（全区分共通）の頻出用語／午前I（全区分共通）

バックトラッキングの意味

解の候補を順に構成していき、途中で条件を満たさないと分かった時点でその先を打ち切って直前の分岐へ戻る探索法。深さ優先探索に「枝刈り」を組み合わせた形で、組合せ問題の全解列挙や充足解の発見に使う。

8クイーン問題では、駒を1列ずつ置きながら既存の駒と利きが重なった瞬間に置き直す。数独ソルバや部分和問題、迷路の解の列挙も同じ骨組みで書ける。

枝刈りは平均的な速度を改善するだけで、最悪計算量は全探索と変わらない点に注意。また「戻る」処理は状態を元に戻す操作を伴うので、更新した変数の復元漏れがバグの温床になる。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。