制約充足問題とは
制約充足問題とは、満たすべき条件（制約）をすべて同時にクリアする組み合わせを探す、問題の表し方の枠組みのことです。数独やスケジュール作成のように「あちらを立てればこちらが立たず」という絡み合った条件を、コンピュータが扱える形に整理します。古典的なAIや最適化の分野で、幅広い問題を解くための共通の土台になってきました。
英語表記：constraint satisfaction problem（CSP）
変数・定義域・制約という3つの部品
制約充足問題は、3つの部品で問題を書き表します。決めたい中身である「変数」、各変数が取りうる値の範囲「定義域」、値の組み合わせを縛る「制約」の3つ。数独でいえば、各マスが変数、そこに入る1〜9が定義域、「同じ行・列・枠に同じ数字を置かない」が制約にあたります。あとはすべての制約を満たす1通りの埋め方を探すだけ、というわけです。
ビジネスでの使われ方
身近な活用は、社員の勤務シフトや会議室の割り当て、配送計画などです。「この人は夜勤できない」「会議室は同時に2件入れられない」といった条件を制約として書けば、あとはコンピュータが矛盾のない組み合わせを探してくれます。解き方の基本は、候補を順に当てはめ、行き詰まったら戻ってやり直す「バックトラッキング」。人手では膨大すぎる組み合わせも、条件を整理して機械に任せられるのが強みでしょう。ただし条件が厳しすぎると解そのものが存在しない場合もあり、そこの見極めは欠かせません。
Topic数独もシフト表も、機械には同じ問題に見える
人間の目には、数独パズルと社員のシフト表づくり、地図の色分けは、まったく別物に見えます。ところが制約充足問題として書き直すと、どれも「変数・定義域・制約」で表せる同じ形の問題になります。だから一つの解き方（ソルバ）を、分野をまたいで使い回せるのです。バラバラに見える困りごとを共通の骨組みに落とし込む。ここに、問題を抽象化して捉えるコンピュータ科学の面白さが表れています。
制約充足問題に関するよくある質問
- 制約充足問題と最適化問題は何が違いますか？
- 制約充足問題は「条件をすべて満たす答えを見つける」ことが目的で、見つかればどれでも正解です。最適化問題は、満たしたうえで「最もコストが低い」など一番良い答えを選びます。実務では両者を組み合わせて使うことも多いです。
- 制約充足問題は、今のAIブームとどう関係しますか？
- 大量データから学ぶ今の生成AIとは系統が異なり、人が条件を明示して解く古典AI寄りの枠組みです。とはいえシフト作成や配車などの実務では今も現役で、ルールがはっきりした問題に強みがあります。
