JPH10275084A - 制約充足問題の解決装置及び解決方法、システム構築装置及び構築方法 - Google Patents

Abstract

(57)【要約】 【課題】 大規模な制約充足問題を高速に処理する。 【解決手段】 代替案集合生成部１が、与えられた問題
を、各部分が最大２個の代替案を含む部分集合に分解す
る。解計算部２が、分解された部分集合ごとに、部分の
代替案間の制約を満足する代替案の組み合わせを解とし
て計算する。各部分が最大２個の代替案を持つ部分集合
に関する解の計算は、部分が多数でもきわめて短時間で
行うことができる。このため、分解された各部分集合ご
との計算所要時間をすべて合計しても、もとの問題のま
ま解を計算する所要時間よりも大幅に短縮される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、いわゆる制約充足
問題の解を計算する技術の改良に関するもので、大規模
な問題についても、高速に解を計算するようにしたもの
である。

【０００２】

【従来の技術】複数の部分から構成される問題として、
制約充足問題が知られている。制約充足問題は、複数の
部分がそれぞれいくつかの選択肢（代替案と呼ぶ）をと
ることができ、異なった部分の代替案間に、許される組
み合わせや許されない組み合わせのような制約が存在す
る問題である。制約充足問題の解は、全ての制約を満足
するように、全ての部分に代替案をあてはめたものであ
る。

【０００３】ここで、制約充足問題の例を示す。例え
ば、４つの部分Ａ，Ｂ，Ｃ，Ｄからなる機械Ｘについ
て、個々の部分ごとに、実現する方式（実現方式）が３
個ずつ存在するとする。すなわち、部分Ａに対して実現
方式ａ１，ａ２及びａ３（以下「｛ａ１，ａ２，ａ
３｝」のように表す）、部分Ｂに対して｛ｂ１，ｂ２，
ｂ３｝、部分Ｃに対して｛ｃ１，ｃ２，ｃ３｝、部分Ｄ
に対して｛ｄ１，ｄ２，ｄ３｝が存在するとする。な
お、部分毎に存在する個々の選択肢（例えば実現方式ａ
１）を代替案と呼ぶ。

【０００４】また、部分ＡとＢ、ＡとＣ、ＡとＤ、また
ＢとＣ、ＢとＤ、ＣとＤのそれぞれの間に存在する制約
として、実現方式の番号が同じであってはならないとす
る。例えば、Ａの実現方式がａｊ（ｊ＝１，２，３）で
あれば、部分Ｂ，Ｃ，Ｄの実現方式はそれぞれｂｋ，ｃ
ｋ，ｄｋ（ｋ≠ｊ）でなければならない。同様に、Ｂの
実現方式がｂｊ（ｊ＝１，２，３）ならば、部分Ｃ，Ｄ
の実現方式はそれぞれｃｋ，ｄｋ（ｋ≠ｊ）でなければ
ならず、Ｃの実現方式がｃｊ（ｊ＝１，２，３）なら、
部分Ｄの実現方式はｄｋ（ｋ≠ｊ）でなければならな
い。

【０００５】上記のような場合に、組み合わせに関する
全ての条件（組み合わせ条件）が満たされるように、各
部分Ａ，Ｂ，Ｃ，Ｄの実現方式を決定して機械Ｘを設計
することを考える。この問題の例では、全ての組み合わ
せ条件を満足する実現方式の組み合わせ、すなわち解は
存在しないので、機械Ｘを設計することはできないとい
う解となる。しかし、この判断を下すまでには、 ｛ａ１，ｂ１，ｃ１，ｄ１｝ ｛ａ１，ｂ１，ｃ１，ｄ２｝ ｛ａ１，ｂ１，ｃ１，ｄ３｝ ｛ａ１，ｂ１，ｃ２，ｄ１｝ ｛ａ１，ｂ１，ｃ２，ｄ２｝ というように、各部分の実現方式の組み合わせの全てに
ついて、組み合わせ条件を満たすかどうか確認する必要
がある。そして、この例のように部分の数がわずか４個
程度の場合でも、設計者がこれを即座に判断するのは困
難である。問題を構成する部分の数が多くなると、この
決定はさらに困難になる。例えば、各々が４個ずつの実
現方式を選択しうる部分が３０個も存在する場合は、確
認しなければならない代替案の組み合わせは、順列組み
合わせにしたがって膨大な数となる。このため、前記の
ような決定を組織的に行うことは事実上不可能である。
したがって、制約充足問題の解を得るための決定は、従
来では、経験則に基づいた多くの試行錯誤を経て行われ
ていた。

【０００６】制約充足問題が発生する分野は、上記のよ
うに部分ごとにどのような要素を用いて機械を作るか決
めるような場合には限られない。例えば、ソフトウェア
の個々の部分にどのようなパラメータを設定するか、あ
る領域に複数の物をどのように配置するか、など多くの
場合にこのような制約充足問題に遭遇する。このため、
制約充足問題は、エキスパートシステムなどの実現にお
いて非常に重要な位置を占めるものである。

【０００７】制約充足問題は、一般的には次のように定
式化できる。すなわち、制約充足問題とは、複数の部分
から成り、各部分の実現又は各部分の機能の実行に関係
する手段として有限個の代替案を持ち、それらの部分の
対から成る集合に属する個々の対を構成する２つの部分
間の代替案の組み合わせに制約が存在するシステム（問
題）において、個々の部分にそれらの制約を満足するよ
うに代替案を設定する問題である。

【０００８】

【発明が解決しようとする課題】しかし、制約充足問題
は、特殊な場合を除くとＮＰ完全な問題である。ここ
で、ＮＰ完全な問題は、ｘのｙ乗を「ｘ＾ｙ」と表すこ
ととすると、問題の解を計算するのに必要な計算量を、
次のように表すことができるものである。すなわち、部
分の数をＮ、各部分に許された代替案の個数の最大をｄ
個とすると、各部分に互いに矛盾の無い代替案を設定す
るには、最悪の場合、ｄ＾Ｎオーダーの計算が必要であ
る。例えば、部分の数Ｎ＝１００、代替案の最大個数ｄ
＝２とすると２＾１００オーダーの計算が必要になり、
実用的な時間内では到底計算することができない。

【０００９】制約充足問題の解法としては、Ａｄａｐｔ
ｉｖｅ ＣｏｎｓｉｓｔｅｎｃｙＡｌｇｏｒｉｔｈｍな
ど、制約関係が影響を及ぼす範囲を居所化して計算量を
削減する手法も存在するが（参考文献：Ｒｉｎａ Ｄｅ
ｃｈｔｅｒ，ＪｕｄｅａＰｅａｒｌ：“Ｎｅｔｗｏｒｋ
−Ｂａｓｅｄ Ｈｅｕｒｉｓｔｉｃｓ ｆｏｒＣｏｎｓ
ｔｒａｉｎｔ−Ｓａｔｉｓｆａｃｔｉｏｎ Ｐｒｏｂｌ
ｅｍｓ，”Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅ
ｎｃｅ ３４（１９８８））、この手法では、計算の実
行中に、本来存在しない制約関係が追加されるので、多
くの場合にはほぼｄ＾Ｎオーダーの計算が必要になる。

【００１０】また、多項式オーダー計算量の手法とし
て、部分間の制約関係を表わす制約グラフが木構造やあ
るいは木構造の拡張であるｋ−木構造を持つ場合に有効
なものが開発されているが（参考文献：Ｅｕｇｅｎｅ
Ｆｒｅｕｄｅｒ：“Ｃｏｍｐｌｅｘｉｔｙ ｏｆ Ｋ−
Ｔｒｅｅ Ｓｔｒｕｃｔｕｒｅｄ Ｃｏｎｓｔｒａｉｎ
ｔ Ｓａｔｉｓｆａｃｔｉｏｎ Ｐｒｏｂｌｅｍ
ｓ，”）、この手法が前提とする仮定が実際の応用で満
たされるのは希であった。

【００１１】したがって、制約充足問題がエキスパート
システムなどの実現において非常に重要な位置を占める
にもかかわらず、従来では、部分間の制約関係を表わす
グラフが木構造を持つなど特殊な場合を除けば、非常に
小規模な問題しか扱うことはできなかった。

【００１２】本発明は、上記のような従来技術の問題点
を解決するために提案されたもので、その第１の目的
は、大規模な制約充足問題を高速に解決することのでき
る装置並びに方法を提供することにある。また、本発明
の他の目的は、複数の代替案を有する複数の部分から構
成され、且つ各部分の代替案間に制約が存在する機械や
コンピュータプログラムなどのシステムを、その制約を
満足するように、従来技術に比較して容易に構築するこ
とができる装置及び方法を提供することにある。

【００１３】

【課題を解決するための手段】上記の目的を達成するた
め、請求項１の発明は、それぞれ複数の代替案を持つ部
分を複数有し、部分の代替案間に組み合わせに制約が存
在する問題の解を計算する制約充足問題の解決装置にお
いて、与えられた問題を、各部分が最大２個の代替案を
含む部分集合に分解する手段と、分解された部分集合ご
とに、部分の代替案間の制約を満足する代替案の組み合
わせを分析する手段と、を有することを特徴とする。請
求項４の発明は、請求項１の発明を方法の観点から把握
したものであって、それぞれ複数の代替案を持つ部分を
複数有し、部分の代替案間に組み合わせに制約が存在す
る問題の解を計算する制約充足問題の解決方法におい
て、与えられた問題を、各部分が最大２個の代替案を含
む部分集合に分解するステップと、分解された部分集合
ごとに、部分の代替案間の制約を満足する代替案の組み
合わせを分析するステップと、を含むことを特徴とす
る。請求項１，４の発明では、与えられた問題が、各部
分が最大２個の代替案を含む部分集合に分解される。各
部分が最大２個の代替案を持つ部分集合に関する解の計
算は、部分が多数でもきわめて短時間で行うことができ
る。このため、分解された各部分集合ごとの計算所要時
間をすべて合計しても、もとの問題のまま解を計算する
所要時間よりも大幅に短縮される。このため、大規模な
制約充足問題も高速に解決することができる。

【００１４】請求項２の発明は、請求項１記載の制約充
足問題の解決装置において、前記解を計算する手段は、
部分集合から、前記制約に合致する代替案の組み合わせ
を表す可到達値集合を計算する手段と、計算された可到
達値集合を完全化する手段と、完全化された可到達値集
合から解を計算する手段と、を有することを特徴とす
る。請求項２の発明では、問題を構成する部分が多数で
あっても、可到達値集合を完全化する手順によって、部
分集合からきわめて短時間に解を計算することができる
ので、問題全体の解を計算する所要時間が大幅に短縮さ
れる。

【００１５】請求項３の発明は、請求項１又は２記載の
制約充足問題の解決装置において、前記分解する手段又
は前記計算する手段のうち少なくとも一方を複数設けた
ことを特徴とする。請求項３の発明では、問題を部分集
合へ分解したり部分集合からの解の計算が並列処理でき
るので、特に大規模な問題の場合も、処理が高速に行わ
れる。

