バックトラッキングとは？
バックトラッキングとは、候補を1つずつ試しながら解を組み立て、条件を満たさないと分かった時点で直前の選択まで戻って別の候補を試す解法。深さ優先探索に「見込みが無ければ引き返す」枝刈りを加えたもので、組合せ問題やパズルの求解に用いられる。
ばっくとらっきんぐ
バックトラッキングの意味
候補を1つずつ試しながら解を組み立て、条件を満たさないと分かった時点で直前の選択まで戻って別の候補を試す解法。深さ優先探索に「見込みが無ければ引き返す」枝刈りを加えたもので、組合せ問題やパズルの求解に用いられる。
バックトラッキングの具体例
8王妃問題では、1列目から順に王妃を置き、既に置いた駒と利きが重なる位置は選ばない。どの行にも置けなくなったら1つ前の列に戻して別の行を試す。迷路の探索でも、行き止まりに当たったら分岐点まで戻って別の道を選ぶ。
バックトラッキングは試験でどう引っ掛けられる？
全ての組合せを機械的に試す総当たりと混同されやすいが、途中で見込みが無い枝を切り捨てる点が違う。ただし最悪の場合は総当たりと同じ計算量になり、必ず速くなるわけではない点に注意。
バックトラッキングと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。