JPH08249187A - 探索装置 - Google Patents

Abstract

(57)【要約】 【目的】 探索に関する各種の方針を、対象問題の内容
に応じて柔軟に変更できるようにし、変数の種類に応じ
て動的に変更できるようにする。 【構成】 設定点毎探索処理部３は、以下の〜の処
理により、変数格納部５に格納されている変数への制約
条件群（対象問題における制約条件群）を満足する値の
設定を試みる探索処理を行う。 状況スタック格納部６内の状況スタックへの設定点
（設定点格納部８内の設定点リスト中の設定点）の設定
および削除を行って探索処理を進める。 関数格納部７内の値設定関数，設定点選択関数およ
び設定点追加関数と設定点内の各属性値とに基づき、探
索に関する各種の方針を決定する。 条件検査部９を用いて、条件格納部４内の制約条件
群に関する検査を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、制約条件群を満足する
ように変数の値を設定する処理により深さ優先探索（縦
型探索）を行う探索装置に関し、特に異なる定義の値域
を持つ変数が混在しうる変数群（値域が上限域と下限域
とで与えられるような連続の値域を持つ変数や離散値の
有限集合で与えられる変数や離散値の無限集合で与えら
れる変数等が混在しうる変数群）を持つ問題に対して制
約条件群を満足するように変数の値を設定する処理を行
う探索装置に関する。

【０００２】

【従来の技術】深さ優先探索では、変数群と変数の値域
と満足すべき制約条件群とが入力として与えられて、次
のような処理が行われる。 各変数に対して値を設定して、制約条件群が満足さ
れているか否かを検査する。 制約条件群が満足されていない場合には、値の次候
補を変数に設定して再度検査を行う。 候補値を全て試したが制約条件群が満足されない場
合には、以前に値の設定が行われた変数にさかのぼって
値の次候補を試す。

【０００３】深さ優先探索は、他の探索手法に比べて必
要となるメモリ量が比較的少なくてよいため、問題が大
きくなりがちな実用の場でしばしば用いられる。

【０００４】なお、深さ優先探索については、「人工知
能，Ｐ．Ｈ．ウィンストン（Ｗｉｎｓｔｏｎ）著，長尾
真・白井良明訳，培風館，１９８０年９月１０日初版発
行」に詳しい。

【０００５】図１０は、このような深さ優先探索を行う
従来の探索装置の一例の構成を示すブロック図である。
この探索装置は、制御部１００２を介して中央処理装置
１００１に接続されており、変数毎探索処理部１００３
と、条件格納部１００４と、変数格納部１００５と、状
況スタック格納部１００６と、条件検査部１００７とを
含んで構成されている。

【０００６】次に、この探索装置の動作について説明す
る。ここでは、探索対象の問題（対象問題）として、以
下の例題１が与えられた場合を考える。

【０００７】例題１：「各々が｛１ ３ ５｝の値域
（離散値の有限集合で与えられる値域）を持つ変数Ａ，
ＢおよびＣが存在し、制約条件群として条件「Ａ＜５」
（条件とする），条件「Ａ＋Ｂ＞７」（条件とす
る）および条件「Ｃ＞２」（条件とする）が定義され
ている場合に、変数Ａ，ＢおよびＣの値を求める問
題。」

【０００８】変数格納部１００５には、変数名と個々の
変数の値域の定義とからなる変数情報が格納される。例
題１に関しては、｛１ ３ ５｝の値域を持つ変数Ａ，
ＢおよびＣの変数名（Ａ，ＢおよびＣ）と値域の定義
（｛１ ３ ５｝）とが変数格納部１００５に格納され
る。

【０００９】条件格納部１００４には、制約条件群が格
納される。例題１に関しては、上述の条件〜が条件
格納部１００４に格納される。

【００１０】状況スタック格納部１００６には、状況ス
タックが格納される。状況スタックは、探索処理の過程
で探索ツリーをたどる際の分岐の状況を処理済みの変数
の履歴（探索履歴）として管理する。

【００１１】条件検査部１００７は、変数を入力として
受け取り、条件格納部１００４に格納された制約条件群
（ここでは、条件〜）から入力変数（入力した変
数）に関係する制約条件群だけを選び出し、入力変数に
設定されている値がそれらの制約条件群を満足している
か否かを調べる。例題１に関して、変数Ａに３が設定さ
れており他の変数（変数ＢおよびＣ）に値が設定されて
いない場合には、変数Ａに関係する制約条件である条件
と条件とを取り出し、現時点の値設定状況で調べる
ことが可能な条件だけを検査する。この場合に、条件
は満足されているため、条件検査部１００７は「制約
条件を満足している」と判定する。

【００１２】変数毎探索処理部１００３は、以下のよう
な処理を行う（以下に、変数毎探索処理部１００３の詳
細な処理フローを図１１の流れ図を用いて説明する）。

【００１３】変数群への値設定の要求（探索処理の実行
の要求）が中央処理装置１００１から制御部１００２を
介して伝達されると、まず、終了条件判定ステップ１１
０１を起動する。終了条件判定ステップ１１０１では、
変数格納部１００５に格納された全ての変数に値（制約
条件群を満足する値）が設定されているか否かを検査す
る。１回目の終了条件判定ステップ１１０１の起動時に
は、値が設定された変数が１つも存在していないので、
終了条件判定ステップ１１０１の検査結果は「失敗」と
なる。

【００１４】なお、検査／判定における命題（終了条件
判定ステップ１１０１では「全ての変数に値が設定され
ている」という命題）に対する答が「偽」である場合に
は、当該検査／判定における検査／判定結果（以下、単
に検査結果という）が「失敗」であると表現する（同様
に、当該命題に対する答が「真」である場合には、当該
検査結果が「成功」であると表現する）。

【００１５】終了条件判定ステップ１１０１の検査結果
が「失敗」である場合には、変数選択ステップ１１０２
を起動する。変数選択ステップ１１０２では、「変数格
納部１００５に格納された変数であり、まだ値が設定さ
れていない変数」を、予め与えられる基準に従って選択
する。例えば「アルファベットの早い順に選択する」と
いう基準が与えられているならば、例題１に関しては最
初に変数Ａを選択する。

【００１６】次に、状況スタックプッシュステップ１１
０３を起動する。状況スタックプッシュステップ１１０
３では、直前の変数選択ステップ１１０２で選択した変
数を状況スタック格納部１００６に格納された状況スタ
ックの一番上（最上部）に積む。例題１に関しては、１
回目の状況スタックプッシュステップ１１０３の起動時
には、空状態の状況スタックに変数Ａを積む。

【００１７】次に、変数初期値バインドステップ１１０
４を起動する。変数初期値バインドステップ１１０４で
は、直前の変数選択ステップ１１０２で選択した変数
に、予め与えられる基準に従って、初期値を与える。例
えば「値域の最小値を用いる」という基準が与えられて
いるならば、例題１に関しては、１回目の変数初期値バ
インドステップ１１０４の起動時には、変数Ａの初期値
として１を設定する。

【００１８】次に、状況スタック値書込みステップ１１
０５を起動する。状況スタック値書込みステップ１１０
５では、状況スタックの最上部に積まれた変数に付随す
る情報として変数の現在値を状況スタックに書き込む。
例題１に関しては、１回目の状況スタック値書込みステ
ップ１１０５の起動時には、状況スタックに積まれた変
数Ａに付随する情報として１を格納する。

【００１９】次に、制約検査ステップ１１０６を起動す
る。制約検査ステップ１１０６では、条件検査部１００
７を用いて、制約条件群が満たされているか否かを検査
する。この時点では、変数Ａに１が設定されており、他
の変数には値が設定されていない（条件検査部１００７
の入力変数がＡのみである場合に該当する）ので、変数
Ａに関係する制約条件である条件と条件とが取り出
され、現時点の値設定状況で調べることが可能な条件
だけが検査され、条件は満たされているので、制約検
査ステップ１１０６の検査結果は「成功」となる。

【００２０】制約検査ステップ１１０６の検査結果が
「成功」である場合には、終了条件判定ステップ１１０
１に戻って処理を続け、残りの変数への値の設定を行
う。

【００２１】制約検査ステップ１１０６の検査結果が
「失敗」である場合には、値調整ステップ１１０７を起
動する。値調整ステップ１１０７では、予め与えられる
基準に従って、状況スタックの最上部に格納された変数
に設定されている値を変更する処理を行う（代替値の計
算を行う）。例題１に関して、「値域に指定された要素
（値）を左端から順に候補とする」という基準が与えら
れているならば、現在値が３であれば次には代替値とし
て５を計算（選択）する。

【００２２】次に、値検査ステップ１１０８を起動す
る。値検査ステップ１１０８では、直前に起動された値
調整ステップ１１０７で代替値の計算が可能であったか
否かを検査する。例題１に関して、「値域に指定された
要素を左端から順に候補とする」という基準が与えられ
ており変数Ｂに５が設定されている状態で値調整ステッ
プ１１０７が起動された場合には、次に選択すべき値が
存在しないため、値検査ステップ１１０８の検査結果は
「失敗」となる。

【００２３】値検査ステップ１１０８の検査結果が「成
功」である場合には、変数値設定ステップ１１０９を起
動する。変数値設定ステップ１１０９では、値調整ステ
ップ１１０７で新規に計算された値（代替値として選択
された値）を変数（状況スタックの最上部に格納された
変数）に設定する。例題１に対する探索処理において、
変数Ａに設定されていた値の１の代替値として３を選択
したならば、変数Ａに３を設定する。

【００２４】変数値設定ステップ１１０９の処理が終了
すると、処理の流れを状況スタック値書込みステップ１
１０５に戻し、新しく設定された値を現在値として状況
スタック値書込みステップ１１０５以降の一連の処理を
行う。

【００２５】値検査ステップ１１０８の検査結果が「失
敗」である場合には、変数値解除ステップ１１１０を起
動する。変数値解除ステップ１１１０では、変数（状況
スタックの最上部の変数）を値未設定の状態に戻す。例
題１に対する探索処理において、変数Ａに１が設定され
ており変数Ｂに５が設定されていたとすると、変数Ｂに
５が設定されている状態で値調整ステップ１１０７を起
動した場合には、次に選択すべき値が存在しないため、
値検査ステップ１１０８の検査結果は「失敗」となり、
変数Ｂを値未設定の状態に戻す。

【００２６】変数値解除ステップ１１１０の処理が終了
すると、次に状況スタックポップステップ１１１１を起
動する。状況スタックポップステップ１１１１では、状
況スタックの最上部に積まれた変数を削除する。この場
合（変数値解除ステップ１１１０で変数Ｂを未設定の状
態に戻した場合）には、変数Ｂを削除する。

【００２７】状況スタックポップステップ１１１１の処
理が終了すると、次にスタック空検査ステップ１１１２
を起動する。スタック空検査ステップ１１１２では、状
況スタックが空か否かを検査する。なお、この検査時に
「状況スタックが空」ということは、どのような値設定
を行っても、制約条件群を満足するような値の設定を全
ての変数に対して行うことが不可能であることを示して
いる。

【００２８】スタック空検査ステップ１１１２の検査結
果が「成功」である場合（状況スタックが空であった場
合）には、異常終了ステップ１１１３を起動する。異常
終了ステップ１１１３では、当該探索処理の異常終了の
旨を制御部１００２を介して中央処理装置１００１に返
却する。

【００２９】スタック空検査ステップ１１１２の検査結
果が「失敗」である場合（状況スタックが空でない場
合）には、バックトラックが可能な探索ツリーの分岐点
がまだ残っているということなので、その分岐点の他の
枝の探索を行う。すなわち、値調整ステップ１１０７か
ら先の処理を繰り返す。例題１に対する探索処理の場
合、先に述べたように変数Ｂを状況スタックから削除し
た後でも、変数Ａが状況スタックの中に残っているの
で、変数Ａについてまだ試していない値群（３および
５）に関する探索を継続して行う。

【００３０】終了条件判定ステップ１１０１の検査結果
が「成功」である場合（全変数に制約条件を違反しない
値が設定できた場合）には、正常終了ステップ１１１４
を起動する。正常終了ステップ１１１４では、当該探索
処理の正常終了の旨とその際の変数群の各変数名および
各値とを制御部１００２を介して中央処理装置１００１
に返却する。

【００３１】図１２は、例題１に対して従来の探索装置
を用いて探索処理を行う場合の探索ツリーの展開の概念
を示す図である。

【００３２】１２０１行〜１２１０行に示すような順序
で探索が行われ、最終的に変数Ａが１、変数Ｂが５、変
数Ｃが３という解（制約条件群を満たす値）にたどり着
く。すなわち、以下の〜に示す順序で探索が行われ
る。

【００３３】 １２０１行で、変数Ａに１が設定され
て、条件（「Ａ＜５」）が満たされる。

【００３４】 １２０２行〜１２０４行で、変数Ｂに
対して｛１ ３ ５｝の値が試されるが、全ての値につ
いて条件（「Ａ＋Ｂ＞７」）が満たされない。

【００３５】 そこで、１２０５行で、変数Ａにバッ
クトラックし、変数Ａに３が設定される。

【００３６】 １２０６行〜１２０８行で、変数Ｂに
対して｛１ ３ ５｝の値が試され、最後の値５におい
て条件が満たされる。

【００３７】 次に、変数Ｃへの値の設定が行われ、
１２０９行〜１２１０行で、変数Ｃに対して｛１ ３｝
の値が試され、値３で条件（「Ｃ＞２」）が満たされ
て、この問題（例題１）の解が求められる。

【００３８】図１５は、例題１に対して従来の探索装置
を用いて探索処理を行う際の状況スタック格納部１００
６内の状況スタックの推移の概念を示す図である。

【００３９】「（１）変数Ａの選択。（２）変数Ａへの
１の代入。（３）変数Ｂの選択。（４）変数Ｂへの１の
代入。（５）変数Ｂの値の解除。（６）変数Ｂへの３の
代入。（７）変数Ｂの値の解除。（８）変数Ｂへの５の
代入。（９）変数Ｂの値の解除。（１０）変数Ｂの選択
の解除（変数Ｂの削除）。（１１）変数Ａの値の解除。
（１２）変数Ａへの３の代入。（１３）変数Ｂの選択。
（１４）変数Ｂへの１の代入。（１５）変数Ｂの値の解
除。（１６）変数Ｂへの３の代入。（１７）変数Ｂの値
の解除。（１８）変数Ｂへの５の代入。（１９）変数Ｃ
の選択。（２０）変数Ｃへの１の代入。（２１）変数Ｃ
の値の解除。（１６）変数Ｃへの３の代入。」という一
連の流れで探索処理が行われるため、状況スタックの内
容は１５００〜１５２２に示すように推移する。

【００４０】初期状態では、１５００に示すように、状
況スタックは空である。上述の（１）の処理が行われる
と、１５０１に示すように変数Ａが状況スタックに格納
される。（２）の処理が行われると、１５０２に示すよ
うに変数Ａに対する値の１が追加される。（３）の処理
が行われると、１５０３に示すように変数Ｂが状況スタ
ックの一番上に積まれる。以下同様にして、対象問題
（例題１）に対する解が求められた状態である１５２２
に至るまで処理が継続される。

【００４１】以上の説明で明らかなように、従来の探索
装置では、変数に設定した値が制約違反（制約条件を満
足しないこと）を起こした場合に次にどのような値を変
数に設定してみるかという方針や、次にどの変数にバッ
クトラックするかという方針等は、予め与えておく基準
によって定められており、対象問題毎に柔軟に、また変
数毎に動的に変更することができなかった。

【００４２】

【発明が解決しようとする課題】上述した従来の探索装
置では、探索に関する各種の方針は予め与えておく基準
によって定められており、対象問題の内容に応じて柔軟
に変更することはできなかった。しかし、対象問題の性
質によっては、次候補生成の方針等をその対象問題の内
容に適合するように変更できるならば高速に良い解にた
どり着ける。

【００４３】ここで、別の対象問題として以下の例題２
を考える。

【００４４】例題２：「１から１０００までの自然数を
値域に持つ変数ＡおよびＢを扱い、制約条件群として
「Ｂ＜５０１」（条件とする）および「Ａ＋Ｂ＞１４
９９」（条件とする）が与えられた場合に、変数Ａお
よびＢの値を求める問題。」

【００４５】なお、本探索装置において、次にどの変数
にバックトラックするかを指定する変数選択方針として
「アルファベット順」という方針が予め定められてお
り、変数に設定した値が制約違反を起こした時に次にど
のような値を設定してみるかを指定する代替値計算方針
として「値域の最小の側からの順」という方針が予め定
められていたとする。

【００４６】この場合には、Ａ＝１０００およびＢ＝５
００という解にたどり着くが、探索処理の過程で多量の
バックトラックが必要となる。

【００４７】実際の問題を扱う場合には、対象問題にお
ける変数に対する予備知識として、「変数Ａは大きい」
や「変数Ｂは１００の倍数である」等の付加情報がある
場合が多い。付加情報を利用して変数毎の代替値計算方
針や変数選択方針等を柔軟に変更することができれば、
高速に解にたどり着くことができると思われる。

【００４８】すなわち、上記の例題２において、上記の
付加情報に基づいて、「変数Ａの場合は初期値から１ず
つ値を変更し、変数Ｂの場合は初期値から１００ずつ変
更する」や「変数Ａは最大値から値を減少させ、変数Ｂ
は最小値から値を増加させていく」という変数毎に異な
る代替値計算方針を採用するならば、高速に解にたどり
着くような探索処理の実現が可能となる。

【００４９】また、値域が上限値と下限値とで与えられ
るような連続の値域を持つ変数や離散値の無限集合で与
えられる変数等の異なる定義の値域を持つ変数が混在す
る変数群を持つ問題に対する探索の場合には、探索に関
する代替値計算方針は変数毎に動的に変更することが望
ましい。例えば、製造業の工場で製品の生産のために必
要となる各作業の設備利用開始時刻を決める生産スケジ
ューリング問題に対する探索処理の場合には、ある設備
に対する変数では１日に１種類の製品しか処理できない
ために１日単位で値を変更すれば良いのに対して、別の
設備に対する変数では１時間単位で作業を入れ換えられ
るために１時間単位で値を変更する必要が生じる。

【００５０】さらに、上述の生産スケジューリング問題
等においては、作業の全体の流れのボトルネックと予想
される設備を利用する作業に関連する変数への値の設定
は、「ボトルネックと予想される設備を利用する」とい
う当該変数の属性を考慮して、探索処理の早い段階で行
った方が探索処理の効率が良くなる。

【００５１】以上のように、探索処理においては、対象
問題の内容を考慮して、また対象問題における変数の各
種の属性を考慮して、探索に関する各種の方針を柔軟か
つ動的に決定することが望ましいと考えられる。しかし
ながら、従来の探索装置では、そのような考慮がなされ
ていなかった。

【００５２】本発明の目的は、上述の点に鑑み、対象問
題の内容に応じて予め（探索処理に先立って）定義でき
る３種類の関数（値設定関数，設定点追加関数および設
定点選択関数）を設け、「変数名」および「現在値」以
外の属性を持ちうる設定点というデータ構造（従来の探
索装置における変数のデータ構造は「変数名」および
「現在値」という属性のみを持つデータ構造であるとい
える）を導入することにより、探索に関する各種の方針
を、対象問題の内容に応じて柔軟に変更でき、変数の種
類に応じて動的に変更することができる探索装置を提供
することにある。これにより、対象問題に対する解を許
容時間以内に導くことができるシステム（探索装置を含
むシステム）を構築することができる。

【００５３】

【課題を解決するための手段】本発明の探索装置は、異
なる定義の値域を持つ変数が混在しうる変数群を持つ対
象問題に対する探索処理を行い、与えられた制約条件群
を満足するように変数の値の設定を行う探索装置におい
て、「変数名」と「現在値」とを属性として含むデータ
構造であり、探索ツリーの分岐点の候補を表すデータ構
造であり、「変数名」および「現在値」以外の属性群と
して対象問題に適合する属性群を有するデータ構造であ
る設定点の集合である設定点リストを格納する設定点格
納部と、設定点を入力として受け取り入力設定点の属性
値を基に入力設定点に係る変数に対して次に試すべき値
を計算する関数である値設定関数，前記設定点格納部内
の設定点リストから次に処理べき設定点を選択する関数
である設定点選択関数，および設定点を入力として受け
取り入力設定点が表す探索ツリーの分岐点より一段先の
分岐点の候補群を求めて当該候補群である設定点群を返
却する関数である設定点追加関数の３種類の関数であ
り、対象問題の内容に適合するように予め定義されてい
る関数群を格納する関数格納部と、対象問題における制
約条件群を格納する条件格納部と、対象問題における変
数を格納する変数格納部と、探索ツリーを探索する際の
分岐の状況を「処理した設定点の履歴」として管理する
状況スタック格納部と、変数を入力として受け取り、前
記条件格納部に格納された制約条件群から入力変数に関
係する制約条件群を選択し、選択した制約条件群を入力
変数に設定されている値が満足しているか否か検査する
条件検査部と、前記状況スタック格納部内の状況スタッ
クへの設定点の設定および削除を行って探索処理を進
め、探索に関する各種の方針を前記関数格納部内の関数
群および設定点内の各属性値に基づいて決定し、前記条
件格納部内の制約条件群に関する検査を前記条件検査部
を用いて行い、前記変数格納部に格納されている変数へ
の制約条件群を満足する値の設定を試みる探索処理を行
う設定点毎探索処理部とを有する。

【００５４】また、本発明の探索装置は、上述の探索装
置に対して、前記関数格納部内の設定点追加関数によっ
て設定点が追加される際の依存元の設定点および依存先
の設定点を示す情報を含む依存情報を格納する依存情報
格納部を加え、前記設定点毎探索処理部により行われる
全ての処理を行うとともに以下のおよびに示すよう
な依存情報に関する処理を行う第２設定点毎探索処理部
を前記設定点毎探索処理部の代わりに設けることによっ
ても実現できる。 前記関数格納部内の設定点追加関数によって設定点
が追加される際に前記依存情報格納部への依存情報の設
定を行う。 バックトラックを行う際に前記依存情報格納部内の
依存情報に基づいて当該バックトラックを行う。

【００５５】

【作用】本発明の探索装置では、異なる定義の値域を持
つ変数が混在しうる変数群を持つ対象問題に対する探索
処理を行い与えられた制約条件群を満足するように変数
の値の設定を行う探索装置において、設定点格納部が設
定点（「変数名」と「現在値」とを属性として含むデー
タ構造であり、探索ツリーの分岐点の候補を表すデータ
構造であり、「変数名」および「現在値」以外の属性群
として対象問題に適合する属性群を有するデータ構造）
の集合である設定点リストを格納し、関数格納部が値設
定関数（設定点を入力として受け取り入力設定点の属性
値を基に入力設定点に係る変数に対して次に試すべき値
を計算する関数），設定点選択関数（設定点格納部内の
設定点リストから次に処理べき設定点を選択する関数）
および設定点追加関数（設定点を入力として受け取り入
力設定点が表す探索ツリーの分岐点より一段先の分岐点
の候補群を求めて当該候補群である設定点群を返却する
関数）の３種類の関数であって対象問題の内容に適合す
るように予め定義されている関数群を格納し、条件格納
部が対象問題における制約条件群を格納し、変数格納部
が対象問題における変数を格納し、状況スタック格納部
が探索ツリーを探索する際の分岐の状況を「処理した設
定点の履歴」として管理し、条件検査部が変数を入力と
して受け取り条件格納部に格納された制約条件群から入
力変数に関係する制約条件群を選択し当該制約条件群を
入力変数に設定されている値が満足しているか否か検査
し、設定点毎探索処理部が以下の〜の処理によって
変数格納部に格納されている変数への制約条件群を満足
する値の設定を試みる探索処理を行う。 状況スタック格納部内の状況スタックへの設定点の
設定および削除を行って探索処理を進める。 探索に関する各種の方針を関数格納部内の関数群お
よび設定点内の各属性値に基づいて決定する。 条件格納部内の制約条件群に関する検査を条件検査
部を用いて行う。

【００５６】また、本発明の探索装置では、上述の探索
装置において、関数格納部内の設定点追加関数によって
設定点が追加される際の依存元の設定点および依存先の
設定点を示す情報を含む依存情報を格納する依存情報格
納部が設けられ、第２設定点毎探索処理部が設定点毎探
索処理部の処理の代わりに次の〜に示すような処理
を行うことも可能である。 設定点毎探索処理部により行われる全ての処理を行
う。 関数格納部内の設定点追加関数によって設定点が追
加される際に依存情報格納部への依存情報の設定を行
う。 バックトラックを行う際に依存情報格納部内の依存
情報に基づいて当該バックトラックを行う。

【００５７】

【実施例】次に、本発明について図面を参照して詳細に
説明する。

【００５８】図１は、本発明の探索装置の第１の実施例
（請求項１記載の発明に対応する実施例）の構成を示す
ブロック図である。

【００５９】本実施例の探索装置は、設定点毎探索処理
部３と、条件格納部４と、変数格納部５と、状況スタッ
ク格納部６と、関数格納部７と、設定点格納部８と、条
件検査部９とを含んで構成されている。なお、本実施例
の探索装置は、制御部２を介して、中央処理装置１と接
続されている。

【００６０】本実施例の探索装置は、従来の探索装置
（図１０参照）になかった関数格納部７と設定点格納部
８とを付加したことと、従来の探索装置の変数毎探索処
理部１００３に代えて設定点毎探索処理部３を設けたこ
ととを特徴とする。

【００６１】図２は、設定点格納部８に格納される設定
点のデータ構造の一例を示す図である。

【００６２】図３（ａ）〜（ｃ）は、関数格納部７に格
納される値設定関数，設定点選択関数および設定点追加
関数の記述例を示す図である。

【００６３】図４は、設定点毎探索処理部３の詳細な処
理フローを示す流れ図である。この処理は、設定点初期
入力ステップ４０１と、終了条件判定ステップ４０２
と、設定点選択ステップ４０３と、状況スタックプッシ
ュステップ４０４と、変数初期値バインドステップ４０
５と、状況スタック値書込みステップ４０６と、制約検
査ステップ４０７と、設定点追加ステップ４０８と、変
数検査ステップ４０９と、値調整ステップ４１０と、値
検査ステップ４１１と、変数値設定ステップ４１２と、
変数値解除ステップ４１３と、状況スタックポップステ
ップ４１４と、スタック空検査ステップ４１５と、第２
異常終了ステップ４１６と、終了検査ステップ４１７
と、正常終了ステップ４１８と、第１異常終了ステップ
４１９とからなる。

【００６４】図５，図６，図１３および図１６は、本実
施例の探索装置の動作を説明するための図である。

【００６５】次に、このように構成された本実施例の探
索装置の動作について説明する。ここでは、探索対象の
問題（対象問題）として、製造業の工場で製品の生産の
ために必要となる各作業の設備利用開始時刻を決める生
産スケジューリング問題の１つである以下の例題３が与
えられた場合を考える。

【００６６】例題３：「９：００（９時０分を意味す
る。以下同様）から１８：００までの間の時刻が値域で
ある変数ＡおよびＧがあり、変数Ａは作業１を設備１で
行う際の作業開始時刻とし、変数Ｇは作業２を設備２で
行う際の作業開始時刻とする場合に、変数ＡおよびＧの
値を求める問題。なお、制約条件群として次の〜の
条件が定義されているものとする。」 設備１は毎時ちょうど（毎時０分）からしか利用を
開始することができない。 設備２は１０分間隔で作業を開始できる。 作業２は作業１が終了してから３０分以上、５０分
以内に開始しなければならない（しかし、なるべく、作
業１との時間間隔をあけた方が望ましい）。 １２：００から１３：００までの間（昼休みの間）
は、設備（設備１および２）は停止する。したがって、
昼休みにかかってしまうように作業（作業１および２）
をスケジュールしてはならない。 作業１は３時間を要し、作業２は１時間２０分を要
する。 作業は９：００から１８：００までの間に行う（設
備の稼働可能時間は９：００から１８：００までの間で
ある）。

【００６７】変数格納部５には、値として時刻が設定可
能な変数ＡおよびＧ（例題３における変数）が格納され
る。

【００６８】条件格納部４には、上述の制約条件群が格
納される。

【００６９】設定点格納部８には、設定点の集合である
設定点リストが格納される。設定点は、「変数名」と
「現在値」とを属性として含むデータ構造であり、探索
ツリーの分岐点の候補を表すデータ構造であり、「変数
名」および「現在値」以外の属性群として対象問題に適
合する属性群を有するデータ構造である。

【００７０】ここでは、例えば、図２に示すようなデー
タ構造の設定点が取り扱われる。