【００１６】請求項５の発明は、複数の部分から構成さ
れ、それぞれの部分が複数の代替案を有し、かつ前記各
部分の代替案の間の組み合わせに制約が存在するシステ
ムを構築する装置において、前記システムの各部分を、
各部分が最大２個の代替案を含む部分集合に分解する手
段と、分解された部分集合ごとに、部分の代替案間の制
約を満足する代替案の組み合わせを計算することによ
り、前記制約を満足するシステムを構築することを特徴
とする。また、請求項６の発明は、複数の部分から構成
され、それぞれの部分が複数の代替案を有し、かつ前記
各部分の代替案の間の組み合わせに制約が存在するシス
テムを構築する方法において、前記システムの各部分
を、各部分が最大２個の代替案を含む部分集合に分解
し、分解された部分集合ごとに、部分の代替案間の制約
を満足する代替案の組み合わせを計算することにより、
前記制約を満足するシステムを構築することを特徴とす
る。

【００１７】このような構成を有する請求項５または請
求項６の発明によれば、多数の部分から構成され、各部
分の代替案間に制約が存在する複雑なシステムを従来技
術に比較して簡単な手法で構成することが可能になる。

【００１８】

【発明の実施の形態】以下、本発明の実施の形態（以下
「実施形態」という）である制約充足問題の解決装置
（以下「本装置」という）について、図面を参照して説
明する。

【００１９】（１）構成 まず、図１は、本装置の要部について、概略的な構成を
示す機能ブロック図である。なお、図１に示すように、
本装置は、コンピュータ上においてプログラム１００に
よってＣＰＵ１０１を制御することによって実現され、
この場合の具体的な実現態様は種々考えられる。このた
め、以下の説明では、本装置の各機能に対応する仮想的
回路ブロックとして「〜部」をもって本装置を説明す
る。なお、ＣＰＵ１０１は、プログラム１００で指定さ
れたとおりに、コンピュータの各種ハードウェア資源を
利用しながら、前記各仮想的回路ブロックの作用を実現
する。

【００２０】ハードウェア資源の典型例として、ＣＰＵ
１０１には、バス及び入出力制御回路１０２を介して、
ＲＡＭなどの記憶素子からなるメモリ１０３、ハードデ
ィスクドライブなどの補助記憶装置１０４、入力装置と
してマウス１０５やキーボード１０６、出力装置として
表示装置１０７やプリンタ１０８を接続することが考え
られる。但し、これらハードウェア資源は例示に過ぎ
ず、情報の記憶・入力・出力などの目的を達成できる他
の各種装置を用いることもできる。

【００２１】このようなハードウェア資源を用いて実現
される本装置は、次のように構成される。すなわち、本
装置は、図１に示すように、経路３から入力される問題
を部分集合に分解する代替案集合生成部１と、分解され
た部分集合から問題の解を計算する解計算部２とを有す
る。代替案集合生成部１は、与えられた問題を、各部分
が最大２個の代替案を持つ部分集合に分解する手段であ
る。これら代替案集合生成部１と解計算部２は、経路
４，５及び７によって接続される。このうち経路５は、
部分集合を解計算部１に送るためのもので、経路４は、
部分集合に対応する組み合わせの制約を解計算部１に送
るためのものである。また、経路７は、一つの部分集合
の処理を終えた解計算部１が、次の部分集合の送信を代
替案集合生成部１に要求するためのものである。解計算
部２は、部分集合から求めた解を、経路６を通じて出力
する。

【００２２】次に、図２は、本装置の構成を、より具体
的に示す機能ブロック図である。なお、図２では、図１
の経路４，５及び７をまとめて経路１１として示す。ま
た、経路３及び６は、図１の経路３及び６に対応する。
本装置は、図２に示すように、代替案集合生成部１及び
解計算部２の他に、解計算パターン記憶部８、結果記憶
部９及び解出力部１０を有する。このうち、解計算パタ
ーン記憶部８は、解を１つだけ求めるのか、全ての解を
求めるのかといったユーザによる指定を記憶する部分で
ある。結果記憶部９は、解計算部２が計算した結果を記
憶する部分である。解出力部１０は、解計算パターン記
憶部８に記憶された指定に応じて、解計算部２に解を要
求し、返送された解をユーザに出力する部分である。解
計算部２は、解を要求されたときに、結果記憶部９に記
憶された情報に基づく解を解出力部１０に返送する。

【００２３】また、図３は、解計算部２の具体的な構成
を示す機能ブロック図である。すなわち、解計算部２
は、図３に示すように、経路１１から与えられた部分集
合から、前記制約に合致する代替案の組み合わせを表す
可到達値集合を計算する可到達値集合計算部１６と、計
算された可到達値集合を完全化する値完全化部１７と、
を有する。完全化された可到達値集合から解を計算する
解発生部１８と、を有する。

【００２４】（２）作用 上記のような構成を有する本実施の形態では、次のよう
な手順によって問題の解が計算される。なお、以下の説
明では、次のように定義される用語を用いる。すなわ
ち、全ての制約を満足する各部分の代替案の組み合わせ
を、システムあるいは問題の解と呼ぶ。また、部分Ｘk
の代替案が部分Ｘj の代替案に制約される時、部分Ｘk
と部分Ｘj は互いに隣接するという。また、部分Ｘk に
隣接する全ての部分の集合を部分Ｘk の隣接集合と呼
び、Ｎ（Ｘk ）と表わす。また、部分Ｘk と部分Ｘj が
隣接して、部分Ｘk の代替案ｗk と部分Ｘj の代替案ｗ
j が組み合わせ制約を満たす時、代替案ｗk と代替案ｗ
j は可接続であると呼ぶ。また、互いに隣接する部分の
任意の列｛Ｘj ，…，Ｘk ｝上に互いに可接続な代替案
列｛ｗj ，…，ｗk ｝が存在する時、部分Ｘk の代替案
ｗk は部分Ｘj の代替案ｗj から可到達であるという。
ここで、｛Ｘj ，…，Ｘk ｝は同一の部分Ｘh を複数個
含んでもよく、また、そのとき、部分Ｘj と部分Ｘk 以
外の部分Ｘh 上の代替案は出現するごとに異なっていて
もよい。さらに、代替案ｗk の部分Ｘj 上の可到達値集
合ｒ（Ｘj ：ｗk ）を、代替案ｗk から可到達な値だけ
から成る部分Ｘj の代替案の集合と定義する。

【００２５】（２−１）問題の入力 問題の解を得ようとするユーザは、代替案集合生成部１
へ、経路３を通して問題と制約とを与えるとともに、処
理の開始を要求する。なお、使用者は、処理の開始を要
求する際に、解を計算するパターンとして、与えられた
解ｍ個の解だけを計算するのか、全ての解を計算するか
の区別を入力する。代替案集合生成部１は、入力された
区別を、経路１４を通じて、解計算パターン記憶部８に
記憶する。

【００２６】与えられる問題は、問題を構成する部分の
集合と、個々の部分ごとに許された代替案の集合によっ
て表される。また、問題に対する制約は、問題に含まれ
る各部分の代替案間の組み合わせの制約であり、制約関
係がある部分の対の集合、及び個々の対を構成する２つ
の部分に対して許された、又は禁止された代替案の組み
合わせによって表される。

【００２７】すなわち、問題は、部分の集合 Ｘ＝｛Ｘ1 ，Ｘ2 ，… ＸN ｝ 各部分ごとに許された代替案集合列 Ｖ＝｛Ｖ1 ，Ｖ2 ，… ＶN ｝ 制約関係がある部分の対の集合 Ｚ＝｛（Ｘi ，Ｘj ），（Ｘk ，Ｘm ），…｝ のように与えられる。

【００２８】また、制約は、個々の対（Ｘi ，Ｘj ）に
対して許された代替案の組み合わせの集合 Ｃij＝｛（ｗip，ｗjq），（ｗkr，ｗjs），…｝ からなり、代替案集合生成部１はこれら問題と制約を合
わせて Ｘ1 ，Ｘ2 ，… ＸN Ｖ1 ，Ｖ2 ，… ＶN （Ｘi ，Ｘj ）＝（ｗip，ｗjq），（ｗkr，ｗjs），… （Ｘk ，Ｘm ）＝（ｗkt，ｗmu），（ｗkv，ｗmy），… ・・・ ・・・ の形で受け取る。

【００２９】（２−２）部分集合への分解 代替案集合生成部１は、与えられた問題を、各部分が最
大２個の代替案を含む部分集合に分割する。この分割で
は、部分ごとの代替案を最大２個ずつのグループにまと
め、異なった部分のグループを順列組み合わせにしたが
って組み合わせることによって部分集合を作成する。

【００３０】例えば、部分Ａが代替案ａ１，ａ２，ａ
３，ａ４を持ち、部分Ｂが代替案ｂ１，ｂ２，ｂ３，ｂ
４を持つとき、部分Ａの各代替案はグループ｛ａ１，ａ
２｝及び｛ａ３，ａ４｝にまとめられ、部分Ｂの代替案
はグループ｛ｂ１，ｂ２｝及び｛ｂ３，ｂ４｝にまとめ
られる。そして、部分Ａのグループと部分Ｂのグループ
を組み合わせて、 ｛ａ１，ａ２｝と｛ｂ１，ｂ２｝ ｛ａ１，ａ２｝と｛ｂ３，ｂ４｝ ｛ａ３，ａ４｝と｛ｂ１，ｂ２｝ ｛ａ３，ａ４｝と｛ｂ３，ｂ４｝ という４通りの部分集合が作成される。すなわち、各部
分Ｘj に許された代替案の集合Ｖj を取り出し、各々が
２個以下の代替案から成る部分集合の列｛Ｖj （１），
Ｖj （２），…，Ｖj （ｊm ）｝に分割する。

【００３１】なお、具体的な分割の手法は、本装置を適
用しようとする問題の性質に合わせて決定すればよい。
例えば、ユーザが具体的な問題の内容を理解したうえ
で、所望の分割ルールを入力することによって、解決し
ようとする問題ごとに異なった所望のルールを適用する
ことができる。

【００３２】（２−３）部分集合の解計算部２への送付 代替案集合生成部１は、生成された部分集合ごとに、制
約と共に、 Ｘ1 ，Ｘ2 ，ＸN Ｖ1 （１），Ｖ2 （２），ＶN （１） （Ｘi ，Ｘj ）＝（ｗip，ｗjq），（ｗkr，ｗjs），… （Ｘk ，Ｘm ）＝（ｗkt，ｗmu），（ｗkv，ｗmy），… ・・・ ・・・ の形で、経路１１を通して解計算部２に送る。ただし、
ここでは、制約の存在する部分の対（Ｘi ，Ｘj ）に許
された代替案の組としては、与えられた組（ｗip，ｗj
q）の中で、部分集合中の代替案Ｖi に一方の代替案ｗi
pが含まれ、部分集合中の代替案Ｖj に他方の代替案ｗj
qが含まれるものだけを選択して送る。

【００３３】なお、代替案集合生成部１から解計算部２
への部分集合の送信は、指定された解の計算パターンに
応じて、次のように行われる。解計算部２は、一つの部
分集合に基づく計算が終了すると、処理終了の通知及び
解が存在したか否かを、経路１１を通じて代替案集合生
成部１に送る。代替案集合生成部１は、解計算部２から
解の存在を通知されかつ解計算パターン記憶部８に、１
個の解だけを求める指示が記憶されている場合以外は、
つまり、与えられた数の解がまだ得られていないかある
いは全ての解を求める指示があるときは、次のデータを
解計算部２に送る。

【００３４】代替案集合生成部１から解計算部２に一度
に送られるデータは、 Ｘ1 ，Ｘ2 ，…，ＸN Ｖ1 （１），…，ＶN-1 （１），ＶN （２） （Ｘi ，Ｘj ）＝（ｗip，ｗjq），（ｗkr，ｗjs），… （Ｘk ，Ｘm ）＝（ｗkt，ｗmu），（ｗkv，ｗmy），… のような内容である。代替案集合生成部１は、部分集合
を逐次生成する場合、以下同様にして、辞書順に代替案
集合を解計算部２に送る。このように順次送られるデー
タは、次のようになる。 ｛Ｖ1 （１），…，ＶN （１）｝ ｛Ｖ1 （１），…，ＶN-1 （１），ＶN （２）｝ ｛Ｖ1 （１），…，ＶN-1 （１），ＶN （３）｝ ・・・ ｛Ｖ1 （１），…，ＶN-1 （１），ＶN （ＮT ）｝ ｛Ｖ1 （１），…，ＶN-1 （２），ＶN （１）｝ ｛Ｖ1 （１），…，ＶN-1 （２），ＶN （２）｝ ・・・ ｛Ｖ1 （１），…，ＶN-1 （２），ＶN （ＮT ）｝ ｛Ｖ1 （１），…，ＶN-1 （３），ＶN （１）｝ ｛Ｖ1 （１），…，ＶN-1 （３），ＶN （２）｝ ・・・ ｛Ｖ1 （１），…，ＶN-1 （３），ＶN （ＮT ）｝ ｛Ｖ1 （１），…，ＶN-1 （２T ），ＶN （ＮT ）｝ この場合、代替案集合生成部１は、解が求まった通知を
受け取るかあるいは最後の ｛Ｖ１（１），…，ＶN-1 （２T ），ＶN （ＮT ）｝ に対応するシステム構成データを送り終わるまで、経路
１１を通して Ｘ1 ，Ｘ2 ，…，ＸN Ｖ1 （ｊ1 ），Ｖ2 （ｊ2 ），…，ＶN （ｊN ） （Ｘi ，Ｘj ）＝（ｗip，ｗjq），（ｗkr，ｗjs），… （Ｘk ，Ｘm ）＝（ｗkt，ｗmu），（ｗkv，ｗmy），… のように、解計算部２にデータを送る。

【００３５】全ての解が必要な場合は、代替案集合生成
部１から解計算部２に全ての部分集合を送る必要がある
が、この場合は、全ての部分集合を一括して解計算部２
に送る構成も考えられるし、計算終了ごとに逐次部分集
合を生成して送ることも考えられる。部分集合を一括送
付する場合は、次の部分集合を要求するための経路７は
用いられない。

【００３６】部分集合を逐次生成して送付するときは、
代替案集合生成部１は、一つの部分集合を生成するごと
に、その部分集合を解計算部２に送る。解計算部２は、
経路５を通して受け取った部分集合について解を計算
し、処理が終了した段階で、あるいは終了を予測した段
階で、経路７を通して代替案集合生成部１に新たな代替
案集合の送信を要求し、代替案集合生成部１はこれに応
えて新たな代替案集合と場合によっては許可あるいは禁
止された代替案の組み合わせ情報を、それぞれ経路５、
経路４を通して解計算部２に送る。なお、部分集合につ
いての処理の終了は、解が存在しないことが判明した場
合を含む。

【００３７】（２−４）解の計算 解計算部２は、｛Ｖ1 （ｋ1 ），Ｖ2 （ｋ2 ），…，Ｖ
N （ｋN ）｝を経路５を通して受け取ると、各部分Ｘj
に許された代替案がＶj （ｋj ）であるとして、つまり
各部分が高々２個の代替案を持つとして、全ての部分上
の矛盾の無い代替案の組み合わせを計算する。なお、問
題全体は部分｛Ｘ1 ，…，ＸN ｝から成り、代替案集合
生成部１から解計算部２へは、各部分Ｘj に許される代
替案の集合として２個以下の代替案からなる集合｛ｗj
1，ｗj2｝が与えられるとする。なお、入力情報として
与えられた個々の部分に許された代替案の集合によって
解が構成できる場合は、その解は｛Ｖ1 （ｋ1 ），Ｖ2
（ｋ2 ），…，ＶN （ｋN ）｝（１≦ｋj ≦ｊm ｝のい
ずれかを代替案の集合とした場合の解であるので、これ
ら部分集合から解を求めることによって、結果的に、問
題全体から求められるのと同一の解を全て求めることが
できる。解計算部における解の計算は、次に示すよう
に、可到達値集合の計算、可到達値集合の完全化、完全
化された可到達集合からの解の計算、という処理によっ
て行われる。

【００３８】（２−４−１）可到達値集合の計算（ステ
ップ４１〜４９） まず、可到達値集合を計算する手順を示すフローチャー
トを、図４（前半）及び図５（後半）に示す。なお、図
４及び図５のフローチャートは、接続子１〜４によって
一体になっているものである。

【００３９】まず、可到達値集合計算部１６が、部分Ｘ
j の各代替案ｗjp（ｐ＝１，２）に対して各部分Ｘj 上
の可到達値集合ｒ（Ｘj ：ｗk ）を計算する（ステップ
４１〜４９）。この計算では、まず、ステップ４１で、
部分Ｘj の各代替案ｗjp＝（ｐ＝１，２）に対して、部
分Ｘj 上の代替案ｗjpの可到達集合ｒ（Ｘj ：ｗjp）を
代替案ｗjpだけから成る集合とし、部分Ｘj 以外の部分
Ｘk （ｋ≠ｊ）上では可到達値集合ｒ（Ｘk ：ｗjp）を
空集合にする。ここで、ステップ４１において、既にそ
の上の可到達集合ｒ（Ｘh ：ｗjp）を計算済みの部分の
集合を既算集合Ｆと表し、その上の可到達集合ｒ（Ｘh
：ｗjp）を計算すべき部分の集合を未算集合Ｇと表
し、後述するステップ群で可到達値集合ｒ（Ｘh ：ｗj
p）から代替案が削減されたことを記憶する集合を削除
集合Ｈと表す。

【００４０】ステップ４２〜４５では、未算集合Ｇに属
する各部分Ｘh 上の可到達値集合ｒ（Ｘh ：ｗjp）を計
算する。なお、この手順で用いられる未算集合Ｇ＊は未
算集合Ｇの複製である。まず、ステップ４２では、既算
集合Ｆに属して部分Ｘh に隣接する全ての部分Ｘks上の
可到達値集合ｒ（Ｘks：ｗjp）が部分Ｘh の代替案ｗh
と可接続な代替案を含む時、可到達値集合ｒ（Ｘh ：ｗ
jp）に代替案ｗh を追加する。さらに、ステップ４３で
は、可到達値集合ｒ（Ｘh ：ｗj1）と可到達値集合ｒ
（Ｘh ：ｗj2）の両方が空集合になる場合には解が存在
しないので、処理を終了する。

【００４１】可到達値集合ｒ（Ｘh ：ｗj1）と可到達値
集合ｒ（Ｘh ：ｗj2）のいずれかが空集合でない場合
は、ステップ４４において可到達値集合ｒ（Ｘh ：ｗj
p）のどの代替案とも可接続ではない代替案を可到達値
集合ｒ（Ｘks：ｗjp）から削減する。つまり、可到達値
集合ｒ（Ｘks：ｗjp）の代替案ｗs が可到達値集合ｒ
（Ｘh ：ｗjp）のどの代替案とも可接続でない場合は、
代替案ｗs は代替案ｗjpから可到達ではないので、可到
達値集合ｒ（Ｘks：ｗjp）から代替案ｗs を削減すると
共に、代替案ｗs を削減した影響でさらに削減すべき代
替案を計算するために削除集合Ｈに｛Ｘks：ｗs ，ｗj
p｝を追加する。

【００４２】また、ステップ４５では、ステップ１０と
同じように、可到達値集合ｒ（Ｘks：ｗj1）と可到達値
集合ｒ（Ｘks：ｗj2）の両方が空集合になる場合には解
が存在しないので、処理を終了する。

【００４３】ステップ４２〜４５を繰り返すことによっ
て未算集合Ｇに属する全ての部分Ｘh 上の可到達値集合
ｒ（Ｘh ：ｗjp）が計算されると、ステップ４６、４７
で（図５）、削除集合Ｈに属する代替案を可到達集合か
ら削減したことによってさらに削減すべき可到達集合の
代替案を計算する。ステップ４６では、削除集合Ｈから
削減された可到達集合の代替案｛Ｘr ：ｗr ，ｗjp｝を
取り出し、既算集合ＦとＮ（Ｘr ）の両方に含まれる部
分Ｘh 上の可到達値集合ｒ（Ｘh ：ｗjp）が可到達値集
合ｒ（Ｘr ：ｗjp）に属する代替案ｗr ではない代替案
ｗrvと可接続な代替案を含まなければ、部分Ｘj の代替
案が代替案ｗjpである解は存在しないので既算集合Ｆに
属する全ての部分Ｘi に対して、可到達値集合ｒ（Ｘi
：ｗjp）を空集合にする。また、削除集合Ｈから、最
後の項が代替案ｗjpと一致する全ての｛Ｘi ：ｗi ，ｗ
jp｝を削減する。

【００４４】既算集合ＦとＮ（Ｘr ）の両方に含まれる
全ての部分Ｘh 上の可到達値集合ｒ（Ｘh ：ｗjp）が代
替案ｗrvと可接続な代替案を含む場合は、ステップ４７
で代替案ｗrvと可接続でない代替案ｗh を可到達値集合
ｒ（Ｘh ：ｗjp）から削減して、削除集合Ｈに｛Ｘh ：
ｗh ，ｗjp｝を追加する。さらに、ステップ４８では、
可到達値集合ｒ（Ｘh ：ｗj1）と可到達値集合ｒ（Ｘh
：ｗj2）の両方が空集合になる場合には解が存在しな
いので処理を終了する。

【００４５】削除集合Ｈが空集合になると、ステップ４
９で次に可到達値集合を計算すべき部分の集合未算集合
Ｇを、未算集合Ｇに属する部分の隣接集合に属して既算
集合Ｆには属さない部分の集合とする。

【００４６】最終的に、各部分Ｘk がすべての部分Ｘk
上で可到達値集合ｒ（Ｘk ：ｗj ）が空にならない代替
案ｗj を含む場合には、解が存在するので、可到達値集
合計算部１６は、可到達値集合ｒ（Ｘk ：ｗj ）を経路
１２を通じて結果記憶部９に書き込む。

