制約処理パッケージにより、資源割り当ての課題が、より容易に処理できるようになりました。
IF/PrologV5.0制約処理パッケージ(オプション)は、IF/Prologに最新の「制約に基づ いた問題解決」パラダイムを導入しました。これにより、従来「複雑す ぎて扱えない」とされてきた拡張的な領域の問題も、IF/Prologを使用 して解決することができるようになりました。 例えば、航空・鉄道での運航計画、生産計画、乗務員などの人員配置 計画を始めとするほぼすべての資源割り当ての課題が、効果的な宣言的 方法で処理できるようになりました。
制約処理パッケージでは、異なる制約クラスを、異なるPrologの モジュールに分割しています。モジュール化はIF/Prologの非常に 重要な特長であり、産業分野でのアプリケーションでも使用され実証 されてきました。既存のアプリケーションのコードとの互換性もあり ます。
現在、様々な分野で、制約処理パッケージを使用したアプリケーシ ョンの開発が進んでいます。また、すでに以下に挙げるような本格 的なアプリケーション開発中に制約処理技術の改良も行なわれ、 この技術自体もすでに実証されています。
制約処理パッケージは、Prologが提供する計算領域に加えて、さら に5つの計算領域を備えています。
・長精度整数と有理数: 任意の長さを持つ整数と有理数の正確な計算。 ・コルーチン: 変数の具体化に伴って活性化されるデータ駆動型計算。 ・数値的制約: 累積、論理和、最小化、最大化などの高レベル述語を 含む有理数の線形方程式、不等式を解くシステム。 ・有限領域: 変数に結びつけられた値の領域を能動的に狭める。この 技術により、有効な値の可能な組合せのみを考慮し、探索空間を非常 に小さくすることができる。 ・論理制約: ブール式として形式化される関係を使用し、効率の良い 決定木の操作を行なう。
IF/Prologの開発環境は、制約ベースのアプリケーションを簡単に デバッグやトレースできるように拡張されました。 デバッガと トレーサは、制約の一時停止や活性化を分かりやすく示すために、 従来の4ポートから10ポートのセマンティックモデルになりました。 この環境は文字ベースおよびMotifの両方のバージョンで使用する ことができます。これにより、ランタイムの操作を容易に制御でき るようになりました。さらに、オンラインでのハイパーテキスト マニュアルも用意されており、この開発環境を使用することにより プログラマの生産性を飛躍的に改善することができます。
制約処理パッケージは、IF/Prologの他のデータベースインタフェ ース、プログラミング言語インタフェース、文字セット、グラフィ カルウィンドウシステムとの互換性を持っています。このパッケー ジは、IF/Prologがサポートしているすべてのハードウェアプラット フォーム上で使うことができるオプションとして提供されています。
制約処理パッケージの第1の利点として、プログラマの生産性の向上 が挙げられます。制約処理パッケージにより、プログラムをより 宣言的に書くことができるようになりました。これにより、複雑な 問題をより単純に解決することが可能です。さらに、上に挙げたよ うな使いやすい開発環境ができたことで、より効率的にプログラミ ングができるようになりました。
第2に、プログラム実行に必要な時間が短縮されました。 制約処理のために必要であるとして追加された内部データエリアは すべて、ユーザアプリケーションから透明な形で、自動的にリサイ ズされ、ガーベッジコレクションが行なわれているために、プログ ラム実行に必要な時間が短縮されました。制約処理パッケージは、 システムカーネルの中心的な部分となり、最新の制約技術の実装形 となっています。
制約処理パッケージにより、問題解決の速度がいかに向上したかを 示すのが次の表です。Sun SPARCstation IPX上のIF/Prolog V4.1と IF/Prolog V5.0とで書かれたサンプルプログラムの実行速度を比較 しています。 IF/Prolog V5.0を使った場合については、制約処理 パッケージを使った場合と使わない場合の解決を比較しています。 制約処理パッケージを利用した場合の処理速度がいかに速いかがわ かります。
| (1) | (2) | (3) | |
| Eight-Queens | 30.13 | 18.01 | 4.19 |
| Farmer | 4.50 | 3.42 | 0.98 |
| SEND MORE MONEY | 65.50 | 53.47 | 0.85 |
(1) IF/Prolog V4.1での測定 (2) IF/Prolog V5.0での測定 (3) IF/PrologV5.0 および制約処理パッケージでの測定
CPU時間の単位は秒。100回測定の結果
制約処理パッケージは、ANSI標準互換Cにより書かれています。こ の中にある述語は、ISO Prolog標準に定義されたものと同じスタイ ルであり、この標準と同じように厳しく定義されています。
この新しい制約処理パッケージは学術研究用のシステムCHIPを土台 にしています。CHIPはECRC(European Computer Research Centre)が 開発したシステムです。 シーメンス(IF/Prolog5.0の開発元)は、 CHIPで試験的に開発された制約処理技術に、新しい技術を加え、 SNI Prolog 3.1を開発しました。 この度、これらの技術がより 改良されモジュール化されIF/Prolog5.0に統合され、製品化され ました。
制約処理パッケージではコルーチン、数値的制約、有限領域、論理 制約の4つの制約クラスを提供しています。このすべてのクラスに 対して、Prologモジュールは様々な内蔵述語を提供しています。 ここで、制約クラスに内蔵されたすべての述語を説明することはでき ませんが、下の例ではその一部を紹介しています。
IF/Prologの中で数字として解釈実行される範囲が拡張され、長精度 整数や有理数も扱うようになりました。長精度整数では小数点以上 約三十万桁までの数字の処理が可能です。(ほとんど任意の整数を 扱うことができます。 有理数は、2つの長精度整数の約分されない部分として表現され、 これにより高精度な計算式を処理することができます。
コルーチンは、データ制御下のゴールの数値を与え始める基礎的な メカニズムであり、これを用いて、より宣言的にPrologプログラム を書くことができます。内蔵述語を使用して、数個の変数に値が 与えられるまでゴールの数値を与えることを遅延させることも 可能です。
しかし、一般的な制約メカニズムとしては、コルーチンのみでは十分 ではありません。なぜならば、従来型のPrologと同様に、コルーチンは 一貫性条件を受身的にテストしているからです。より効率的な方法は、 予め変数の領域を限定し、一貫性条件を能動的に処理することです。 いずれにせよ、コルーチンはより複雑な制約を定義するのに役立ちます。
以下の例では、コールーチンを使用することにより、いかにうまく 宣言型プログラミングができるかを示しています。この例の場合、 Prologは左から右へと手続きを踏んでサブゴールを証明しますので、 宣言的観点からは正しくありません。
[user] ?- A \= a, A = b.
no
[user] ?- A = b, A \= a.
A = b
yes
論理的な観点から見ると、サブゴールの順序はどちらが先でもかま いません。このような場合、制約処理パッケージのコルーチンクラスの 内蔵述語であるfreeze/2を使用して、"A"の変数に値が与えられるまで、 最初のゴールである "A \ = a" の証明を遅らせることができます。
[user] ?- freeze(A, A \= a), A = b. A = b yes
数値的制約を使用して、解答が無限にあり「値が連続している」 最適化問題を解決することができます。数値的制約は、等式、 不等式の組合せを増分アルゴリズムによって解きます。 (別ページのプログラミング例を御覧下さい。)
有限領域という制約クラスは、不連続の問題を解決するのに有効で す。「不連続」とは、ここで、有限領域の制約によって表現された 条件を満足する数値が有限であるという意味です。この場合、従来の Prologでは「値を生成してみてテストする」というプログラミン グのパラダイムが使われていましたが、可能な値のみを生成する というパラダイムになりました。
有限領域の変数は、例えば、間隔、列挙、数列などで制限された整数 です。変数は、限られた領域で値をとることができます。有限領域用 の制約のクラスの中では、変数間を、数学的な制約、記号的制約で 特定することができます。さらに、累積制約も提供されます。 (別ページのプログラミング例を御覧下さい。)
論理制約は、量的な測定を必要としないスケジューリングや決定 支援の分野でのアプリケーションに非常に適した手法です。 バイナリ領域で真の値を演算し、条件値を効果的に決定するために 用いられます。
実行中に、真の値が、多くの「論理」内蔵述語に伝えられます。 論理単一化アルゴリズムが、決定を容易に組合せることができる ように真の領域を越えて動作します。 (別ページのプログラミング例を御覧下さい。)
| 冒頭へ |
|