【００７１】図２中の２０１行は、属性「変数名」の定
義であり、当該設定点に係る変数の変数名を格納する。
図２の設定点の場合には、変数名「Ａ」が設定されてい
る。

【００７２】２０２行は、属性「初期値」の定義であ
り、当該変数への初期値を格納する。この場合には、時
刻「９：００」が設定されている。

【００７３】２０３行は、属性「探索有無」の定義であ
り、探索において当該変数の値が変更可能か否かを指定
する。この場合には、「有」、すなわち他の値に変更し
て探索を試みることが可能である旨が指定されている。

【００７４】２０４行は、属性「探索方針」の定義であ
り、属性「探索有無」において「有」と指定された場合
の探索方針を指定する。この場合には、「→」（この矢
印の示す探索方針の内容については後述する）が指定さ
れている。

【００７５】２０５行は、属性「変更可能域」の定義で
あり、当該変数の値の有効範囲を指定する。この場合に
は、「［９：００．．１８：００］（９：００から１
８：００まで）」が設定されている。

【００７６】２０６行は、属性「値設定関数名」の定義
であり、当該変数の値（現在値）の代替値を計算する関
数（値設定関数）の関数名を格納する。この場合には、
関数名「ｓｅｔｔｅｉ−ｆｕｎｃ１」が設定されてい
る。

【００７７】２０７行は、属性「現在値」の定義であ
り、設定点毎探索処理部３の処理における途中の演算結
果（現在の値）を格納する。この場合には、まだ値が未
設定である。

【００７８】なお、設定点のデータ構造は、図２中の２
０１行〜２０７行に示すような７つの属性（「変数
名」，「初期値」，「探索有無」，「探索方針」，「変
更可能域」，「値設定関数名」および「現在値」）から
なるデータ構造に限定されるものではない。属性「変数
名」および属性「現在値」以外の属性としては、例え
ば、変数初期値バインドステップ４０５，変数検査ステ
ップ４０９，値調整ステップ４１０および値検査ステッ
プ４１１の処理内容と、値設定関数，設定点選択関数お
よび設定点追加関数の構成とに応じて、必要な任意の属
性の定義を追加することが可能である。

【００７９】関数格納部７には、対象問題に適合するよ
うに予め（当該対象問題に対する探索処理に先立って）
定義されている３種類の関数（値設定関数，設定点選択
関数および設定点追加関数）が格納される。ここでは、
例えば、図３（ａ）〜（ｃ）に示すような記述（この記
述はＬｉｓｐによるものである）を有する関数が格納さ
れているものとする。

【００８０】図３（ａ）中の３０１行〜３０９行は、値
設定関数の記述例である。

【００８１】値設定関数は、設定点を入力として受け取
り、入力設定点（入力した設定点）の属性値を基に入力
設定点に係る変数に対して次に試すべき値を計算する関
数である。

【００８２】３０１行では、関数名としてｓｅｔｔｅｉ
−ｆｕｎｃ１が定義され、入力として設定点ｓｅｔｔｅ
ｉ−ｄａｔ１が与えられている。

【００８３】３０２行〜３０４行では、設定点ｓｅｔｔ
ｅｉ−ｄａｔ１の属性「変数名」の頭文字に従って時間
刻みが決定されており、頭文字がＡからＦの場合には時
間刻みが１時間（６０分）とされ、頭文字がＧからＺの
場合には時間刻みが１０分とされる。

【００８４】３０５行〜３０８行では、設定点ｓｅｔｔ
ｅｉ−ｄａｔ１の属性「探索方針」に定義されている探
索方針が「→」の場合には当該設定点の属性「現在値」
に設定されている値が時間刻み分だけ増加され、探索方
針が「←」の場合にはその値が時間刻み分だけ減少さ
れ、その計算結果が返却される。

【００８５】３０９行では、設定点ｓｅｔｔｅｉ−ｄａ
ｔ１の属性「探索方針」に「←」および「→」以外が格
納されていた場合の計算が行われる。この場合には、代
替値を計算できないため、ＦＡＬＳＥが返却される。

【００８６】例題３に対する探索において、「変数名：
Ａ，初期値：９：００，探索有無：有，探索方針：→，
変更可能域：［９：００．．１８：００］，値設定関数
名：ｓｅｔｔｅｉ−ｆｕｎｃ１，および現在値：９：０
０」という７つの属性値を持った設定点が入力として与
えられたならば、関数ｓｅｔｔｅｉ−ｆｕｎｃ１（関数
名がｓｅｔｔｅｉ−ｆｕｎｃ１の関数。以下同様の表記
方法を用いる）は１０：００という時刻を返却する。

【００８７】値設定関数は、図３（ａ）に示すような時
刻計算を行う関数のみに限定されるものではなく、入力
として設定点を与えられて、出力として代替値または
「計算が不可能であった旨を示す情報（例えば、ＦＡＬ
ＳＥ）」を返却する関数であればどのような内容であっ
てもよい。

【００８８】例えば、関数ｓｅｔｔｅｉ−ｆｕｎｃ１で
は、設定点に属性「探索方針」が定義され、その属性に
格納された矢印の方向（「←」および「→」の別）によ
って時間刻みの増減の方向が決定されているが、設定点
に属性「変数名」および「現在値」以外の属性を追加せ
ずに時間刻みの増減の方向および刻み値を固定とするよ
うな定義や、設定点以外の情報に基づいて増減の方向お
よび刻み値を判断するような定義を持っていてもよい。

【００８９】図３（ｂ）中の３１０行〜３１１行は、設
定点選択関数の記述例である。

【００９０】設定点選択関数は、設定点格納部８内の設
定点リストから次に処理すべき設定点（ここでは、先頭
にある設定点）を選択する関数である。

【００９１】３１０行では、関数名としてｓｅｎｔａｋ
ｕ−ｆｕｎｃ１が定義され、入力として設定点リストｓ
ｅｔｔｅｉ−ｌｉｓｔ１が与えられる。

【００９２】３１１行では、その設定点リストの先頭要
素（先頭の設定点）が選択され返却される。

【００９３】図３（ｂ）に示す設定点選択関数では、設
定点格納部８に格納される設定点リストに対して、ラス
トイン・ファーストアウトの動作が実現される。ラスト
イン・ファーストアウトとは、最後に追加された要素が
最初に取り出されるようなリストの処理順序手法であ
る。

【００９４】設定点選択関数は、図３（ｂ）に示すよう
な単純な処理を行う関数に限定されるものではなく、入
力として設定点リストを与えられて、出力として当該設
定点リストの１要素（１つの設定点）または「選択可能
な設定点が存在しなかった場合にその旨を示す情報（例
えば、ＦＡＬＳＥ）」を返却する関数であればどのよう
な内容であってもよい。

【００９５】図３（ｃ）中の３１２行〜３３２行は、設
定点追加関数の記述例である。

【００９６】設定点追加関数は、設定点を入力として受
け取り、入力設定点が表す探索ツリーの分岐点より一段
先の分岐点の候補群を求めて当該候補群である設定点群
を返却する関数である。

【００９７】３１２行では、関数名としてａｄｄ−ｆｕ
ｎｃ１が定義され、入力として設定点ｓｅｔｔｅｉ１が
与えられる。

【００９８】３１３行では、設定点ｓｅｔｔｅｉ１の属
性「変数名」の値を引数として次の変数を選択する関数
ｇｅｔ−ｎｅｘｔ−ｓｙｍｂｏｌが起動され、変数名が
求められ、その変数名がｎｅｘｔ−ｓｙｍｂｏｌという
変数に束縛される。関数ｇｅｔ−ｎｅｘｔ−ｓｙｍｂｏ
ｌは、例題３に対する探索においては、変数格納部５に
格納された変数群からアルファベット順に変数名を抽出
して、最後の変数に達した場合にはＮＩＬ（偽）を返却
する関数である。

【００９９】３１４行〜３３１行は、ｎｅｘｔ−ｓｙｍ
ｂｏｌに束縛された値がＮＩＬ以外であった場合に動作
する。

【０１００】３１５行では、関数ｇｅｎｅｒａｔｅ−ｎ
ｅｗ−ｓｅｔｔｅｉ−ｔｅｎが用いられて新しい設定点
が生成され、その設定点が変数ｎｅｗ−ｓｅｔｔｅｉに
束縛される。

【０１０１】３１６行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉの属性「変数名」に、３１３行においてｎｅｘｔ−ｓ
ｙｍｂｏｌに束縛された値が格納される。

【０１０２】３１７行〜３１９行では、設定点ｎｅｗ−
ｓｅｔｔｅｉの属性「変更可能域」に、本設定点追加関
数への入力設定点であるｓｅｔｔｅｉ１の属性「現在
値」の値（時刻）を基にして、作業と作業との間であけ
なければならない時間間隔を指定した値が格納される。

【０１０３】３２０行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉの属性「値設定関数名」に、関数名ｓｅｔｔｔｉ−ｆ
ｕｎｃ１が格納される。

【０１０４】３２１行〜３２２行では、設定点ｎｅｗ−
ｓｅｔｔｅｉの属性「初期値」に、本設定点追加関数へ
の入力設定点であるｓｅｔｔｅｉ１の属性「現在値」の
値（時刻）を基にして、作業と作業との間であけなけれ
ばならない時間間隔を指定した値が格納される。

【０１０５】３２３行〜３２８行は、ｎｅｘｔ−ｓｙｍ
ｂｏｌに束縛された変数名の頭文字がＡ〜Ｎの間であっ
た場合に動作する。

【０１０６】３２４行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉの属性「探索有無」に「有」が格納される。

【０１０７】３２５行〜３２６行は、ｎｅｘｔ−ｓｙｍ
ｂｏｌに束縛された変数名の頭文字がＡ〜Ｆの間であっ
た場合に動作する。