【００４７】（２−４−２）可到達値集合の完全化 値集合完全化部１７は、可到達値集合計算部１６で求め
た可到達値集合を完全化する。図６は、値集合を完全化
する手順を示すフローチャートである。すなわち、この
手順では、ループの制御変数としてｊとｋを用いなが
ら、ステップ６１で、各部分Ｘk と部分Ｘj に対して、
部分Ｘk の代替案ｗkpの部分Ｘj 上の可到達値集合ｒ
（Ｘj ：ｗkp）が代替案ｗjqを含むが可到達値集合ｒ
（Ｘj ：ｗjq）が空集合である場合は、可到達値集合ｒ
（Ｘj ：ｗkp）から代替案ｗjqを削減する。

【００４８】（２−４−３）完全化された可到達値集合
からの解の算出 さらに、解発生部１８では、値集合完全化部１７で完全
化した可到達値集合を用いて解を計算する。図７は、解
の計算の手順を示すフローチャートである。すなわち、
ステップ７１では、ｋ＝１から順に可到達値集合ｒ（Ｘ
k ：ｗk ）が空ではない部分Ｘk の代替案ｗk を１つ選
択する。ここでｋ＝Ｎならばこれまでに選択して部分Ｘ
1 ，…，ＸN 上の代替案の組ｗ1 ，…，ｗN が解である
ので処理を終了する。ｋ＜Ｎの場合は部分ＸK の代替案
ｗk に矛盾する部分Ｘj （ｊ＞ｋ）の代替案を削減する
ために、ステップ７２で可到達値集合ｒ（Ｘj ：ｗk ）
に含まれないから部分Ｘj の代替案ｗj が存在すると、
可到達値集合ｒ（Ｘj ：ｗj ）から代替案ｗj を削減す
る。

【００４９】なお、以上の図４〜７に示した手順によっ
て全ての部分に矛盾の無い代替案の割り当て（解）が決
まることは明らかである。なぜならば、各部分Ｘk が高
々２個の代替案を含む場合にはシステム全体に矛盾の無
い代替案を割り当てることのできる必要十分条件は、各
部分Ｘk が代替案ｗk を持ち全ての部分Ｘj 上で可到達
集合ｒ（Ｘj ：ｗk ）が空ではなく、さらに、可到達値
集合ｒ（Ｘj ：ｗk ）が代替案ｗj を含むなら可到達値
集合ｒ（Ｘj ：ｗj ）が空ではないことであるためであ
る。

【００５０】（２−４−４）解の出力 代替案集合生成部１は、解計算部２から解の存在を通知
され、かつ、解計算パターン記憶部８に指示された個数
の解が得られた場合、あるいは全ての部分集合Ｖ1 （ｊ
1 ），Ｖ2 （ｊ2 ），…，ＶN （ｊN ）に対する処理を
終了した場合は、経路１３を通して解出力部１０に解の
出力指令を送出する。この出力指令を受け取った解出力
部１０は、経路６を通して解計算部２に、すでに計算し
た可到達値集合から解を算出する指令を送り、解計算部
２中の解発生部１８（図３）がこれを受けて、結果記憶
部９に記憶された可到達値集合から解を計算し、経路６
を経由して解出力部１０に解を返す。最終的な解は、そ
れを受け取った解出力部１０が、個々の応用で受け入れ
られる形式で出力する。このとき、解出力部１０は、解
計算パターン記憶部８に記憶された指示にしたがって、
ｍ個の解が必要な場合はｍ個の解だけを、そうでない場
合は全ての解を出力する。

【００５１】（３）実例１ なお、具体的な例題を用いて、上記のような処理手順に
よって解を計算する実例を示す。例題は、図８に示すよ
うに、部分Ａ，Ｂ，Ｃ，Ｄがそれぞれ代替案ａ１〜ａ
６，ｂ１〜ｂ６，ｃ１〜ｃ６，ｄ１〜ｄ６を持つもので
ある。そして、部分Ａ−Ｂ，Ｂ−Ｃ，Ｃ−Ｄ，Ｄ−Ａ間
に制約が存在するものとする。図８では、部分Ｄ−Ａ間
の関係を除いて、部分間の代替案間で許される組み合わ
せを線で結んで示している。この他に、代替案ａ１に対
してｄ１又はｄ２だけを、また、代替案ａ４に対してｄ
３だけを組み合わせることが許される。

【００５２】すなわち、部分と代替案が 部分Ａ：代替案ａ１，ａ２，ａ３，ａ４，ａ５，ａ６ 部分Ｂ：代替案ｂ１，ｂ２，ｂ３，ｂ４，ｂ５，ｂ６ 部分Ｃ：代替案ｃ１，ｃ２，ｃ３，ｃ４，ｃ５，ｃ６ 部分Ｄ：代替案ｄ１，ｄ２，ｄ３，ｄ４，ｄ５，ｄ６ であり、代替案の可能な組み合わせが 部分Ａと部分Ｂ（ａ１：ｂ１），（ａ３：ｂ３），（ａ
４：ｂ６），（ａ５：ｂ５） 部分Ａと部分Ｄ（ａ１：ｄ１／ｄ２），（ａ４：ｄ３） 部分Ｂと部分Ｃ（ｂ１：ｃ２），（ｂ２：ｃ２），（ｂ
３：ｃ３），（ｂ６：ｃ５） 部分Ｃと部分Ｄ（ｃ２：ｄ１），（ｃ５：ｄ２／ｄ
３），（ｃ６：ｄ６） のように問題を設定すると、解としては｛ａ１，ｂ１，
ｃ２，ｄ１｝と｛ａ４，ｂ６，ｃ５，ｄ３｝の２つが存
在する。解となる代替案間の組み合わせを図８では太線
で結んで示す。この例題に対して、実施形態の手順で解
を求める例を以下に示す。

【００５３】（３−１）代替案集合生成部による処理 まず、代替案集合生成部１には部分Ａ，部分Ｂ，部分
Ｃ，部分Ｄ： （ａ１，ａ２，ａ３，ａ４，ａ５，ａ６），（ｂ１，ｂ
２，ｂ３，ｂ４，ｂ５，ｂ６），（ｃ１，ｃ２，ｃ３，
ｃ４，ｃ５，ｃ６），（ｄ１，ｄ２，ｄ３，ｄ４，ｄ
５，ｄ６） （部分Ａ，部分Ｂ）＝（ａ１，ｂ１），（ａ３，ｂ
３），（ａ４，ｂ６），（ａ５，ｂ５）／（部分Ａ，部
分Ｄ）＝（ａ１，ｄ１），（ａ１，ｄ２），（ａ４，ｄ
３）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），（ｂ２，
ｃ２），（ｂ３，ｃ３），（ｂ６，ｃ５）／（部分Ｃ，
部分Ｄ）＝（ｃ２，ｄ１），（ｃ５，ｄ２），（ｃ５，
ｄ３），（ｃ６，ｄ６）／ なるデータが入力される（図９）。

【００５４】すると、代替案集合生成部１は各部分に許
された代替案の集合を２個以下の代替案の集合に分割し
て （ア）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２），（ｄ１，ｄ
２） （部分Ａ，部分Ｂ）＝（ａ１，ｂ１）／（部分Ａ，部分
Ｄ）＝（ａ１，ｄ１），（ａ１，ｄ２）／（部分Ｂ，部
分Ｃ）＝（ｂ１，ｃ２），（ｂ２，ｃ２）／（部分Ｃ，
部分Ｄ）＝（ｃ２，ｄ１）／ （図１０） （イ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２），（ｄ３，ｄ
４） （部分Ａ，部分Ｂ）＝（ａ１，ｂ１）／（部分Ａ，部分
Ｄ）＝無し／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），
（ｂ２，ｃ２）／（部分Ｃ，部分Ｄ）＝無し／ （図１１） （ウ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２），（ｄ５，ｄ
６）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ１），／（部分Ａ，部
分Ｄ）＝無し／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），
（ｂ２，ｃ２）／（部分Ｃ，部分Ｄ）＝無し／ （図１２） （エ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ３，ｃ４），（ｄ１，ｄ
２）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ１）／（部分Ａ，部分
Ｄ）＝（ａ１，ｄ１），（ａ１，ｄ２）／（部分Ｂ，部
分Ｃ）＝無し／（部分Ｃ，部分Ｄ）＝無し／ （図１３） （オ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ３，ｃ４），（ｄ３，ｄ
４）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ１）／（部分Ａ，部分
Ｄ）＝無し／（部分Ｂ，部分Ｃ）＝無し／（部分Ｃ，部
分Ｄ）＝無し／ （図１４） ・・・・・・ ・・・・・・ （Ｐ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ３，ａ
４），（ｂ５，ｂ６），（ｃ５，ｃ６），（ｄ３，ｄ
４）： （部分Ａ，部分Ｂ）＝（ａ４，ｂ６）／（部分Ａ，部分
Ｄ）＝（ａ４，ｄ３）／（部分Ｂ，部分Ｃ）＝（ｂ６，
ｃ５）／（部分Ｃ，部分Ｄ）＝（ｃ５，ｄ３）／ （図１５） ・・・・・・ （Ｑ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ５，ａ
６），（ｂ５，ｂ６），（ｃ５，ｃ６），（ｄ５，ｄ
６）： （部分Ａ，部分Ｂ）＝（ａ５，ｂ５）／（部分Ａ，部分
Ｄ）＝無し／（部分Ｂ，部分Ｃ）＝（ｂ６，ｃ５）／
（部分Ｃ，部分Ｄ）＝（ｃ６，ｄ６）／ （図１６）の順に問題を生成して、解計算部２に送る。

【００５５】（３−２）解計算部２による処理 代替案集合生成部１から最初の入力データ （ア）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２），（ｄ１，ｄ
２）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ１）／（部分Ａ，部分
Ｄ）＝（ａ１，ｄ１），（ａ１，ｄ２）／（部分Ｂ，部
分Ｃ）＝（ｂ１，ｃ２），（ｂ２，ｃ２）／（部分Ｃ，
部分Ｄ）＝（ｃ２，ｄ１）／が与えられると（図１
０）、解計算部２では、図４及び５に示した手順にした
がって、まず、各代替案の各部分上での可到達値集合を
計算する。

【００５６】すなわち、ステップ４１ではＡの代替案ａ
１，ａ２に対して、まず、部分Ａ上の可到達値集合ｒ
（Ａ：ａ１）＝ａ１，可到達値集合ｒ（Ａ：ａ２）＝ａ
２とする。また、既算集合Ｆ＝｛Ａ｝で、Ａに隣接する
部分の集合はＢ，Ｄであるので未算集合Ｇ＝未算集合Ｇ
＊＝｛Ｂ，Ｄ｝となる（図１７）。そこで、ステップ４
２ではまずＢを未算集合Ｇ＊から取り出して未算集合Ｇ
＊＝｛Ｄ｝とし、さらに、代替案ａ１とｂ１が可接続で
あるので可到達値集合ｒ（Ｂ：ａ１）＝｛ｂ１｝（部分
Ｂでａ１と可接続のものはｂ１、の意）となるが、代替
案ａ２と可接続なＢの代替案が無いので可到達値集合ｒ
（Ｂ：ａ２）は空集合となる（図１８）。ここで、可到
達値集合ｒ（Ｂ：ａ１）＝｛ｂ１｝は、部分Ｂで代替案
ａ１と可接続のものはｂ１、の意である。なお、図１８
において、代替案ｂ２については、部分Ａのどの代替案
とも可接続ではない。

