バックトラック法【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更新)

他の辞典による解説 (外部サイト)

この記事の著者 : (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる