バックトラック法【backtracking method】バックトラッキング
概要
バックトラック法(backtracking method)とは、コンピュータで数学的な問題の解を探索するアルゴリズム(計算手順)の一種で、解の候補を虱潰しに試していくが、途中で解になり得ないと分かった候補群は間引く手法。条件を満たす要素の組み合わせを求めるような問題に適用することができ、厳密に解を求めることができるが、すべての組み合わせを調べる総当り方式(全探索)よりは効率が良い手法として知られる。
複数の要素の組み合わせが条件を満たすか調べる問題で、いくつかの要素を決定してみて、それ以上何を組み合わせても条件を満たすことがないと判明したら、その組み合わせについては探索を終了し、一手前に戻って(backtrack:引き返す)別の組み合わせを試していく。
例えば、サイコロA、B、Cの3つを振って和が10以上のものをすべて列挙するという問題を全探索で解くと、(A,B,C)=(1,1,1)から始めて(6,6,6)まで216通りすべての組み合わせについて調べることになる。
バックトラック法の場合、(A,B)=(1,1)を決定した時点でCが何であっても10以上にはならないことが分かるため、(1,1,x)の探索は行わず、(1,2,x)の探索へ移る。この手順を繰り返すと、(A,B)=(1,1)(1,2)(2,1)はまとめて飛ばしてしまえるため、全探索より18回少ない検証で解を求めることができる。
(2021.6.15更新)