【０１０８】３２６行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉの属性「探索方針」に「→」が格納される。

【０１０９】３２７行〜３２８行は、ｎｅｘｔ−ｓｙｍ
ｂｏｌに束縛された変数名の頭文字がＧ〜Ｎの間であっ
た場合に動作する。

【０１１０】３２８行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉの属性「探索方針」に「←」が格納される。

【０１１１】３２９行〜３３０行は、ｎｅｘｔ−ｓｙｍ
ｂｏｌに束縛された変数名の頭文字がＯ〜Ｚの間であっ
た場合に動作する。

【０１１２】３３０行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉの属性「探索有無」に「無」が格納される。

【０１１３】３３１行では、設定点ｎｅｗ−ｓｅｔｔｅ
ｉを要素とする設定点リストが返却される。

【０１１４】３３２行は、変数ｎｅｘｔ−ｓｙｍｂｏｌ
に格納された値がＮＩＬであった場合に動作し、ＦＡＬ
ＳＥを返却する。

【０１１５】例題３に対する探索において、「変数名：
Ａ，初期値：９：００，探索有無：有，探索方針：→，
変更可能域：［９：００．．１８：００］，値設定関数
名：ｓｅｔｔｅｉ−ｆｕｎｃ１，および現在値：９：０
０」という７つの属性値を持った設定点が入力として与
えられたならば、関数ａｄｄ−ｆｕｎｃ１は「変数名：
Ｇ，初期値：１２：５０，探索有無：有，探索方針：
←，変更可能域：［１２：３０．．１２：５０］，値設
定関数名：ｓｅｔｔｅｉ−ｆｕｎｃ１，および現在値：
−」という７つの属性値を持った設定点を要素として持
つ設定点リストを返却する。

【０１１６】設定点追加関数は、図３（ｃ）に示すよう
な時刻処理を行う関数に限定されるものではなく、入力
として設定点を与えられて、出力として新規設定点を要
素とする設定点リストまたは「新規設定点が生成不可能
な場合にその旨を示す情報（例えば、ＦＡＬＳＥ）」を
返却する関数であればどのような内容であってもよい。

【０１１７】例えば、関数ａｄｄ−ｆｕｎｃ１には、変
数群からアルファベット順に変数名を抽出して次の変数
名を決める動作が含まれているが、予め定められる他の
優先順位に従って変数名を選択するような動作が含まれ
ていてもよい。また、関数ａｄｄ−ｆｕｎｃ１では、属
性「変数名」および「現在値」以外の属性群が定義され
ているが、これらの属性群は例題３における変数初期値
バインドステップ４０５，変数検査ステップ４０９，値
調整ステップ４１０および値検査ステップ４１１の処理
内容と値設定関数，設定点選択関数および設定点追加関
数の構成とに応じて必要な属性が追加定義されたもので
あり、これらの属性群に限定されるものではない。さら
に、入力設定点以外の情報として、例えばすでに処理し
た設定点群の履歴情報等を用いて計算することも可能で
ある。

【０１１８】設定点毎探索処理部３は、以上のような条
件格納部４，変数格納部５，関数格納部７および設定点
格納部８の存在（探索ツリーを探索する際の分岐の状況
を「処理した設定点の履歴」として管理するために状況
スタックを格納する状況スタック格納部６の存在も含
む）を前提として、条件検査部９を用いて、以下に示す
ような処理を行う（図４参照）。なお、以下の説明にお
いて、「変数の値の設定」とは、当該変数に係る設定点
の属性「現在値」への値の設定を意味する（後述する第
２の実施例に関する説明においても同様）。

【０１１９】まず、設定点初期入力ステップ４０１を起
動する。設定点初期入力ステップ４０１では、中央処理
装置１から制御部２を介して入力される設定点群を設定
点格納部８に格納する。例えば、例題３に対する探索の
過程で、図２に示すような設定点を入力する。

【０１２０】次に、終了条件判定ステップ４０２を起動
する。終了条件判定ステップ４０２では、全ての設定点
の処理が終了したか否かを調べる。処理済みの設定点は
必ず状況スタック格納部６内の状況スタック上に積まれ
ているため、変数格納部５に格納された変数群に係る設
定点群が全て状況スタックに積まれているならば、全て
の設定点の処理は終了しているといえる。したがって、
終了条件判定ステップ４０２では、状況スタック格納部
６内の状況スタックに変数格納部５に格納された変数群
に係る設定点群が全て積まれているか否かによって終了
条件判定を行っている。例えば、１回目の終了条件判定
ステップ４０２の起動時には、状況スタックに１つも設
定点が積まれていないので、終了条件は満たされずに処
理を継続する（終了条件判定ステップ４０２の検査結果
が「失敗」となる）。

【０１２１】次に、設定点選択ステップ４０３を起動す
る。設定点選択ステップ４０３では、関数格納部７に格
納された設定点選択関数を起動して、設定点格納部８に
格納された設定点リストから１つの設定点を選択する。
例題３に関する１回目の設定点選択ステップ４０３の起
動時には、変数Ａに係る設定点を選択する。この設定点
を、仮に「設定点１」と呼ぶものとする。

【０１２２】次に、状況スタックプッシュステップ４０
４を起動する。状況スタックプッシュステップ４０４で
は、直前の設定点選択ステップ４０３で選択した設定点
を状況スタック格納部６内の状況スタックに積む。

【０１２３】図５に、この時点（状況スタックプッシュ
ステップ４０４の１回目の起動時）における、状況スタ
ックプッシュステップ４０４の動作前の状況スタック
（状況スタック５０１）の状態と状況スタックプッシュ
ステップ４０４の動作後の状況スタック（状況スタック
５０２）の状態とを示す。

【０１２４】状況スタック５０１には、まだ、設定点が
１つも格納されていない。

【０１２５】状況スタック５０２には、設定点１が格納
されている。なお、続けて、別の設定点（設定点２とす
る）が状況スタックプッシュステップ４０４で処理され
た場合には、設定点１の上に設定点２が積まれる。

【０１２６】次に、変数初期値バインドステップ４０５
を起動する。変数初期値バインドステップ４０５では、
直前の設定点選択ステップ４０３で選択した設定点に係
る変数に対する初期値を求める。

【０１２７】例題３に対する探索においては、設定点に
は属性「初期値」が定義されており、設定点が生成され
る時点で属性「初期値」に値が与えられている。したが
って、設定点１に係る変数の値（設定点１内の属性「現
在値」）に対して、設定点内で定義された初期値（属性
「初期値」の値）を与える。例えば、図２に示すような
設定点に関しては、変数Ａの値として初期値「９：０
０」が求められることになる。

【０１２８】変数初期値バインドステップ４０５の処理
内容としては、上述の「設定点の属性「初期値」を利用
する」という処理内容に限定されるものではなく、以下
の〜等に示すようなバリエーションが考えられる。 中央処理装置１を介して初期値を計算する。 設定点以外のデータに基づいて初期値を計算する。 固定の初期値を持つ。

【０１２９】次に、状況スタック値書込みステップ４０
６を起動する。状況スタック値書込みステップ４０６で
は、状況スタック格納部６内の状況スタック中の最上部
の設定点の属性「現在値」に値をセットする（直前の変
数初期値バインドステップ４０５または変数値設定ステ
ップ４１２（後述参照）で求めた値をセットする）。

【０１３０】図６に、この時点（状況スタック値書込み
ステップ４０６の１回目の起動時）における、状況スタ
ック値書込みステップ４０６の動作前の状況スタック
（状況スタック６０１）の状態と状況スタック値書込み
ステップ４０６の動作後の状況スタック（状況スタック
６０２）の状態とを示す。

【０１３１】状況スタック６０１においては、設定点１
の属性「現在値」は未設定である。

【０１３２】状況スタック６０２においては、設定点１
の属性「現在値」に値「９：００」が格納されている。
再度、状況スタック値書込みステップ４０６が起動され
て設定点１が処理される場合には、属性「現在値」の値
が再び書き換えられる（この場合には、変数値設定ステ
ップ４１２で求められた値が書き込まれることにな
る）。

【０１３３】次に、制約検査ステップ４０７を起動す
る。制約検査ステップ４０７では、条件検査部９を用い
て、条件格納部４に格納された制約条件群の中で、今回
値を設定した変数（直前の変数初期値バインドステップ
４０５または後述する変数値設定ステップ４１２で値
（当該変数に係る設定点内の属性「現在値」の値）を設
定した変数）に関係する制約条件群のチェックを行う。
ここで、チェックした制約条件群が全て満たされている
場合、あるいは値が設定されていない変数が関係するた
めに制約条件をチェックできない場合には、制約検査ス
テップ４０７の検査結果は「成功」となる。なお、条件
検査部９は、変数を入力として受け取り、条件格納部に
格納された制約条件群から入力変数に関係する制約条件
群を選択し、選択した制約条件群を入力変数に設定され
ている値（入力変数に係る設定点の属性「現在値」の
値）が満足しているか否かを検査する処理を行う。

【０１３４】制約検査ステップ４０７の検査結果が「成
功」である場合には、設定点追加ステップ４０８を起動
する。設定点追加ステップ４０８では、関数格納部７に
格納された設定点追加関数を用いて、直前に値が設定さ
れた変数（その変数に係る設定点）を基に次の設定点を
生成する。例題３に対する探索において、図３（ｃ）の
設定点追加関数を用いた場合を考えるならば、変数Ａに
係る設定点に基づいて変数Ｇに係る設定点が追加され
る。

【０１３５】制約検査ステップ４０７の検査結果が「失
敗」である場合、すなわち違反する制約条件が見つかっ
た場合には、変数検査ステップ４０９を起動する。変数
検査ステップ４０９では、その制約違反に関する変数に
おけるバックトラックが可能か否かを検査する。