【００５７】さらに、ステップ４４では、可到達値集合
ｒ（Ａ：ａ２）の要素ａ２が可到達値集合ｒ（Ｂ：ａ
２）のどの要素とも可接続ではないので、可到達値集合
ｒ（Ａ：ａ２）から代替案ａ２が削除されて空集合とな
り、削除集合Ｈに｛Ａ，ａ２，ａ２｝が追加される（図
１９）。なお、図１９において代替案ａ２は、部分Ｂの
どの代替案とも可接続ではない。

【００５８】ここで、既算集合Ｆに部分Ｂが追加されて
既算集合Ｆ＝｛Ａ，Ｂ｝となり、未算集合Ｇ＊が空では
ないのでステップ４２に戻って未算集合Ｇ＊から部分Ｄ
を取り出し未算集合Ｇ＊が空集合になる。ここで、部分
Ｄには代替案ｄ１とｄ２が存在し、ともに代替案ａ１と
可接続であるので（部分ＢとＤは制約関係が無い）可到
達値集合ｒ（Ｄ：ａ１）＝｛ｄ１，ｄ２｝、また、既算
集合Ｆ＝｛Ａ，Ｂ，Ｄ｝となる（図２０）。すると、未
算集合Ｇ＊が空集合であり、また、削除集合Ｈが｛Ａ，
ａ２，ａ２｝を含んでいるので、ステップ４６に進む
が、既に可到達値集合ｒ（Ａ：ａ２）が空集合であるの
で、何も起こらずにステップ４９に進む。ここでは、未
算集合Ｇ＝｛Ｂ，Ｄ｝に隣接して既算集合Ｆに含まれな
い部分として未算集合Ｇ＝｛Ｃ｝が計算され、未算集合
Ｇ＊＝未算集合Ｇとなってステップ４２に戻る（図２
１）。

【００５９】ステップ４２では、今度はまず、部分Ｃを
未算集合Ｇ＊＝｛Ｃ｝から取り出して未算集合Ｇ＊を空
集合とし、さらに代替案ｃ２とｂ１およびｃ２とｄ１が
可接続であるので可到達値集合ｒ（Ｃ：ａ１）＝｛ｃ
２｝となるが（図２２）、代替案ｄ２と可接続な可到達
値集合ｒ（Ｃ：ａ１）の要素が存在しないので、ステッ
プ４４で可到達値集合ｒ（Ｄ：ａ１）＝｛ｄ１，ｄ２｝
からｄ２が削除され、｛Ｄ，ｄ２，ａ１｝が削除集合Ｈ
に追加される（図２３）。なお、図２２において、代替
案ｃ１は、部分Ｄのどの代替案とも可接続ではない。ま
た、図２３において、代替案ｄ２は、部分Ｃのどの代替
案とも可接続ではない。

【００６０】また、代替案ｃ１と可接続な可到達値集合
ｒ（Ｂ：ａ１）、可到達値集合ｒ（Ｄ：ａ１）の要素が
ないので代替案ｃ１は可到達値集合ｒ（Ｃ：ａ１）には
含まれない（図２２）。次に既算集合ＦにＣが追加され
て既算集合Ｆ＝｛Ａ，Ｂ，Ｃ，Ｄ｝となる。さらに削除
集合Ｈが｛Ｄ，ｄ２，ａ１｝を含むのでステップ４６に
進むが、Ｄに隣接するＡ，Ｃ上では可到達値集合ｒ
（Ａ：ａ１）の要素ａ１と可到達値集合ｒ（Ｃ：ａ１）
の要素ｃ２がともにｄ２ではない可到達値集合ｒ（Ｄ：
ａ１）の要素ｄ１と可接続であるので、何も起こらずに
ステップ４９に進む（図２４）。なお、図２４におい
て、代替案ａ１は、代替案ｄ２と可接続であるが、代替
案ｄ１とも可接続であるので、代替案ｄ２が削除されて
も何も起こらない。

【００６１】ここでは、既算集合Ｆに含まれない要素が
もう存在しないので未算集合Ｇが空集合となり、今度は
部分Ｂの代替案ｂ１とｂ２の可到達値集合の算出が行わ
れる。同様に部分Ｃ，Ｄに対する処理が行なわれて、結
局 ｒ（Ａ：ａ１）＝｛ａ１｝，ｒ（Ａ：ａ２）＝空，ｒ
（Ｂ：ａ１）＝｛ｂ１｝，ｒ（Ｂ：ａ２）＝空，ｒ
（Ｃ：ａ１）＝｛ｃ２｝，ｒ（Ｃ：ａ２）＝空，ｒ
（Ｄ：ａ１）＝｛ｄ１｝，ｒ（Ｄ：ａ２）＝空，ｒ
（Ａ：ｂ１）＝｛ａ１｝，ｒ（Ａ：ｂ２）＝空，ｒ
（Ｂ：ｂ１）＝｛ｂ１｝，ｒ（Ｂ：ｂ２）＝空，ｒ
（Ｃ：ｂ１）＝｛ｃ２｝，ｒ（Ｃ：ｂ２）＝空，ｒ
（Ｄ：ｂ１）＝｛ｄ１｝，ｒ（Ｄ：ｂ２）＝空，ｒ
（Ａ：ｃ１）＝空， ｒ（Ａ：ｃ２）＝｛ａ１｝，
ｒ（Ｂ：ｃ１）＝空， ｒ（Ｂ：ｃ２）＝｛ｂ
１｝，ｒ（Ｃ：ｃ１）＝空， ｒ（Ｃ：ｃ２）＝
｛ｃ２｝，ｒ（Ｄ：ｃ１）＝空， ｒ（Ｄ：ｃ２）
＝｛ｄ１｝，ｒ（Ａ：ｄ１）＝｛ａ１｝，ｒ（Ａ：ｂ
２）＝空，ｒ（Ｂ：ｄ１）＝｛ｂ１｝，ｒ（Ｂ：ｄ２）
＝空，ｒ（Ｃ：ｄ１）＝｛ｃ２｝，ｒ（Ｃ：ｄ２）＝
空，ｒ（Ｄ：ｄ１）＝｛ｄ１｝，ｒ（Ｄ：ｄ２）＝空と
なる。

【００６２】図６に示す可到達値集合を完全化する処理
では、これらの可到達値集合から、可到達値集合ｒ
（Ｐ：ｑ）がｐを含み可到達値集合ｒ（Ｐ：ｐ）が空集
合である場合に可到達値集合ｒ（Ｐ：ｑ）からｐを削除
するが、この例ではこのような場合は無いので何も起こ
らない。さらに、図７に示す解の計算の処理では、まず
ステップ７１で可到達値集合ｒ（Ａ：ａ１）＝｛ａ１｝
であるので代替案ａ１が選ばれる。ステップ７２では、
可到達値集合ｒ（Ｂ：ａ１），可到達値集合ｒ（Ｃ：ａ
１），可到達値集合ｒ（Ｄ：ａ１）に含まれない部分
Ｂ，Ｃ，Ｄの要素ｂ２，ｃ１，ｄ２の可到達値集合はい
ずれも空集合であるので、何もせずにステップ７２に戻
り、今度は可到達値集合ｒ（Ｂ：ｂ１）＝｛ｂ１｝であ
るのでＢの代替案としてｂ１が選ばれる。以降同様に、
ｃ２，ｄ１が選ばれて、結局解｛ａ１，ｂ１，ｃ２，ｄ
１｝が求まる。

【００６３】同じ操作が（イ）以降のすべてのデータに
対して施されるが、データ（Ｐ）以外は解を持たないの
で、すべての可到達値集合が空集合となるが、データ
（Ｐ）に対しては解｛ａ４，ｂ６，ｃ５，ｄ３｝が求ま
る。

【００６４】（４）実例２ 次に、代替案集合を分割しないと、解が存在しないにも
かかわらず可到達値集合が空にはならない実例を示す。

【００６５】（４−１）代替案集合生成部による処理 部分と代替案を 部分Ａ代替案ａ１，ａ２，ａ３ 部分Ｂ代替案ｂ１，ｂ２，ｂ３ 部分Ｃ代替案ｃ１，ｃ２，ｃ３ 部分Ｄ代替案ｄ１，ｄ２，ｄ３ 代替案の可能な組み合わせを 部分Ａと部分Ｂ（ａ１：ｂ２／ｂ３），（ａ２：ｂ１／
ｂ３），（ａ３：ｂ１／ｂ２） 部分Ａと部分Ｃ（ａ１：ｃ２／ｃ３），（ａ２：ｃ１／
ｃ３），（ａ３：ｃ１／ｃ２） 部分Ａと部分Ｄ（ａ１：ｄ２／ｄ３），（ａ２：ｄ１／
ｄ３），（ａ３：ｄ１／ｄ２） 部分Ｂと部分Ｃ（ｂ１：ｃ２／ｃ３），（ｂ２：ｃ１／
ｃ３），（ｂ３：ｃ１／ｃ２） 部分Ｂと部分Ｄ（ｂ１：ｄ２／ｄ３），（ｂ２：ｄ１／
ｄ３），（ｂ３：ｄ１／ｄ２） 部分Ｃと部分Ｄ（ｃ１：ｄ２／ｄ３），（ｃ２：ｄ１／
ｄ３），（ｃ３：ｄ１／ｄ２） とすると、まず、代替案集合生成部１には 部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ２，ａ
３），（ｂ１，ｂ２，ｂ３），（ｃ１，ｃ２，ｃ３），
（ｄ１，ｄ２，ｄ３）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ２），（ａ１，ｂ
３），（ａ２，ｂ１），（ａ２，ｂ３），（ａ３，ｂ
１），（ａ３，ｂ２）／（部分Ａ，部分Ｃ）＝（ａ１，
ｃ２），（ａ１，ｃ３），（ａ２，ｃ１），（ａ２，ｃ
３），（ａ３，ｃ１），（ａ３，ｃ２）／（部分Ａ，部
分Ｄ）＝（ａ１，ｄ２），（ａ１，ｄ３），（ａ２，ｄ
１），（ａ２，ｄ３），（ａ３，ｄ１），（ａ３，ｄ
２）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），（ｂ１，
ｃ３），（ｂ２，ｃ１），（ｂ２，ｃ３），（ｂ３，ｃ
１），（ｂ３，ｃ２）／（部分Ｂ，部分Ｄ）＝（ｂ１，
ｄ２），（ｂ１，ｄ３），（ｂ２，ｄ１），（ｂ２，ｄ
３），（ｂ３，ｄ１），（ｂ３，ｄ２）／（部分Ｃ，部
分Ｄ）＝（ｃ１，ｄ２），（ｃ１，ｄ３），（ｃ２，ｄ
１），（ｃ２，ｄ３），（ｃ３，ｄ１），（ｃ３，ｄ
２）／なるデータが入力される（図２５）。

