[制約プログラミング落穂拾い] 宣言性の光と影（４）

制約プログラミング技術は、解くべき問題の表現方法を提供するだけではなく、問題解決の効率的な手法も提供します。「宣言性」は前者に直接関係しますが、その一方で、後者に関係するのが前回も触れた「制約伝播」機構です。
いわば制約が存在することを積極的に用いて、制約を充たさない値を事前に削ることによって無駄な候補を調べる手間を省くようになっているのでした。

ここで注意したいのは、制約伝播の仕組みは、それだけで解が求まる（※）ことを保証するものではないことです。制約伝播の仕組みでは完全性が保たれる限りで候補の絞込みを行ないます。どの程度の絞込みが起きるかは問題依存です。より詳細には、問題空間にある変数の領域の大きさ、制約の種類、そして勿論、個別の処理系における制約の実装の仕方に依存します。

※厳密には制約プログラミングにおいて「解を求めること」の定義は必ずしも自明ではありません。項書換などのプログラム変換につながる流れで、ある種の標準形に変形することを「解を求めること」とする立場も考えられます。ではありますが、ここでは普通に制約を充足する変数の値の組を求めることを「解を求めること」とします。

制約伝播のメカニズム自体にもコストが発生しますから、極端な場合には、かけたコストほどの効果が得られない、つまり無駄な伝播ばかりして候補の絞込みがほとんど起きないような場合も考えられます。

その一方で、制約伝播のみでは解が求まらないのだとしたら、制約伝播の機構は、探索の手法と組み合わせて用いなくてはならないことになります。

ここでは探索の技術については詳しく述べませんが、探索が解を求める方法としては一般性・汎用性は高いけれど、効率の点では良くないのは明らかなことです。
ここからわかることは、既知のより効率的なアルゴリズムで解くことができる問題としてのモデル化が可能なら、制約プログラミングを用いる必要はないということです。
制約プログラミングが効率的なのは、いわゆるナイーブなdon't know nondeterminismに比べての話であり、従って、探索して解くしかない場合に有効であると考えるべきなのです。

裏返せば、制約プログラミングで解をうまく求めるためには、様々な工夫が必要になると考えるべきなのです。制約伝播機構はうまく働けば非常に強力ですが、学習用の例題ならともかく、実用的なプログラムが制約伝播機構だけで開発できることはほとんどありません。

それでは制約プログラミングは実用にならないのでしょうか。

決してそんなことはありません。既知の効率的なアルゴリズムでのモデル化がいつも可能なわけではありません。現実の問題は複雑なので、エレガントなモデル化が可能なケースは決して多くはないでしょう。開発期間や予算などリソースの制限があって、充分な調査ができないかも知れません(※2)。環境の変化によって問題が途中で変わるかも知れません。それ以前に、いわゆるスケジューリングに関する知識獲得（ここではかつて人工知能で扱われていた意味合いで用いています）の限界で、途中でモデルの変更が必要になるかも知れません。制約プログラミングが用いられる計画系のシステム開発は、そもそも典型的なウォーター・フォール型の開発プロセスに必ずしもフィットしないのです。

※2.学会などで実務家の発表に対して、大学で研究されている優秀な先生が調査不足を指摘されるケースを時折見かけますが、同じ実務家として我が身を振り返って自分の勉強不足を反省させられる一方で、現実のプロジェクトの諸条件の厳しさを想像するにつけ、そうした指摘を受ける実務家の方に同情してしまいます。

制約プログラミングは、現実のプロジェクトでこそ力を発揮します。
今回見てきたとおり、制約プログラミングを実用的な問題に適用するには、探索手法の工夫が必要になります。処理系が提供しているプリミティブでは間に合わないことの方が多いというのが私の実感です。
そしてほとんどの場合、探索の完全性も放棄して、実用上許容できる時間内に、実用上許容できる品質の解を得るための試行錯誤をしていくことになるのです。そうしたことを受け入れてしまえば、制約プログラミングは非常に生産性の高いツールであると言えるのではないかと私は思います。

次回は今回の議論を踏まえて、再度、制約プログラミングを実用システムの開発に用いる際の課題を整理しようと思います。