制約充足問題#

読み: せいやくじゅうそくもんだい
英名: Constraint Satisfaction Problem
別名: CSP

制約充足問題は，複数の制約を満たす解を求める問題を指し，変数の集合，変数の領域の集合，制約式の集合の 3 つで構成される．具体的な問題には，エイトクイーン，グラフ色彩問題，線画解釈，数独，ラテン魔方陣等のパズル的な問題が多い．一方，実務ではスケジューリング問題等に多く，特に各制約に重みを付けた重み付き制約充足問題となることが多い．また，目的関数が与えられる場合には制約充足最適化問題と呼ばれる．重み付き制約充足問題，制約充足最適化問題共に，制約充足問題の拡張となっている．制約充足問題の多くは NP 困難に分類されるため厳密解法だけでなく，近似解法の研究も多くされている．

制約充足問題の厳密解法としては，バックトラッキング法をベースにした制約伝搬の手法を用いることが多い．近似解法としては，欲張り法，局所探索法，タブーサーチ，遺伝的アルゴリズム，アニーリング法等の多くの解法が提案されている．Nuorium Optimizer には制約充足最適化問題の厳密解法，および重み付き制約充足問題の近似解法が搭載されている．