制約伝播とは
Constraint Propagation
制約充足問題において、変数の取り得る値の範囲を制約に基づき絞り込み、矛盾を早期に検出する手法
概要
制約伝播(Constraint Propagation)とは、制約充足問題(CSP: Constraint Satisfaction Problem)を解く際に、各変数が取り得る値の候補(定義域)を、変数間の制約に基づいて反復的に絞り込んでいく手法。ある変数の定義域が絞られると、それに関連する制約を通じて他の変数の定義域にも影響が伝播していく。 絞り込みの過程でいずれかの変数の定義域が空になった場合は、その時点で解が存在しない(矛盾)ことを検出でき、探索木の枝刈りに利用できる。 アーク整合性(arc consistency)を実現するAC-3アルゴリズムなどが代表的な制約伝播アルゴリズムであり、バックトラック探索と組み合わせて用いることで、数独やスケジューリング、自動計画など組合せ最適化問題の探索空間を削減できる。
比較
- 実行可能解 — 制約伝播は実行可能解の探索空間を絞り込むための手法の1つ