【００６６】すると、代替案集合生成部１は各部分に許
された代替案の集合を２個以下の代替案の集合に分割し
て （ア）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２）， （ｄ１，ｄ２）：（部分Ａ，部分Ｂ）＝（ａ１，ｂ
２），（ａ２，ｂ１）／（部分Ａ，部分Ｃ）＝（ａ１，
ｃ２），（ａ２，ｃ１）／（部分Ａ，部分Ｄ）＝（ｃ
１，ｄ２），（ａ２，ｄ１）／（部分Ｂ，部分Ｃ）＝
（ｂ１，ｃ２），（ｂ２，ｃ１）／（部分Ｂ，部分Ｄ）
＝（ｂ１，ｄ２），（ｂ２，ｄ１）／（部分Ｃ，部分
Ｄ）＝（ｃ１，ｄ２），（ｃ２，ｄ１）／ （図２７） （イ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２），（ｄ３）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ２），（ａ２，ｂ１）
／（部分Ａ，部分Ｃ）＝（ａ１，ｃ２），（ａ２，ｃ
１）／（部分Ａ，部分Ｄ）＝（ａ１，ｄ３），（ａ２，
ｄ３）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），（ｂ
２，ｃ１）／（部分Ｂ，部分Ｄ）＝（ｂ１，ｄ３），
（ｂ２，ｄ３）／（部分Ｃ，部分Ｄ）＝（ｃ１，ｄ
３），（ｃ２，ｄ３）／ （ウ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ３），（ｄ１，ｄ２）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ２），（ａ２，ｂ１）
／（部分Ａ，部分Ｃ）＝（ａ１，ｃ３），（ａ２，ｃ
３）／（部分Ａ，部分Ｄ）＝（ａ１，ｄ２），（ａ２，
ｄ１）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ３），（ｂ
２，ｃ３）／（部分Ｂ，部分Ｄ）＝（ｂ１，ｄ２），
（ｂ２，ｄ１）／（部分Ｃ，部分Ｄ）＝（ｃ１，ｄ
３），（ｃ２，ｄ３）／ （エ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ３），（ｃ１，ｃ２），（ｄ１，ｄ２）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ３），（ａ２，ｂ３）
／（部分Ａ，部分Ｃ）＝（ａ１，ｃ２），（ａ２，ｃ
１）／（部分Ａ，部分Ｄ）＝（ａ１，ｄ２），（ａ２，
ｄ１）／（部分Ｂ，部分Ｃ）＝（ｂ３，ｃ２），（ｂ
３，ｃ１）／（部分Ｂ，部分Ｄ）＝（ｂ３，ｄ２），
（ｂ３，ｄ１）／（部分Ｃ，部分Ｄ）＝（ｃ１，ｄ
２），（ｃ２，ｄ１）／ （オ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ３），
（ｂ１，ｂ２），（ｃ１，ｃ２），（ｄ１，ｄ２）： （部分Ａ，部分Ｂ）＝（ａ３，ｂ１），（ａ３，ｂ２）
／（部分Ａ，部分Ｃ）＝（ａ３，ｃ１），（ａ３，ｃ
２）／（部分Ａ，部分Ｄ）＝（ａ３，ｄ１），（ａ３，
ｄ２）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），（ｂ
２，ｃ１）／（部分Ｂ，部分Ｄ）＝（ｂ１，ｄ２），
（ｂ２，ｄ１）／（部分Ｃ，部分Ｄ）＝（ｃ１，ｄ
２），（ｃ２，ｄ１）／ （カ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ３），（ｄ３）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ２），（ａ２，ｂ１）
／（部分Ａ，部分Ｃ）＝（ａ１，ｃ３），（ａ２，ｃ
３）／（部分Ａ，部分Ｄ）＝（ａ１，ｄ３），（ａ２，
ｄ３）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ３），（ｂ
２，ｃ３）／（部分Ｂ，部分Ｄ）＝（ｂ１，ｄ３），
（ｂ２，ｄ３）／（部分Ｃ，部分Ｄ）＝（ｃ３，ｄ３）
／ …… （Ａ）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ３），
（ｂ３），（ｃ３），（ｄ３）： （部分Ａ，部分Ｂ）＝無し／（部分Ａ，部分Ｃ）＝無し
／（部分Ａ，部分Ｄ）＝無し）／（部分Ｂ，部分Ｃ）＝
無し／（部分Ｂ，部分Ｄ）＝無し／（部分Ｃ，部分Ｄ）
＝無し／の順に問題を生成して、解計算部２に送る。

【００６７】（４−２）解計算部２による処理 代替案集合生成部１から最初の入力データ （ア）部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ
２），（ｂ１，ｂ２），（ｃ１，ｃ２）， （ｄ１，ｄ２）：（部分Ａ，部分Ｂ）＝（ａ１，ｂ
２），（ａ２，ｂ１）／（部分Ａ，部分Ｃ）＝（Ａ１，
Ｃ２），（Ａ２，Ｃ１）／（部分Ａ，部分Ｄ）＝（ａ
１，ｄ２），（ａ２，ｄ１）／（部分Ｂ，部分Ｃ）＝
（ｂ１，ｃ２），（ｂ２，ｃ１）／（部分Ｂ，部分Ｄ）
＝（ｂ１，ｄ２），（ｂ２，ｄ１）／（部分Ｃ，部分
Ｄ）＝（ｃ１，ｄ２），（ｃ２，ｄ１）／が与えられた
場合を考える。

【００６８】この場合、図４に示す手順では、まず各代
替案の各部分上での可到達値集合を計算する。すなわ
ち、ステップ４１では、例えばＡの代替案ａ１に対し
て、まず部分Ａ上の可到達値集合ｒ（Ａ：ａ１）＝ａ１
とする。ステップ４２〜４５では最初は既算集合Ｆ＝
｛Ａ｝であり、また、部分Ａに隣接する部分の集合は
Ｂ，Ｃ，Ｄであるので未算集合Ｇ＊＝｛Ｂ，Ｃ，Ｄ｝で
ある。そこで未算集合Ｇ＊からまずＢを取り出すと、可
到達値集合ｒ（Ｂ：ａ１）＝｛ｂ２｝となる。次に未算
集合Ｇ＊からＣを取り出すと、部分Ｃの代替案ｃ１とｃ
２は共に可到達値集合ｒ（Ａ：ａ１）＝｛ａ１｝と可到
達値集合ｒ（Ｂ：ａ１）＝｛ｂ２｝のどちらかと矛盾す
るので可到達値集合ｒ（Ｃ：ａ１）は空集合になる。同
じように可到達値集合ｒ（Ｃ：ａ２）も空集合になるの
で、（ア）は解を持たず処理は終了する（図２７）。な
お、図２７において、代替案ｃ１は、可到達値集合ｒ
（Ａ：ａ１）のどの代替案とも可接続ではなく、また、
代替案ｃ２は、可到達値集合ｒ（Ｂ：ａ１）のどの代替
案とも可接続ではない。

【００６９】この場合は（イ）以下も解を持たずに処理
が終了し、結局に代替案集合生成部１に最初に与えられ
た元の問題は解を持たないことになる。元の問題は実際
に解を持たないので正しく処理が終わったことになる。

【００７０】しかし、元の代替案集合を分割せずに 部分Ａ，部分Ｂ，部分Ｃ，部分Ｄ：（ａ１，ａ２，ａ
３），（ｂ１，ｂ２，ｂ３），（ｃ１，ｃ２，ｃ３），
（ｄ１，ｄ２，ｄ３）： （部分Ａ，部分Ｂ）＝（ａ１，ｂ２），（ａ１，ｂ
３），（ａ２，ｂ１），（ａ２，ｂ３），（ａ３，ｂ
１），（ａ３，ｂ２）／（部分Ａ，部分Ｃ）＝（ａ１，
ｃ２），（ａ１，ｃ３），（ａ２，ｃ１），（ａ２，ｃ
３），（ａ３，ｃ１），（ａ３，ｃ２）／（部分Ａ，部
分Ｄ）＝（ａ１，ｄ２），（ａ１，ｄ３），（ａ２，ｄ
１），（ａ２，ｄ３），（ａ３，ｄ１），（ａ３，ｄ
２）／（部分Ｂ，部分Ｃ）＝（ｂ１，ｃ２），（ｂ１，
ｃ３），（ｂ２，ｃ１），（ｂ２，ｃ３），（ｂ３，ｃ
１），（ｂ３，ｃ２）／（部分Ｂ，部分Ｄ）＝（ｂ１，
ｄ２），（ｂ１，ｄ３），（ｂ２，ｄ１），（ｂ２，ｄ
３），（ｂ３，ｄ１），（ｂ３，ｄ２）／（部分Ｃ，部
分Ｄ）＝（ｃ１，ｄ２），（ｃ１，ｄ３），（ｃ２，ｄ
１），（ｃ２，ｄ３），（ｃ３，ｄ１），（ｃ３，ｄ
２）／をそのまま解計算部２に与える場合を考える（図
２５）。

【００７１】この場合も、ステップ４１ではまず部分Ａ
上の代替案ａ１の可到達値集合はｒ（Ａ：ａ１）＝ａ１
となり、ステップ４２〜４５では最初は既算集合Ｆ＝
｛Ａ｝で、また、部分Ａに隣接する部分の集合はＢ，
Ｃ，Ｄであるので未算集合Ｇ＊＝｛Ｂ，Ｃ，Ｄ｝である
ことまでは先と同じである。そこで未算集合Ｇ＊からま
ずＢを取り出すと、この場合は、可到達値集合ｒ（Ｂ：
ａ１）＝｛ｂ２，ｂ３｝である。したがって、次に未算
集合Ｇ＊から部分Ｃを取り出すと、ｃ２とｃ３がａ１と
矛盾しないが、ｃ２はａ１およびｂ３と矛盾せず、ま
た、ｃ３はａ１およびｂ２と矛盾しないので、可到達値
集合ｒ（Ｃ：ａ１）＝｛ｃ２，ｃ３｝となる。同じよう
にして、結局 ｒ（Ａ：ａ１）＝ａ１ ｒ（Ｂ：ａ１）＝｛ｂ２，ｂ３｝ ｒ（Ｃ：ａ１）＝｛ｃ２，ｃ３｝ ｒ（Ｄ：ａ１）＝｛ｄ２，ｄ３｝ ｒ（Ａ：ａ２）＝ａ２ ｒ（Ｂ：ａ２）＝｛ｂ１，ｂ３｝ ｒ（Ｃ：ａ２）＝｛ｃ１，ｃ３｝ ｒ（Ｄ：ａ２）＝｛ｄ１，ｄ３｝ ｒ（Ａ：ａ３）＝ａ３ ｒ（Ｂ：ａ３）＝｛ｂ１，ｂ２｝ ｒ（Ｃ：ａ３）＝｛ｃ１，ｃ２｝ ｒ（Ｄ：ａ３）＝｛ｄ１，ｄ２｝ ・・・ となる。したがって、解が存在しないことをここでは判
定できず、ステップ３で種々の組み合わせを試してそれ
が判ることになる（図２６）。

【００７２】（５）証明 なお、上記の処理手順によって解が正しく求められるこ
との証明を以下に示す。

【００７３】（５−１）定義１：制約充足問題 ＣＳＰ
（Ｘ，Ｚ，Ｖ，Ｃ） Ｘ＝｛Ｘ1 ，Ｘ2 ，・・・｝を変数の集合、ＺをＸに属
する変数の対の集合とし、変数対

