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