【０１３６】例題３に関しては、設定点の属性「探索有
無」に「無」と設定されていた場合には、この設定点に
係る変数では他の値をとることができないためにバック
トラックができず、変数検査ステップ４０９の検査結果
は「失敗」となる。

【０１３７】変数検査ステップ４０９の処理内容は、上
述の「設定点の属性「探索有無」を利用する」という処
理内容に限定されるものではなく、予めバックトラック
ができない変数群を示す情報を格納しておいてその情報
に基づいてバックトラックの可否を判断する手法等のバ
リエーションが考えられる。

【０１３８】変数検査ステップ４０９の検査結果が「失
敗」である場合には、変数値解除ステップ４１３および
状況スタックポップステップ４１４を順次起動する。変
数値解除ステップ４１３では当該変数の値を解除し、状
況スタックポップステップ４１４では状況スタックから
当該変数に係る設定点を取り除く（削除する）。

【０１３９】状況スタックポップステップ４１４の処理
が終了したならば、スタック空検査ステップ４１５を起
動する。スタック空検査ステップ４１５では、状況スタ
ックが空であるか否かの検査を行う。

【０１４０】スタック空検査ステップ４１５の検査結果
が「失敗」、すなわち状況スタックが空でなかった場合
には、処理を続行する（変数検査ステップ４０９に戻
る）。

【０１４１】スタック空検査ステップ４１５の検査結果
が「成功」、すなわち状況スタックが空であった場合に
は、第２異常終了ステップ４１６を起動する。第２異常
終了ステップ４１６では、設定点追加関数に問題があっ
た、あるいは設定点初期入力ステップ４０１で入力した
初期入力の設定点群に問題があったとして異常終了し、
制御部２を介して中央処理装置１にその旨を報告する。

【０１４２】変数検査ステップ４０９の検査結果が「成
功」である場合には、値調整ステップ４１０を起動す
る。値調整ステップ４１０では、関数格納部７に格納さ
れた値設定関数を起動し、状況スタックの最上部に格納
された設定点に係る変数に対する代替値の計算を行う。

【０１４３】例題３に対する探索においては、当該設定
点の属性「値設定関数名」に従って、状況スタックの最
上部に格納された変数に対する代替値の計算を行う。例
えば、それまでの変数Ａの値が９：００であれば、次の
代替値として１０：００を選択（計算）する。

【０１４４】値調整ステップ４１０において代替値を得
る手法（処理内容）としては、上述の「設定点の属性
「値設定関数名」を利用する」という処理内容に限定さ
れるものではなく、以下のおよび等のバリエーショ
ンが考えられる。 値設定関数を直接与え、その値設定関数によって代
替値の計算を行う。 設定点の属性「変数名」に基づいてその変数の代替
値を計算する。

【０１４５】値調整ステップ４１０の処理が終了する
と、値検査ステップ４１１を起動する。値検査ステップ
４１１では、直前の値調整ステップ４１０で得られた代
替値が変数に設定する値として適当であるか否かを検査
する。適当である場合には値検査ステップ４１１の検査
結果は「成功」となり、不適当である場合には検査結果
は「失敗」となる。

【０１４６】例題３に対する探索においては、直前に起
動された値調整ステップ４１０で計算された代替値が当
該設定点の属性「変更可能域」に含まれる範囲の値であ
るならば値検査ステップ４１１の検査結果は「成功」と
なり、そうでないならば当該検査結果は「失敗」とな
る。例えば、変数Ｇの値に１２：３０が設定されている
状態で値調整ステップ４１０が起動されて代替値として
１２：２０が求められた場合には、１２：２０は「変更
可能域」における範囲外になってしまい、値検査ステッ
プ４１１の検査結果は「失敗」となる。

【０１４７】値検査ステップ４１１の処理内容は、上述
の「設定点の属性「変更可能域」を利用する」という処
理内容に限定されるものではなく、以下のおよび等
のバリエーションが考えられる。 値として有効（適当）な範囲を直接格納しておいて
その情報に基づいて検査する。 過去に試した全ての値を設定点の中に保存していお
いて、その情報に基づいて値の検査を行う。

【０１４８】値検査ステップ４１１の検査結果が「成
功」である場合には、変数値設定ステップ４１２を起動
する。変数値設定ステップ４１２では、値調整ステップ
４１０で新規に計算した値（代替値）を当該変数の値
（当該変数に係る設定点内の属性「現在値」の値）に設
定する。例えば、値調整ステップ４１０で変数Ａに設定
されていた値９：００の代替値として１０：００を計算
したならば、変数値設定ステップ４１２で変数Ａの新た
な値として１０：００を設定する。なお、この値を状況
スタック内の変数Ａに係る設定点の属性「現在値」に書
き込むのは、状況スタック値書込みステップ４０６にお
いてである。

【０１４９】変数値設定ステップ４１２の処理が終了し
たならば、次に状況スタック値書込みステップ４０６に
戻り、新しく設定された値に関して状況スタック値書込
みステップ４０６から先の一連の処理を行う。

【０１５０】値検査ステップ４１１の検査結果が「失
敗」である場合には、変数検査ステップ４０９の検査結
果が「失敗」である場合と同様の流れで処理を行う。

【０１５１】なお、終了条件判定ステップ４０２の検査
結果が「成功」である場合には、終了検査ステップ４１
７を起動する。終了検査ステップ４１７では、変数格納
部５に格納された全ての変数群に値（制約条件群を満た
す値）が設定されているか否かを検査する。

【０１５２】終了検査ステップ４１７の検査結果が「成
功」である場合には、正常終了ステップ４１８を起動す
る。正常終了ステップ４１８では、対象問題（ここで
は、例題３）に対する探索処理の正常終了と各変数の解
（変数格納部５に格納された全ての変数群の値）とを、
制御部２を介して中央処理装置１に返却する。

【０１５３】終了検査ステップ４１７の検査結果が「失
敗」である場合には、第１異常終了ステップ４１９を起
動する。第１異常終了ステップ４１９では、対象問題に
対する探索処理の異常終了を、制御部２を介して中央処
理装置１に返却する。

【０１５４】図１３は、例題３に対して本実施例の探索
装置を用いて探索処理を行う場合の探索ツリーの展開の
概念を示す図である。

【０１５５】本実施例の探索装置では、例題３に対し
て、図１３の１３０１行〜１３１０行に示すような順序
で探索が行われ、最終的に変数Ａが１３：００、変数Ｇ
が１６：４０という解にたどり着く。すなわち、以下の
〜に示す順序で探索が行われる。

【０１５６】 １３０１行で、変数Ａの値（変数Ａに
係る設定点の属性「現在値」の値）に９：００が設定さ
れる。

【０１５７】 １３０２行〜１３０４行で、変数Ｇの
値（変数Ｇに係る設定点の属性「現在値」の値）として
｛１２：５０ １２：４０ １２：３０｝の各値が試さ
れるが、全て条件「１２：００から１３：００までの
間は設備が停止する」を違反する。

【０１５８】 そこで、１３０５行で、変数Ａにバッ
クトラックし、変数Ａの値に１０：００が設定される
が、条件を違反する。

【０１５９】 同様に、１３０６行〜１３０７行で、
変数Ａの値に１１：００および１２：００が設定される
が、両方ともに条件を違反する。

【０１６０】 そこで、１３０８行で、変数Ａの値に
１３：００が設定される。

【０１６１】 次に、変数Ｇへの値の設定が行われ、
１３０９行〜１３１０行で変数Ｇの値として｛１６：５
０ １６：４０｝の各値が試され、値１６：５０では条
件「設備の稼働可能時間は９：００から１８：００ま
での間である」を違反し、値１６：４０で条件が満た
され、この問題（例題３）の解が求められる。

【０１６２】図１６は、例題３に対して本実施例の探索
装置を用いて探索処理を行う際の状況スタックの推移の
概念を示す図である。

【０１６３】「（１）設定点１の選択、変数Ａの値（変
数Ａに係る設定点の属性「現在値」の値）への９：００
の代入。（２）設定点２の選択、変数Ｇの値（変数Ｇに
係る設定点の属性「現在値」の値）への１２：５０の代
入。（３）変数Ｇの値の解除、変数Ｇの値への１２：４
０の代入。（４）変数Ｇの値の解除、変数Ｇの値への１
２：３０の代入。（５）変数Ｇの値の解除、変数Ｇの選
択の解除、変数Ａの値の解除、変数Ａの値への１０：０
０の代入。（６）変数Ａの値の解除、変数Ａの値への１
１：００の代入。（７）変数Ａの値の解除、変数Ａの値
への１２：００の代入。（８）変数Ａの値の解除、変数
Ａの値への１３：００の代入。（９）変数Ｇの選択、変
数Ｇの値への１６：５０の代入。（１０）変数Ｇの値の
解除、変数Ｇの値への１６：４０の代入。」という一連
の流れで探索処理が行われるため、状況スタックの内容
は１６０１〜１６１１に示すように推移する。

【０１６４】初期状態では、１６０１に示すように状況
スタックは空である。（１）の処理が行われると、１６
０２に示すように設定点１が格納され、設定点１に変数
Ａの値が追加される。（２）の処理が行われると、１６
０３に示すように設定点２が状況スタックの一番上に積
まれる。以下同様にして、例題３に対する解が得られた
状態である１６１１に至るまで、処理が継続される。

【０１６５】図７は、本発明の探索装置の第２の実施例
（請求項２記載の発明に対応する実施例）の構成を示す
ブロック図である。

【０１６６】本実施例の探索装置は、第２設定点毎探索
処理部７０３と、条件格納部７０４と、変数格納部７０
５と、状況スタック格納部７０６と、関数格納部７０７
と、設定点格納部７０８と、条件検査部７０９と、依存
情報格納部７１０とを含んで構成されている。なお、本
実施例の探索装置は、制御部７０２を介して、中央処理
装置７０１と接続されている。

