(57)【要約】【課題】制約伝播法において、任意の算術式を用いて表現された制約を効率良く処理することができる制約伝播装置２０を提供する。【解決手段】本発明の制約伝播装置２０は、変数または１つ以上の変数で表現される式のいずれかである引数を用いて制約を表現し、当該制約毎に制約を満足する可能性のない値を引数のドメインから削除するドメイン変更処理を設け、当該ドメイン変更処理において引数のドメインが変更された場合に、ドメインが変更された引数が式ならば、当該式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインを再計算し、ドメインが変更された引数が変数ならば、当該変数を用いて表現される全ての式のそれぞれについて、当該式のドメインを再計算する。【選択図】図１
2008226096.tif 000002
【特許請求の範囲】
【請求項１】
有限個の変数と、変数毎に当該変数が取りうる値の集合を示すドメインとを用いて、与えられた制約を満たさない値をそれぞれの変数のドメインから削除することにより、与えられた制約を満たす変数のドメインを出力する制約伝播装置であって、
前記制約は、定数および１つ以上の引数、または、複数の引数を用いて表現され、
前記引数は、変数、または、式であり、
前記式は、定数および１つ以上の変数、または、複数の変数を用いて表現され、
前記引数が式である場合には、当該引数のドメインは、当該式に含まれるそれぞれの変数のドメインから算出され、
前記制約には、当該制約を満たさない引数の値を、当該引数のドメインから削除するための１つ以上のドメイン変更処理が記述されており、
前記制約に記述されているドメイン変更処理毎に、当該ドメイン変更処理を含む変更要求を生成して変更要求格納手段に格納する変更要求生成手段と、
前記変更要求格納手段に格納されている変更要求を１つずつ選択し、選択した変更要求に含まれるドメイン変更処理を実行する変更要求実行手段と、
前記変更要求実行手段によって、前記ドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式か否かを判定し、
実行されたドメイン変更処理で用いられた引数が式である場合に、当該式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求格納手段に格納し、
実行されたドメイン変更処理で用いられた引数が変数である場合に、当該変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して前記計算要求格納手段に格納する第一の計算要求登録手段と、
前記計算要求格納手段内の前記変数計算要求または前記式計算要求を１つずつ実行する計算要求実行手段と
を備えることを特徴とする制約伝播装置。
【請求項２】
請求項１に記載の制約伝播装置であって、
前記第一の計算要求登録手段は、
前記変更要求実行手段によって実行されたドメイン変更処理で用いられた引数のドメインが変化した場合に、実行されたドメイン変更処理で用いられた引数が式か否かを判定することを特徴とする制約伝播装置。
【請求項３】
請求項１に記載の制約伝播装置であって、
前記制約には、前記ドメイン変更処理毎に、当該ドメイン変更処理を実行するための条件がさらに記述されており、
前記変更要求実行手段によって前記ドメイン変更処理が１つ実行されるたびに、当該ドメイン変更処理の対象となっている引数のドメインの変更が、いずれかの前記制約の条件に該当するか否かを判定し、該当する条件に対応するドメイン変更処理を含む変更要求を新たに生成して変更要求格納手段に格納する変更要求再生成手段
をさらに備えることを特徴とする制約伝播装置。
【請求項４】
請求項３に記載の制約伝播装置であって、
前記条件は、対応する制約に用いられる引数のドメインの、下限値の変化を示す情報、上限値の変化を示す情報、または、全体の変化を示す情報のいずれかであることを特徴とする制約伝播装置。
【請求項５】
請求項３に記載の制約伝播装置であって、
前記変更要求再生成手段は、さらに、
前記計算要求実行手段によって前記計算要求格納手段内の前記変数計算要求または前記式計算要求が１つ実行されるたびに、当該計算要求の対象となっている変数または式のドメインの変更が、いずれかの前記制約の条件に該当するか否かをさらに判定し、該当する条件に対応するドメイン変更処理を含む変更要求を新たに生成して変更要求格納手段に格納することを特徴とする制約伝播装置。
【請求項６】
請求項５に記載の制約伝播装置であって、
前記変更要求再生成手段は、
前記変更要求実行手段によって実行されたドメイン変更処理で用いられた引数のドメインが変化した場合に、当該ドメイン変更処理の対象となっている引数のドメインの変更が、いずれかの前記制約の条件に該当するか否かを判定し、
前記計算要求実行手段によって実行された前記変数計算要求で用いられた変数または前記式計算要求で用いられた式のドメインが変化した場合に、当該計算要求の対象となっている変数または式のドメインの変更が、いずれかの前記制約の条件に該当するか否かを判定することを特徴とする制約伝播装置。
【請求項７】
請求項１に記載の制約伝播装置であって、
前記計算要求実行手段によって前記計算要求格納手段内の前記変数計算要求または前記式計算要求が１つ実行されるたびに、実行された計算要求が変数計算要求か否かを判定し、実行された計算要求が変数計算要求である場合に、当該変数計算要求で対象となる変数を保持し、
当該変数計算要求で用いられた式以外のそれぞれの式について前記式計算要求を生成して前記計算要求格納手段に格納し、
さらに、当該式計算要求の対象となるそれぞれの式について、当該式で用いられる変数の中で、保持している変数以外の全ての変数について前記変数計算要求を生成して前記計算要求格納手段に格納する第二の計算要求登録手段をさらに備え、
前記変更要求実行手段は、
前記計算要求格納手段に格納されている全ての計算要求が前記計算要求実行手段によって実行された後に、前記変更要求格納手段に格納されている次の変更要求を１つ選択することを特徴とする制約伝播装置。
【請求項８】
請求項１に記載の制約伝播装置であって、
前記変更要求実行手段によってドメイン変更処理が１つ実行された結果、当該ドメイン変更処理で用いられた引数のドメインが空になった場合、または、前記計算要求実行手段によって前記計算要求格納手段内の前記変数計算要求または前記式計算要求が１つ実行された結果、当該計算要求で対象とする変数または式のドメインが空になった場合に、与えられた全ての制約を満たす変数の値が存在しない旨と共に、ドメインが空になった変数または式を示す情報、当該ドメイン変更処理を示す情報、および、当該ドメイン変更処理を含む制約を示す情報を出力する失敗判定手段
をさらに備えることを特徴とする制約伝播装置。
【請求項９】
請求項８に記載の制約伝播装置であって、
前記制約には、失敗と判定されるべき、変数または式のドメインの状態を規定する失敗条件がさらに記述されており、
前記失敗判定手段は、さらに、
前記変更要求実行手段によってドメイン変更処理が１つ実行された結果、当該ドメイン変更処理で用いられた引数のドメインが前記失敗条件に該当する場合、または、前記計算要求実行手段によって前記計算要求格納手段内の前記変数計算要求または前記式計算要求が１つ実行された結果、当該計算要求で対象とする変数または式のドメインが前記失敗条件に該当する場合に、与えられた全ての制約を満たす変数の値が存在しない旨と共に、ドメインが空になった変数または式を示す情報、当該ドメイン変更処理を示す情報、および、当該ドメイン変更処理を含む制約を示す情報を出力することを特徴とする制約伝播装置。
【請求項１０】
有限個の変数と、変数毎に当該変数が取りうる値の集合を示すドメインとを用いて、与えられた制約を満たさない値をそれぞれの変数のドメインから削除することにより、与えられた制約を満たす変数のドメインを出力する制約伝播装置における制約伝播方法であって、
前記制約は、定数および１つ以上の引数、または、複数の引数を用いて表現され、
前記引数は、変数、または、式であり、
前記式は、定数および１つ以上の変数、または、複数の変数を用いて表現され、
前記引数が式である場合には、当該引数のドメインは、当該式に含まれるそれぞれの変数のドメインから算出され、
前記制約には、当該制約を満たさない引数の値を、当該引数のドメインから削除するための１つ以上のドメイン変更処理が記述されており、
前記制約伝播装置は、
前記制約に記述されているドメイン変更処理毎に、当該ドメイン変更処理を含む変更要求を生成して変更要求格納手段に格納する変更要求生成ステップと、
前記変更要求格納手段に格納されている変更要求を１つずつ選択し、選択した変更要求に含まれるドメイン変更処理を実行する変更要求実行ステップと、
前記変更要求実行ステップにおいて前記ドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式か否かを判定し、
実行されたドメイン変更処理で用いられた引数が式である場合に、当該引数に対応する式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求格納手段に格納し、
実行されたドメイン変更処理で用いられた引数が変数である場合に、当該引数に対応する変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して前記計算要求格納手段に格納する第一の計算要求登録ステップと、
前記計算要求格納手段内の前記変数計算要求または前記式計算要求を１つずつ実行する計算要求処理ステップと
を実行することを特徴とする制約伝播方法。
【請求項１１】
コンピュータを、有限個の変数と、変数毎に当該変数が取りうる値の集合を示すドメインとを用いて、与えられた制約を満たさない値をそれぞれの変数のドメインから削除することにより、与えられた制約を満たす変数のドメインを出力する制約伝播装置として機能させるプログラムであって、
前記制約は、定数および１つ以上の引数、または、複数の引数を用いて表現され、
前記引数は、変数、または、式であり、
前記式は、定数および１つ以上の変数、または、複数の変数を用いて表現され、
前記引数が式である場合には、当該引数のドメインは、当該式に含まれるそれぞれの変数のドメインから算出され、
前記制約には、当該制約を満たさない引数の値を、当該引数のドメインから削除するための１つ以上のドメイン変更処理が記述されており、
前記コンピュータを、
前記制約に記述されているドメイン変更処理毎に、当該ドメイン変更処理を含む変更要求を生成して変更要求格納手段に格納する変更要求生成手段、
前記変更要求格納手段に格納されている変更要求を１つずつ選択し、選択した変更要求に含まれるドメイン変更処理を実行する変更要求実行手段、
前記変更要求実行手段によって、前記ドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式か否かを判定し、
実行されたドメイン変更処理で用いられた引数が式である場合に、当該引数に対応する式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求格納手段に格納し、
実行されたドメイン変更処理で用いられた引数が変数である場合に、当該引数に対応する変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して前記計算要求格納手段に格納する第一の計算要求登録手段、および
前記計算要求格納手段内の前記変数計算要求または前記式計算要求を１つずつ実行する計算要求実行手段
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物流の配送計画、工場の生産計画、機材や要員の配置計画等の各種スケジューリング、回路設計、画像処理、遺伝子解析、言語処理等の様々な分野において、制約充足問題を解くために用いられる制約伝播法、すなわち、与えられた有限個の変数と、各変数の取りうる値の領域（ドメイン）と、変数の値に関する有限個の制約の下で、制約を満足する可能性がない無効な値を各変数のドメインから削除する技術に関する。
【背景技術】
【０００２】
従来から広く認知されている制約伝播法は、制約が関与する各変数の全ての値の組合せに対して、制約を満足するかどうかを判定する方式が利用されてきた。例えば、変数ｘと変数ｙとの間に制約Ｃ（ｘ、ｙ）があるとすると、変数ｘのドメインの中から値を１つ取り出し、当該取り出した値について、制約Ｃ（ｘ，ｙ）を満足する値が変数ｙのドメイン中に存在するかどうかを判定し、そのような値が存在しなければ、取り出した値を変数ｘのドメインから削除する。そして、変数ｘのドメインから値がひとつでも削除された場合には、変数ｘが関与する他の全ての制約（Ｃ’（ｘ，ｙ’））に対して、ｘとｙ’との間で同様の判定処理（ただし変数ｙ’の値が削除対象）を行う。
【０００３】
このように、従来の制約伝播法は、制約を満足しない値が削除されなくなるまで判定処理を繰返し実行するというものである。このような従来の制約伝播方法は、変数ｘのドメインの要素数をＸ、変数ｙのドメインの要素数をＹとすると、変数ｘと変数ｙとに適用される制約１個に対して、充足判定をＸ×Ｙ回実行する必要がある。一般的には制約伝播が終了するまでに複数の制約に対して充足判定をおこなう必要があることから、処理時間が非常に大きくなるという問題点がある。
【０００４】
これに対して、特許文献１または特許文献２に開示された技術では、制約を満足する可能性のない値を変数のドメインから削除するプログラム（伝播ルーチンと呼ばれる）を制約の種類毎に予め用意しておき、前述の充足判定処理に代えて伝播ルーチンを一回実行することで処理時間の短縮を図っている。
【０００５】
【特許文献１】特開平５−２１６６６９号公報
【特許文献２】特開平９−３４７１８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、例えば変数ｘと変数ｙとの大小関係を定める「ｘ＜ｙ」を制約として用いることができるが、記号「＜」を用いた制約としては、「３ｘ＜ｙ＋４」、「ｘ＋２ｙ＜ｚ＋３」、「ｘ２−９ｙ＜ｚ３」等のように、両辺に単純な変数ではなく、変数を組合せた「算術式」を取るものが考えられる。これらは制約の種類（＜）こそ共通しているものの、関与する式の形がそれぞれ異なるため、制約を満足するように変数のドメインを正しく保つという観点からは実際には異なる制約と言える。
【０００７】
したがって、特許文献１または特許文献２に開示された技術では、変数のドメインを変更するための伝播ルーチンを、各制約毎（算術式毎）に個別に定義する必要がある。しかし、あらゆる算術式が用いられる可能性を考慮して、全ての制約それぞれに対応する伝播ルーチンをもれなく定義することは、現実的には不可能である。
【０００８】
本発明は上記事情を鑑みてなされたものであり、本発明の目的は、制約伝播法において、任意の算術式を用いて表現された制約を効率良く処理できるようにすることにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明は、変数または１つ以上の変数で表現される式のいずれかである引数を用いて制約を表現し、当該制約毎に制約を満足する可能性のない値を引数のドメインから削除するドメイン変更処理を設け、当該ドメイン変更処理において引数のドメインが変更された場合に、ドメインが変更された引数が式ならば、当該式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインを再計算し、ドメインが変更された引数が変数ならば、当該変数を用いて表現される全ての式のそれぞれについて、当該式のドメインを再計算する。
【００１０】
例えば、本発明の第１の態様は、有限個の変数と、変数毎に当該変数が取りうる値の集合を示すドメインとを用いて、与えられた制約を満たさない値をそれぞれの変数のドメインから削除することにより、与えられた制約を満たす変数のドメインを出力する制約伝播装置であって、制約は、定数および１つ以上の引数、または、複数の引数を用いて表現され、引数は、変数、または、式であり、式は、定数および１つ以上の変数、または、複数の変数を用いて表現され、引数が式である場合には、当該引数のドメインは、当該式に含まれるそれぞれの変数のドメインから算出され、制約には、当該制約を満たさない引数の値を、当該引数のドメインから削除するための１つ以上のドメイン変更処理が記述されており、制約に記述されているドメイン変更処理毎に、当該ドメイン変更処理を含む変更要求を生成して変更要求格納手段に格納する変更要求生成手段と、変更要求格納手段に格納されている変更要求を１つずつ選択し、選択した変更要求に含まれるドメイン変更処理を実行する変更要求実行手段と、変更要求実行手段によって、ドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式か否かを判定し、実行されたドメイン変更処理で用いられた引数が式である場合に、当該引数に対応する式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求格納手段に格納し、実行されたドメイン変更処理で用いられた引数が変数である場合に、当該引数に対応する変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して計算要求格納手段に格納する第一の計算要求登録手段と、計算要求格納手段内の変数計算要求または式計算要求を１つずつ実行する計算要求実行手段とを備えることを特徴とする制約伝播装置を提供する。
【００１１】
また、本発明の第２の態様は、有限個の変数と、変数毎に当該変数が取りうる値の集合を示すドメインとを用いて、与えられた制約を満たさない値をそれぞれの変数のドメインから削除することにより、与えられた制約を満たす変数のドメインを出力する制約伝播装置における制約伝播方法であって、制約は、定数および１つ以上の引数、または、複数の引数を用いて表現され、引数は、変数、または、式であり、式は、定数および１つ以上の変数、または、複数の変数を用いて表現され、引数が式である場合には、当該引数のドメインは、当該式に含まれるそれぞれの変数のドメインから算出され、制約には、当該制約を満たさない引数の値を、当該引数のドメインから削除するための１つ以上のドメイン変更処理が記述されており、制約伝播装置は、制約に記述されているドメイン変更処理毎に、当該ドメイン変更処理を含む変更要求を生成して変更要求格納手段に格納する変更要求生成ステップと、変更要求格納手段に格納されている変更要求を１つずつ選択し、選択した変更要求に含まれるドメイン変更処理を実行する変更要求実行ステップと、変更要求実行ステップにおいてドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式か否かを判定し、実行されたドメイン変更処理で用いられた引数が式である場合に、当該引数に対応する式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求格納手段に格納し、実行されたドメイン変更処理で用いられた引数が変数である場合に、当該引数に対応する変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して計算要求格納手段に格納する第一の計算要求登録ステップと、計算要求格納手段内の変数計算要求または式計算要求を１つずつ実行する計算要求処理ステップとを実行することを特徴とする制約伝播方法を提供する。
【００１２】
また、本発明の第３の態様は、コンピュータを、有限個の変数と、変数毎に当該変数が取りうる値の集合を示すドメインとを用いて、与えられた制約を満たさない値をそれぞれの変数のドメインから削除することにより、与えられた制約を満たす変数のドメインを出力する制約伝播装置として機能させるプログラムであって、制約は、定数および１つ以上の引数、または、複数の引数を用いて表現され、引数は、変数、または、式であり、式は、定数および１つ以上の変数、または、複数の変数を用いて表現され、引数が式である場合には、当該引数のドメインは、当該式に含まれるそれぞれの変数のドメインから算出され、制約には、当該制約を満たさない引数の値を、当該引数のドメインから削除するための１つ以上のドメイン変更処理が記述されており、コンピュータを、制約に記述されているドメイン変更処理毎に、当該ドメイン変更処理を含む変更要求を生成して変更要求格納手段に格納する変更要求生成手段、変更要求格納手段に格納されている変更要求を１つずつ選択し、選択した変更要求に含まれるドメイン変更処理を実行する変更要求実行手段、変更要求実行手段によって、ドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式か否かを判定し、実行されたドメイン変更処理で用いられた引数が式である場合に、当該引数に対応する式で用いられている全ての変数のそれぞれについて、当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求格納手段に格納し、実行されたドメイン変更処理で用いられた引数が変数である場合に、当該引数に対応する変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して計算要求格納手段に格納する第一の計算要求登録手段、および計算要求格納手段内の変数計算要求または式計算要求を１つずつ実行する計算要求実行手段として機能させることを特徴とするプログラムを提供する。
【発明の効果】
【００１３】
本発明によれば、制約伝播法において、任意の算術式を用いて表現された制約を効率良く処理することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態について説明する。
【００１５】
図１は、本発明の一実施形態に係る制約伝播処理システム１０の構成を示すシステム構成図である。制約伝播処理システム１０は、例えばキーボード等の入力装置１１、例えばディスプレイ等の出力装置１２、および制約伝播装置２０を備える。
【００１６】
制約伝播装置２０は、制約とは無関係に与えられた変数および式のドメインを、制約を満たすように修正する初期伝播において、変数に関する変数データ、式に関する式データ、およびこれら変数および式の値が満たすべき制約に関する制約データを、入力装置１１を介してユーザから受け付ける。そして、制約伝播装置２０は、受け付けた変数および式に関するデータの中から、受け付けた制約を全て満たす値を出力装置１２へ出力する。
【００１７】
また、初期伝播によって変数および式のドメインが正しく保たれている状況下で特定の変数もしくは式のドメインを変更し、制約を満たすように他の変数または式のドメインを修正する再伝播において、制約伝播装置２０は、変数データ、式データ、および制約データに加えて、どの変数または式のドメインをどのように変更するかを示す変更情報を、入力装置１１を介して受け付ける。そして、制約伝播装置２０は、ドメインの変更を反映した変数および式に関するデータの中から、受け付けた制約を全て満たす値を出力装置１２へ出力する。
【００１８】
ここで、入力装置１１を介して制約伝播装置２０へ入力されるデータについて説明する。図２は、変数データ３０のデータ構造の一例を示す。変数データ３０には、それぞれの変数を識別する変数ＩＤ３１毎に、変数名３２、および、対応する変数が取りうる値の範囲を示すドメイン３３が含まれる。
【００１９】
変数は、離散的な値をとる。本実施形態において変数は整数である。ドメインの表記における[a..b]は、変数が取りうる値の最小値がａ、最大値がｂであり、変数は、ａおよびｂの間にある連続する全ての整数を値として取りうることを示している。なお、区間[a..b]において、ａ≦ｂを常に満足するものとする。ドメインは１個以上の重なりがない区間の集まりであり、図２の例では、変数ｘは、区間[7..9]もしくは区間[12..15]の中のいずれかの値を取ることが示されている。
【００２０】
図３は、式データ４０のデータ構造の一例を示す。式データ４０には、それぞれの式を識別する式ＩＤ４１毎に、式名４２、対応する式の構成を示す構成情報４３、式に含まれる引数に用いられる変数ＩＤである引数ＩＤ４４、および、対応する式が取りうる値の範囲を示すドメイン４５が含まれる。
【００２１】
本実施形態において、式は、定数および１つ以上の変数、または、複数の変数を用いて表現される。図３では、式ｅ１が、引数ｘ１およびｘ２を用いて「ｅ１＝ｘ１＋２＊ｘ２」と定義されている例が示されている。また、図３において、引数ＩＤ４４−１は引数ｘ１に適用される変数のＩＤを示し、引数ＩＤ４４−２は引数ｘ２に適用される変数のＩＤを示している。式を構成する変数は内部変数と呼ばれる。また、式は、図３に示すように２個の内部変数を用いて表現されるものに限定されない。
【００２２】
式のドメインは、当該式に用いられる変数のドメインを、当該式の構成情報に従って演算することによって得られる。例えば図３の式ｅ１は、引数ｘ１の実体である変数ｙのドメインに対して、引数ｘ２の実体である変数ｚのドメインを２倍して加えることで得られる。すなわち、まず引数ｘ２のドメイン｛[2..3]｝を２倍して｛[4..6]｝を得て、その区間[4..6]を引数ｘ１のドメイン｛[1..2],[5..7]｝の各区間へ足し込めば良い。区間同士の足し算は、両者の下限値同士と上限値同士を単純に足し合わせれば良い。これにより式ｅ１のドメインは、図３に示すように｛[5..8],[9..13]｝となる。
【００２３】
図４は、制約データ５０のデータ構造の一例を示す。制約データ５０には、それぞれの制約を識別する制約ＩＤ５１毎に、１つ以上の引数を用いて制約の具体的な内容を示す制約内容５２、制約内容５２に含まれる引数に用いられる式または変数のＩＤである引数ＩＤ５３、制約内容５２に含まれるいずれか１つの引数のドメインを変更する処理を規定するドメイン変更ルール（図５において後述）を識別するルールＩＤ５４、および、ドメイン変更の失敗を判定するための失敗条件５５が含まれる。
【００２４】
図４において、引数ＩＤ５３−１は引数ｘ１に適用される変数または式のＩＤを示し、引数ＩＤ５３−２は引数ｘ２に適用される変数または式のＩＤを示している。また、図４では、例えば制約ＩＤが「０００１」に対応する制約の場合、制約内容は「ｘ１＜ｘ２（引数ｘ１は引数ｘ２よりも小さい）」であり、引数はｘ１とｘ２の２つであり、ドメイン変更ルールも２つであり、失敗条件は「引数ｘ１または引数ｘ２のドメインが空」である。制約ＩＤが「０００１」に対応する制約の場合、引数ｘ１は図２に示した変数ｘを、引数ｘ２は図３に示した式ｅ１をそれぞれ参照している。なお、制約は、図４に示すように２個の引数および２個のドメイン変更ルールを有するものに限定されない。
【００２５】
ドメイン変更ルール６０には、例えば図５に示すように、それぞれのドメイン変更ルールを識別するルールＩＤ６１毎に、対応する制約を満たすために１つの引数のドメインを削除する処理を規定するドメイン変更処理６３、ドメイン変更処理６３を起動するための引数のドメインの変更態様を規定する条件６２、および、対応する制約の制約ＩＤ６４が含まれる。
【００２６】
ここで、ドメイン変更処理は、１つの制約について１つ以上定義される。制約毎に定義されたドメイン変更処理は、引数のドメインが、他の制約に対応するドメイン変更処理等によって変更された場合には、全て実行される必要がない場合が多い。例えば、「ｘ＜ｙ」なる制約に対応するドメイン変更処理は、「ｙのドメインにおいて、ｘの最小値以下のｙの値を削除する処理」と、「ｘのドメインにおいて、ｙの最大値以上のｘの値を削除する処理」となるが、これらの処理が実行されて、ｘとｙのドメインが共に制約「ｘ＜ｙ」を満たしている状態で、他の制約に対応するドメイン変更処理によって、例えばｘの最小値が変更された場合、ｙの最大値は変化していないので、「ｘのドメインにおいて、ｙの最大値以上のｘの値を削除する処理」は不要となる。
【００２７】
このように、他の制約に対応するドメイン変更処理等によって、どの引数のドメインがどのように変化したかに応じて、どのドメイン変更処理が実行されるべきかを、制約毎に予め設定することができる。図５に示した例では、「どの引数のドメインがどのように変化したか」を示す部分が条件６２に該当し、「どのようなドメイン変更処理が実行されるべきか」を示す部分がドメイン変更処理６３に該当する。
【００２８】
図５では、図４の制約ＩＤが「０００１」に対応する制約（ｘ１＜ｘ２）における２つのドメイン変更ルールが示されている。ルールＩＤが「３００１」に対応するドメイン変更ルールでは、「引数ｘ１の下限値が変化」するという条件が満たされた場合に、「引数ｘ２のドメインから引数ｘ１の最小値以下の値を削除」するというドメイン変更処理が起動されることが示されている。一方、ルールＩＤが「３００２」に対応するドメイン変更ルールでは、「引数ｘ２の上限値が変化」するという条件が満たされた場合に、「引数ｘ１のドメインから引数ｘ２の最大値以上の値を削除」するというドメイン変更処理が起動されることが示されている。
【００２９】
制約データ５０の失敗条件５５は、制約の引数（変数もしくは式）のドメインが制約を充足することができない状態を規定するものである。図４において、制約ＩＤが「０００１」に対応する失敗条件は、「ｘ１またはｘ２のドメインが空」である。「ドメインが空」とは、とりうる値が存在しないということであり、一般的にどのような制約であっても、引数の変数もしくは式のドメインがひとつでも空ならば制約の充足は不可能となる。
【００３０】
したがって、この「ドメインが空」という条件は、制約ＩＤが「０００１」に対応する制約に限らず、全ての制約に共通する普遍的なものである。図４では説明のわかりやすさのために普遍条件を「失敗条件」に明記したが、本実施形態では、後述するように、失敗判定処理においてこの普遍条件は明記しなくとも必ずチェックされるので、それ以外に失敗条件が存在しない制約については「失敗条件」の欄に何も設定されなくてもよい。
【００３１】
なお、制約固有の失敗条件としては様々なものが考えられる。例えば図６に示すように、「ｘ１、ｘ２、ｘ３は互いに異なる値を持つ」という制約の場合、「ｘ１、ｘ２、ｘ３のいずれかのドメインに含まれる値の中で、相異なる値の個数が３未満」という固有の失敗条件が存在する。すなわち、引数ｘ１、ｘ２、ｘ３のドメインはいずれも値１および値２を有し、どの引数のドメインも空ではないが、相異なる値の個数が２個（値１と値２）しかないため、ｘ１、ｘ２、ｘ３の値を互いに異なるように設定することが不可能である。
【００３２】
次に、図１を参照して、制約伝播装置２０の詳細な機能構成について説明する。制約伝播装置２０は、入力データ受付部２００、変更要求リスト格納部２０１、変更要求生成部２０２、変更要求再生成部２０３、変更要求実行部２０４、第一の計算要求登録部２０５、計算要求リスト格納部２０６、計算要求実行部２０７、第二の計算要求登録部２０８、失敗判定部２０９、および入力データ格納部２１０を備える。
【００３３】
入力データ受付部２００は、図２で説明した変数データ３０、図３で説明した式データ４０、図４で説明した制約データ５０、および、図５で説明したドメイン変更ルール６０を、入力装置１１を介してユーザから受け付ける。そして、入力データ受付部２００は、変数データ３０を入力データ格納部２１０内の変数テーブル２１１に、式データ４０を入力データ格納部２１０内の式テーブル２１２に、制約データ５０を入力データ格納部２１０内の制約テーブル２１３に、ドメイン変更ルール６０を入力データ格納部２１０内のドメイン変更ルールテーブル２１４に、それぞれ格納する。
【００３４】
また、入力データ受付部２００は、変数データ３０、式データ４０、制約データ５０、およびドメイン変更ルール６０と共に、変更情報をユーザから受け付けなかった場合に、初期伝播と判定し、初期伝播を示す情報を変更要求生成部２０２へ送る。一方、変数データ３０、式データ４０、制約データ５０、およびドメイン変更ルール６０と共に、変更情報をユーザから受け付けた場合、入力データ受付部２００は、再伝播と判定し、再伝播を示す情報と共に、受け付けた変更情報を変更要求生成部２０２へ送る。
【００３５】
変更要求生成部２０２は、入力データ受付部２００から初期伝播を示す情報を受信した場合に、ドメイン変更ルールテーブル２１４内のドメイン変更処理および当該ドメイン変更処理に対応付けられている制約ＩＤを全て取り出し、それぞれのドメイン変更処理について、ドメイン変更処理および当該ドメイン変更処理に対応する制約ＩＤを含む変更要求を生成して変更要求リスト格納部２０１に格納する。
【００３６】
また、変更要求生成部２０２は、入力データ受付部２００から、再伝播を示す情報と共に、変更情報を受信した場合に、どの変数または式のドメインをどのように変更するかを示す変更情報をドメイン変更処理とし、対応する制約ＩＤを空欄とする変更要求を生成して変更要求リスト格納部２０１に格納する。
【００３７】
変更要求リスト格納部２０１には、例えば図７に示すような変更要求リスト２０１０が格納される。変更要求リスト２０１０には、それぞれの変更要求を識別する変更要求ＩＤ２０１１毎に、制約ＩＤ２０１２およびドメイン変更処理２０１３が格納される。このように、変更要求とは、条件およびドメイン変更処理を含むドメイン変更ルールから条件を取り除いたものである。なお、ドメイン変更処理２０１３の欄には、ドメイン変更処理の詳細が格納される以外に、対応するドメイン変更処理を特定可能な、ドメイン変更処理の識別情報が格納されてもよい。
【００３８】
変更要求実行部２０４は、変更要求リスト格納部２０１内に格納された変更要求を１つずつ選択し、選択した変更要求に含まれる制約ＩＤに基づき変数テーブル２１１、式テーブル２１２、および制約テーブル２１３を参照して、引数のドメインを特定し、特定した引数のドメインを、選択した変更要求に含まれるドメイン変更処理に従って変更するドメイン変更処理を実行する。そして、変更要求実行部２０４は、ドメインの変更結果を変数テーブル２１１または式テーブル２１２に反映させる。
【００３９】
変更要求実行部２０４は、変更要求を処理するたびに、処理した変更要求を変更要求リスト格納部２０１内から削除し、変更要求リスト格納部２０１内に変更要求が存在しなくなった場合に、変数テーブル２１１および式テーブル２１２内のデータを出力装置１２へ出力する。
【００４０】
変更要求再生成部２０３は、変更要求実行部２０４によって変更要求が１つ処理されるたびに、当該変更要求に対応するドメイン変更処理で用いられる引数のドメインに変化があったか否かを判定する。当該引数のドメインに変化があった場合、変更要求再生成部２０３は、当該引数の実体（変数または式）のドメインの変化態様（例えばドメインの上限が変化した旨や下限が変化した旨等）を記憶する。
【００４１】
そして、変更要求再生成部２０３は、入力データ格納部２１０内のドメイン変更ルールテーブル２１４を参照して、記憶しているドメインの変化態様が、条件に該当するドメイン変更ルールを全て抽出し、抽出したそれぞれのドメイン変更ルールから変更要求を新たに生成し、生成した変更要求を変更要求リスト格納部２０１に格納する。
【００４２】
このように、変更要求実行部２０４によって引数のドメインが変更されたことにより、当該引数が関連する制約について、当該引数がこれらの制約を満たすか否かを再び検証することができ、１つの制約によって変更された引数のドメインの影響を他の制約へ伝播させることができる。
【００４３】
ここで、変更要求実行部２０４によって引数のドメインが変更された場合に、当該引数を用いて表現される制約に対応付けられているドメイン変更処理を全て抽出して変更要求実行部２０４に実行させるとすれば、変更要求再生成部２０３は、変更要求実行部２０４に無駄なドメイン変更処理を実行させることになる場合がある。これに対して、変更要求再生成部２０３は、引数のドメインの変化態様が条件に該当するドメイン変更ルールのドメイン変更処理を変更要求実行部２０４に実行させることにより、変更要求実行部２０４に無駄なドメイン変更処理を実行させることなく、制約を効率良く伝播させることができる。
【００４４】
第一の計算要求登録部２０５は、変更要求実行部２０４によって変更要求に含まれるドメイン変更処理が１つ実行されるたびに、実行されたドメイン変更処理で用いられた引数が式であるか否かを判定する。実行されたドメイン変更処理で用いられた引数が式である場合、第一の計算要求登録部２０５は、当該式で用いられている全ての変数について、ドメイン変更後の当該式のドメインを満たすように変数のドメインの再計算を要求する変数計算要求を生成して計算要求リスト格納部２０６に格納する。
【００４５】
一方、実行されたドメイン変更処理で用いられた引数が変数である場合、第一の計算要求登録部２０５は、当該変数を用いる全ての式のそれぞれについて、当該式のドメインの再計算を要求する式計算要求を生成して計算要求リスト格納部２０６に格納する。
【００４６】
計算要求リスト格納部２０６には、例えば図８に示すような計算要求リスト２０６０が格納される。計算要求リスト２０６０には、それぞれの計算要求を識別する計算要求ＩＤ２０６１毎に、ドメインの計算対象となる式の式ＩＤ２０６２、変数計算または式計算の別を示す種別２０６３、および、式を用いた変数計算において除外すべき変数のＩＤを示す除外変数２０６４が格納される。除外変数２０６４は、種別が変数計算の計算要求に対して除外変数がある場合に、後述する第二の計算要求登録部２０８によって設定される。
【００４７】
計算要求実行部２０７は、計算要求リスト格納部２０６内の計算要求を１つずつ実行する。ここで、処理する計算要求が式計算要求である場合、計算要求実行部２０７は、計算対象の式に関する情報を式テーブル２１２から取得し、当該式に用いられている変数に関する情報を変数テーブル２１１から取得する。そして、計算要求実行部２０７は、式の構成情報に従ってこれらの変数のドメインを計算して式のドメインを算出し、算出した式のドメインで式テーブル２１２内の対応する式のドメインを更新する。
【００４８】
一方、処理する計算要求が変数計算要求である場合、計算要求実行部２０７は、計算対象の式に関する情報を式テーブル２１２から取得し、当該式に用いられている変数に関する情報を変数テーブル２１１から取得する。そして、計算要求実行部２０７は、除外変数として設定されている変数以外の変数のドメインを、計算対象の式のドメインを満たすように再計算し、計算した変数のドメインで変数テーブル２１１内の対応する変数のドメインを更新する。
【００４９】
第二の計算要求登録部２０８は、計算要求実行部２０７によって計算要求リスト格納部２０６内の計算要求が１つ実行されるたびに、実行された計算要求が変数計算要求か否かを判定する。計算要求実行部２０７によって実行された計算要求が変数計算要求である場合、第二の計算要求登録部２０８は、当該変数計算要求で対象となった変数のＩＤを保持する。
【００５０】
そして、第二の計算要求登録部２０８は、当該変数計算要求の計算対象の式以外の式のそれぞれについて式計算要求を新たに生成して計算要求リスト格納部２０６に格納する。そして、第二の計算要求登録部２０８は、計算要求リスト格納部２０６に格納した式計算要求の対象となる式のそれぞれについて、当該式で用いられる変数の中で、保持している変数のＩＤを除外変数に設定した変数計算要求を生成して計算要求リスト格納部２０６に格納する。
【００５１】
失敗判定部２０９は、入力データ格納部２１０内の変数テーブル２１１および式テーブル２１２を監視し、変数または式のドメインが変化した場合に、制約テーブル２１３を参照して、ドメインが変化した変数または式のドメインが、空となったか否か、または、いずれかの制約に対応付けられている失敗条件に該当するか否かを判定する。
【００５２】
変数または式のドメインが空となったか、または、いずれかの制約に対応付けられている失敗条件に該当する場合、失敗判定部２０９は、与えられた全ての制約を満たす変数または式の値が存在しない旨を示す失敗情報２１５を入力データ格納部２１０に登録し、登録した失敗情報２１５を出力装置１２へ出力する。
【００５３】
このように、失敗判定部２０９は、制約の伝播過程で失敗条件が満たされた時点で、失敗を示す情報を出力するので、制約伝播装置２０は、制約を充足する変数の値が存在しない旨をより迅速にユーザに通知することができる。
【００５４】
なお、失敗情報２１５には、失敗と判定される直前に実行されたドメイン変更処理を識別する情報、当該ドメイン変更処理を含む制約ＩＤ、および、失敗と判定された原因となった変数または式のＩＤが含まれていてもよい。
【００５５】
次に、制約伝播装置２０の動作について、図９を用いて説明する。図９は、制約伝播装置２０の動作の一例を示すフローチャートである。入力データ受付部２００が、入力装置１１を介してユーザから、図２で説明した変数データ、図３で説明した式データ、図４で説明した制約データ、および図５で説明したドメイン変更ルールを受け付けた場合に、制約伝播装置２０は、本フローチャートに示す動作を開始する。
【００５６】
まず、入力データ受付部２００は、入力装置１１を介して受け付けた変数データ、式データ、制約データ、およびドメイン変更ルールを、入力データ格納部２１０内の変数テーブル２１１、式テーブル２１２、制約テーブル２１３、およびドメイン変更ルールテーブル２１４に、それぞれ格納する（Ｓ１００）。
【００５７】
次に、入力データ受付部２００は、変数データ、式データ、制約データ、およびドメイン変更ルールと共に、変更情報をユーザから受け付けたか否かを判定する（Ｓ１０１）。変数データ、式データ、制約データ、およびドメイン変更ルールと共に、変更情報をユーザから受け付けていない場合（Ｓ１０１：Ｎｏ）、入力データ受付部２００は、初期伝播と判定し、初期伝播を示す情報を変更要求生成部２０２へ送る。
【００５８】
そして、変更要求生成部２０２は、入力データ受付部２００から初期伝播を示す情報を受信し、ドメイン変更ルールテーブル２１４内のドメイン変更処理および当該ドメイン変更処理に対応付けられている制約ＩＤを全て取り出して変更要求を生成し、生成した変更要求を変更要求リスト格納部２０１に格納する（Ｓ１０２）。
【００５９】
変数データ、式データ、制約データ、およびドメイン変更ルールと共に、変更情報をユーザから受け付けた場合（Ｓ１０１：Ｙｅｓ）、入力データ受付部２００は、再伝播と判定し、再伝播を示す情報と共に、受け付けた変更情報を変更要求生成部２０２へ送る。そして、変更要求生成部２０２は、受信した変更情報をドメイン変更処理とし、制約ＩＤを空欄とする変更要求を生成して変更要求リスト格納部２０１に格納する（Ｓ１０３）。
【００６０】
次に、制約伝播装置２０は、変更要求リスト格納部２０１に格納された変更要求を処理する変更要求処理を実行する（Ｓ２００）。図１０は、変更要求処理（Ｓ２００）の一例を示すフローチャートである。
【００６１】
まず、変更要求実行部２０４は、変更要求リスト格納部２０１内に格納された変更要求を１つ選択し、選択した変更要求に含まれる制約ＩＤに基づき変数テーブル２１１、式テーブル２１２、および制約テーブル２１３を参照して、引数のドメインを特定し、特定した引数のドメインを、選択した変更要求に含まれるドメイン変更処理に従って変更するドメイン変更処理を実行する。そして、変更要求実行部２０４は、ドメインの変更結果を変数テーブル２１１または式テーブル２１２に反映させ、選択した変更要求を変更要求リスト格納部２０１から削除する（Ｓ２０１）。
【００６２】
次に、変更要求再生成部２０３は、入力データ格納部２１０を参照して、変更要求実行部２０４によって実行されたドメイン変更処理で用いられた引数のドメインに変化があったか否かを判定する（Ｓ２０２）。当該引数のドメインに変化がなかった場合（Ｓ２０２：Ｎｏ）、制約伝播装置２０は、本フローチャートに示した変更要求処理を終了する。
【００６３】
なお、ドメインは縮小、すなわちサイズが小さくなる方向へのみ変更が許可されるので、変数テーブル２１１および式テーブル２１２内のドメインは、ドメイン変更処理の結果が常に反映されるわけではない。そのため、ドメイン変更処理が実行されてもドメインが変化しない場合もありうる。
【００６４】
一方、当該引数のドメインに変化があった場合（Ｓ２０２：Ｙｅｓ）、変更要求再生成部２０３は、当該引数の実体（変数または式）のドメインの変化態様（例えばドメインの上限が変化した旨や下限が変化した旨）を記憶する。そして、失敗判定部２０９は、制約テーブル２１３を参照して、ドメインが変化した変数または式のドメインが、空となったか、または、いずれかの制約に対応付けられている失敗条件に該当するか否かを判定する（Ｓ２０３）。
【００６５】
ドメインが変化した変数または式のドメインが、空となった、または、いずれかの制約に対応付けられている失敗条件に該当する場合（Ｓ２０３：Ｙｅｓ）、失敗判定部２０９は、与えられた全ての制約を満たす変数または式の値が存在しない旨を示す失敗情報２１５を入力データ格納部２１０に登録し（Ｓ２０４）、制約伝播装置２０は、本フローチャートに示した変更要求処理を終了する。
【００６６】
ドメインが変化した変数または式のドメインが、空でもなく、いずれの制約に対応付けられている失敗条件にも該当しない場合（Ｓ２０３：Ｎｏ）、変更要求再生成部２０３は、変更要求の再生成処理を実行する（Ｓ４００）。図１１は、変更要求再生成処理（Ｓ４００）の一例を示すフローチャートである。
【００６７】
変更要求再生成部２０３は、入力データ格納部２１０内のドメイン変更ルールテーブル２１４を参照して、全てのドメイン変更ルールを選択したか否かを判定する（Ｓ４０１）。全てのドメイン変更ルールを選択した場合（Ｓ４０１：Ｙｅｓ）、変更要求再生成部２０３は、本フローチャートに示した変更要求再生成処理を終了する。
【００６８】
全てのドメイン変更ルールを選択していない場合（Ｓ４０１：Ｎｏ）、変更要求再生成部２０３は、ドメイン変更ルールテーブル２１４から未選択のドメイン変更ルールを１つ選択し（Ｓ４０２）、変更要求実行部２０４によってドメインが変更された引数について、当該変更の内容が、選択したドメイン変更ルールの条件に該当するか否かを判定する（Ｓ４０３）。ドメインの変更内容が、選択したドメイン変更ルールの条件に該当しない場合（Ｓ４０３：Ｎｏ）、変更要求再生成部２０３は、再びステップＳ４０１に示した処理を実行する。
【００６９】
ドメインの変更内容が、選択したドメイン変更ルールの条件に該当する場合（Ｓ４０３：Ｙｅｓ）、変更要求再生成部２０３は、選択したドメイン変更ルールから変更要求を新たに生成して変更要求リスト格納部２０１に格納し（Ｓ４０４）、変更要求再生成部２０３は、再びステップＳ４０１に示した処理を実行する。
【００７０】
以上、変更要求再生成処理（Ｓ４００）について説明した。なお、図１１の処理フローは、全てのドメイン変更ルールを対象として一致判定をおこなうが、条件に含まれる変数または式に従ってルールを事前に分類しておき、ドメインが変化した変数または式に関するルールだけを取り出して一致判定をおこなうこととしてもよい。これにより、判定対象を必要なルールだけに限定することができるので効率良く処理を行うことができる。
【００７１】
図１０に戻って変更要求処理（Ｓ２００）の説明を続ける。
【００７２】
変更要求再生成処理（Ｓ４００）が実行された後、第一の計算要求登録部２０５は、ステップＳ２０１において実行されたドメイン変更処理で用いられた引数が式であるか否かを判定する（Ｓ２０５）。ステップＳ２０１において実行されたドメイン変更処理で用いられた引数が式である場合（Ｓ２０５：Ｙｅｓ）、第一の計算要求登録部２０５は、当該式のＩＤ、変数計算を示す種別、および空欄の除外変数を含む変数計算要求を生成して計算要求リスト２０６０に格納し（Ｓ２０６）、制約伝播装置２０は、本フローチャートに示した変更要求処理を終了する。
【００７３】
一方、ステップＳ２０１において実行されたドメイン変更処理で用いられた引数が変数である場合（Ｓ２０５：Ｎｏ）、第一の計算要求登録部２０５は、当該変数を含む式のそれぞれについて、当該式のＩＤ、式計算を示す種別、および空欄の除外変数を含む式計算要求を生成して計算要求リスト２０６０に格納する（Ｓ２０７）。
【００７４】
そして、第一の計算要求登録部２０５は、ステップＳ２０７において計算要求リスト２０６０に登録されたそれぞれの式計算要求に含まれる式ＩＤについて、当該式ＩＤ、変数計算を示す種別、および、ステップＳ２０１おいてドメインが変更された変数を除外変数とする変数計算要求を生成して計算要求リスト２０６０に格納し（Ｓ２０８）、制約伝播装置２０は、本フローチャートに示した変更要求処理を終了する。
【００７５】
以上、変更要求処理（Ｓ２００）について説明した。図９に戻って説明を続ける。
【００７６】
変更要求処理（Ｓ２００）が実行された後、失敗判定部２０９は、入力データ格納部２１０を参照して、失敗情報２１５が登録されているか否かを判定する（Ｓ１０４）。失敗情報２１５が入力データ格納部２１０に登録されている場合（Ｓ１０４：Ｙｅｓ）、失敗判定部２０９は、失敗情報２１５を出力装置１２へ出力し（Ｓ１０８）、制約伝播装置２０は、本フローチャートに示す動作を終了する。
【００７７】
失敗情報２１５が入力データ格納部２１０に登録されていない場合（Ｓ１０４：Ｎｏ）、計算要求実行部２０７は、計算要求リスト格納部２０６内の計算要求リスト２０６０が空か否かを判定する（Ｓ１０５）。計算要求リスト２０６０が空の場合（Ｓ１０５：Ｙｅｓ）、変更要求実行部２０４は、変更要求リスト格納部２０１内の変更要求リスト２０１０が空か否かを判定する（Ｓ１０６）。
【００７８】
変更要求リスト２０１０が空ではない場合（Ｓ１０６：Ｎｏ）、制約伝播装置２０は、再び図１０を用いて説明した変更要求処理を実行する。一方、変更要求リスト２０１０が空である場合（Ｓ１０６：Ｙｅｓ）、変更要求実行部２０４は、入力データ格納部２１０内の変数テーブル２１１に格納されているデータおよび式テーブル２１２に格納されているデータを出力装置１２へ出力し（Ｓ１０７）、制約伝播装置２０は、本フローチャートに示す動作を終了する。
【００７９】
ステップＳ１０５において、計算要求リスト２０６０が空ではない場合（Ｓ１０５：Ｎｏ）、制約伝播装置２０は、計算要求リスト格納部２０６内の計算要求を処理する計算要求処理を実行し（Ｓ３００）、失敗判定部２０９は、再びステップＳ１０４に示した処理を実行する。
【００８０】
図１２は、計算要求処理（Ｓ３００）の一例を示すフローチャートである。
【００８１】
まず、計算要求実行部２０７は、計算要求リスト格納部２０６から計算要求を１つ選択して（Ｓ３０１）、選択した計算要求の種別が式計算か否かを判定する（Ｓ３０２）。選択した計算要求の種別が式計算である場合（Ｓ３０２：Ｙｅｓ）、計算要求に含まれる式ＩＤに対応する式データを式テーブル２１２から取得し、当該式データの引数に対応する変数の変数データを変数テーブル２１１から取得してドメイン再計算処理を実行する（Ｓ３０３）。
【００８２】
ステップＳ３０３のドメイン再計算処理では、計算要求実行部２０７は、選択した計算要求に対応する式の式データに含まれる構成情報に従って、引数に対応する変数のドメインを演算することにより、式のドメインを再計算し、再計算した式のドメインで、式テーブル２１２内の対応する式のドメインを更新する。
【００８３】
一方、選択した計算要求の種別が変数計算である場合（Ｓ３０２：Ｎｏ）、計算要求に含まれる式ＩＤに対応する式データを式テーブル２１２から取得し、当該式データの引数に対応する変数の変数データを変数テーブル２１１から取得してドメイン再計算処理を実行する（Ｓ３０４）。
【００８４】
ステップＳ３０４のドメイン再計算処理において、計算要求実行部２０７は、選択した計算要求に対応する式のドメインを満たすように、当該式に用いられている変数のドメインを変更し、変更したドメインで、変数テーブル２１１内の対応する変数のドメインを更新する。
【００８５】
なお、ステップＳ３０４において、計算要求に除外変数が含まれている場合には、計算要求実行部２０７は、除外変数以外の変数のドメインを、当該計算要求に含まれる式ＩＤの式のドメインを満たすように変更する。また、ステップＳ３０３またはＳ３０４において、計算要求実行部２０７は、計算要求に対応するドメイン再計算処理を実行するたびに、当該計算要求を計算要求リスト格納部２０６から削除する。
【００８６】
次に、変更要求再生成部２０３は、入力データ格納部２１０を参照して、計算要求実行部２０７によって実行されたドメイン再計算処理で用いられた引数のドメインに変化があったか否かを判定する（Ｓ３０５）。当該引数のドメインに変化がなかった場合（Ｓ３０５：Ｎｏ）、制約伝播装置２０は、本フローチャートに示した計算要求処理を終了する。
【００８７】
一方、当該引数のドメインに変化があった場合（Ｓ３０５：Ｙｅｓ）、変更要求再生成部２０３は、当該引数の実体（変数または式）のドメインの変化態様（例えばドメインの上限が変化した旨や下限が変化した旨）を記憶する。そして、失敗判定部２０９は、制約テーブル２１３を参照して、ドメインが変化した変数または式のドメインが、空となったか、または、いずれかの制約に対応付けられている失敗条件に該当するか否かを判定する（Ｓ３０６）。
【００８８】
ドメインが変化した変数または式のドメインが、空となった、または、いずれかの制約に対応付けられている失敗条件に該当する場合（Ｓ３０６：Ｙｅｓ）、失敗判定部２０９は、与えられた全ての制約を満たす変数または式の値が存在しない旨を示す失敗情報を入力データ格納部２１０に登録し（Ｓ３０７）、制約伝播装置２０は、本フローチャートに示した計算要求処理を終了する。
【００８９】
ドメインが変化した変数または式のドメインが、空でもなく、いずれの制約に対応付けられている失敗条件にも該当しない場合（Ｓ３０６：Ｎｏ）、変更要求再生成部２０３は、図１１において説明した変更要求再生成処理を実行する（Ｓ４００）。
【００９０】
次に、第二の計算要求登録部２０８は、ステップＳ３０３またはＳ３０４において実行されたドメイン再計算処理によって変数のドメインが変更されたか否かを判定する（Ｓ３０８）。ドメイン再計算処理によって式のドメインが変更された場合（Ｓ３０８：Ｎｏ）、制約伝播装置２０は、本フローチャートに示す計算要求処理を終了する。
【００９１】
ドメイン再計算処理によって変数のドメインが変更された場合（Ｓ３０８：Ｙｅｓ）、第二の計算要求登録部２０８は、ドメインが再計算された変数を含む式の中で、ドメイン再計算処理に用いられた式以外の式について、当該式の式ＩＤ、および、式計算を示す種別を有する式計算要求を計算要求リスト格納部２０６に登録する（Ｓ３０９）。
【００９２】
そして、第二の計算要求登録部２０８は、ステップＳ３０９において登録されたそれぞれの式計算要求について、当該式計算要求に含まれる式ＩＤ、および、変数計算を示す種別を含み、ステップＳ３０４のドメイン再計算処理でドメインが変更された変数を除外変数とする変数計算要求を計算要求リスト格納部２０６に登録し（Ｓ３１０）、制約伝播装置２０は、本フローチャートに示す計算要求処理を終了する。
【００９３】
本実施形態の制約伝播装置２０を用いれば、例えば変数ｘと式ｅとが図１３に示す関係にある場合に、変更要求に従って変数ｘ１のドメインを変更すると、変数ｘと式ｅとの間に次のような伝播が発生する。
（１）  まず、変数ｘ１についての変更要求処理（図１０参照）の中で、第一の計算要求登録部２０５は、ステップＳ２０７において変数ｘ１を含む全ての式、即ちｅ１の計算要求を生成すると共に、ステップＳ２０８において式ｅ１に含まれる変数ｘ１以外の全ての変数、即ち変数ｘ２の計算要求を生成して計算要求リスト格納部２０６に登録する。
（２）  次に、計算要求実行部２０７は、図１２のステップＳ３０３において、（１）で生成した計算要求を処理して式ｅ１のドメインを再計算し、その後、ステップＳ３０４において、（１）で生成した計算要求を処理して変数ｘ２のドメインを再計算する。
（３）  これにより式ｅ１と変数ｘ２のドメインが変化したとすると、第二の計算要求登録部２０８は、図１２の計算要求処理におけるステップＳ３０９において、変数ｘ２を内部変数とする式ｅ１以外の式、即ち式ｅ２の計算要求を生成すると共に、ステップＳ３１０において、式ｅ２に含まれる変数ｘ２以外の変数、即ち変数ｘ３の計算要求を生成してリストに登録する。
（４）  次に、計算要求実行部２０７は、図１２のステップＳ３０３において、（３）で生成した計算要求を処理して式ｅ２のドメインを再計算し、その後、ステップＳ３０４において、（３）で生成した計算要求を処理して変数ｘ３のドメインを再計算する。
（５）  これにより式ｅ２と変数ｘ３のドメインが変化したとすると、第二の計算要求登録部２０８は、図１２の計算要求処理におけるステップＳ３０９において、変数ｘ３を内部変数とする式ｅ２以外の式、即ち式ｅ３の計算要求を生成すると共に、ステップＳ３１０において、式ｅ３に含まれる変数ｘ３以外の変数、即ち変数ｘ４の計算要求を生成してリストに登録する。
（６）  次に、計算要求実行部２０７は、図１２のステップＳ３０３において、（５）で生成した計算要求を処理して式ｅ３のドメインを再計算し、その後、ステップＳ３０４において、（５）で生成した計算要求を処理して変数ｘ４のドメインを計算する。しかし、これにより両者のドメインが変化しても計算要求を生成すべき新たな変数または式が存在しないため、新たな計算要求が計算要求リスト格納部２０６に登録されず、計算要求リスト格納部２０６内の計算要求リスト２０６０は空となり伝播が終了する。
【００９４】
図１４は、制約伝播装置２０の機能を実現するコンピュータ７０のハードウェア構成の一例を示す。コンピュータ７０は、ＣＰＵ（Central Processing Unit）７１、ＲＡＭ（Random Access Memory）７２、ＲＯＭ（Read Only Memory）７３、ＨＤＤ（Hard Disk Drive）７４、通信インターフェイス（Ｉ／Ｆ）７５、入出力インターフェイス（Ｉ／Ｆ）７６、およびメディアインターフェイス（Ｉ／Ｆ）７７を備える。
【００９５】
ＣＰＵ７１は、ＲＯＭ７３またはＨＤＤ７４に格納されたプログラムに基づいて動作し、各部の制御を行う。ＲＯＭ７３は、コンピュータ７０の起動時にＣＰＵ７１が実行するブートプログラムや、コンピュータ７０のハードウェアに依存するプログラム等を格納する。
【００９６】
ＨＤＤ７４は、ＣＰＵ７１によって実行されるプログラム、ならびに、変更要求リスト格納部２０１、計算要求リスト格納部２０６、および入力データ格納部２１０内の各データを格納する。通信インターフェイス７５は、通信ネットワークを介して他の機器からデータを受信してＣＰＵ７１へ送ると共に、ＣＰＵ７１が生成したデータを、通信ネットワークを介して他の機器へ送信する。
【００９７】
ＣＰＵ７１は、入出力インターフェイス７６を介して、キーボードやマウス等の入力装置１１およびディスプレイ等の出力装置１２を制御する。ＣＰＵ７１は、入出力インターフェイス７６を介して、入力装置１１からデータを取得する。また、ＣＰＵ７１は、生成したデータを、入出力インターフェイス７６を介して出力装置１２へ出力する。
【００９８】
メディアインターフェイス７７は、記録媒体７８に格納されたプログラムまたはデータを読み取り、ＲＡＭ７２に提供する。ＲＡＭ７２を介してＣＰＵ７１に提供されるプログラムは、記録媒体７８に格納されている。当該プログラムは、記録媒体７８から読み出されて、ＲＡＭ７２を介してコンピュータ７０にインストールされ、ＣＰＵ７１によって実行される。
【００９９】
コンピュータ７０にインストールされて実行されるプログラムは、コンピュータ７０を、入力データ受付部２００、変更要求リスト格納部２０１、変更要求生成部２０２、変更要求再生成部２０３、変更要求実行部２０４、第一の計算要求登録部２０５、計算要求リスト格納部２０６、計算要求実行部２０７、第二の計算要求登録部２０８、失敗判定部２０９、および入力データ格納部２１０として機能させる。
【０１００】
記録媒体７８は、例えばＤＶＤ（Digital Versatile Disk）、ＰＤ（Phase change rewritable Disk）等の光学記録媒体、ＭＯ（Magneto-Optical disk）等の光磁気記録媒体、テープ媒体、磁気記録媒体、または半導体メモリ等である。コンピュータ７０は、これらのプログラムを、記録媒体７８から読み取って実行するが、他の例として、他の装置から、通信媒体を介して、これらのプログラムを取得してもよい。通信媒体とは、通信ネットワーク、または、当該通信ネットワークを伝搬するディジタル信号または搬送波を指す。
【０１０１】
なお、本実施形態において、制約伝播装置２０は、当該制約伝播装置２０専用の１台のコンピュータ７０によって実現されるが、他の形態として、制約伝播装置２０の機能は、ソフトウェアライブラリとして提供され、他のアプリケーションプログラムが動作するコンピュータ７０内にインストールされて、当該アプリケーションプログラムから呼び出されることによって、制約伝播装置２０の機能を実現するようにしてもよい。
【０１０２】
以上、本発明の実施の形態について説明した。
【０１０３】
上記説明から明らかなように、本実施形態の制約伝播装置２０によれば、制約伝播法において、任意の算術式を用いて表現された制約を効率良く処理することができる。
【０１０４】
上記において、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【０１０５】
【図１】本発明の一実施形態に係る制約伝播処理システム１０の構成を示すシステム構成図である。
【図２】変数データ３０のデータ構造の一例を示す図である。
【図３】式データ４０のデータ構造の一例を示す図である。
【図４】制約データ５０のデータ構造の一例を示す図である。
【図５】ドメイン変更ルール６０のデータ構造の一例を示す図である。
【図６】失敗条件の一例を説明するための概念図である。
【図７】変更要求リスト格納部２０１に格納される変更要求リスト２０１０のデータ構造の一例を示す図である。
【図８】計算要求リスト格納部２０６に格納される計算要求リスト２０６０のデータ構造の一例を示す図である。
【図９】制約伝播装置２０の動作の一例を示すフローチャートである。
【図１０】変更要求処理（Ｓ２００）の一例を示すフローチャートである。
【図１１】変更要求再生成処理（Ｓ４００）の一例を示すフローチャートである。
【図１２】計算要求処理（Ｓ３００）の一例を示すフローチャートである。
【図１３】式と内部変数の関係を例示する概念図である。
【図１４】制約伝播装置２０の機能を実現するコンピュータ７０のハードウェア構成の一例を示す図である。
【符号の説明】
【０１０６】
１０・・・制約伝播処理システム、１１・・・入力装置、１２・・・出力装置、２０・・・制約伝播装置、２００・・・入力データ受付部、２０１・・・変更要求リスト格納部、２０２・・・変更要求生成部、２０３・・・変更要求再生成部、２０４・・・変更要求実行部、２０５・・・第一の計算要求登録部、２０６・・・計算要求リスト格納部、２０７・・・計算要求実行部、２０８・・・第二の計算要求登録部、２０９・・・失敗判定部、２１０・・・入力データ格納部、２１１・・・変数テーブル、２１２・・・式テーブル、２１３・・・制約テーブル、２１４・・・ドメイン変更ルールテーブル、２１５・・・失敗情報、３０・・・変数データ、３１・・・変数ＩＤ、３２・・・変数名、３３・・・ドメイン、４０・・・式データ、４１・・・式ＩＤ、４２・・・式名、４３・・・構成情報、４４・・・引数ＩＤ、４５・・・ドメイン、５０・・・制約データ、５１・・・制約ＩＤ、５２・・・制約内容、５３・・・引数ＩＤ、５４・・・ルールＩＤ、５５・・・失敗条件、６０・・・ドメイン変更ルール、６１・・・ルールＩＤ、６２・・・条件、６３・・・ドメイン変更処理、６４・・・制約ＩＤ、７０・・・コンピュータ、７１・・・ＣＰＵ、７２・・・ＲＡＭ、７３・・・ＲＯＭ、７４・・・ＨＤＤ、７５・・・通信インターフェイス、７６・・・入出力インターフェイス、７７・・・メディアインターフェイス、７８・・・記録媒体
【図１】
2008226096.tif 000003
【図２】
2008226096.tif 000004
【図３】
2008226096.tif 000005
【図４】
2008226096.tif 000006
【図５】
2008226096.tif 000007
【図６】
2008226096.tif 000008
【図７】
2008226096.tif 000009
【図８】
2008226096.tif 000010
【図９】
2008226096.tif 000011
【図１０】
2008226096.tif 000012
【図１１】
2008226096.tif 000013
【図１２】
2008226096.tif 000014
【図１３】
2008226096.tif 000015
【図１４】
2008226096.tif 000016