制約プログラミング 制約論理プログラミング

ウィキペディア

制約プログラミング

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/07/27 22:58 UTC 版)

制約論理プログラミング

制約プログラミングはホストとなる言語に制約を埋め込む。最初のホスト言語は論理プログラミング言語であったため、これを「制約論理プログラミング」と呼んだ。この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