バックトラック法
読み方：バックトラックほう
【英】backtracking method
【英】backtracking method
バックトラック法とは、探索アルゴリズムの一種で、検索ルートの途中で条件に一致するものが無いことが分かった場合に、一つ前に戻り別ルートでの検索を行う手法のことである。
バックトラック法を利用すると、効率的な検索アルゴリズムが存在しないような問題を解決する際でも、ある程度は効率的に、条件に当てはまるものを検索することができる。多くの場合、バックトラック法の実装には、再帰呼び出しの技術が利用される。
組み合わせの問題であるような数学的パズルをコンピュータで解くような例では、バックトラック法が最も効率的であるか、あるいは本質的にバックトラック法が唯一の解決策であることも多い。代表的な例として、エイトクイーン問題（Nクイーン問題）などがある。
- バックトラックほうのページへのリンク
