Loading article…
人工知能とオペレーションズリサーチでは、制約充足とは、変数が満たさなければならない条件を課す一連の制約を通して解を見つけるプロセスです。[ 1 ] したがって、解とは、すべての制約を満たす変数への値の割り当て、つまり実行可能領域内の点です。
制約充足問題で使用される手法は、考慮される制約の種類によって異なります。多くの場合、有限領域に対する制約が用いられ、制約充足問題は一般的に有限領域に対する制約に基づく問題と同一視されます。このような問題は通常、探索、特にバックトラッキングや局所探索によって解決されます。制約伝播は、このような問題に使用されるもう1つの手法です。これらの手法のほとんどは一般的に不完全であり、問題を解決するか、充足不可能であることを証明することはできますが、常にそうとは限りません。制約伝播法は、与えられた問題をより簡単に解決できるように、探索と組み合わせて使用されることもあります。その他に考慮される制約の種類は、実数または有理数に対する制約です。これらの制約に関する問題の解決は、変数消去法またはシンプレックス法によって行われます。
制約充足問題は、1970年代に人工知能の分野で一般的な問題として始まりました（例えば、( Laurière 1978 )を参照）。しかし、制約が不等式を定義する多変数線形方程式として表現される場合、この分野は19世紀のジョセフ・フーリエにまで遡ります。1946年にジョージ・ダンツィヒが線形計画法（数学的最適化の特殊なケース）のためのシンプレックス法を発明したことで、数百の変数を含む問題の実行可能な解を決定することが可能になりました。
1980年代から1990年代にかけて、プログラミング言語に制約を組み込む技術が開発されました。制約プログラミングを本質的にサポートするように設計された最初の言語はPrologでした。それ以来、 C++やJavaなどの他の言語でも制約プログラミングライブラリが利用可能になりました （Javaの場合はChoco [ 2 ]など）。
人工知能で最初に定義された制約は、与えられた世界で変数の集合が取り得る値を列挙するものです。可能な世界とは、世界（現実または想像上の世界）がどのようなものであるかを表す変数への値の完全な割り当てです。[ 3 ]非公式には、有限ドメインとは、任意の要素の有限集合です。このようなドメイン上の制約充足問題には、そのドメインからのみ値を取ることができる変数の集合と、各制約が変数のグループに対して許容される値を指定する制約の集合が含まれます。この問題の解は、すべての制約を満たす変数の評価です。言い換えれば、解とは、すべての制約がこれらの値によって満たされるように各変数に値を割り当てる方法です。
状況によっては、追加の要件が存在する場合があります。解決策（およびそれに到達する最速または最も計算効率の良い方法）だけでなく、その解決策に至った過程にも関心があるかもしれません。例えば、「最も単純な」解決策（論理的、非計算的な意味での「単純さ」であり、明確に定義される必要がある）を求める場合などです。これは、数独のような論理ゲームでよく見られるケースです。
実際には、制約条件は、その条件を満たす変数の値をすべて列挙するのではなく、簡潔な形式で表現されることが多い。最もよく使われる制約条件の一つは、（言うまでもなく）対象となる変数の値がすべて異なっていなければならないというものである。
制約充足問題として表現できる問題には、8クイーン問題、数独問題、その他多くの論理パズル、ブール充足可能性問題、スケジューリング問題、誤差範囲推定問題、グラフ彩色問題などのグラフ上の様々な問題がある。
通常、上記の制約充足問題の定義には含まれませんが、算術方程式と不等式は、それらに含まれる変数の値を制限し、したがって制約の一形態とみなすことができます。それらの定義域は、無限である数値の集合（整数、有理数、または実数）です。したがって、これらの制約の関係も無限になる可能性があります。たとえば、満たす値のペアは無限に存在する。算術方程式や不等式は、有限領域に限定される「制約充足問題」の定義には含まれないことが多い。しかし、制約プログラミングでは頻繁に使用される。
フトシキやカクロ（クロスサムとも呼ばれる）などの有限論理パズルに存在する算術的不等式や方程式は、非算術的制約として扱うことができることが示されています（パターンベースの制約充足と論理パズル[ 4 ]を参照）。
有限領域における制約充足問題は、一般的に探索法を用いて解決されます。最もよく用いられる手法は、バックトラッキング、制約伝播、局所探索の変種です。これらの手法は、非線形制約を持つ問題にも適用されます。
変数消去法とシンプレックス法は、線形方程式や多項式方程式、不等式、および定義域が無限の変数を含む問題を解くために用いられる。これらは通常、最適化問題として解かれ、最適化対象関数は制約違反の数となる。
有限領域における制約充足問題の解決は、領域サイズに関してNP完全問題である。研究により、許容される制約関係を制限するものや、制約の範囲がツリー構造を形成する必要があるものなど、扱いやすいサブケースがいくつか見つかっており、場合によっては問題の再定式化が必要となる。また、研究により、制約充足問題と有限モデル理論などの他の分野の問題との関連性も明らかになっている。
制約プログラミングとは、制約をプログラミング言語として用いて問題を符号化し解決する手法です。これは多くの場合、制約をホスト言語と呼ばれるプログラミング言語に埋め込むことによって行われます。制約プログラミングは、 Prolog IIにおける項の等価性の形式化から始まり、論理プログラミング言語に制約を埋め込むための一般的なフレームワークへと発展しました。最も一般的なホスト言語はProlog、C++、Javaですが、他の言語も使用されています。
制約論理プログラムとは、節の本体に制約を含む論理プログラムです。例えば、節は、本体にA(X):-X>0,B(X)制約を含む節です。制約は目標にも存在できます。目標と、目標を証明するために使用される節の制約は、制約ストアと呼ばれる集合に蓄積されます。この集合には、評価を進めるためにインタプリタが充足可能であると想定した制約が含まれます。結果として、この集合が充足不可能と検出された場合、インタプリタはバックトラックします。論理プログラミングで使用される項の等式は、制約の特殊な形式とみなされ、単一化を使用して単純化できます。結果として、制約ストアは、通常の論理プログラミングで使用される置換の概念の拡張とみなすことができます。制約論理プログラミングで使用される最も一般的な種類の制約は、整数/有理数/実数に対する制約と、有限領域に対する制約です。X>0
並行制約論理プログラミング言語も開発されている。これらは、終了しない可能性のある並行プロセスをプログラミングすることを目的としている点で、非並行制約論理プログラミングとは大きく異なる。制約処理ルールは並行制約論理プログラミングの一形態と見なすことができるが、非並行制約論理プログラミング言語内で使用されることもある。制約処理ルールを用いることで、条件の真偽に基づいて制約を書き換えたり、新しい制約を推論したりすることができる。
制約充足ツールキットとは、命令型プログラミング言語用のソフトウェアライブラリであり、制約充足問題を記述して解決するために使用される。
制約ツールキットは、命令型プログラミング言語に制約を組み込むための手段です。しかし、これらは問題のエンコードと解決のための外部ライブラリとしてのみ使用されます。制約を命令型プログラミング言語に統合するアプローチは、Kaleidoscopeプログラミング言語で採用されています。
制約は関数型プログラミング言語にも組み込まれている。
{{cite news}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)