last update: 26 October 2007

制約プログラミングとは

制約プログラミングって何？

制約プログラミングは、

• 「問題を制約の集合として記述してコンピュータに与えると、コンピュータが制約を充たした答を見つけてくれる」

何が制約プログラミングではないのか？--関連分野

上記のような定義では、「どのように解くか」について、具体的なアルゴリズムが 指定されているわけではありませんから、広義にとれば非常に多くの領域が含まれ ます。制約充足問題（CSP）に対する解法としては、思い付くままに挙げても、

• OR（オペレーションズリサーチ）で研究されてきた様々なアルゴリズム、線形計画法、ニュートン法、動的計画法、etc.
• 木探索ベースの様々な手法
• 併合法やプログラミング変換における簡約などのような制約の書換えに基づく手法
• minimum-conflict、タブー探索、シミュレーテッドアニーリング（SA)などの解改善アルゴリズム
• ニューラルネットワークを用いた探索
• 遺伝的アルゴリズム（GA)

• SCMなどにより注目を集めているTOC理論（Theory of Constraint）
• 自然言語処理における制約に基づく文法理論(HPSG, Constraint Grammer, etc.)

• 制約は数値的なものに限定しない。問題の計算領域を問わずに制約として扱う。
  
• 問題空間の中に含まれる矛盾を検出し、整合性を維持するための効率的なアルゴリズムが中心技術となる。
• 解の探索法としては木探索法がベースで、探索の際に制約を積極的に利用して探索 空間の縮小を行うことが基本となる。

制約論理プログラミングという言葉を聞いたことはあるけど、、、

制約論理プログラミング(Constraint Logic Programming)というのは、上述の ような制約プログラミングを論理プログラミングの拡張として実現したものです。 論理プログラミングは、制約プログラミングと多くの特徴を共有しており、 制約プログラミングの一部であると言ってもよいほどです。実際、論理プログラミング 言語の代表とされているPrologの処理系の多くは、現在、制約ソルバーを備えて いますし、必ずしもPrologをベースとしていなくても、多くの制約プログラミングの ためのシステムは、論理プログラミングの考え方に基づいています。狭い意味での 制約プログラミングは、制約論理プログラミングと同じものと言ってもよいと 思います。

どのような特徴があるの？

制約プログラミングには、以下のような特徴があると言えるでしょう。

• 宣言的であり、情報の流れを一方向に固定しない。
• 制約される対象領域によって、制約解消の定義も解法も異なる。
• 制約を利用することにより探索の効率化が期待できる。
• プロトタイピングが容易。開発生産性が高い。
• オブジェクト指向パラダイムとの親和性が高い。

宣言性は、制約プログラミングの最も大きな特徴です。これは問題の定義と解法を分離することに関係します。関数プログラミングも、論理プログラミングも宣言性という特徴は持っていますが、関数プログラミングにおいては、情報の流れは決まっています。また、論理プログラミング言語も実装上は情報の流れが決まっていることがありました。勿論、情報の流れが固定できることは、多くの場合、問題解決の効率を考えると有利です。また、いつも双方向性が可能であるとは限りません。しかしながら、宣言性という点では、制約プログラミングは最も徹底的であると言えるでしょう。

更に、制約を利用することにより探索の効率化を図るという点で、問題解決の効率にも配慮しているといえます。ただし、制約される対象領域によって制約解消の定義も解法も異なるため、制約ソルバーは対象領域毎に用意する必要があります。逆に見れば、いろいろな効率のよい解法を、制約プログラミングの枠組みの中に集めることができるため、非常に柔軟でオープンであるとも考えられます。

プロトタイピングが容易であるとか、開発生産性が高いという特徴は、その多くを宣言性に負っているといえます。また、制約をオブジェクト間の関係と考えれば、オブジェクト指向パラダイムとの親和性が高いことは予想されますが、実際、多くの制約処理系はオブジェクト指向になっています。

実用になるの？

制約プログラミングは、様々な実用的なシステムを開発するための基礎技術の一つ であり、様々な分野への適用が可能です。商用のシステムが販売されてから10年ほどに なりますが、その間に数多くの実用システムが制約プログラミングに基づいて開発 され、運用されてきました。
どのような分野に適用されてきたかについては応用分野を、 実際の事例については応用事例をご覧ください。

どういう点が優れているの？

特徴として述べた項目と重複しますが、制約プログラミングの長所としてあげられるのは以下のような点です。

• 宣言的なので、特定の解き方を前提とせずに、解くべき問題の記述に専念できます。
• 様々な解き方を場合場合によって使い分けるようなシステムを構成する際の枠組みと なることができます。

欠点は？

一方、制約プログラミングの欠点として挙げられるのは以下のような点です。

• 宣言的であるということは、プログラムを見ただけでは挙動がわからないことでも あります。手続き型言語のように、書いた通りに動く、というわけには行きません。また、宣言的な書き方がいつでも書きやすいわけではありません。
• 大域的な探索を行うアプローチでは、制約解消による探索の効率化があっても、なお 解を求めるための時間的・空間的コストが大きすぎる場合があります。

なぜ流行らないの？

すでに述べたように、制約プログラミングには長所も短所もあり、必ずしも良いことづくめではありませんが、それにしても、制約プログラミングが流行しないのはなぜなのでしょう？これについては、以下のように考えられます。

• ハードウェアをはじめとする環境が、制約プログラミングを行うには貧弱すぎ、制約プログラミングは「高価な技術」だった。
• 論理プログラミングの拡張という側面が強調されすぎて、論理型言語と不可分のものと考えられる傾向にあった。

実際、制約プログラミングが実用化された初期の時代には、制約プログラミングは最先端の技術であるという側面を強調した宣伝がされていたように思われますし、それに応じて商用のツールも非常に高価なもので、利用できるのは大規模なプロジェクトにかぎられていました。

しかし、今や時代が変わり、以下のような状況になっています。

• ハードウェアの能力は飛躍的に向上し、当初は高価なワークステーション上でした利用できなかった制約プログラミングが、性能では当時のワークステーションを遥かに上回り、しかも安価なPC上で利用できるようになった。
• 制約プログラミングは確かに論理プログラミングの拡張と考えることができますが、論理プログラミングの特定の実装を前提に考える必要はありません。実際、これまでも論理型言語の拡張ではない、手続き型言語（特にオブジェクト志向型言語）上のライブラリとして制約処理系が実装され、その上で多くの実用アプリケーションを構築することが可能であることが実証されてきました。

まだ、制約プログラミング技術は若く、条件が整ってきたこれからが本格的な実用の時代といえるのではないでしょうか？