1 基本概念
制約充足問題は、複数の変数に値を割り当てながら、あらかじめ与えられた条件を同時に満たすかを問う枠組みである。論理学、人工知能、計算機科学の分野で重要な位置を占め、抽象度の高い定式化によって多様な問題を共通の形式で扱える点に特徴がある。数独や地図の塗り分けのような例は、この考え方を直感的に示す代表例である。
1.1 定義
一般には、変数の集合、各変数の取りうる値の集合、そしてそれらに課される制約の集合からなる問題として定式化される。目的は、すべての制約を満たす割り当てを見つけること、あるいはそのような割り当てが存在しないことを判定することである。解の有無を確かめるだけの形から、実際の解を構成する形まで、扱い方には幅がある。
1.2 変数と値域
変数は、配置対象や選択対象を表す記号的な要素である。各変数には、代入可能な値の集合が対応し、この集合を値域と呼ぶ。値域は固定の場合もあれば、探索の途中で絞り込まれる場合もあり、問題の難しさや解法の性質に大きく関わる。
1.3 制約の種類
制約は、変数同士の関係や許される組合せを定める。制約の形は単純なものから複雑なものまであり、問題の表現力を左右する。どの種類の制約を採用するかによって、解法の設計や計算量の見通しも変化する。
1.3.1 単項制約
単項制約は、1つの変数だけに関する条件である。たとえば、ある変数は特定の値を取ってはならない、あるいはある範囲に限るといった制約がこれに当たる。値域の初期削減に直接結びつきやすく、前処理として有効である。
1.3.2 二項制約
二項制約は、2つの変数の間に成り立つ関係を記述する。代表的なものには、等しい、異なる、大小関係を満たす、といった条件がある。多くの実用例では、この形の制約が多数を占め、グラフ構造との相性がよい。
1.3.3 高次制約
高次制約は、3個以上の変数を同時に結びつける条件である。和の合計や相互排他、全体の配置条件などが典型例となる。二項制約だけでは表しにくい関係を自然に記述できる反面、処理はやや複雑になりやすい。
1.4 解と充足
制約をすべて満たす割り当てを解と呼ぶ。解が1つでも存在すれば充足可能、存在しなければ不充足とされる。場合によっては、1つの解を得るだけでなく、全解の列挙や最適な解の選別が求められることもある。
2 表現方法
制約充足問題は、同じ内容でも異なる表現に写し替えられることが多い。表現の選択は、理論的な解析だけでなく、実装時の効率にも影響する。制約の構造を見やすく表す方法と、既存の計算技術に乗せやすい方法の両方が用いられる。
2.1 制約グラフ
制約グラフでは、変数を頂点、変数間の制約を辺として表す。どの変数どうしが直接関係しているかが一目で分かるため、構造の把握に便利である。特に二項制約が中心の問題では、局所的な結びつきを分析する手段として広く使われる。
2.2 制約ネットワーク
制約ネットワークは、変数、値域、制約を一体として扱う表現である。グラフ表現よりも情報量が多く、各変数の候補値や制約の具体的内容を明示できる。探索や伝播の実装では、この形式が基礎になることが多い。
2.3 命題論理への変換
制約充足問題は、命題変数と論理式の組合せへ翻訳できる場合がある。こうした変換により、充足可能性判定の技法を流用しやすくなる。特にSATソルバの発展により、大規模問題を論理形式へ落とし込む方法が実務でも重要になった。
2.4 整数計画への変換
一部の制約充足問題は、整数変数と線形制約からなる整数計画問題として表現できる。これにより、最適化で培われた分枝限定法やカット平面法などの手法と接続できる。制約の形によっては、論理式よりも数理最適化の枠組みのほうが扱いやすい。
3 解法
解法の中心は、候補を系統的に絞り込みながら、制約を破らない割り当てを探すことにある。単純な列挙から高度な伝播付き探索まで幅は広いが、いずれも不要な試行を減らす工夫が重要である。問題構造に応じて、複数の手法を組み合わせるのが一般的である。
3.1 全探索
全探索は、可能な割り当てを順に調べる最も基本的な方法である。理論的には分かりやすいが、候補数が急増しやすく、実用規模では計算量の面で不利になりやすい。それでも、問題の性質を確認する基準としては有用である。
3.2 バックトラッキング
バックトラッキングは、変数に順番に値を入れ、矛盾が生じたら直前の選択に戻る探索法である。全探索に比べて、制約違反が早く見つかれば大きな節約になる。実際には、制約検査と枝刈りを組み合わせることで、かなり効率的に動作する。
3.3 制約伝播
制約伝播は、ある変数の値が決まったとき、その影響を他の変数へ伝えて候補を減らす処理である。局所的な情報を使って、将来の矛盾を早めに露見させる役割を持つ。探索と併用されることが多く、現代的な制約解法の核となっている。
3.3.1 領域削減
領域削減は、各変数の値域から不可能な値を取り除く操作である。制約の伝播によって候補が減れば、探索空間が小さくなり、後続の判断も容易になる。場合によっては、単独で解が確定することもある。
3.3.2 整合性の概念
整合性は、制約を満たす候補が局所的にどの程度残っているかを表す尺度である。代表的なものに、ノード整合性、アーク整合性、より強い整合性がある。これらは、解の存在を保証するものではないが、探索効率を高める上で重要である。
3.4 探索順序の工夫
どの変数から処理し、どの値を先に試すかは、探索性能に大きく影響する。適切な順序付けは、早期の失敗検出や分岐数の削減につながる。ヒューリスティクスの導入は、実用的な解法ではほぼ不可欠である。
3.4.1 変数選択
変数選択では、未割り当ての変数のうち、どれを次に扱うかを決める。候補数が少ない変数を優先する方法や、他への影響が大きい変数を選ぶ方法が知られている。これにより、難しい箇所を早めに露出させやすくなる。
3.4.2 値選択
値選択は、ある変数に対してどの候補値から試すかを決める。将来の選択肢をできるだけ多く残す値を優先する戦略がよく用いられる。局所的な成功だけでなく、後続の探索負荷を見込んで順序を決める点に意味がある。
4 応用
制約充足問題は、抽象的な理論にとどまらず、実際の組合せ問題の共通基盤として使われる。パズル、割り当て、計画、設計など、候補の組合せを整理する必要がある場面で特に有効である。明確なルールがある問題ほど、モデル化の利点が現れやすい。
4.1 パズル
多くの論理パズルは、制約充足問題として自然に表現できる。盤面や文字列に対して条件を課し、整合する配置を探す形で解釈されるためである。こうした見方は、手作業の推理と計算機による探索の両方に適している。
4.1.1 数独
数独では、各マスに1から9までの数字を入れ、行・列・ অঞ্চ別の重複を避ける。制約の構造が明快で、制約伝播やバックトラッキングの題材として頻繁に用いられる。教育用の例としても、理論と実装の両面で扱いやすい。
4.1.2 クロスワード
クロスワードの自動作成や解答支援では、交差する単語同士の文字一致が主要な制約となる。長さ、語彙、交差位置の条件を組み合わせることで、配置候補を絞り込める。単語の選択と配置の双方を同時に考える点が特徴である。
4.2 資源割り当て
資源割り当てでは、人員、機器、部屋、時間などの資源を条件に従って配分する。衝突回避や容量制限などが制約として現れ、実務上の有用性が高い。適切に定式化すると、複雑な運用上の判断を体系的に整理できる。
4.3 予定表作成
予定表作成は、授業、会議、試験、勤務の配置を決める問題である。重なりの禁止、必要人数、利用可能時間帯などが相互に絡み合うため、制約充足の典型例とみなされる。現実の条件が増えるほど、探索と伝播の組合せが重要になる。
4.4 組合せ設計
組合せ設計では、条件を満たす要素の集合や配置を構成する。実験計画、符号理論、テストケース設計などに関連し、所定の性質を持つ組合せを探す場面で利用される。制約充足の枠組みは、候補の体系的な構成を支える手段として役立つ。