制約プログラミング
制約プログラミング
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2023年1月） |
| プログラミング・パラダイム |
|---|
|
制約プログラミング（せいやくプログラミング、Constraint Programming）はプログラミングパラダイムの一つである。 制約プログラミングにおいては、変数間の関係を制約という形で記述することによりプログラムを記述する。制約が他のプログラミングパラダイムのプリミティブと異なっているのは、実行すべきステップではなく解の特性を記述するという点である。制約プログラミングにおける制約は様々である。制約充足問題での制約やシンプレックス法における制約などがある。制約は通常、プログラミング言語に埋め込まれているか別個のライブラリで提供される。
制約プログラミングは制約を論理プログラミングに埋め込んだ制約論理プログラミングが起源である。1987年、Jaffer と Lassez がProlog IIにある種の制約を取り入れたのが最初であった。制約論理プログラミング言語の実装としては、Prolog III、CLP(R)、CHIP がある。今日でも GNU Prolog などの制約論理プログラミングのインタプリタが存在している。
論理プログラミング以外では、制約は関数型言語、項書き換え、命令型言語などと融合させることができる。関数プログラミングでの制約としては、マルチパラダイムプログラミング言語 Oz がある。制約を取り入れた命令型言語としては Kaleidscope がある。しかし、制約プログラミング（制約論理を含む）のための専用の言語は少なく、ツールキット的な形態でライブラリとして既存の言語向けに提供されている場合がほとんどである。
制約論理プログラミング
制約プログラミングはホストとなる言語に制約を埋め込む。最初のホスト言語は論理プログラミング言語であったため、これを「制約論理プログラミング」と呼んだ。この2つのパラダイムは論理変数やバックトラッキングといった多くの重要な共通点がある。現在の多くのProlog処理系には何らかの制約論理プログラミング用ライブラリが用意されている。
制約プログラミングも論理プログラミングもチューリング完全であり、論理プログラムを制約プログラムに書き換えることも逆も可能である。論理プログラムよりも制約プログラムの方が性能がよい問題もあり、そのような場合に事前に変換を行うこともある。
両者の最大の違いは、世界をモデリングする流儀と手法である。問題によっては論理プログラムとして書くのが自然で単純だし、別の問題は制約プログラムとして書くのが自然である。
制約プログラミングは、同時に最も多くの制約を充足する状態を探索する。その場合、問題は複数の未知の変数を含む世界の状態として記述される。制約プログラムはそれら変数全部の値を探索する。
時相並行制約プログラミング(Temporal Concurrent Constraint programming; TCC)や非決定性時相並行制約プログラミング（Non-deterministic Temporal Concurrent Constraint programming）は時を扱う制約プログラミングの一種である。
以下に制約論理言語の例を挙げる:
- B-Prolog （Prologベース、プロプライエタリ）
- CHIP V5 （Prologベース、C++/C言語のライブラリも含む、プロプライエタリ）
- Ciao Prolog （Prologベース、フリーソフトウェア: GPL/LGPL）
- ECLiPSe （Prologベース、オープンソース）
- SICStus （Prologベース、プロプライエタリ）
- GNU Prolog
- YAP Prolog
領域
制約プログラミングにおける制約は何らかの特定の領域に関するものであることが多い。制約プログラミングでの一般的な領域としては次のものがある:
- ブーリアン領域: 真/偽の制約だけが適用される
- 整数領域、有理数領域
- 線形領域: 線形関数のみを記述し、解析する（非線形問題を扱う手法もある）
- 有限領域: 有限集合について制約を定義する
- 混合領域: 上記のうち2つ以上を同時に扱う
このうち、有限領域が最も成功している。オペレーションズリサーチなどの分野では、制約プログラミングと言えば有限領域の制約プログラミングを指す。
有限領域の制約プログラミングは制約充足問題を解くのに便利であり、局所整合やその近似に基づいているものが多い。
有限領域の制約の記法はホスト言語によって異なる。以下ではPrologで制約論理プログラミングを使って古典的な覆面算 SEND+MORE=MONEY を解くプログラムを示す:
sendmore(Digits) :-
Digits = [S,E,N,D,M,O,R,Y], % 変数生成
Digits :: [0..9], % 変数を領域に対応させる
S #\= 0, % 制約: S は 0 ではない
M #\= 0,
alldifferent(Digits), % 全ての要素はそれぞれ異なった値となる
1000*S + 100*E + 10*N + D % 他の制約
+ 1000*M + 100*O + 10*R + E
#= 10000*M + 1000*O + 100*N + 10*E + Y,
labeling(Digits). % 探索開始
インタプリタはパズルの各文字に対応して変数を生成する。:: という記号はそれら変数の領域を指定するもので、上の例では値の範囲が {0,1,2,3, ..., 9} となる。制約 S#\=0 と M#\=0 は、これらの変数がゼロにはならないことを指定する。インタプリタはこれらの制約を評価して、それらの変数がとりうる範囲から 0 を除く。次に制約 alldifferent(Digits) を評価する。これは範囲を狭めることにはならず、単に格納される。最後の制約は、"SEND+MORE=MONEY" の各文字を数字に置き換えた式が数式として真であることを示している。この制約から、まず M=1 が導き出される（4桁と4桁の加算で5桁になるということは、答えの5桁目は必ず 1 となる）。ここで変数 M に関わる全制約が呼び出され、alldifferent 制約への制約伝播により、他の変数のとりうる範囲から 1 が除かれる。制約伝播によって全ての変数の値が一意に定まるか、全制約を満たす解がないことが判明する。ただし、どちらとも判別できずに終了することもある。
命令型制約プログラミング
命令型プログラミングでも制約プログラミングが別ライブラリとして提供されることが多い。制約プログラミングに関する主なライブラリを以下に挙げる:
- Choco （Javaライブラリ、BSDライセンス）
- Gecode （C++ライブラリ、MITライセンス）
- IBM ILOG CPLEX CP Optimizer （C++ライブラリ、プロプライエタリ）
- iZ-C （C言語ライブラリ、プロプライエタリ、基本的に無償）
- Minion （C++による制約充足問題を解くシステム、GPL）
- Scarab （Scalaライブラリ、BSDライセンス）
- FaCiLe（OCaml用の整数および整数集合領域用ライブラリ、LGPL）
外部リンク
- Constraint programmingのページへのリンク
