(57)【要約】【課題】制約プログラミングを用いたアプリケーションプログラムにおいて、アプリケーションプログラム自体の改造を必要とすることなく、制約条件の変更を可能とすること。【解決方法】アプリケーション４の実行時に、制約変数管理手段８１により、制約定義記憶部６から制約定義を読み込み、制約変数を抽出し、その制約変数名をキーとして当該制約変数のデータドメインをデータドメイン記憶部７から取得し、制約充足ソルバ５固有の内部表現に変換して制約変数名とともに記憶し、制約条件構築手段８２により、制約定義から関係式を抽出し、前記記憶された制約充足ソルバ５固有の内部表現に変換された制約変数を利用して、抽出した関係式を制約充足ソルバ５固有の内部表現として構築することにより、アプリケーション４とは独立に定義された制約条件から動的に制約定義を構築可能とする。【選択図】図１
2007328580.tif 000002
【特許請求の範囲】
【請求項１】
制約変数の取り得る値の集合であるデータドメインの中から該制約変数間の関係式で表される制約条件の集合からなる制約定義を充足する制約充足解を、制約変数及び制約定義を固有の内部表現に変換して制約充足解を探索する制約充足ソルバを用いて求めるアプリケーションプログラムの実行方法において、
コンピュータが、
前記制約定義を記憶する制約定義記憶部から制約定義を読み込むステップと、
前記制約定義から制約変数を抽出するステップと、
データドメインを該制約変数の名前である制約変数名とともに記憶するデータドメイン記憶部から前記抽出した制約変数の制約変数名をキーとして当該制約変数のデータドメインを取得するステップと、
データドメインを制約充足ソルバ固有の内部表現に変換し、これを制約変数名とともに記憶するステップと、
前記制約定義から関係式を抽出するステップと、
前記記憶した制約充足ソルバ固有の内部表現に変換された制約変数を利用して、前記抽出した関係式を制約充足ソルバ固有の内部表現として構築するステップとを実行する
ことを特徴とするアプリケーションプログラムの実行方法。
【請求項２】
制約変数の取り得る値の集合であるデータドメインの中から該制約変数間の関係式で表される制約条件の集合からなる制約定義を充足する制約充足解を、制約変数及び制約定義を固有の内部表現に変換して制約充足解を探索する制約充足ソルバを用いて求めるアプリケーションプログラムの実行装置において、
制約定義を記憶する制約定義記憶部と、
データドメインを該制約変数の名前である制約変数名とともに記憶するデータドメイン記憶部と、
制約定義記憶部から制約定義を読み込み、該制約定義から制約変数を抽出し、該制約変数の制約変数名をキーとしてデータドメイン記憶部から当該制約変数のデータドメインを取得し、制約充足ソルバ固有の内部表現に変換し、これを制約変数名とともに記憶する制約変数管理手段と、
前記制約定義から関係式を抽出し、前記制約変数管理手段に記憶された制約充足ソルバ固有の内部表現に変換された制約変数を利用して、前記抽出した関係式を制約充足ソルバ固有の内部表現として構築する制約条件構築手段とを備えた
ことを特徴とするアプリケーションプログラムの実行装置。
【請求項３】
制約変数の取り得る値の集合であるデータドメインの中から該制約変数間の関係式で表される制約条件の集合からなる制約定義を充足する制約充足解を、制約変数及び制約定義を固有の内部表現に変換して制約充足解を探索する制約充足ソルバを用いて求めるアプリケーションプログラムを、コンピュータに実行させるためのプログラムにおいて、
コンピュータに、
前記制約定義を記憶する制約定義記憶部から制約定義を読み込むステップと、
前記制約定義から制約変数を抽出するステップと、
データドメインを該制約変数の名前である制約変数名とともに記憶するデータドメイン記憶部から前記抽出した制約変数の制約変数名をキーとして当該制約変数のデータドメインを取得するステップと、
データドメインを制約充足ソルバ固有の内部表現に変換し、これを制約変数名とともに記憶するステップと、
前記制約定義から関係式を抽出するステップと、
前記記憶した制約充足ソルバ固有の内部表現に変換された制約変数を利用して、前記抽出した関係式を制約充足ソルバ固有の内部表現として構築するステップとを実行させる
ことを特徴とするアプリケーションプログラムの実行プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に制約プログラミングを用いたアプリケーションプログラム（以下、単にアプリケーションと呼ぶ。）を実行する技術に関する。
【背景技術】
【０００２】
制約プログラミングとは、制約条件を満たす答えを探して見つけ出す問題を解くための手法・考え方の枠組みである。制約プログラミングにおいては、解くべき問題の宣言と、問題を満たす解の探索という２つの手順を踏む。ここで、解くべき問題の宣言とは、取り得る値の集合からなる「制約変数」と呼ばれる変数を定義し、制約条件を表す「制約変数間の関係式」を定義することを意味する。また、解の探索には「制約充足ソルバ」という汎用的なプログラムを利用することが一般的である。
【０００３】
制約充足ソルバでは、そのインタフェースを通して制約変数や制約条件を当該制約充足ソルバ固有の内部表現へと変換することで、制約条件を満たす解を様々な戦略を用いて効率的に探索することが可能であるという特徴を有する。
【０００４】
制約充足ソルバとしては、フリーで利用可能なものや商用で利用可能なものなど複数存在し、例えば、Ｃｒｅａｍ、ｉＺ−Ｃ（非特許文献１参照）、ＩＬＯＧ  Ｓｏｌｖｅｒ、Ｃｈｏｃｏなどがある。それぞれの制約充足ソルバは、開発環境、実行環境、インタフェースなどの差異はあるが、基本的な処理の流れは同じである。多くの制約充足ソルバは、制約充足ソルバの生成、初期化、制約変数を内部表現に変換する制約変数定義、制約条件を定義する制約条件式、制約条件式を制約充足ソルバに加えて制約を有効にする制約伝播、制約を充たす解集合を取得する解取得という手順を踏む。
【非特許文献１】”iZ:Constraint Programing 制約プログラミング入門”、［ｏｎｌｉｎｅ］、株式会社ＮＴＴデータセキスイシステムズ、［平成１８年５月２９日検索］、インターネット＜ＵＲＬ：http://www.isac.co.jp/iz/tutorial.html＞
【発明の開示】
【発明が解決しようとする課題】
【０００５】
制約プログラミングを用いたアプリケーションは、使用する制約充足ソルバ固有の内部表現による、制約変数の定義と制約条件の定義とからなる解くべき問題の宣言を内部構造として組み込むことが多い。このような場合、開発時に想定した制約条件が変わるような変更が生じると、アプリケーションの改造が必要となるが、そのコストは一般に高く、容易でないという問題があった。
【課題を解決するための手段】
【０００６】
本発明では、前記課題を解決するため、制約定義を記憶する制約定義記憶部と、データドメインを制約変数名とともに記憶するデータドメイン記憶部とを設け、アプリケーションの実行時に、制約定義記憶部から制約定義を読み込み、該制約定義から制約変数を抽出し、データドメイン記憶部から前記抽出した制約変数の制約変数名をキーとして当該制約変数のデータドメインを取得し、制約充足ソルバ固有の内部表現に変換し、これを制約変数名とともに記憶するとともに、前記制約定義から関係式を抽出し、前記記憶した制約充足ソルバ固有の内部表現に変換された制約変数を利用して、前記抽出した関係式を制約充足ソルバ固有の内部表現として構築することにより、アプリケーション自体に、制約変数の定義と制約条件の定義とからなる解くべき問題の宣言を内部構造として組み込むことを不要とした。
【発明の効果】
【０００７】
本発明によれば、制約変数の定義と制約条件の定義とからなる解くべき問題の宣言をアプリケーション実行時に動的に取得・構築可能とすることで、従来の手法ではアプリケーションのソースコードの変更が必要となる制約条件に変更が生じた際に、アプリケーションとは独立に定義された、制約条件のみを書き換えることで前述の変更に対処可能であり、アプリケーションのソースコードの改変のコストを削減する効果が期待できる。それに付随して、ソースコードの再コンパイル、再インストールのコストを削減する効果も期待できる。但し、制約定義の変更だけでは対処できない変更、例えば、データ項目の追加、削除、変更などが生じた場合には、ソースコードの改変が必要となることも有り得る。
【発明を実施するための最良の形態】
【０００８】
図１は本発明のアプリケーション（プログラム）の実行装置の実施の形態の一例、ここでは周知のコンピュータ上に実現した例を示すもので、図中、１はコンピュータ、２は入力装置、３は表示装置である。
【０００９】
コンピュータ１は、制約プログラミングを用いた所定のアプリケーション（プログラム）４及び該アプリケーション４が利用する所定の制約充足ソルバ５に対する実行環境を提供するとともに、記録媒体もしくは通信回線を介してインストールされた、図２及び図３に示すフローチャートに対応するプログラムに従って動作し、この際、制約定義記憶部６、データドメイン記憶部７及び制約処理機能部８を構成する。
【００１０】
入力装置２は、キーボード、マウス等からなり、オペレータ（検査者）がコンピュータ１に所定の情報、例えば制約定義記憶部６やデータドメイン記憶部７に記憶させるデータを入力するためのものである。表示装置３は、液晶ディスプレイ、ＣＲＴ等の画像表示装置からなり、コンピュータ１における所定の処理結果、例えばアプリケーション４による処理結果である制約条件を満たす解をオペレータに提示するためのものである。
【００１１】
制約定義記憶部６は、入力装置２から直接入力され又は図示しない記憶媒体から読み出されて入力され又は図示しない通信媒体を介して他の装置等から入力された、アプリケーション４が扱う制約変数間の関係式で表される制約条件の集合からなる制約定義を記憶している。また、データドメイン記憶部７は、前記同様の態様で入力された、制約変数の取り得る値の集合であるデータドメインを該制約変数の名前である制約変数名とともに記憶している。
【００１２】
制約処理機能部８は、アプリケーション４から制約定義及びデータドメインそれぞれの所在に関する情報を入力し、これら入力した情報に基づいて、制約定義記憶部６及びデータドメイン記憶部７から、それぞれ制約定義及びデータドメインを読み込む。そして、制約充足ソルバ５に、読み込んだ制約定義及びデータドメインを該制約充足ソルバ５固有の内部表現に変換させ、得られた制約の内部表現をアプリケーション４に出力する。
【００１３】
これらの機能を実現するため、制約処理機能部８は、制約変数管理手段８１及び制約条件構築手段８２とからなる構成をとる。
【００１４】
制約変数管理手段８１は、制約定義記憶部６から制約定義を読み込み、該制約定義から制約変数を抽出し、該制約変数の制約変数名をキーとしてデータドメイン記憶部７から当該制約変数のデータドメインを取得し、制約充足ソルバ５固有の内部表現に変換し、これを制約変数名とともに記憶する。
【００１５】
制約条件構築手段８２は、前記制約変数管理手段８１から渡された制約定義もしくは制約定義記憶部６から制約定義を読み込み、該制約定義から関係式を抽出し、前記制約変数管理手段８１に記憶された制約充足ソルバ固有の内部表現に変換された制約変数を利用して、前記抽出した関係式を制約充足ソルバ５固有の内部表現として構築する。
【００１６】
図２は制約変数管理手段８１の処理手順を示すフローチャート、図３は制約条件構築手段８２の処理手順を示すフローチャートであり、以下、これらに従って、本発明装置の動作について詳細に説明する。
【００１７】
最初に、制約変数管理手段８１が処理を行う。制約変数管理手段８１は、制約定義記憶部６から制約定義を読み込み（ｓ１）、該読み込んだ制約定義から字句を一つずつ抜き出す（ｓ２）。そして、抜き出した字句が予め決められた制約変数名の条件（例えばアルファベットから始まる文字列）にマッチする（ｓ３）なら、その文字列、即ち制約変数名を記憶するとともに、この制約変数名をキーとしてデータドメイン記憶部７から当該制約変数のデータドメインを取得する（ｓ４）。続いて、その字句について、制約充足ソルバ５固有の内部表現に変換する（ｓ５）。そして、制約変数名と変換された制約変数の実体あるいは参照を関連付けて記憶する（ｓ６）。この作業を全ての字句について行い（ｓ７）、その後、制約定義の実体あるいはそれへの参照を制約条件構築手段８２へ渡し（ｓ８）、処理を終了する。
【００１８】
続いて、制約条件構築手段８２が処理を行う。制約条件構築手段８２は制約定義を読み込み（ｓ１１）、該読み込んだ制約定義から関係式を一つずつ抜き出す（ｓ１２）。そして、抜き出した関係式の構文解析を行い（ｓ１３）、所定の方法により、制約充足ソルバ５固有の内部表現として構築する。
【００１９】
具体的には、関係式の中に用いられている字句を一つずつ読み込み、読み込んだ字句について、制約変数名、演算子、括弧に分類した上で、関係式の意味を損なわないために演算子の優先順位、括弧の位置を考慮し、演算子に該当する制約変数間の制約を制約充足ソルバ５に定義されたインタフェースを適宜呼び出すことで該制約充足ソルバ５の中に制約を内部表現として構築する。この処理に必要となる制約変数の実体あるいは参照は、制約変数名をキーに制約変数管理手段８１より取得する。そして、このようにして構築した制約充足ソルバ５固有の内部表現による関係式を該制約充足ソルバ５に追加する（ｓ１４）。
【００２０】
この処理を全ての関係式について個別に行い（ｓ１５）、関係式がなくなった時点で処理を終了する（ｓ１６）。
【００２１】
以上の処理が終了すると、制約処理機能部８は制約充足ソルバ５の内部表現をアプリケーション４に出力として渡し、処理を終了する。
【００２２】
次に、本発明における処理の詳細について例を挙げて説明する。
【００２３】
本例において、アプリケーション４が扱うデータ間の制約（制約定義）は、制約定義記憶部６に記憶されたファイル「ｃｏｎｓｔ．ｔｘｔ」に記述され、各データのドメインは、データドメイン記憶部７に記憶されたファイル「ｄａｔａ．ｔｘｔ」に記述されているとする。「ｃｏｎｓｔ．ｔｘｔ」及び「ｄａｔａ．ｔｘｔ」の内容をそれぞれ図４及び図５に示す。
【００２４】
以下、制約処理機能部８がこれらのファイルを入力した時に、制約を構築するまでの処理手順を以下に示す。
【００２５】
１．制約処理機能部８の制約変数管理手段８１は、アプリケーション４よりファイル「ｃｏｎｓｔ．ｔｘｔ」とファイル「ｄａｔａ．ｔｘｔ」の所在の情報を入力する。
【００２６】
２．制約変数管理手段８１は、入力した所在の情報に基づいて、制約定義記憶部６及びデータドメイン記憶部７から各ファイルを入力する。
【００２７】
３．制約変数名として「ａ」を抜き出す。
【００２８】
４．変数名「ａ」をキーとしてファイル「ｄａｔａ．ｔｘｔ」を参照して値域｛１，３，５｝を取得する。
【００２９】
５．「ａ」を制約充足ソルバ５のインタフェースを用いて制約充足ソルバ５固有の内部表現に変換し、制約変数名をキーとして変換された実体への参照を記憶する。
【００３０】
６．制約変数名として「ｂｂ」を抜き出す。
【００３１】
７．変数名「ｂｂ」をキーにファイル「ｄａｔａ．ｔｘｔ」を参照して値域｛２，３，４｝を取得する。
【００３２】
８．「ｂｂ」を制約充足ソルバ５のインタフェースを用いて制約充足ソルバ５固有の内部表現に変換し、制約変数名をキーとして変換された実体への参照を記憶する。
【００３３】
９．制約変数名として「ｃ１」を抜き出す。
【００３４】
１０．変数名「ｃ１」をキーにファイル「ｄａｔａ．ｔｘｔ」を参照して値域｛３，４｝を取得する。
【００３５】
１１．「ｃ１」を制約充足ソルバ５のインタフェースを用いて制約充足ソルバ５固有の内部表現に変換し、制約変数名をキーとして変換された実体への参照を記憶する。
【００３６】
１２．制約変数管理手段８１は、以降の字句がないことを認識し、ファイル「ｃｏｎｓｔ．ｔｘｔ」を制約条件構築手段８２へ渡し、処理を終了する。
【００３７】
１３．制約条件構築手段８２は、制約変数管理手段８１からファイル「ｃｏｎｓｔ．ｔｘｔ」を入力する。
【００３８】
１４．関係式「（ａ＝＝３）‖（ｂｂ！＝２）」を抜き出す。
【００３９】
１５．関係式「（ａ＝＝３）‖（ｂｂ！＝２）」に相当する制約定義を制約充足ソルバ５のインタフェースを用いて制約充足ソルバ５固有の内部表現として構築し、制約充足ソルバ５に出力する。この時、字句「ａ」と「ｂｂ」は、制約変数名をキーとして参照を取得し、制約定義の構築に利用する。
【００４０】
１６．関係式「（ｃ１＞＝４）＆＆（ａ＜＝５）」を抜き出す。
【００４１】
１７．関係式「（ｃ１＞＝４）＆＆（ａ＜＝５）」に相当する制約定義を制約充足ソルバ５のインタフェースを用いて構築し、制約充足ソルバ５に出力する。この時、字句「ｃ１」と「ａ」は、制約変数名をキーとして参照を取得し、制約定義の構築に利用する。
【００４２】
１８．制約条件構築手段８２は、以降の制約条件がないことを認識し、処理を終了する。
【００４３】
以上の手順により、独立に定義された制約条件をアプリケーション４の実行時に動的に取得し、構築することが可能となる。
【００４４】
これ以降は、制約充足ソルバ５のインタフェースを適切に呼び出すことで、制約条件に示された制約を満たす解集合を取得することが可能である。
【００４５】
なお、これまでの説明では、特に制約充足ソルバを特定しないで発明の処理手順を示したが、先の項でも示したように、種々の制約充足ソルバにおいて処理の流れに本質的な違いはないので、それぞれの制約充足ソルバのインタフェースを適当に用いることで、上記手順は実行可能である。
【００４６】
また、本例では、制約定義ファイルのデータ間の制約の表現方法とその意味は、Ｃ言語やＪａｖａ（登録商標）などのプログラミング言語で条件式の記述に用いられているものを利用したが、本来、これは制約処理機能部８が要求するものであり、制約処理機能部８が処理可能なものであることが必要条件である。また、ドメインを管理するファイルやデータベースのデータ構造についても同様で、制約処理機能部８が処理できるものであることが要求される。
【００４７】
＜実施の形態の他の例＞
前述した実施の形態では、アプリケーションと制約処理機能部を独立にした構成を示したが、制約処理機能部の全部あるいは一部の機能をアプリケーションの内部に組み込む構成も可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明のアプリケーションの実行装置の実施の形態の一例を示す構成図
【図２】制約変数管理手段の処理手順を示すフローチャート
【図３】制約条件構築手段の処理手順を示すフローチャート
【図４】制約条件式の一例を示す図
【図５】データファイルの一例を示す図
【符号の説明】
【００４９】
１：コンピュータ、２：入力装置、３：表示装置、４：アプリケーション（プログラム）、５：制約充足ソルバ、６：制約定義記憶部、７：データドメイン記憶部、８：制約処理機能部、８１：制約変数管理手段、８２：制約条件構築手段。
【図１】
2007328580.tif 000003
【図２】
2007328580.tif 000004
【図３】
2007328580.tif 000005
【図４】
2007328580.tif 000006
【図５】
2007328580.tif 000007