【数１】 が採り得る値の組み合わせに制約があるとする。つまり
｛Ｘi ，Ｘj ｝には許された値の組しか代入することが
できない。この時、Ｘのすべての変数にすべての制約を
満たす値を代入する問題をＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）と
呼ぶ。また、制約を満足する値の組をＣＳＰ（Ｘ，Ｚ，
Ｖ，Ｃ）の解と呼ぶ。ここで、Ｖ＝｛Ｖ1，Ｖ2 ，・・
・｝は変数Ｘi （ｉ＝１，２，・・・）に代入可能な値
の集合Ｖiの列であり、Ｃ＝｛Ｃi ，j ｝はＺの変数対
｛Ｘi ，Ｘj ｝（ｉ，ｊ＝１，２，・・・）に許された
値の組み合わせの集合の列である。

【００７４】さらにＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）の変数

【数２】 は

【数３】 であれば互いに隣接すると言い、Ｘi に隣接するすべて
の変数の集合をＸi の隣接集合と呼ぶ。また、

【数４】 とする時、｛Ｖi ，Ｖj ｝の要素の組｛ｖi ，ｖj ｝が
Ｃの要素であれば、ｖiとｖj は可接続であるという。

【００７５】（５−２）定義２：可到達値集合 ＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）の互いに隣接するループを含
む任意の変数列｛Ｘi，…，Ｘk ｝上に、Ｘi ，Ｘk 上
で各々ｗi ，ｗk となる互いに可接続な値の列

【数５】 が存在する時、Ｘk の値ｗk はＸi の値ｗi から可到達
であるという。そしてｗi から可到達なすべての値から
成るＶk の部分集合を、Ｘk 上のｗi の可到達値集合と
呼びｒ（Ｘk ：ｗi ）と表わす。ただし変数列｛Ｘi ，
…，Ｘk ｝が同じ変数を複数個含む場合は、Ｘi とＸk
以外の変数Ｘp に与えられる値は各々異なっていてもよ
い。

【００７６】（５−３）定義３：完全な値集合 ＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）において、Ｘ＝｛Ｘ1 ，Ｘ2
，・・・｝、Ｖ＝｛Ｖ1 ，Ｖ2 ，・・・｝とし、Ｖの
部分集合を

【数６】 としてＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）を構成する。また、可
到達値集合ｒ（Ｘh ：ｗk ）をＣＳＰ（Ｘ，Ｚ，Ｖ，
Ｃ）における値

【数７】 のＸh 上の可到達値集合とする。ここで、すべてのｉに
対して Ｖi ≠φであり、また、

【数８】 ならば任意のＸj 上で 可到達値集合ｒ（Ｘj ：ｗk ）
≠φ、さらに

【数９】 なら

【数１０】 が成り立つ時、値集合Ｖは完全であるという。また、Ｖ
が完全な値集合Ｖを含む時、ＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）
は完全であるという。さらにＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）
の完全な値集合Ｖが、ＣＳＰ（Ｘ，Ｖ，Ｚ，Ｃ）の任意
の解｛ｗ1 ，ｗ2，・・・｝に属するすべての値ｗj を
含む時、ＶはＣＳＰ（Ｘ，Ｖ，Ｚ，Ｃ）の最大の完全な
値集合であるという。

【００７７】（５−４）定理１ 各変数Ｘi の値集合Ｖi が高々２個の値から成るＣＳＰ
（Ｘ，Ｚ，Ｖ，Ｃ）が解を持つ必要十分条件は、ＣＳＰ
（Ｘ，Ｚ，Ｖ，Ｃ）が完全であることである。また、Ｖ
が完全な値集合であると、任意の値

【数１１】 を含むＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）の解が存在する。

【００７８】（５−６）証明 ＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）がＮ個の変数｛Ｘ1 ，・・
・，ＸN ｝を持つとして、その解を｛ｖ1 ，・・・，ｖ
N ｝とする。すると Ｖ＝｛ｖ1 ，・・・，ｖN｝は明
らかに完全である。したがって、定理の条件はＣＳＰ
（Ｘ，Ｚ，Ｖ，Ｃ）が解を持つための必要条件である。
そこでＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）の完全な値集合をＶと
し、ＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）における変数Ｘk の値ｗ
k のＸh 上の可到達値集合をｒ（Ｘh ：ｗk ）として、
定理の条件が十分条件であることを証明する。

【００７９】まず、Ｖが完全で

【数１２】 ならすべてのＸh 上で

【数１３】 となることを示す。そこであるＸh 上で

【数１４】 であると仮定する。するとＶh が高々２つの要素｛ｗh
，ｗh ｝しか含まず、可到達値集合ｒ（Ｘh ：ｗk ）
≠φ、可到達値集合ｒ（Ｘh ：ｗj ）≠φであるので、

【数１５】 なら

【数１６】 でかつ、可到達値集合ｒ（Ｘh ：ｗk ）はｗh を、ま
た、可到達値集合ｒ（Ｘh：ｗj ）はｗh を含まない。

【００８０】つまりＸk からＸh に至るある経路Ｐが存
在して、ｗk から始まるＰ上のすべての互いに可接続な
値列のＸh 上の値がｗh だけであるので、

【数１７】 が成り立つ。また、可到達値集合ｒ（Ｘh ：ｗj ）がｗ
h を含まないことから、可到達値集合ｒ（Ｘj ：ｗh ）
がｗj を含まない。もし

【数１８】 なら、Ｘj とＸh を結ぶ任意の経路Ｑ＝｛Ｘj ，Ｘq1，
・・・，Ｘqm，Ｘh ｝に対して、Ｑを逆にたどるＸh と
Ｘj を結ぶ経路Ｐ＝｛Ｘh ，Ｘqm，・・・，Ｘq1，Ｘj
｝上に互いに可接続な値列｛ｗh ，ｗqm，・・・，ｗq
1，ｗj ｝が存在するので、｛ｗj ，ｗq1，・・・，ｗq
m，ｗh ｝がＸj とＸh を結ぶＱ上の互いに可接続な値
列となり、

【数１９】 となるからである。したがって、ｗj が可到達値集合ｒ
（Ｘj ：ｗk ）の要素ではないことになり、

【数２０】 である仮定に矛盾する。つまり、Ｖが完全で

【数２１】 ならすべてのＸh 上で

【数２２】 が成り立つ。

【００８１】そこで次に、Ｖが完全なら変数集合｛Ｘ1
，・・・，ＸN ｝上にＶの要素の列｛ｗ1 ，・・・，
ｗN ｝が存在して、任意のＸk ，Ｘj とＸh に対して

【数２３】 となることを示す。まずＶが完全なら変数Ｘ1 の値

【数２４】 が存在して、Ｘ2 上に

【数２５】 が存在する。また、上述の性質から、任意のＸh 上で

【数２６】 が成り立つ。そこで｛Ｘ1 ，・・・，Ｘn ｝（ｎ≧２）
上にＶの要素の列｛ｗ1，・・・，ｗn ｝が存在して、
ｋ≦ｎ，ｊ≦ｎ ならば任意のＸh 上で

【数２７】 が成り立つと仮定する。すると２個の要素から成る集合
Ａの部分集合Ａ1 とＡ2が

【数２８】 を満たすなら、

【数２９】 か

【数３０】 であるので、各変数Ｘh が高々２個の値しか含まないこ
とから、｛ｗ1 ，・・・，ｗn ｝の順序を｛ｗk1，・・
・，ｗkn｝と並べ替えて

【数３１】 となるようにすることができる。

【００８２】したがって、 ｈ＝ｎ＋１ とすると

【数３２】 であり、

【数３３】 が存在するので、｛Ｘ1 ，・・・，Ｘn ，Ｘn+1 ｝の値
列｛ｗ1 ，・・・，ｗn，ｗn+1 ｝に対しても｛ｋ，ｊ
≦ｎ＋１｝ならば任意のＸh 上で

【数３４】 が成り立つ。

【００８３】つまり、帰納法によってＶが完全であれば
｛Ｘ1 ，・・・，ＸN ｝の値列｛ｗ1 ，・・・，ｗN ｝
が存在して、任意のＸh に対して

【数３５】 となることが証明される。ここで｛ｗ1 ，・・・，ｗN
｝がＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）の解であることは明ら
かである。また、解｛ｗ1 ，・・・，ｗN ｝を構成する
上述の過程における変数Ｘ1 およびその値ｗ1 の選び方
には

【数３６】 であること以外の制限は無いので、任意の

【数３７】 を含むＣＳＰ（Ｘ，Ｚ，Ｖ，Ｃ）の解が存在することも
分かる。

【００８４】（６）実施の形態による効果 以上のように、本実施形態では、与えられた問題が、各
部分が最大２個の代替案を含む部分集合に分解される。
各部分が最大２個の代替案を持つ部分集合に関する解の
計算は、部分が多数でもきわめて短時間で行うことがで
きる。このため、分解された各部分集合ごとの計算所要
時間をすべて合計しても、もとの問題のまま解を計算す
る所要時間よりも大幅に短縮される。このため、大規模
な制約充足問題も高速に解決することができる。

【００８５】また、本実施形態では、問題を構成する部
分が多数であっても、可到達値集合を完全化する手順に
よって、部分集合からきわめて短時間に解を計算するこ
とができるので、問題全体の解を計算する所要時間が大
幅に短縮される。

【００８６】つまり、ある部分に許された代替案の数が
２個より多い場合に各部分に矛盾無く代替案を割り当て
る問題は、各部分に２個以下の代替案が許されている場
合に矛盾無く代替案を割り当てる問題の集合に変換でき
るので、変換された個々の問題を高速に処理することに
よって、元の割り当てが高速に実行できるようになる。

【００８７】なお、本実施形態において、記憶量及び計
算量を実質的に律し、律速段階となるのは解の計算であ
る。この点、本発明によれば、各部分が２個以下の代替
案を持つ時、部分の数をＮ、各部分と制約関係にある部
分の平均個数をｃとすると、従来のように２＾Ｎに比例
するのではなく、Ｏ（４ｃ・Ｎ＾２）オーダーの計算量
で矛盾の無い代替案の組み合わせが求まる。なお、この
場合、必要な記憶量でＯ（４×Ｎ＾２）オーダーとな
る。したがって、Ｎの数が１００でも計算量はＯ（４０
０，０００）オーダーであり、実用的な時間内に代替案
の組み合わせを算出できるようになる。

【００８８】従来は特殊な場合を除くと全ての場合を調
べ尽くす方法しか無く、具体的には、ある部分の代替案
を選び、次の部分の代替案との矛盾の有無を確認すると
いう作業を、部分ごとの順列組み合わせで全て行う必要
が生じる。このため、最悪の場合には矛盾の無い代替案
の組み合わせを求めるのにＯ（１００×ｃ／２×２＾１
００）オーダー以上の計算が必要であったが、本発明に
よって１／２＾９０以下に計算量を削減できたことにな
る。

【００８９】なお、コンピュータによる個々の計算に１
０オーダー程度の命令が必要になるので、全体ではＯ
（４０ｃ×Ｎ＾２）オーダーの処理量となり、各々が２
個以下の代替案を持つ１００個の部分が存在し、各部分
と制約関係のある部分の平均個数が１０であるとする
と、計算量は最大でＯ（４００×１００＾２）＝Ｏ
（４，０００，０００）となる。

