JPH08249190A - 順序付け問題の解法を生成する方法 - Google Patents
順序付け問題の解法を生成する方法Info
- Publication number
- JPH08249190A JPH08249190A JP8011793A JP1179396A JPH08249190A JP H08249190 A JPH08249190 A JP H08249190A JP 8011793 A JP8011793 A JP 8011793A JP 1179396 A JP1179396 A JP 1179396A JP H08249190 A JPH08249190 A JP H08249190A
- Authority
- JP
- Japan
- Prior art keywords
- search
- items
- edges
- solution
- segments
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
Landscapes
- Engineering & Computer Science (AREA)
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Economics (AREA)
- Strategic Management (AREA)
- Marketing (AREA)
- Game Theory and Decision Science (AREA)
- Entrepreneurship & Innovation (AREA)
- Development Economics (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Physics & Mathematics (AREA)
- General Business, Economics & Management (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】
【課題】 順序付け問題の解法を生成する方法の提供。
【解決手段】人工知能又はオペレーションリサーチで開
発できるタイプの順序付け問題の解法を生成する方法で
ある。この方法は、アイテムの各々が属性のセットを有
し且つ所与の限定数のｎアイテムに与えられた制約及び
目的のセットが存在するとき、前記ｎアイテムの近最適
の特性の下位シーケンスの複数のセットを発見し、そし
て前記制約を同時に満足させることにより下位シーケン
スの数を最小にするステップを含む。
発できるタイプの順序付け問題の解法を生成する方法で
ある。この方法は、アイテムの各々が属性のセットを有
し且つ所与の限定数のｎアイテムに与えられた制約及び
目的のセットが存在するとき、前記ｎアイテムの近最適
の特性の下位シーケンスの複数のセットを発見し、そし
て前記制約を同時に満足させることにより下位シーケン
スの数を最小にするステップを含む。
Description
【０００１】
【発明の属する技術分野】本発明は指定された順序付け
問題の新規の解法を生成する方法に関する。
問題の新規の解法を生成する方法に関する。
【０００２】
【従来の技術】本発明は、例えば、人工知能又はオペレ
ーティングリサーチを含む領域で開発しうるタイプの順
序付け問題に関する解法の生成に関係する。大抵の順序
付け問題は組合せ問題であるから、これらの領域におけ
る順序付け問題は特に挑戦的であり、そして現実的な次
元での産業の順序付け問題では、問題の規模及び複雑さ
は、既存の探索アルゴリズム又は任意選択の解決手法、
例えば数学プログラミングを、計算上実行不可能にす
る。
ーティングリサーチを含む領域で開発しうるタイプの順
序付け問題に関する解法の生成に関係する。大抵の順序
付け問題は組合せ問題であるから、これらの領域におけ
る順序付け問題は特に挑戦的であり、そして現実的な次
元での産業の順序付け問題では、問題の規模及び複雑さ
は、既存の探索アルゴリズム又は任意選択の解決手法、
例えば数学プログラミングを、計算上実行不可能にす
る。
【０００３】更に、多くの産業の順序付け問題は制約及
び目的に関して明白に定義されない。制約及び目的は多
数のパラメータの概括的な関数でもよく、又は抽象的な
方法でのみ表現できる。産業の生産順序付け問題では前
記の例を数多く見受ける。
び目的に関して明白に定義されない。制約及び目的は多
数のパラメータの概括的な関数でもよく、又は抽象的な
方法でのみ表現できる。産業の生産順序付け問題では前
記の例を数多く見受ける。
【０００４】更に、これらの種類の産業の順序付け問題
では、しばしば全ての所与の制約を満足させる実行可能
な解法を見出せない。しかしながら、前記状況下でさえ
も、制約を満足させる下位シーケンス (以後それらをセ
グメントと呼ぶ) のセットの発見がなお望まれることが
ある。従って、多くのこれらの問題で、最適解法の発見
が必ずしも一番重要ではなく、むしろ、数時間かける代
わりに、妥当な時間、例えば１０分内に近最適な解法を
得ることがもっと重要であろう。さもなければ、しばし
ば要求される再スケジューリングは実際には不可能であ
る。
では、しばしば全ての所与の制約を満足させる実行可能
な解法を見出せない。しかしながら、前記状況下でさえ
も、制約を満足させる下位シーケンス (以後それらをセ
グメントと呼ぶ) のセットの発見がなお望まれることが
ある。従って、多くのこれらの問題で、最適解法の発見
が必ずしも一番重要ではなく、むしろ、数時間かける代
わりに、妥当な時間、例えば１０分内に近最適な解法を
得ることがもっと重要であろう。さもなければ、しばし
ば要求される再スケジューリングは実際には不可能であ
る。
【０００５】
【発明が解決しようとする課題】多くの異なる順序付け
問題のなかで、本発明が直面する主たる問題は下記のよ
うに特徴付けられる。所与の有限数のｎ個のアイテムの
場合、関連付けられた属性の各々、及び包括的なアイテ
ムに限定された制約及び目的のセットは、同時に前記制
約を満足させるアイテムの近最適なシーケンスを提供す
る。
問題のなかで、本発明が直面する主たる問題は下記のよ
うに特徴付けられる。所与の有限数のｎ個のアイテムの
場合、関連付けられた属性の各々、及び包括的なアイテ
ムに限定された制約及び目的のセットは、同時に前記制
約を満足させるアイテムの近最適なシーケンスを提供す
る。
【０００６】
【課題を解決するための手段】この順序付け問題の解決
のために、可能なシーケンスを探索する幾つかの一般的
に受け入れられた方法が列挙された文献がある。可能性
の一部をより早く取り除くために僅かに多くの知能的な
探索をそれぞれ行うこれらの方法の幾つかは互いに構築
し合うけれども、それらは基本的には変数をラベル付け
する探索アルゴリズムである。この方法では、この順序
付け問題は下記のように公式化できる: (1) 各々が関連した一定数の離散した定義域、D1,
D2,...,Dnを有する有限のｎ変数、v1,v2,...,vnのセッ
ト、及び(2) 制約及び目的のセットを与えられる。我々
が例えば５アイテムを有する場合、定義域Diの最初のエ
レメントは全て５入力アイテムである。目標は所与の制
約を同時に満足させる変数をラベル付けする、即ちその
値を割当てると同時に目的を最適化することである。変
数の各値はアイテムであるから、最初の変数を開始する
値の列挙はシーケンスを生ずる。しばしば、それは全て
の変数の値を発見できないことがある。
のために、可能なシーケンスを探索する幾つかの一般的
に受け入れられた方法が列挙された文献がある。可能性
の一部をより早く取り除くために僅かに多くの知能的な
探索をそれぞれ行うこれらの方法の幾つかは互いに構築
し合うけれども、それらは基本的には変数をラベル付け
する探索アルゴリズムである。この方法では、この順序
付け問題は下記のように公式化できる: (1) 各々が関連した一定数の離散した定義域、D1,
D2,...,Dnを有する有限のｎ変数、v1,v2,...,vnのセッ
ト、及び(2) 制約及び目的のセットを与えられる。我々
が例えば５アイテムを有する場合、定義域Diの最初のエ
レメントは全て５入力アイテムである。目標は所与の制
約を同時に満足させる変数をラベル付けする、即ちその
値を割当てると同時に目的を最適化することである。変
数の各値はアイテムであるから、最初の変数を開始する
値の列挙はシーケンスを生ずる。しばしば、それは全て
の変数の値を発見できないことがある。
【０００７】本発明の新規の方法を強調し、対比しそし
て定義することを見越して産業の問題の種々の変数ラベ
ル付けアルゴリズムがここに示され分析される。
て定義することを見越して産業の問題の種々の変数ラベ
ル付けアルゴリズムがここに示され分析される。
【０００８】［変数ラベル付けによる順序付け］変数ラ
ベル付けアルゴリズムは基本的には普通の引き返しツリ
ー探索を用いる順次アルゴリズムである。引き返しは、
定義域値を順次に例示し、そして追加毎にそれがどの制
約も侵害しないことを保証するために部分的な解法を検
査することにより問題を解決する方法である。("Estima
ting the efficiency of backtracking programs", Knu
th, D., Mathematics of Computation 29, No. 129, p
p.121-136, 1975 を参照されたい。)
ベル付けアルゴリズムは基本的には普通の引き返しツリ
ー探索を用いる順次アルゴリズムである。引き返しは、
定義域値を順次に例示し、そして追加毎にそれがどの制
約も侵害しないことを保証するために部分的な解法を検
査することにより問題を解決する方法である。("Estima
ting the efficiency of backtracking programs", Knu
th, D., Mathematics of Computation 29, No. 129, p
p.121-136, 1975 を参照されたい。)
【０００９】変数は任意の順序で例示できるが、この説
明では、下位の索引の変数を最初に試みる索引順に例示
されるものとする。新しい現在の変数viの例示の各々
で、 (探索ツリーの枝に対応する) 部分的な解法が制約
を満足させるかどうかを調べるために、その変数の全部
又は部分的にかかわる制約／目的に対してこの部分的な
解法が検査される。満足させた場合には、次の変数vi+1
を例示することにより枝が拡張される。さもなければ、
現在の変数の定義域Diにある別の値が試される。探索の
間に、Diが空になる場合、過去の変数の部分的な値の割
当ては解法となりえない。なぜなら、一貫した値は全て
の他の定義域に残りえず、引き返しは最後に例示された
過去の変数に戻り、未指定の値はそれをその次の値で再
例示するためにその定義域に残るからである。
明では、下位の索引の変数を最初に試みる索引順に例示
されるものとする。新しい現在の変数viの例示の各々
で、 (探索ツリーの枝に対応する) 部分的な解法が制約
を満足させるかどうかを調べるために、その変数の全部
又は部分的にかかわる制約／目的に対してこの部分的な
解法が検査される。満足させた場合には、次の変数vi+1
を例示することにより枝が拡張される。さもなければ、
現在の変数の定義域Diにある別の値が試される。探索の
間に、Diが空になる場合、過去の変数の部分的な値の割
当ては解法となりえない。なぜなら、一貫した値は全て
の他の定義域に残りえず、引き返しは最後に例示された
過去の変数に戻り、未指定の値はそれをその次の値で再
例示するためにその定義域に残るからである。
【００１０】従って、このアルゴリズムは部分的な解法
を生成し、そして、(a) 解法が発見され、又は(b) 解法
が実行不可能と分かるまで、それらに基づいて構築する
が、実行不可能と分かった時点で引き返す。
を生成し、そして、(a) 解法が発見され、又は(b) 解法
が実行不可能と分かるまで、それらに基づいて構築する
が、実行不可能と分かった時点で引き返す。
【００１１】解法が存在する場合には、基本的な引き返
し探索アルゴリズムは解法の発見を保証する。しかしな
がら、それはスラッシングとして知られた動作を表わ
す。なぜなら、それは同じ制約侵害を繰り返し発見し、
後に探索の失敗を知り、従って解法発見前に行われる引
き返しの量が増加するからである。解法の発見に要した
時間は変数の数の増加とともに指数関数的に増加する("
Consistency in networks of relations", Mackworth,
A.K., Artificial Intelligence 8, pp. 99-118,1977
及び Constraint Satisfaction in Logic Programming,
Van Hentenryck,P., The MTI Press, 1989 を参照され
たい)。
し探索アルゴリズムは解法の発見を保証する。しかしな
がら、それはスラッシングとして知られた動作を表わ
す。なぜなら、それは同じ制約侵害を繰り返し発見し、
後に探索の失敗を知り、従って解法発見前に行われる引
き返しの量が増加するからである。解法の発見に要した
時間は変数の数の増加とともに指数関数的に増加する("
Consistency in networks of relations", Mackworth,
A.K., Artificial Intelligence 8, pp. 99-118,1977
及び Constraint Satisfaction in Logic Programming,
Van Hentenryck,P., The MTI Press, 1989 を参照され
たい)。
【００１２】ハイブリッドアルゴリズムはこのようなス
ラッシング動作の回避して引き返し探索の性能を改良す
るために導入された("Increasing tree search efficie
ncyfor constraint satisfaction problems", Haralick
R. M. and Elliott G., Artificial Intelligence 14,
pp. 263-313, 1980 を参照されたい)。
ラッシング動作の回避して引き返し探索の性能を改良す
るために導入された("Increasing tree search efficie
ncyfor constraint satisfaction problems", Haralick
R. M. and Elliott G., Artificial Intelligence 14,
pp. 263-313, 1980 を参照されたい)。
【００１３】ハイブリッドアルゴリズムは探索空間をも
っと迅速に取り除くために引き返し探索と定義域縮小ア
ルゴリズムを組合わせる。それらの共通の方法は、現在
の変数を新たに例示するために、引き返し探索を続行す
る前に、将来の変数の定義域から全ての矛盾した値を除
去することにより、ツリー探索空間をできるだけ多く取
り除くことである。その実行時間の性能は普通の引き返
しツリー探索よりもずっと良いが、特に実行可能な解法
がないとき、非常に大量のメモリ空間が要求されること
により、このアルゴリズムはなお欠陥を有する。
っと迅速に取り除くために引き返し探索と定義域縮小ア
ルゴリズムを組合わせる。それらの共通の方法は、現在
の変数を新たに例示するために、引き返し探索を続行す
る前に、将来の変数の定義域から全ての矛盾した値を除
去することにより、ツリー探索空間をできるだけ多く取
り除くことである。その実行時間の性能は普通の引き返
しツリー探索よりもずっと良いが、特に実行可能な解法
がないとき、非常に大量のメモリ空間が要求されること
により、このアルゴリズムはなお欠陥を有する。
【００１４】つまり、最良の変数ラベル付けアルゴリズ
ムでさえも上記に定義された産業の順序付け問題を解決
するのに十分ではない。次のセクションで、変数のラベ
ル付けによる順序付けアルゴリズムの欠点を列挙する。
ムでさえも上記に定義された産業の順序付け問題を解決
するのに十分ではない。次のセクションで、変数のラベ
ル付けによる順序付けアルゴリズムの欠点を列挙する。
【００１５】［変数ラベル付けアルゴリズムにおける問
題］産業の順序付け問題では、変数ラベル付けアルゴリ
ズムは解法を生成するための主要な方法とみなされてい
る。しかしながら、部分的な上記説明のように、それで
もなお解法を得ることは下記の理由で困難である。
題］産業の順序付け問題では、変数ラベル付けアルゴリ
ズムは解法を生成するための主要な方法とみなされてい
る。しかしながら、部分的な上記説明のように、それで
もなお解法を得ることは下記の理由で困難である。
【００１６】［問題１: 実行可能な解法が存在しないこ
とがある］通常は問題が実行可能な解法を有するかどう
かの事前知識を与えられていない。それゆえ、実行可能
な解法がない状況では、多大の引き返しを伴う長時間の
探索が続けられるので、スラッシング動作が現われる。
一般に、このようなケースでは、探索が終了するまでに
数時間又は数日を要することも稀ではない。この問題に
より、多くの産業は、初期の目標が一週間のスケジュー
ルの作成になっていても、二日又は三日のスケジュール
のみを作成することがある。
とがある］通常は問題が実行可能な解法を有するかどう
かの事前知識を与えられていない。それゆえ、実行可能
な解法がない状況では、多大の引き返しを伴う長時間の
探索が続けられるので、スラッシング動作が現われる。
一般に、このようなケースでは、探索が終了するまでに
数時間又は数日を要することも稀ではない。この問題に
より、多くの産業は、初期の目標が一週間のスケジュー
ルの作成になっていても、二日又は三日のスケジュール
のみを作成することがある。
【００１７】この現象は実行可能な解法の存在が感知可
能ではない探索手法の使用を示唆する。更に、実行可能
な全体的なシーケンスが入手できない場合でも、下位シ
ーケンスのセットを生成できることが望ましい。
能ではない探索手法の使用を示唆する。更に、実行可能
な全体的なシーケンスが入手できない場合でも、下位シ
ーケンスのセットを生成できることが望ましい。
【００１８】［問題２: 順次割当ては高価である］変数
ラベル付けは順次アルゴリズムである。根ノードでの探
索の着手で(n-1)の選択が存在する。そして、第１のレ
ベルで、それらから選択される(n-2) の値を有する。ｋ
番目のレベルで、(n-k) の選択を有する。よって、ｋ番
目のレベルで、見込みのありそうな探索ツリー組合せの
数は
ラベル付けは順次アルゴリズムである。根ノードでの探
索の着手で(n-1)の選択が存在する。そして、第１のレ
ベルで、それらから選択される(n-2) の値を有する。ｋ
番目のレベルで、(n-k) の選択を有する。よって、ｋ番
目のレベルで、見込みのありそうな探索ツリー組合せの
数は
【数１】(n-1) x (n-2) x...x(n-k)
【００１９】である。組合せの大きさは探索レベルが増
すにつれて指数関数的に成長する。よって、実社会の問
題で見られるように、ｎが大きいとき、極めて大きいメ
モリ容量及び探索の時間を必要とする。異なる探索経路
をたどるためにかなりの量の引き返しが起きる場合に
は、このスラッシング動作は更に悪化する。
すにつれて指数関数的に成長する。よって、実社会の問
題で見られるように、ｎが大きいとき、極めて大きいメ
モリ容量及び探索の時間を必要とする。異なる探索経路
をたどるためにかなりの量の引き返しが起きる場合に
は、このスラッシング動作は更に悪化する。
【００２０】探索レベルの成長とともに空間／時間の指
数関数的な増加を要求しない探索手法の方を選択する。
数関数的な増加を要求しない探索手法の方を選択する。
【００２１】［問題３: 探索空間の経路選択が遅い］実
社会の業務では、しばしば異なるスケジューリングのシ
ーケンスが望まれる。例えば、全体として遅延を最小に
する生産シーケンス、又は最小生産費のシーケンス、等
が必要になる。それゆえ、幾つかの異なる解法を取得
し、そのなかから適切な解法が選択できることがしばし
ば好まれる。
社会の業務では、しばしば異なるスケジューリングのシ
ーケンスが望まれる。例えば、全体として遅延を最小に
する生産シーケンス、又は最小生産費のシーケンス、等
が必要になる。それゆえ、幾つかの異なる解法を取得
し、そのなかから適切な解法が選択できることがしばし
ば好まれる。
【００２２】変数ラベル付けアルゴリズムでは、変数が
例示されると、現在の変数の親までの前の変数の例示は
全て同じであり、現在の変数の値のみが異なる。
例示されると、現在の変数の親までの前の変数の例示は
全て同じであり、現在の変数の値のみが異なる。
【００２３】よって、探索空間の回りの移動は非常に遅
い。更に、解決点が探索空間内の現在の点から遠く離れ
ている場合、その解決点の近くに到達するのに非常に長
い探索時間を要する。
い。更に、解決点が探索空間内の現在の点から遠く離れ
ている場合、その解決点の近くに到達するのに非常に長
い探索時間を要する。
【００２４】［問題４: シーケンスはラベル付けの順序
が感知可能である］変数ラベル付けアルゴリズムでは、
変数が値を割当てられると、探索ツリーは拡張される。
ひとたび割当てが行われたならば、その値は探索がこの
点まで引き返すまで変更されない。前の起こりうる間違
いを回復するために使用できる機構はない。その結果、
探索結果は変数ラベル付けの順序が感知可能であり、ラ
ベルを変更する試みは非常に高価な動作を必要とする。
が感知可能である］変数ラベル付けアルゴリズムでは、
変数が値を割当てられると、探索ツリーは拡張される。
ひとたび割当てが行われたならば、その値は探索がこの
点まで引き返すまで変更されない。前の起こりうる間違
いを回復するために使用できる機構はない。その結果、
探索結果は変数ラベル付けの順序が感知可能であり、ラ
ベルを変更する試みは非常に高価な動作を必要とする。
【００２５】この欠点はラベル付けの順序に関係なく同
じ探索結果を生成できる探索アルゴリズムを発見する必
要性を示唆する。
じ探索結果を生成できる探索アルゴリズムを発見する必
要性を示唆する。
【００２６】［本発明の動機］上記の問題はより効率的
で且つロバストな探索方法を発見する課題を与えるもの
である。ここに定義される発明は下記の４つの問題を解
決する: (1) 実行可能な解法を有しない問題の解法 (又は下位シ
ーケンス) の取得。 (2) 順次に値を変数に割当てるとき表示されたスラッシ
ング動作の回避。それは大量の引き返しにより計算資源
を多く取り過ぎる。 (3) 短時間に多くの異なる解法の発見の必要性。 (4) ラベル付けの順序が感知可能ではない解法を有する
ロバストな探索アルゴリズムの必要性。
で且つロバストな探索方法を発見する課題を与えるもの
である。ここに定義される発明は下記の４つの問題を解
決する: (1) 実行可能な解法を有しない問題の解法 (又は下位シ
ーケンス) の取得。 (2) 順次に値を変数に割当てるとき表示されたスラッシ
ング動作の回避。それは大量の引き返しにより計算資源
を多く取り過ぎる。 (3) 短時間に多くの異なる解法の発見の必要性。 (4) ラベル付けの順序が感知可能ではない解法を有する
ロバストな探索アルゴリズムの必要性。
【００２７】上記の変数ラベル付けアルゴリズムの欠点
の解決として、本発明はエッジラベル付け順序付け手法
を含む新規の方法を提供する。この新規の方法の目標
は、実行可能な解法が存在しない場合でも、近最適の解
法を迅速に生成することである。
の解決として、本発明はエッジラベル付け順序付け手法
を含む新規の方法を提供する。この新規の方法の目標
は、実行可能な解法が存在しない場合でも、近最適の解
法を迅速に生成することである。
【００２８】従って、そのために: (1) アイテムの各々が属性のセットを有し且つ所与の有
限数のｎアイテムに与えられた制約及び目的のセットが
存在する場合、前記ｎアイテムの近最適特性の下位シー
ケンスの複数のセットを発見するステップと、(2) 下位
シーケンスの数が最小になるように前記制約を同時に満
足させるステップとを含む新規の方法をここに開示す
る。
限数のｎアイテムに与えられた制約及び目的のセットが
存在する場合、前記ｎアイテムの近最適特性の下位シー
ケンスの複数のセットを発見するステップと、(2) 下位
シーケンスの数が最小になるように前記制約を同時に満
足させるステップとを含む新規の方法をここに開示す
る。
【００２９】新規の方法は幾つかの重要で意味のある利
点を実現できる。例えば、新規の方法は実社会の順序付
け問題の近最適解法を迅速に発見する能力を有する。実
行可能性のない解法についても、新規の方法は妥当な解
法を生成できる。
点を実現できる。例えば、新規の方法は実社会の順序付
け問題の近最適解法を迅速に発見する能力を有する。実
行可能性のない解法についても、新規の方法は妥当な解
法を生成できる。
【００３０】更に、新規の方法はとりわけ: (1) 全ての制約を満足させる、複数の実行可能且つ近最
適シーケンスを迅速に発見する方法; (2) ビーム探索手法の利用により実質的に異なる解法を
取得する方法; (3) エッジ連結の順序が感知可能なセグメントを有する
特性の利用により下位シーケンスの特性を低下させずに
ビーム探索を用いる方法; (4) １つの探索アルゴリズムの使用により解法を得るに
は大き過ぎる問題に同じ順序付けアルゴリズムをうまく
適用する方法; (5) 迅速な順序付けソフトウェアツールを開発する方法 に詳細に記述される能力及び利点を含む。
適シーケンスを迅速に発見する方法; (2) ビーム探索手法の利用により実質的に異なる解法を
取得する方法; (3) エッジ連結の順序が感知可能なセグメントを有する
特性の利用により下位シーケンスの特性を低下させずに
ビーム探索を用いる方法; (4) １つの探索アルゴリズムの使用により解法を得るに
は大き過ぎる問題に同じ順序付けアルゴリズムをうまく
適用する方法; (5) 迅速な順序付けソフトウェアツールを開発する方法 に詳細に記述される能力及び利点を含む。
【００３１】
【発明の実施の形態】下位シーケンスのセット発見は下
記の２つのステップ: (1) アイテムが前処理され、一貫
性のあるエッジを有するセグメントグラフを生成するこ
とが望ましいステップと、(2) セグメントグラフのエッ
ジはアルゴリズムによりラベル付けされることが望まし
いステップとを含む。できれば各エッジを０ (破棄され
る) 又は１ (選択される) としてラベル付けする。全て
のエッジがラベル付けに使い尽くされたとき、最終的な
セグメントのセットを有する。
記の２つのステップ: (1) アイテムが前処理され、一貫
性のあるエッジを有するセグメントグラフを生成するこ
とが望ましいステップと、(2) セグメントグラフのエッ
ジはアルゴリズムによりラベル付けされることが望まし
いステップとを含む。できれば各エッジを０ (破棄され
る) 又は１ (選択される) としてラベル付けする。全て
のエッジがラベル付けに使い尽くされたとき、最終的な
セグメントのセットを有する。
【００３２】［セグメントグラフ］エッジラベル付け手
法への入力は、それぞれが属性、制約及び目的を所有で
きるアイテムのセットである。アイテムは１つの方向の
みが合理的であるように方向性の属性を所有できる。例
えば、異なる幅の鋼スラブのセットを含むアイテムが与
えられたとき、それらの生産はそれらが広い方から狭い
方の順に生産される規則に従わなければならない。時に
はアイテムの１つの端を他の端から区別する必要がある
から、それらにヘッド及びテイルをラベル付けすること
が望ましい。２つの端が区別できないケースでは、ヘッ
ド及びテイルは任意に指定できる。
法への入力は、それぞれが属性、制約及び目的を所有で
きるアイテムのセットである。アイテムは１つの方向の
みが合理的であるように方向性の属性を所有できる。例
えば、異なる幅の鋼スラブのセットを含むアイテムが与
えられたとき、それらの生産はそれらが広い方から狭い
方の順に生産される規則に従わなければならない。時に
はアイテムの１つの端を他の端から区別する必要がある
から、それらにヘッド及びテイルをラベル付けすること
が望ましい。２つの端が区別できないケースでは、ヘッ
ド及びテイルは任意に指定できる。
【００３３】入力アイテム及び制約により、入力アイテ
ムがノードになり、そしてどの関連制約も侵害しない任
意の２つのアイテムがエッジにより連結されることが望
ましい、セグメントグラフを構築する。２つのアイテム
間に、又はしばしば多くのアイテムにわたり、幾つかの
制約がありうる。エッジは方向性を所有できる。図１に
示された例 (参照番号10) では、５ノード (アイテム)
及び７エッジ E1,E2,...,E7を有する。
ムがノードになり、そしてどの関連制約も侵害しない任
意の２つのアイテムがエッジにより連結されることが望
ましい、セグメントグラフを構築する。２つのアイテム
間に、又はしばしば多くのアイテムにわたり、幾つかの
制約がありうる。エッジは方向性を所有できる。図１に
示された例 (参照番号10) では、５ノード (アイテム)
及び７エッジ E1,E2,...,E7を有する。
【００３４】アイテムの "H"及び "T"はそれぞれヘッド
及びテイルを表わす。セグメントグラフに示されたエッ
ジはまだ０又は１とラベル付けされていない。エッジを
０又は１にラベル付けすることは、解法探索空間を２つ
の部分: エッジを有する解法を含む部分と、エッジを有
しない解法を含む部分とに分割する。
及びテイルを表わす。セグメントグラフに示されたエッ
ジはまだ０又は１とラベル付けされていない。エッジを
０又は１にラベル付けすることは、解法探索空間を２つ
の部分: エッジを有する解法を含む部分と、エッジを有
しない解法を含む部分とに分割する。
【００３５】エッジラベル付けアルゴリズムはセグメン
ト又は下位シーケンスのセットを生ずる。セグメントは
基本的には順序づけられたアイテムのセットである。一
様の取扱いをするために、できれば生のアイテムをセグ
メントとみなす、従って、最初は、全てのアイテムはセ
グメントである。セグメントは、アイテムと同様に、そ
れ自身の属性及びヘッド／テイルを有する。
ト又は下位シーケンスのセットを生ずる。セグメントは
基本的には順序づけられたアイテムのセットである。一
様の取扱いをするために、できれば生のアイテムをセグ
メントとみなす、従って、最初は、全てのアイテムはセ
グメントである。セグメントは、アイテムと同様に、そ
れ自身の属性及びヘッド／テイルを有する。
【００３６】探索プロセスの間に、エッジにより連結さ
れた任意の２つの既存のセグメントを連結することによ
り、新しいセグメントは動的に生成できる。例えば、図
１の最初のセグメントグラフから、幾つかのエッジのな
かのエッジE1を選択する場合、新しいセグメント ((Tア
イテム1 H)) (Hアイテム2 T)を生成できる。 (本明細書
では、方向を表わすために、トリプル形式を用いる; そ
れはアイテム１のヘッドがアイテム２のヘッドと連結さ
れることを表わす; よって、アイテム１のテイル及びア
イテム２のテイルは新たに生成されたセグメントのテイ
ル及びヘッドになる。) ここで、E4を選択する場合、２
つの既存のセグメント ((Tアイテム1 H)) (Hアイテム2
T)及びアイテム４、即ちより詳細には(Tアイテム4 H)が
連結されて新しいセグメント ((Tアイテム4 H)(Tアイテ
ム1 H)(Hアイテム2 T)になる。それは実際には図３に示
された１つのセグメントである。最終的なセグメントの
セットが１つのセグメントを含むとき、それは探してい
る全体的なシーケンスであり、さもなければ、そのセッ
トの各構成部は下位シーケンスに対応する。
れた任意の２つの既存のセグメントを連結することによ
り、新しいセグメントは動的に生成できる。例えば、図
１の最初のセグメントグラフから、幾つかのエッジのな
かのエッジE1を選択する場合、新しいセグメント ((Tア
イテム1 H)) (Hアイテム2 T)を生成できる。 (本明細書
では、方向を表わすために、トリプル形式を用いる; そ
れはアイテム１のヘッドがアイテム２のヘッドと連結さ
れることを表わす; よって、アイテム１のテイル及びア
イテム２のテイルは新たに生成されたセグメントのテイ
ル及びヘッドになる。) ここで、E4を選択する場合、２
つの既存のセグメント ((Tアイテム1 H)) (Hアイテム2
T)及びアイテム４、即ちより詳細には(Tアイテム4 H)が
連結されて新しいセグメント ((Tアイテム4 H)(Tアイテ
ム1 H)(Hアイテム2 T)になる。それは実際には図３に示
された１つのセグメントである。最終的なセグメントの
セットが１つのセグメントを含むとき、それは探してい
る全体的なシーケンスであり、さもなければ、そのセッ
トの各構成部は下位シーケンスに対応する。
【００３７】セグメントグラフはノードのなかの多くの
制約のために一般に非常にまばらである。図１のセグメ
ントグラフは典型的なものである。これは処理している
問題と、対称的な旅行販売者問題のような最適化問題
("Traveling Salesman Problem: A Guided Tour of Co
mbinatorial Optimization", Lawler, E., Lenstra,
J., Rinnooy, A.,and Shmoys, D., 1985を参照された
い) との間の相違である。
制約のために一般に非常にまばらである。図１のセグメ
ントグラフは典型的なものである。これは処理している
問題と、対称的な旅行販売者問題のような最適化問題
("Traveling Salesman Problem: A Guided Tour of Co
mbinatorial Optimization", Lawler, E., Lenstra,
J., Rinnooy, A.,and Shmoys, D., 1985を参照された
い) との間の相違である。
【００３８】探索中のある時点で、セグメントにある全
てのアイテムはそれらに与えられた制約を満足させる。
大抵のケースで、セグメントグラフにあるセグメントは
できるだけ長いセグメントを形成するために組合せされ
ることになっている。目的により、異なるセグメントを
取得できる。一例として、図２及び図３の３つの異なる
セグメントのセット(参照番号12〜16)を参照されたい。
(A) ではしばしばハミルトニアン ("Graph Algorithm
s", Even, S., Computer Science Press, 1979を参照さ
れたい) と呼ばれ且つ全体的なシーケンスである１つの
セグメントを有し、(B) では２つのセグメントを有し、
(C) では、アイテム３が些細ではないセグメントのどれ
にも属しない場合、３つのセグメントを有する。
てのアイテムはそれらに与えられた制約を満足させる。
大抵のケースで、セグメントグラフにあるセグメントは
できるだけ長いセグメントを形成するために組合せされ
ることになっている。目的により、異なるセグメントを
取得できる。一例として、図２及び図３の３つの異なる
セグメントのセット(参照番号12〜16)を参照されたい。
(A) ではしばしばハミルトニアン ("Graph Algorithm
s", Even, S., Computer Science Press, 1979を参照さ
れたい) と呼ばれ且つ全体的なシーケンスである１つの
セグメントを有し、(B) では２つのセグメントを有し、
(C) では、アイテム３が些細ではないセグメントのどれ
にも属しない場合、３つのセグメントを有する。
【００３９】［エッジラベル付け順序付けの詳細］ 各レベルで: 探索について、探索ノードが生成され、各
々は下記の情報を所有できる: ・０から始まるレベル探索レベル (深さ) ・オープン経路: 更に拡張できるセグメントのセット ・クローズ経路: 拡張できず、最初は空であるセグメン
トのセット ・ステート状態: セグメントを更に連結するためにどの
セグメントが実行可能であるかを示す探索に関するもの ・エッジ: 現在の探索レベルの最良の実行可能なエッジ
々は下記の情報を所有できる: ・０から始まるレベル探索レベル (深さ) ・オープン経路: 更に拡張できるセグメントのセット ・クローズ経路: 拡張できず、最初は空であるセグメン
トのセット ・ステート状態: セグメントを更に連結するためにどの
セグメントが実行可能であるかを示す探索に関するもの ・エッジ: 現在の探索レベルの最良の実行可能なエッジ
【００４０】図４及び図５ (参照番号18〜40) はエッジ
ラベル付けアルゴリズムの代表的な流れ図を示し、そし
て以下に各ステップの良好な詳細が記述される: ステップ１: 最初の探索ノード (現在の探索ノード) を
生成する。解法ノード及び探索ノードスタックを初期化
する。セグメントグラフにある全ての現在の一貫性のあ
るエッジが現在の探索ノード.エッジ（Current Search
Node.Edge）に記憶される。 ステップ２: 現在の探索ノードのオープン経路及びクロ
ーズ経路を発見する。現在の探索ノードのオープン経路
（Current Search Node.Open Paths）が空であるかどう
かを検査し、もし空なら、ステップ７に進み、さもなけ
れば、次のステップに移る。 ステップ３: オープン経路のセグメントのセットから、
全てのエッジを集め、そしてそれらを、セグメントグラ
フ構造ならびに定義域の目的により評価されるそれらの
利点により、格付けする。それらから、Ｎがビーム幅で
ある場合、最良のＮエッジを見付けだし、そして分類さ
れた順序でそれらを現在の探索ノード.エッジに記憶す
る。 ステップ４: 現在の探索ノード.エッジ が空の場合、ス
テップ７に進む。さもなければ、最初の (最良の) エッ
ジを現在の探索ノード.エッジ からポップする。現在の
探索ノードが非空のエッジを有する場合、将来の代替探
索経路のために探索ノードスタックにそれをプッシュす
る。
ラベル付けアルゴリズムの代表的な流れ図を示し、そし
て以下に各ステップの良好な詳細が記述される: ステップ１: 最初の探索ノード (現在の探索ノード) を
生成する。解法ノード及び探索ノードスタックを初期化
する。セグメントグラフにある全ての現在の一貫性のあ
るエッジが現在の探索ノード.エッジ（Current Search
Node.Edge）に記憶される。 ステップ２: 現在の探索ノードのオープン経路及びクロ
ーズ経路を発見する。現在の探索ノードのオープン経路
（Current Search Node.Open Paths）が空であるかどう
かを検査し、もし空なら、ステップ７に進み、さもなけ
れば、次のステップに移る。 ステップ３: オープン経路のセグメントのセットから、
全てのエッジを集め、そしてそれらを、セグメントグラ
フ構造ならびに定義域の目的により評価されるそれらの
利点により、格付けする。それらから、Ｎがビーム幅で
ある場合、最良のＮエッジを見付けだし、そして分類さ
れた順序でそれらを現在の探索ノード.エッジに記憶す
る。 ステップ４: 現在の探索ノード.エッジ が空の場合、ス
テップ７に進む。さもなければ、最初の (最良の) エッ
ジを現在の探索ノード.エッジ からポップする。現在の
探索ノードが非空のエッジを有する場合、将来の代替探
索経路のために探索ノードスタックにそれをプッシュす
る。
【００４１】ステップ５: 新しい探索ノードを生成する
ことにより探索ツリーを拡張する。選択されたエッジは
２つの既存のセグメントを連結して１つにすると同時に
新しいセグメントを生成する。 ステップ６: 全ての既存のセグメント及び新たに生成さ
れたセグメントが制約伝達により更新される。 ステップ７: オープン経路及びクローズ経路の大きさの
総計を得る。それがこれまでの最小である場合は、解法
ノードをそれに設定し、それが最小に等しい場合は、そ
れを解法ノードに付加する。適用問題により、異なる基
準の境界を所有できる。例えば、セグメントの重み付け
合計の優先順位、アイテムの期限日の平均、等は大きさ
の総計と一緒に用いうる。 ステップ８: 探索ノードスタックが空である、即ち十分
な数の解法を有する場合、探索を終了する。さもなけれ
ば、探索ノードスタックからノードをポップアップす
る。
ことにより探索ツリーを拡張する。選択されたエッジは
２つの既存のセグメントを連結して１つにすると同時に
新しいセグメントを生成する。 ステップ６: 全ての既存のセグメント及び新たに生成さ
れたセグメントが制約伝達により更新される。 ステップ７: オープン経路及びクローズ経路の大きさの
総計を得る。それがこれまでの最小である場合は、解法
ノードをそれに設定し、それが最小に等しい場合は、そ
れを解法ノードに付加する。適用問題により、異なる基
準の境界を所有できる。例えば、セグメントの重み付け
合計の優先順位、アイテムの期限日の平均、等は大きさ
の総計と一緒に用いうる。 ステップ８: 探索ノードスタックが空である、即ち十分
な数の解法を有する場合、探索を終了する。さもなけれ
ば、探索ノードスタックからノードをポップアップす
る。
【００４２】註: ・探索プロセスは解法ノードに戻る。それは、各々がセ
グメントのセットを有する、少なくとも１つの探索ノー
ドである。 ・探索ノードを用いてこれまでに発見された最良のシー
ケンスを含む探索ノードが保持される。 ・探索中に、非空の実行可能なエッジを有する探索ノー
ドは後で用いるために探索ノードスタックにスタックさ
れる。 ・ステップ２で、現在の探索ノード.オープン 経路が空
である場合、２つの現在のセグメントは互いに連結でき
ないので、探索を続ける必要はない。このケースでは、
現在の探索ノード.クローズ経路（Current Search Nod
e.Closed Paths） に記憶されたセグメントのセットは
最終的なセグメントになる。 ・ステップ３で、現在の探索ノード.エッジ にある可能
なエッジからのエッジのセットを所定の基準によって評
価する。この評価のために、定義域に従属する情報及び
従属しない情報がどちらも用いられる。問題に従属する
評価として、: ・２つの既存のセグメントの長所の総和; ・１つのセグメントから他のセグメントへの移動費用 についての長所を持ちうる。
グメントのセットを有する、少なくとも１つの探索ノー
ドである。 ・探索ノードを用いてこれまでに発見された最良のシー
ケンスを含む探索ノードが保持される。 ・探索中に、非空の実行可能なエッジを有する探索ノー
ドは後で用いるために探索ノードスタックにスタックさ
れる。 ・ステップ２で、現在の探索ノード.オープン 経路が空
である場合、２つの現在のセグメントは互いに連結でき
ないので、探索を続ける必要はない。このケースでは、
現在の探索ノード.クローズ経路（Current Search Nod
e.Closed Paths） に記憶されたセグメントのセットは
最終的なセグメントになる。 ・ステップ３で、現在の探索ノード.エッジ にある可能
なエッジからのエッジのセットを所定の基準によって評
価する。この評価のために、定義域に従属する情報及び
従属しない情報がどちらも用いられる。問題に従属する
評価として、: ・２つの既存のセグメントの長所の総和; ・１つのセグメントから他のセグメントへの移動費用 についての長所を持ちうる。
【００４３】［ビーム探索の利用(ステップ３)］実行可
能なエッジの数がビーム幅よりも多い場合、それらの唯
一の最良のビーム幅数は現在のレベルで考慮される。一
般に、ビーム探索により真に最良のノードが拡張されな
い場合には、変数ラベル付け探索手法は良好な解法を取
得する機会を失うことがある。しかしながら、エッジ選
択の順序が感知不可能であるシーケンスを、エッジラベ
ル付けアルゴリズムの利用により発見できる。換言すれ
ば、たとえ探索レベルで、真に最良のエッジの代わり
に、第２の最良のエッジが拡張されても、通常は次のレ
ベルで真に最良のエッジが選択される。
能なエッジの数がビーム幅よりも多い場合、それらの唯
一の最良のビーム幅数は現在のレベルで考慮される。一
般に、ビーム探索により真に最良のノードが拡張されな
い場合には、変数ラベル付け探索手法は良好な解法を取
得する機会を失うことがある。しかしながら、エッジ選
択の順序が感知不可能であるシーケンスを、エッジラベ
ル付けアルゴリズムの利用により発見できる。換言すれ
ば、たとえ探索レベルで、真に最良のエッジの代わり
に、第２の最良のエッジが拡張されても、通常は次のレ
ベルで真に最良のエッジが選択される。
【００４４】変数ラベル付けによる順序付けで、ビーム
探索の使用による１つの欠点は、真に最良の選択である
ノード拡張の経路をしばしば見逃すことである。その結
果、ビーム探索の単純な採用は悪い結果を生じ、又は良
好な解法の発見に長い時間を要することがある。
探索の使用による１つの欠点は、真に最良の選択である
ノード拡張の経路をしばしば見逃すことである。その結
果、ビーム探索の単純な採用は悪い結果を生じ、又は良
好な解法の発見に長い時間を要することがある。
【００４５】しかしながら、このビーム探索の欠点はエ
ッジラベル付け手法の使用により回避できる。例えば、
図６ (参照番号42〜52) を参照されたい。(A) のセグメ
ントは最終的なセグメント(1 → 2 → 3 → 4)である。
(B)〜(F)は同じ最終的なセグメントを生成する幾つかの
異なるステップを示す。これらの図面で観察できるよう
に、ステップに関係なく同じセグメントを取得できる。
ッジラベル付け手法の使用により回避できる。例えば、
図６ (参照番号42〜52) を参照されたい。(A) のセグメ
ントは最終的なセグメント(1 → 2 → 3 → 4)である。
(B)〜(F)は同じ最終的なセグメントを生成する幾つかの
異なるステップを示す。これらの図面で観察できるよう
に、ステップに関係なく同じセグメントを取得できる。
【００４６】ビーム探索の利用により取得できる別の利
点は、迅速に探索空間を経路選択できることである。対
照的に、変数ラベル付けアルゴリズムでは、基本的には
引き返しに依存するから、探索空間の回りでは迅速に移
動できない。上記のように、この種の探索ではビーム探
索を使用できるけれども、ひとたび行った変数割当て見
逃しは回復できない。しかしながら、それは、エッジラ
ベル付け手法では、変数ラベル付け手法と異なり、この
ような問題を経験しないことがありうる。ビーム幅を制
限することにより、探索空間の回りを迅速に移動でき
る。特殊なケースとして、ビーム幅を１に設定する場
合、葉ノードに接触する１つの探索ツリーは１つの解法
のみを取得する。そして探索ツリーはその探索ツリーの
根から再開始すべきであり、全ての解法を前のものとは
全く異なるものにする。
点は、迅速に探索空間を経路選択できることである。対
照的に、変数ラベル付けアルゴリズムでは、基本的には
引き返しに依存するから、探索空間の回りでは迅速に移
動できない。上記のように、この種の探索ではビーム探
索を使用できるけれども、ひとたび行った変数割当て見
逃しは回復できない。しかしながら、それは、エッジラ
ベル付け手法では、変数ラベル付け手法と異なり、この
ような問題を経験しないことがありうる。ビーム幅を制
限することにより、探索空間の回りを迅速に移動でき
る。特殊なケースとして、ビーム幅を１に設定する場
合、葉ノードに接触する１つの探索ツリーは１つの解法
のみを取得する。そして探索ツリーはその探索ツリーの
根から再開始すべきであり、全ての解法を前のものとは
全く異なるものにする。
【００４７】［シーケンスの評価(ステップ４)］ステッ
プ４で、現在の探索ノード.エッジ が空であることは、
そこから選択する実行可能なエッジをそれ以上取得でき
ないことを意味し、そしてこの点までの探索ツリーがこ
れまでに取得されたシーケンスと較べて最良のものであ
るかどうかを検査する必要がある。これらのシーケンス
は全て現在の 探索ノード.クローズ経路に入れられる。
この時点 (ステップ７) で、所定の基準によりシーケン
スの特性を評価する。その目的は極小のセグメント、即
ちアイテムの数を最小にし、セグメントの数を最小に
し、又は他の基準に関係なく最長のセグメントを取得す
ることである。新たに生成されたセグメントの特性が前
のものに比較できる場合には、それらは解法ノードに入
れられる。
プ４で、現在の探索ノード.エッジ が空であることは、
そこから選択する実行可能なエッジをそれ以上取得でき
ないことを意味し、そしてこの点までの探索ツリーがこ
れまでに取得されたシーケンスと較べて最良のものであ
るかどうかを検査する必要がある。これらのシーケンス
は全て現在の 探索ノード.クローズ経路に入れられる。
この時点 (ステップ７) で、所定の基準によりシーケン
スの特性を評価する。その目的は極小のセグメント、即
ちアイテムの数を最小にし、セグメントの数を最小に
し、又は他の基準に関係なく最長のセグメントを取得す
ることである。新たに生成されたセグメントの特性が前
のものに比較できる場合には、それらは解法ノードに入
れられる。
【００４８】［探索ツリーの拡張 (ステップ５)］探索
ツリーが拡張されると、新しい探索ノードが生成され
る。新しい探索ノードでは、現在の探索ノードにある２
つのセグメントは常に連結されて新しいものになる。よ
って、新しい探索ノードにあるセグメントの数はその親
探索ノードの数よりも１少ない。一般に、(最初のアイ
テムの数と同じ) Ｎセグメントの探索を開始する場合、
それは (根ノードのレベルが０である) ｋ番目の探索レ
ベルで(N - k) に減らされる。
ツリーが拡張されると、新しい探索ノードが生成され
る。新しい探索ノードでは、現在の探索ノードにある２
つのセグメントは常に連結されて新しいものになる。よ
って、新しい探索ノードにあるセグメントの数はその親
探索ノードの数よりも１少ない。一般に、(最初のアイ
テムの数と同じ) Ｎセグメントの探索を開始する場合、
それは (根ノードのレベルが０である) ｋ番目の探索レ
ベルで(N - k) に減らされる。
【００４９】２つの既存のセグメントが連結されて新し
いセグメントになると、下記の下位シーケンス事象が起
きる: ・エッジラベル付け探索ツリーを拡張する。中間情報を
記憶する新しい探索ノードが生成される。 ・新しいセグメントが生成される。 ・２つの既存のセグメント及び新しいセグメントからの
連結可能なエッジが更新される。 ・新しいセグメントで属性: オープン経路、クローズ経
路及び状態が変更される。 ・次のセットの可能なエッジが発見される。
いセグメントになると、下記の下位シーケンス事象が起
きる: ・エッジラベル付け探索ツリーを拡張する。中間情報を
記憶する新しい探索ノードが生成される。 ・新しいセグメントが生成される。 ・２つの既存のセグメント及び新しいセグメントからの
連結可能なエッジが更新される。 ・新しいセグメントで属性: オープン経路、クローズ経
路及び状態が変更される。 ・次のセットの可能なエッジが発見される。
【００５０】［制約の検査による探索空間の除去］ステ
ップ５での新しい探索ノードの生成の後、全ての既存の
エッジがまだ有効かどうかを調べるために検査される。
無効なエッジは除去される。このステップを無効なエッ
ジがこれ以上検出されなくなるまで反復する。探索ツリ
ーの終了の発見で制約伝達が有効に用いられる。有効な
エッジの更新の外に、探索ノードの生成に関連する全て
の情報は更新できる。
ップ５での新しい探索ノードの生成の後、全ての既存の
エッジがまだ有効かどうかを調べるために検査される。
無効なエッジは除去される。このステップを無効なエッ
ジがこれ以上検出されなくなるまで反復する。探索ツリ
ーの終了の発見で制約伝達が有効に用いられる。有効な
エッジの更新の外に、探索ノードの生成に関連する全て
の情報は更新できる。
【００５１】［探索の引き返し又は終了 (ステップ７及
び８)］前述のように、現在の探索ノード.エッジ が空
になると、探索ツリーは葉ノードに達する。そして下記
の２つの選択肢を有する: ・ケース１: 終了 十分な数の満足な解法を取得した場合、単に探索を停止
する。 ・ケース２: 引き返し シーケンスが満足されない、即ちより多くの解法を必要
とする場合、代替経路に沿って探索を続ける。探索ノー
ドスタックを参照し、それがまだ代替経路の実行可能な
エントリ (探索ノード) を有するかどうかを調べる (ス
テップ８)。もしそうなら、スタックをポップアップす
ることにより最上の探索ノードを取得し、そして探索努
力を続けるために引き返す。
び８)］前述のように、現在の探索ノード.エッジ が空
になると、探索ツリーは葉ノードに達する。そして下記
の２つの選択肢を有する: ・ケース１: 終了 十分な数の満足な解法を取得した場合、単に探索を停止
する。 ・ケース２: 引き返し シーケンスが満足されない、即ちより多くの解法を必要
とする場合、代替経路に沿って探索を続ける。探索ノー
ドスタックを参照し、それがまだ代替経路の実行可能な
エントリ (探索ノード) を有するかどうかを調べる (ス
テップ８)。もしそうなら、スタックをポップアップす
ることにより最上の探索ノードを取得し、そして探索努
力を続けるために引き返す。
【００５２】［多くの入力アイテムによる順序付け］シ
ーケンスの生成には多過ぎる入力アイテムを与えられる
と、莫大な量の空間の処理を必要とすることがある。計
算能力がそれをサポートしない場合、エッジラベル付け
を反復して実行できる。この場合、ｋ番目の反復で生ず
るセグメントのセットは(k+1) 番目の反復の入力にな
る。
ーケンスの生成には多過ぎる入力アイテムを与えられる
と、莫大な量の空間の処理を必要とすることがある。計
算能力がそれをサポートしない場合、エッジラベル付け
を反復して実行できる。この場合、ｋ番目の反復で生ず
るセグメントのセットは(k+1) 番目の反復の入力にな
る。
【００５３】結果として生ずるセグメントの数が一定の
所定値よりも少なくなるまで、即ちそれ以上の順序付け
が不要になるまで、エッジラベル付けアルゴリズムを反
復して使用する。これは通常の変数ラベル付け探索アル
ゴリズムは提供できない特徴である。
所定値よりも少なくなるまで、即ちそれ以上の順序付け
が不要になるまで、エッジラベル付けアルゴリズムを反
復して使用する。これは通常の変数ラベル付け探索アル
ゴリズムは提供できない特徴である。
【００５４】［実験の結果］アルゴリズムを検査する手
段として、製鋼所スケジューリング問題及び総合鉄鋼ス
ケジューリング問題の解決を試みた。
段として、製鋼所スケジューリング問題及び総合鉄鋼ス
ケジューリング問題の解決を試みた。
【００５５】連続鋳造機械及び熱間圧延での順序付け問
題は最も困難な産業問題として知られている。製鋼所順
序付け問題は、それが種々の制約を有する点で興味があ
る。なかには連続処理アイテムに限定されるものがあ
る。例えば、１つのタイプの制約はわずかに40スラブの
みが３インチ(１インチは2.54cm)幅の差で圧延できるこ
とを求める。もう１つのタイプの制約は非連続処理アイ
テムに限定される、例えば、２つのグループの超低炭素
スラブの間に少なくとも７時間の間隔が要求される。
題は最も困難な産業問題として知られている。製鋼所順
序付け問題は、それが種々の制約を有する点で興味があ
る。なかには連続処理アイテムに限定されるものがあ
る。例えば、１つのタイプの制約はわずかに40スラブの
みが３インチ(１インチは2.54cm)幅の差で圧延できるこ
とを求める。もう１つのタイプの制約は非連続処理アイ
テムに限定される、例えば、２つのグループの超低炭素
スラブの間に少なくとも７時間の間隔が要求される。
【００５６】最初のスケジューリング問題の実行可能な
スケジュールを生成する努力として、順方向検査アルゴ
リズム、これまでに知られた最良のハイブリッド探索ア
ルゴリズムを試みた。その結果は、予想されたように、
満足できないものであった。多くのケースで、それは、
IBM 3090メインフレームで10時間以上にわたりVM/CMSの
Common Lispを用いて１つの解法すらも発見できなかっ
た。
スケジュールを生成する努力として、順方向検査アルゴ
リズム、これまでに知られた最良のハイブリッド探索ア
ルゴリズムを試みた。その結果は、予想されたように、
満足できないものであった。多くのケースで、それは、
IBM 3090メインフレームで10時間以上にわたりVM/CMSの
Common Lispを用いて１つの解法すらも発見できなかっ
た。
【００５７】エッジラベル付けの順序付けアルゴリズム
は２つの鉄鋼スケジューリング問題に用いられている。
各々のケースで、それは完全に実現され且つ評価され
た。
は２つの鉄鋼スケジューリング問題に用いられている。
各々のケースで、それは完全に実現され且つ評価され
た。
【００５８】それは最初に２要素連続鋳造機械の順序付
けシステムで用いられた。それはプロトタイプの Commo
n Lisp プログラミング言語で実現された。後に、それ
は別のAI言語の生産バージョンで再記述された。このス
ケジューラはIBM メインフレームで４秒以内に数千シー
ケンスを生成でき、そのランタイム速度は全ての他の方
法よりもすぐれている。速度の外に、シーケンスの特性
もすぐれていると評価された。
けシステムで用いられた。それはプロトタイプの Commo
n Lisp プログラミング言語で実現された。後に、それ
は別のAI言語の生産バージョンで再記述された。このス
ケジューラはIBM メインフレームで４秒以内に数千シー
ケンスを生成でき、そのランタイム速度は全ての他の方
法よりもすぐれている。速度の外に、シーケンスの特性
もすぐれていると評価された。
【００５９】もう１つのの用法として、順序付けアルゴ
リズムは実験用鉄鋼スケジューリング計画のコア順序付
けアルゴリズムとして最近用いられた。それはIBM RS/6
000ワークステーション上に Ｃ ＋ ＋ で記述される。C
AP はおよそ5000の入力命令アイテムを有し、それらか
ら多くの生産シーケンスが生成される。大きな入力数に
対処するために、アルゴリズムの２回の連続使用後にセ
グメントが生成される。鋳造及び圧延機械におけるシー
ケンスを生成するのにおよそ10分 (の経過時間) を要す
る。
リズムは実験用鉄鋼スケジューリング計画のコア順序付
けアルゴリズムとして最近用いられた。それはIBM RS/6
000ワークステーション上に Ｃ ＋ ＋ で記述される。C
AP はおよそ5000の入力命令アイテムを有し、それらか
ら多くの生産シーケンスが生成される。大きな入力数に
対処するために、アルゴリズムの２回の連続使用後にセ
グメントが生成される。鋳造及び圧延機械におけるシー
ケンスを生成するのにおよそ10分 (の経過時間) を要す
る。
【００６０】前に１つの解法でさえも取得するのが困難
とみなされたか、さもなければ、不可能であった、２つ
の困難なスケジューリング問題について、前述の実験の
結果は非常に印象的であり、多くの解法を発見すること
ができる。
とみなされたか、さもなければ、不可能であった、２つ
の困難なスケジューリング問題について、前述の実験の
結果は非常に印象的であり、多くの解法を発見すること
ができる。
【００６１】図６及び図７ (参照番号54〜82) は典型的
な前記コンピュータ実現を示す。通常の入力装置56はア
イテム、制約及び目的を含む情報を受取ることができ
る。コンピュータ58は図４及び５の流れ図と同様に動作
することができる。そして通常の出力表示装置82は複数
のスケジュール (下位シーケンスのセット) を提供する
ことができる。
な前記コンピュータ実現を示す。通常の入力装置56はア
イテム、制約及び目的を含む情報を受取ることができ
る。コンピュータ58は図４及び５の流れ図と同様に動作
することができる。そして通常の出力表示装置82は複数
のスケジュール (下位シーケンスのセット) を提供する
ことができる。
【００６２】まとめとして、本発明の構成に関して以下
の事項を開示する。 (１) (a) 属性のセットを有するアイテムがｎ個（但し
ｎ個は有限数）存在し、かつ前記ｎ個のアイテムに対す
る制約及び目的のセットが存在する場合に、前記ｎ個の
アイテムの近最適特性の下位シーケンスの複数のセット
を発見するステップと、(b) 前記下位シーケンスの数が
最小になるように前記制約を同時に満足させるステップ
とを含む方法。 (２) 前記制約のセット及び前記ｎ個のアイテムを用い
て下位シーケンスグラフを生成して２つのアイテムを連
結するエッジを対比させるステップを更に含む、上記
(１)に記載の方法。 (３) 探索手法を用いて下位シーケンスの複数のセット
を探索するステップを更に含む、上記(２)に記載の方
法。 (４) 前記探索手法は: (a) 所与の目的によりエッジを
選択しラベルを付するステップと、(b) 前に選択されラ
ベルが付されたエッジに関連したエッジを識別するステ
ップと、(c) ラベルが付されたエッジが存在しなくなる
まで前記ステップ(a)及び(b)を反復するステップとを含
む、上記(３)に記載の方法。 (５) 下位シーケンスの複数のセットを生成するために
代替エッジを選択するステップを含む、上記(４)に記載
の方法。 (６) 前記ステップをコンピュータ上で実行する、上記
(１)に記載の方法。
の事項を開示する。 (１) (a) 属性のセットを有するアイテムがｎ個（但し
ｎ個は有限数）存在し、かつ前記ｎ個のアイテムに対す
る制約及び目的のセットが存在する場合に、前記ｎ個の
アイテムの近最適特性の下位シーケンスの複数のセット
を発見するステップと、(b) 前記下位シーケンスの数が
最小になるように前記制約を同時に満足させるステップ
とを含む方法。 (２) 前記制約のセット及び前記ｎ個のアイテムを用い
て下位シーケンスグラフを生成して２つのアイテムを連
結するエッジを対比させるステップを更に含む、上記
(１)に記載の方法。 (３) 探索手法を用いて下位シーケンスの複数のセット
を探索するステップを更に含む、上記(２)に記載の方
法。 (４) 前記探索手法は: (a) 所与の目的によりエッジを
選択しラベルを付するステップと、(b) 前に選択されラ
ベルが付されたエッジに関連したエッジを識別するステ
ップと、(c) ラベルが付されたエッジが存在しなくなる
まで前記ステップ(a)及び(b)を反復するステップとを含
む、上記(３)に記載の方法。 (５) 下位シーケンスの複数のセットを生成するために
代替エッジを選択するステップを含む、上記(４)に記載
の方法。 (６) 前記ステップをコンピュータ上で実行する、上記
(１)に記載の方法。
【図１】セグメントグラフの最初のアイテムの構成の例
を示す図である。
を示す図である。
【図２】同じシーケンスから３つの異なるシーケンスを
生成できる方法の例を示す図である。
生成できる方法の例を示す図である。
【図３】同じシーケンスから３つの異なるシーケンスの
セットを生成できる方法の例を示す図である。
セットを生成できる方法の例を示す図である。
【図４】エッジラベル付け探索アルゴリズムの流れ図で
ある。
ある。
【図５】エッジラベル付け探索アルゴリズムの流れ図で
ある。
ある。
【図６】エッジラベル付けの順序付けの連結順序が感知
可能なことを示す図である。
可能なことを示す図である。
【図７】本発明の良好な実施例のコンピュータ実現の流
れ図である。
れ図である。
【図８】本発明の良好な実施例のコンピュータ実現の流
れ図である。
れ図である。
H ヘッド T テイル
Claims (6)
- 【請求項１】(a) 属性のセットを有するアイテムがｎ個
（但しｎは有限数）存在し、かつ前記ｎ個のアイテムに
対する制約及び目的のセットが存在する場合に、前記ｎ
個のアイテムの近最適特性の下位シーケンスの複数のセ
ットを発見するステップと、 (b) 前記下位シーケンスの数が最小になるように前記制
約を同時に満足さるステップとを含む方法。 - 【請求項２】前記制約のセット及び前記ｎ個のアイテム
を用いて下位シーケンスグラフを生成して２つのアイテ
ムを連結するエッジを対比さるステップを更に含む、請
求項１に記載の方法。 - 【請求項３】探索手法を用いて下位シーケンスの複数の
セットを探索するステップを更に含む、請求項２に記載
の方法。 - 【請求項４】前記探索手法は: (a) 所与の目的によりエッジを選択しラベルを付すステ
ップと、 (b) 前に選択されラベルが付されたエッジに関連したエ
ッジを識別するステップと、 (c) ラベルが付されたエッジが存在しなくなるまで前記
ステップ(a) 及び(b)を反復するステップとを含む、請
求項３に記載の方法。 - 【請求項５】下位シーケンスの複数のセットを生成する
ために代替エッジを選択するステップを含む、請求項４
に記載の方法。 - 【請求項６】前記ステップをコンピュータ上で実行す
る、請求項１に記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/384,979 US5666469A (en) | 1995-02-07 | 1995-02-07 | Method for generating solutions for sequencing problems |
| US384979 | 1995-02-07 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH08249190A true JPH08249190A (ja) | 1996-09-27 |
Family
ID=23519540
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP8011793A Pending JPH08249190A (ja) | 1995-02-07 | 1996-01-26 | 順序付け問題の解法を生成する方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5666469A (ja) |
| JP (1) | JPH08249190A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2020021422A (ja) * | 2018-08-03 | 2020-02-06 | 荏原実業株式会社 | 生体情報・業務管理システム、方法およびプログラム |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6175844B1 (en) * | 1997-05-29 | 2001-01-16 | Adobe Systems Incorporated | Ordering groups of text in an image |
| US6160986A (en) * | 1998-04-16 | 2000-12-12 | Creator Ltd | Interactive toy |
| DE60038480T2 (de) * | 1999-06-04 | 2009-04-16 | Koninklijke Philips Electronics N.V. | Bildverarbeitungserfahren, -vorrichtung und medizinisches untersuchungsgerät zur extraktion des pfades einer fadenförmigen struktur in einem bild |
| CA2433996C (en) * | 2001-01-09 | 2012-03-13 | British Telecommunications Public Limited Company | Software tool for heuristic search methods |
| WO2003046781A1 (en) * | 2001-11-23 | 2003-06-05 | British Telecommunications Public Limited Company | Resource allocation method |
| US7137861B2 (en) | 2002-11-22 | 2006-11-21 | Carr Sandra L | Interactive three-dimensional multimedia I/O device for a computer |
| US8965826B2 (en) | 2010-05-17 | 2015-02-24 | International Business Machines Corporation | Dynamic backjumping in constraint satisfaction problem solving |
| US10657180B2 (en) * | 2015-11-04 | 2020-05-19 | International Business Machines Corporation | Building and reusing solution cache for constraint satisfaction problems |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0782544B2 (ja) * | 1989-03-24 | 1995-09-06 | インターナショナル・ビジネス・マシーンズ・コーポレーション | マルチテンプレートを用いるｄｐマツチング方法及び装置 |
| US5146540A (en) * | 1990-02-22 | 1992-09-08 | International Business Machines Corp. | Processor allocation method and apparatus for multiprocessor execution of a constraint satisfaction search |
| US5249261A (en) * | 1990-02-26 | 1993-09-28 | International Business Machines Corporation | Failure history table for optimizing backtrack searches |
| US5228115A (en) * | 1990-03-29 | 1993-07-13 | International Business Machines Corporation | Hybrid backtrack/lookahead search technique for constraint-satisfaction problems |
| US5467268A (en) * | 1994-02-25 | 1995-11-14 | Minnesota Mining And Manufacturing Company | Method for resource assignment and scheduling |
-
1995
- 1995-02-07 US US08/384,979 patent/US5666469A/en not_active Expired - Fee Related
-
1996
- 1996-01-26 JP JP8011793A patent/JPH08249190A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2020021422A (ja) * | 2018-08-03 | 2020-02-06 | 荏原実業株式会社 | 生体情報・業務管理システム、方法およびプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| US5666469A (en) | 1997-09-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4594551B2 (ja) | 統合された確率的ランゲージ・モデルを用いたドキュメント画像復号化方法 | |
| Montoya-Torres et al. | Project scheduling with limited resources using a genetic algorithm | |
| JP3323180B2 (ja) | 決定木変更方法およびデータマイニング装置 | |
| Framinan et al. | Order scheduling with tardiness objective: Improved approximate solutions | |
| JPH0410165A (ja) | 最適計画作成方法 | |
| CN113609806B (zh) | 一种结合子图同构的量子线路程序通用变换方法 | |
| CN111178532B (zh) | 一种量子线路匹配的方法、装置、存储介质和电子装置 | |
| Lin et al. | A scheduling algorithm based on reinforcement learning for heterogeneous environments | |
| JPS62194533A (ja) | 木構造デ−タのパタ−ンマツチング方式 | |
| JPH08249190A (ja) | 順序付け問題の解法を生成する方法 | |
| JP2005276225A (ja) | テーブルを使用したツリーの学習 | |
| US10970050B1 (en) | User interface engine for miniapp development | |
| CN111209095A (zh) | 一种dag并行任务调度中基于树搜索的剪枝方法 | |
| JP2001290796A (ja) | 行列リオーダリング方法及び装置並びに電子回路シミュレーション方法及び装置 | |
| WO1991018343A1 (fr) | Systeme de production | |
| JP2024146863A (ja) | アニーラー・ベースのソルバーを用いた組み合わせ最適化問題の局所探索ベースの解法 | |
| Cooper et al. | The Hamiltonian cycle and travelling salesman problems in cP systems | |
| KR20230132369A (ko) | 양자 회로에서의 리소스 감소 | |
| CN119369408A (zh) | 一种基于分层蒙特卡洛树搜索的工业机器人路径规划与执行方法 | |
| JP6500896B2 (ja) | 属性列挙システム、属性列挙方法および属性列挙プログラム | |
| Guinet | Efficiency of reductions of job-shop to flow-shop problems | |
| CN115146485B (zh) | 基于gpu加速的射频链路仿真方法 | |
| US7107586B2 (en) | Intermediate object linking method and unit | |
| JPWO2009147794A1 (ja) | 有限オートマトン生成システム | |
| Kapsalis et al. | Fast sequential and parallel implementation of genetic algorithms using the GAmeter toolkit |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080315 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 7 Free format text: PAYMENT UNTIL: 20090315 |
|
| LAPS | Cancellation because of no payment of annual fees |