バックトラッキング法とは？
バックトラッキング法とは、解の候補を順に試していき、条件に反すると分かった時点でその先の探索を打ち切って直前の分岐へ戻り、別の候補を試す探索手法。深さ優先探索に「見込みのない枝を切る（枝刈り）」を加えたもので、全通り試すより探索空間を大幅に減らせる。
ばっくとらっきんぐほう
バックトラッキング法の意味
解の候補を順に試していき、条件に反すると分かった時点でその先の探索を打ち切って直前の分岐へ戻り、別の候補を試す探索手法。深さ優先探索に「見込みのない枝を切る（枝刈り）」を加えたもので、全通り試すより探索空間を大幅に減らせる。
バックトラッキング法の具体例
数独で、あるマスに1から順に数字を置き、同じ行や列に重複が生じた時点で次の数字へ移る。すべての数字が置けなければ1つ前のマスへ戻ってやり直す。8クイーン問題や迷路の解法も同じ考え方。
バックトラッキング法は試験でどう引っ掛けられる？
枝刈りをしても最悪の場合は全探索と同じ計算量になり得るため、「必ず高速」とは言えない。分岐限定法（最良値の見込みで枝を切る最適化手法）と混同しないこと。
バックトラッキング法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。