【０１６７】本実施例の探索装置は、第１の実施例の探
索装置に比べて、依存情報格納部７１０を付加したこと
と、設定点毎探索処理部３に代えて第２設定点毎探索処
理部７０３を設けたこととを特徴とする。

【０１６８】図８は、第２設定点毎探索処理部７０３の
詳細な処理フローを示す流れ図である。この処理は、設
定点初期入力ステップ８０１と、終了条件判定ステップ
８０２と、設定点選択ステップ８０３と、状況スタック
プッシュステップ８０４と、変数初期値バインドステッ
プ８０５と、状況スタック値書込みステップ８０６と、
制約検査ステップ８０７と、設定点追加ステップ８０８
と、依存情報確保ステップ８０９と、変数検査ステップ
８１０と、値調整ステップ８１１と、値検査ステップ８
１２と、変数値設定ステップ８１３と、依存関係保存ス
テップ８１４と、変数値解除ステップ８１５と、状況ス
タックポップステップ８１６と、依存検査ステップ８１
７と、スタック空検査ステップ８１８と、第２異常終了
ステップ８１９と、終了検査ステップ８２０と、正常終
了ステップ８２１と、第１異常終了ステップ８２２とか
らなる。

【０１６９】本実施例の探索装置（一般的には、請求項
２記載の発明に係る探索装置）における第２設定点毎探
索処理部７０３では、第１の実施例の探索装置（一般的
には、請求項１記載の発明に係る探索装置）における設
定点毎探索処理部３に対して、依存情報確保ステップ８
０９，依存情報保存ステップ８１４および依存検査ステ
ップ８１７の処理が追加されて、より高速な探索処理が
実現される。

【０１７０】図９は、依存情報格納部７１０に格納され
る依存情報の一例を示す図である。

【０１７１】図１４は、本実施例の探索装置の動作を説
明するための図である。

【０１７２】次に、このように構成された本実施例の探
索装置の動作について説明する。ここでは、第１の実施
例の探索装置に対する本実施例（第２の実施例）の探索
装置の追加部分の動作を中心に、本実施例の探索装置の
動作の説明を行う。また、探索対象の問題（対象問題）
として、以下の定義を持つ例題４が与えられた場合を考
える。

【０１７３】例題４：「自然数である変数Ａ，Ｂおよび
Ｃが存在するとき、以下の制約条件群（条件〜）を
満たす変数Ａ，ＢおよびＣの値を求める問題。」 変数Ａは１０の倍数であり、変数Ｂは５の倍数であ
る。 Ａ＋Ｂ＞４５であり、Ｃ≧２５である。 変数Ｂは、変数Ａに２０を足した値以上であり、４
０を足した値以下である。 変数Ｃは、変数Ａに１を足した値以上であり、１０
を足した値以下である。

【０１７４】変数格納部７０５には、値として自然数が
設定可能な変数Ａ，ＢおよびＣが格納される。

【０１７５】条件格納部７０４には、上述の制約条件群
が格納される。

【０１７６】設定点格納部７０８には、設定点群が格納
される。設定点のデータ構造は、第１の実施例における
データ構造（図２参照）と同様であるものとする。した
がって、設定点の属性群は、「変数名」，「初期値」，
「探索有無」，「探索方針」，「変更可能域」，「値設
定関数名」および「現在値」の７つの属性からなる。

【０１７７】関数格納部７０７には、３種類の関数（値
設定関数，設定点選択関数および設定点追加関数）が格
納される。

【０１７８】例題４に関しては、関数格納部７０７に格
納される３種類の関数の仕様は次の〜に示すように
定義されるものとする。

【０１７９】 値設定関数として、関数ｓｅｔｔｅｉ
−ｆｕｎｃ２が定義される。この関数は、変数Ａの場合
は１０単位の加減算を行い、変数Ｂの場合は５単位の加
減算を行い、変数Ｃの場合は１単位の加減算を行って、
各変数の値を設定する。

【０１８０】 設定点選択関数として、例題３に対す
る設定点選択関数と同一のものが定義され用いられる。

【０１８１】 設定点追加関数として、次のａ〜ｃに
示すような処理を行う関数が定義される。 ａ．属性「初期値」を変更可能域の最小値とし、属性
「探索有無」を「有」とし、属性「探索方針」を「→」
とし、属性「値設定関数名」を「ｓｅｔｔｅｉ−ｆｕｎ
ｃ２」とする新たな設定点を追加する。 ｂ．変数Ａに係る設定点が入力設定点となった場合に、
変数Ｂに係る設定点と変数Ｃに係る設定点とを両方生成
してリストにして返却する。 ｃ．変数Ｂに係る設定点の属性「変更可能域」は変数Ａ
の値（変数Ａに係る設定点の属性「現在値」の値）に１
０を足した値から４０を足した値までの範囲とし、変数
Ｃに係る設定点の属性「変更可能域」は変数Ａの値に１
を足した値から１０を足した値までの範囲とする。

【０１８２】例題４に関して、中央処理装置７０１から
制御部７０２を介して与えられる初期設定点群には、次
のような設定点（設定点１１とする）が定義されている
ものとする。設定点１１の７つの属性の属性値は、「変
数名」が「Ａ」であり、「初期値」が「１０」であり、
「探索有無」が「有」であり、「探索方針」が「→」で
あり、「変更可能域」が「［１．．∞］」であり、「値
設定関数名」が「ｓｅｔｔｅｉ−ｆｕｎｃ２」であり、
「現在値」が未定である。

【０１８３】第２設定点毎探索処理部７０３は、以上の
ような条件格納部７０４，変数格納部７０５，関数格納
部７０７および設定点格納部７０８の存在（状況スタッ
ク格納部７０６および後述する依存情報格納部７１０の
存在も含む）を前提として、条件検査部７０９を用い
て、以下に示すような処理を行う（図８参照）。以下で
は、第１の実施例における設定点毎探索処理部３の処理
と異なる点を中心として説明する。

【０１８４】設定点追加ステップ８０８の処理の終了後
に、依存情報確保ステップ８０９を起動する。依存情報
確保ステップ８０９では、直前の設定点選択ステップ８
０３で選択した設定点と直前の設定点追加ステップ８０
８で追加した設定点を含むリストとを組み合わせた情報
（依存情報）を依存情報格納部７１０に格納する。

【０１８５】図９に示すように、依存情報格納部７１０
に格納された依存情報は、依存元の設定点を示す依存元
情報９０１（ここでは、設定点１１が記述されている）
と、依存元の設定点を入力として設定点追加ステップ８
０８で追加された設定点（依存先の設定点）を含むリス
トが格納される依存先情報９０２（ここでは、設定点１
２が含まれている）とからなる。

【０１８６】なお、依存情報格納部７１０には、複数の
依存情報を格納することができる。

【０１８７】変数検査ステップ８１０の検査結果が「失
敗」である場合または値検査ステップ８１２の検査結果
が「失敗」である場合には、依存関係保存ステップ８１
４を起動する。依存関係保存ステップ８１４では、直前
の設定点選択ステップ８０３で選択されていた設定点を
依存情報格納部７１０から抽出して保存する。すなわ
ち、直前の変数検査ステップ８１０または値検査ステッ
プ８１２で検査の対象となっていた変数に係る設定点を
含む依存先情報を検出し、その依存先情報に対する依存
元情報中の設定点を保存する。

【０１８８】例えば、図９に示すような依存情報が存在
し、直前の変数検査ステップ８１０または値検査ステッ
プ８１２で設定点１２に係る変数が検査の対象であった
場合には、設定点１２を含む依存先情報を依存情報保存
部７１０から検索し、この検索で検出した依存先情報９
０２に対する依存元情報９０１中の設定点１１を取得し
て保存する。

【０１８９】状況スタックポップステップ８１６の処理
の終了後に、依存検査ステップ８１７を起動する。依存
検査ステップ８１７では、状況スタック格納部７０６内
の状況スタックの最上部に位置する設定点が依存関係保
存ステップ８１４で保存された設定点と一致するか否か
の検査を行う。

【０１９０】依存検査ステップ８１７の検査結果が「成
功」である場合には、それ以上、状況スタックをポップ
する必要がないことを認識し、スタック空検査ステップ
８１８に処理を進める。

【０１９１】依存検査ステップ８１７の検査結果が「失
敗」である場合には、値の設定に失敗した変数（直前の
変数検査ステップ８１０または値検査ステップ８１２の
検査の対象であった変数）に係る設定点を含む依存先情
報に対する依存元情報内の設定点まで状況スタックがポ
ップしていないということを認識し、変数値解除ステッ
プ８１５，状況スタックポップステップ８１６および依
存検査ステップ８１７のループ処理を繰り返し、依存検
査ステップ８１７の検査結果が「成功」となるまで当該
ループ処理を続ける。

【０１９２】最後に、図１４を参照して、第１の実施例
の探索装置と比べた場合の本実施例（第２の実施例）の
探索装置の特有の効果について言及する。

【０１９３】図１４は、例題４に対して第１の実施例お
よび第２の実施例の探索装置を用いて探索処理を行う場
合の探索ツリーの展開の概念を示す図である。

【０１９４】例題４を第１の実施例の探索装置（一般的
には、請求項１記載の発明に係る探索装置）を用いて解
いた場合には、図１４中の１４０１行〜１４１６行に示
すような探索ツリーに沿った順序で探索が行われる。

