バックトラッキング法とは？
バックトラッキング法とは、解の候補を1要素ずつ決めながら探索木を深く進み、そこまでの選択では条件を満たせないと分かった時点で直前の分岐まで戻って別の選択を試す方式。全探索を体系的に行いつつ、明らかに無駄な枝を早く切り捨てられる。
ばっくとらっきんぐほう
バックトラッキング法の意味
解の候補を1要素ずつ決めながら探索木を深く進み、そこまでの選択では条件を満たせないと分かった時点で直前の分岐まで戻って別の選択を試す方式。全探索を体系的に行いつつ、明らかに無駄な枝を早く切り捨てられる。
バックトラッキング法の具体例
数独では空きマスに1から順に数字を置き、行・列・ブロックの重複が出た瞬間に戻して次の数字を試す。8クイーン問題、迷路の経路探索、正規表現の照合エンジンなども同じ骨格で実装される。
バックトラッキング法は試験でどう引っ掛けられる？
枝を刈っても最悪は全探索なので、計算量が指数的になり得る点は変わらない。動的計画法が部分問題の答えを再利用して重複計算を消すのに対し、バックトラッキングは候補を試して戻る点が本質的に異なる。
バックトラッキング法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。