バックトラッキング法
バックトラッキング法とは、制約充足問題を解くためのアルゴリズムです。制約充足問題とは、ある集合の要素に対して、ある制約を満たすような組み合わせを求める問題です。たとえば、8個のクイーンを8×8のチェスボードに置く問題は、制約充足問題です。クイーンは1列に2つ以上置くことができません。バックトラッキング法は、この制約を満たすような組み合わせを探索するアルゴリズムです。
バックトラッキング法の基本的な考え方は、以下の通りです。
1. 制約を満たすような組み合わせの候補を一つずつ試す。
2. 候補が制約を満たす場合は、それを解として出力する。
3. 候補が制約を満たさない場合は、候補を捨てて、次の候補を試す。
この処理を、制約を満たすような組み合わせが見つかるまで繰り返します。
バックトラッキング法は、制約充足問題を解くための強力なアルゴリズムですが、すべての問題に適用できるわけではありません。たとえば、制約が非常に複雑な問題や、制約を満たすような組み合わせが非常に少ない問題には、バックトラッキング法は効率的ではありません。
バックトラッキング法は、制約充足問題を解くためのアルゴリズムの一つです。制約充足問題を解くための他のアルゴリズムには、貪欲法や動的計画法などがあります。どのアルゴリズムを使用するかは、問題の性質によって異なります。
参考URL：
誰もが知りたい心理学用語