【０１９５】一方、例題４を第２の実施例の探索装置
（一般的には、請求項２記載の発明に係る探索装置）を
用いて解いた場合には、図１４中の１４０１行〜１４０
６行および１４１３行〜１４１６行に示すような探索ツ
リーに沿った順序で探索が行われる。すなわち、図１４
中の破線の四角形で囲まれた処理（１４０７行〜１４１
２行に示す処理）を省略することができ、以下の〜
に示す順序で探索が行われる。

【０１９６】 １４０１行で、変数Ａの値（変数Ａに
係る設定点の属性「現在値」の値）に１０が設定され
る。

【０１９７】 １４０２行〜１４０３行で、変数Ｂの
値（変数Ｂに係る設定点の属性「現在値」の値）に対し
て、３０および３５の各値が試される。両方とも、条件
中の「Ａ＋Ｂ＞４５」が満たされない。

【０１９８】 １４０４行で、変数Ｂの値に４０が設
定される。条件中の「Ａ＋Ｂ＞４５」が満たされる。

【０１９９】 １４０５行〜１４０６行で、変数Ｃ
（変数Ｃに係る設定点の属性「現在値」）に対して１１
〜２０の値が試される。全て、条件中の「Ｃ≧２５」
が満たされない。

【０２００】さて、でＣについて条件が全て満たさ
れなかった時点で、第１の実施例の探索装置を用いた探
索の場合には、変数Ｂの次の候補値が試される（１４０
７行〜１４１２行参照）。

【０２０１】しかし、本実施例（第２の実施例）の探索
装置を用いた探索の場合には、依存情報格納部７１０内
の依存情報を参照することによって「変数Ｃに係る設定
点が変数Ａに係る設定点に基づいて生成されたこと」が
導かれ（変数Ｃに関する依存先情報に基づいて変数Ａに
関する依存元情報が取得される）、変数Ａへのバックト
ラックが行われ、以下の〜に示す処理が行われる。

【０２０２】 １４１３行で、変数Ａにバックトラッ
クし、変数Ａの値に２０が設定される。

【０２０３】 １４１４行で、変数Ｂの値に対して４
０が設定される。条件中の「Ａ＋Ｂ＞４５」が満たさ
れる。

【０２０４】 １４１５行〜１４１６行で、変数Ｃに
対して２１〜２５の値が試され、変数Ｃの値が２５のと
きに条件中の「Ｃ≧２５」が満たされる。これによっ
て、例題４の解が求められる。

【０２０５】

【発明の効果】以上説明したように、本発明の探索装置
は、設定点というデータ構造（例えば図２参照）を用い
ることと、対象問題に適合する値設定関数，設定点選択
関数および設定点追加関数を対象問題毎に予め定義して
探索処理に用いることとにより、対象問題の内容や変数
の種類に応じて探索に関する各種の方針を変更でき、対
象問題や変数の種類に応じた適切な探索処理を行うこと
が可能となり、探索処理の効率化および処理速度の向上
が可能になるという効果を有する。

【０２０６】すなわち、対象問題の内容に応じて探索に
関する各種の方針を柔軟に変更することができ、変数毎
に異なる探索戦略を取ること（変数の種類に応じて探索
に関する各種の方針を動的に変更すること）によってい
ろいろな種類の変数が混在している対象問題に対する探
索の場合にも各変数に応じた探索を行うことができると
いう効果がある。

【０２０７】また、請求項２記載の発明に係る探索装置
では、請求項１記載の発明に係る探索装置の処理に加え
て依存情報の保存を行うことにより、無駄なバックトラ
ックを省き、より高速な探索処理を実現できるという効
果がある。

【０２０８】以上のように、本発明の探索装置を用いる
ことにより、柔軟でかつ高速な探索処理が可能なシステ
ム（探索装置を含むシステム）の構築が可能となる。

【図面の簡単な説明】

【図１】本発明の探索装置の第１の実施例の構成を示す
ブロック図である。

【図２】図１および図７に示す探索装置で取り扱われる
設定点のデータ構造の一例を示す図である。

【図３】図１中の関数格納部に格納される関数群（値設
定関数，設定点選択関数および設定点追加関数）の記述
例を示す図である。

【図４】図１中の設定点毎探索処理部の処理を示す流れ
図である。

【図５】図１に示す探索装置の動作を説明するための図
（図４中の状況スタックプッシュステップの動作の前後
の状況スタックの状態を示す図）である。

【図６】図１に示す探索装置の動作を説明するための図
（図４中の状況スタック値書込みステップの動作の前後
の状況スタックの状態を示す図）である。

【図７】本発明の探索装置の第２の実施例の構成を示す
ブロック図である。

【図８】図７中の第２設定点毎探索処理部の処理を示す
流れ図である。

【図９】図７中の依存情報格納部に格納される依存情報
の一例を示す図である。

【図１０】従来の探索装置の一例の構成を示すブロック
図である。

【図１１】図１０中の変数毎探索処理部の処理を示す流
れ図である。

【図１２】図１０に示す探索装置の動作を説明するため
の図（探索履歴の一例を示す図）である。

【図１３】図１に示す探索装置の動作を説明するための
図（探索履歴の一例を示す図）である。

【図１４】図７に示す探索装置の動作を説明するための
図（探索履歴の一例を示す図）である。

【図１５】図１０に示す探索装置の動作を説明するため
の図（状況スタックの推移の一例を示す図）である。

【図１６】図１に示す探索装置の動作を説明するための
図（状況スタックの推移の一例を示す図）である。

【符号の説明】

１，７０１ 中央処理装置 ２，７０２ 制御部 ３ 設定点毎探索処理部 ４，７０４ 条件格納部 ５，７０５ 変数格納部 ６，７０６ 状況スタック格納部 ７，７０７ 関数格納部 ８，７０８ 設定点格納部 ９，７０９ 条件検査部 ７０３ 第２設定点毎探索処理部 ７１０ 依存情報格納部 ４０１，８０１ 設定点初期入力ステップ ４０２，８０２ 終了条件判定ステップ ４０３，８０３ 設定点選択ステップ ４０４，８０４ 状況スタックプッシュステップ ４０５，８０５ 変数初期値バインドステップ ４０６，８０６ 状況スタック値書込みステップ ４０７，８０７ 制約検査ステップ ４０８，８０８ 設定点追加ステップ ４０９，８１０ 変数検査ステップ ４１０，８１１ 値調整ステップ ４１１，８１２ 値検査ステップ ４１２，８１３ 変数値設定ステップ ４１３，８１５ 変数値解除ステップ ４１４，８１６ 状況スタックポップステップ ４１５，８１８ スタック空検査ステップ ４１６，８１９ 第２異常終了ステップ ４１７，８２０ 終了検査ステップ ４１８，８２１ 正常終了ステップ ４１９，８２２ 第１異常終了ステップ ８０９ 依存情報確保ステップ ８１４ 依存関係保存ステップ ８１７ 依存検査ステップ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 異なる定義の値域を持つ変数が混在しう
   る変数群を持つ対象問題に対する探索処理を行い、与え
   られた制約条件群を満足するように変数の値の設定を行
   う探索装置において、 「変数名」と「現在値」とを属性として含むデータ構造
   であり、探索ツリーの分岐点の候補を表すデータ構造で
   あり、「変数名」および「現在値」以外の属性群として
   対象問題に適合する属性群を有するデータ構造である設
   定点の集合である設定点リストを格納する設定点格納部
   と、 設定点を入力として受け取り入力設定点の属性値を基に
   入力設定点に係る変数に対して次に試すべき値を計算す
   る関数である値設定関数，前記設定点格納部内の設定点
   リストから次に処理べき設定点を選択する関数である設
   定点選択関数，および設定点を入力として受け取り入力
   設定点が表す探索ツリーの分岐点より一段先の分岐点の
   候補群を求めて当該候補群である設定点群を返却する関
   数である設定点追加関数の３種類の関数であり、対象問
   題の内容に適合するように予め定義されている関数群を
   格納する関数格納部と、 対象問題における制約条件群を格納する条件格納部と、 対象問題における変数を格納する変数格納部と、 探索ツリーを探索する際の分岐の状況を「処理した設定
   点の履歴」として管理する状況スタック格納部と、 変数を入力として受け取り、前記条件格納部に格納され
   た制約条件群から入力変数に関係する制約条件群を選択
   し、選択した制約条件群を入力変数に設定されている値
   が満足しているか否か検査する条件検査部と、 前記状況スタック格納部内の状況スタックへの設定点の
   設定および削除を行って探索処理を進め、探索に関する
   各種の方針を前記関数格納部内の関数群および設定点内
   の各属性値に基づいて決定し、前記条件格納部内の制約
   条件群に関する検査を前記条件検査部を用いて行い、前
   記変数格納部に格納されている変数への制約条件群を満
   足する値の設定を試みる探索処理を行う設定点毎探索処
   理部とを有することを特徴とする探索装置。
2. 【請求項２】 前記関数格納部内の設定点追加関数によ
   って設定点が追加される際の依存元の設定点および依存
   先の設定点を示す情報を含む依存情報を格納する依存情
   報格納部を有することと、 前記設定点毎探索処理部により行われる全ての処理を行
   い、前記関数格納部内の設定点追加関数によって設定点
   が追加される際に前記依存情報格納部への依存情報の設
   定を行い、バックトラックを行う際に前記依存情報格納
   部内の依存情報に基づいて当該バックトラックを行う第
   ２設定点毎探索処理部を、前記設定点毎探索処理部の代
   わりに設けることとを特徴とする請求項１記載の探索装
   置。
3. 【請求項３】 製造業の工場で製品の生産のために必要
   となる各作業の設備利用開始時刻を決める生産スケジュ
   ーリング問題を対象問題とし、設定点の属性が「変数
   名」，「初期値」，「探索有無」，「探索方針」，「変
   更可能域」，「値設定関数」および「現在値」であるこ
   とを特徴とする請求項１または請求項２記載の探索装
   置。