【００９０】また、各部分が３個以上の代替案を持つ場
合にも、部分の数をＮ、各部分と制約関係にある部分の
平均個数をｃとすると、従来の全ての場合を調べ尽くす
方法ではＯ（Ｎ×ｃ×ｄ＾Ｎ）オーダーの計算が必要で
あったが、本発明によるとそれをＯ（４ｃ×Ｎ＾２）×
（ｄ／２）＾Ｎ）オーダーまで削減することができる。

【００９１】また、各部分が４個の代替案を持つ部分が
２０個存在し、各部分と制約関係のある部分の平均個数
が４である場合を考えると、従来方法の計算量はＯ（８
０×４＾２０）＝Ｏ（８０×２＾４０）オーダーであっ
たが、本発明の計算量はＯ（６，４００×２＾２０）で
あり、本発明における個々の計算が１０ステップ程度の
計算機命令で実現されるとしても１／５００以下に計算
量を削減できる。

【００９２】この場合、Ｏ（１６×４００×１０）＝Ｏ
（６４，０００）オーダーの計算を２＾２０個の｛Ｖ1
（ｋ1 ），…，ＶN （ｋN ）｝に対して実行する必要が
あるが、これは一般に用いられる通常のワークステーシ
ョンやパーソナルコンピュータによれば十数分以内程度
で終了する程度の計算量になる。しかも２＾２０個に分
割された個々の部分集合は全く独立に計算できるので、
１０台程度の計算機で並列処理すれば、数分で計算が完
了し、全ての解を求めることができる。

【００９３】本発明は、このように問題を高速に解決す
るので、エキスパート・システムなどを応用したシステ
ムが実用的な時間内で動作するようになる。

【００９４】なお、多くの問題では、部分が多数であっ
ても、個々の部分に設定可能な代替案の個数は限られる
場合が多い。このため、代替案の組み合わせに関する制
約が全ての部分対の間に存在することは少なく、部分の
集合を制約的には互いに独立な集合の組に分解すること
ができる。また、設定可能な代替案の数が多くても、実
質的に意味のある代替案の数は少なくなる場合が多い。
例えば、各代替案に評価値が割り当てられている場合
に、評価値がある値以上になる代替案の数は限られる。
このような事情から、相当複雑な問題でも、部分の数が
大きくても実効的には２０程度になる場合も少なくな
い。したがって、上記のように本発明により解決あるい
は改善できる問題やシステムの範囲は飛躍的に広くな
る。

【００９５】さらに、Ａｄａｐｔｉｖｅ Ｃｏｎｓｉｓ
ｔｅｎｃｙ Ａｌｇｏｒｉｈｍ（ＡＣＡ）のように、制
約関係が影響を及ぼす部分の集合を局所化する方法との
併用により、部分の数がさらに大きい場合も扱えるよう
になる。

【００９６】（７）他の実施の形態 なお、本発明は上記実施の形態に限定されるものではな
いので、次に例示するような他の実施の形態をも包含す
るものである。例えば、上記実施例では、全ての処理を
逐次的に行っているが、短時間で処理を終了させるため
に適当な部分を並列に処理することも可能である（請求
項３）。図２８、図２９は解を並列に算出する構成の例
である。

【００９７】図２８は、代替案集合生成部８１が１つ存
在して、解計算部８２が、解計算部８２１，８２２のよ
うに複数個存在する例である。つまり１つの代替案集合
生成部８１が複数の解計算部８２に各々異なる代替案集
合の組み合わせ｛Ｖ1 （ｋ1），Ｖ2 （ｋ2 ），…，ＶN
（ｋN ）｝を送り、解計算部８２が与えられた代替案
集合の組み合わせに対する解をそれぞれ並列に計算す
る。

【００９８】図２９は、代替案集合生成部９１も、代替
案集合生成部９１１，９１２のように複数個設ける例で
あり、各代替案集合生成部９１は予め指定された範囲の
代替案集合の組み合わせを並列に算出し、各々に接続さ
れた解計算部９２が、接続された代替案集合生成部が算
出した代替案集合の組み合わせに対応する解を並列に計
算する。

【００９９】このようにすれば、問題を部分集合へ分解
したり部分集合からの解の計算が並列処理できるので、
特に大規模な問題の場合も、処理が高速に行われる（請
求項３）。

【０１００】なお、上記各実施形態では、制約充足問題
とその解を求めることを例に挙げて説明したが、本発明
のシステム構築装置及び構築方法においては、この制約
充足問題における各部分と代替案が、システムを構成す
る各部分と各部分が有する代替案に相当する。また、実
施の形態で得られた解が、構築目標となるシステムの構
成を示す。例えば、問題における各部分が機械やプログ
ラムの所定の部分に相当し、代替案が機械やプログラム
の所定の部分を構成するに当たって選択できる複数の異
なった部品を意味する。そして、各部分の代替案間にお
ける制約は、例えば、機械の所定の部分でボルトを使用
した場合には、隣接する部分ではそのボルトに合ったナ
ットを使用する必要があり、所定の部分でボルトの代わ
りに係合用の爪を使用した場合には、隣接する部分では
係合用の孔を使用する必要があるということを意味す
る。

【０１０１】また、本発明では、部分集合から必ずしも
最終的な解までは計算せず、一定の分析を行うようにし
てもよい。また、本発明は、コンピュータをプログラム
で制御することによって実現することが一般的と考えら
れるが、そのようなプログラムを記録した記録媒体も本
発明の一態様である。

【０１０２】

【発明の効果】以上説明したように、本発明によれば、
大規模な制約充足問題も高速に計算することができ、人
工知能をはじめとする複雑な情報処理の実用性が大幅に
向上する。また、本発明によれば、制約充足問題として
把握することのできるシステムの構築作業を、比較的容
易に実施することのできるシステム構築装置及び構築方
法を提供することが可能となる。

【図面の簡単な説明】

【図１】本発明の実施の形態である制約充足問題の解決
装置の要部の構成を概略的に示す機能ブロック図。

【図２】本発明の実施の形態における制約充足問題の解
決装置の構成をより具体的に示す機能ブロック図。

【図３】本発明の実施の形態において、解計算部の具体
的な構成を示す機能ブロック図。

【図４】本発明の実施の形態において、可到達値集合を
算出する手順を示すフローチャート（前半）。

【図５】本発明の実施の形態において、可到達値集合を
算出の手順を示すフローチャート（後半）。

【図６】本発明の実施の形態において、可到達値集合を
完全化する手順を示すフローチャート。

【図７】本発明の実施の形態において、完全化した可到
達値集合から解を計算する手順を示すフローチャート。

【図８】本発明の実施の形態における例題の構成を示す
図。

【図９】本発明の実施の形態における例題の内容を示す
図。

【図１０】本発明の実施の形態における例題を分解して
作成された部分集合（ア）の内容を示す図。

【図１１】本発明の実施の形態における例題を分解して
作成された部分集合（イ）の内容を示す図。

【図１２】本発明の実施の形態における例題を分解して
作成された部分集合（ウ）の内容を示す図。

【図１３】本発明の実施の形態における例題を分解して
作成された部分集合（エ）の内容を示す図。

【図１４】本発明の実施の形態における例題を分解して
作成された部分集合（オ）の内容を示す図。

【図１５】本発明の実施の形態における例題を分解して
作成された部分集合（Ｐ）の内容を示す図。

【図１６】本発明の実施の形態における例題を分解して
作成された部分集合（Ｑ）の内容を示す図。

【図１７】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図１８】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図１９】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図２０】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図２１】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図２２】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図２３】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図２４】本発明の実施の形態における例題を分解して
作成された部分集合から解を得る途中過程において、各
集合の内容を示す図。

【図２５】本発明の実施の形態における例題の他の場合
について、集合の内容を示す図。

【図２６】本発明の実施の形態における例題の他の場合
について、集合の内容を示す図。

【図２７】本発明の実施の形態における例題の他の場合
について、集合の内容を示す図。

【図２８】本発明の他の実施の形態について、構成を示
す概念図。

【図２９】本発明の他の実施の形態について、構成を示
す概念図。

【符号の説明】

１，８１，９１…代替案集合生成部 ２，８２，９２…解計算部 ３〜７，１１〜１５…経路 ８…解計算パターン記憶部 ９…結果記憶部 １０…解出力部 Ｆ，Ｇ，Ｈ…集合 Ａ，Ｂ，Ｃ，Ｄ…部分 ａ１〜ｄ６…代替案 １６…可到達値集合計算部 １７…値完全化部 １８…解発生部 ＳＴＥＰ…手順の各ステップ

Claims (6)

【特許請求の範囲】
1. 【請求項１】 それぞれ複数の代替案を持つ部分を複数
   有し、部分の代替案間に組み合わせに制約が存在する問
   題の解を計算する制約充足問題の解決装置において、 与えられた問題を、各部分が最大２個の代替案を含む部
   分集合に分解する手段と、 分解された部分集合ごとに、部分の代替案間の制約を満
   足する代替案の組み合わせを分析する手段と、 を有することを特徴とする制約充足問題の解決装置。
2. 【請求項２】 前記解を計算する手段は、 部分集合から、前記制約に合致する代替案の組み合わせ
   を表す可到達値集合を計算する手段と、 計算された可到達値集合を完全化する手段と、 完全化された可到達値集合から解を計算する手段と、 を有することを特徴とする請求項１記載の制約充足問題
   の解決装置。
3. 【請求項３】 前記分解する手段又は前記計算する手段
   のうち少なくとも一方を複数設けたことを特徴とする請
   求項１又は２記載の制約充足問題の解決装置。
4. 【請求項４】 それぞれ複数の代替案を持つ部分を複数
   有し、部分の代替案間に組み合わせに制約が存在する問
   題の解を計算する制約充足問題の解決方法において、 与えられた問題を、各部分が最大２個の代替案を含む部
   分集合に分解するステップと、 分解された部分集合ごとに、部分の代替案間の制約を満
   足する代替案の組み合わせを分析するステップと、 を含むことを特徴とする制約充足問題の解決方法。
5. 【請求項５】 複数の部分から構成され、それぞれの部
   分が複数の代替案を有し、かつ前記各部分の代替案の間
   の組み合わせに制約が存在するシステムを構築する装置
   において、 前記システムの各部分を、各部分が最大２個の代替案を
   含む部分集合に分解する手段と、 分解された部分集合ごとに、部分の代替案間の制約を満
   足する代替案の組み合わせを計算することにより、前記
   制約を満足するシステムを構築することを特徴とするシ
   ステム構築装置。
6. 【請求項６】 複数の部分から構成され、それぞれの部
   分が複数の代替案を有し、かつ前記各部分の代替案の間
   の組み合わせに制約が存在するシステムを構築する方法
   において、 前記システムの各部分を、各部分が最大２個の代替案を
   含む部分集合に分解し、 分解された部分集合ごとに、部分の代替案間の制約を満
   足する代替案の組み合わせを計算することにより、前記
   制約を満足するシステムを構築することを特徴とするシ
   ステム構築方法。