(57)【特許請求の範囲】
【請求項１】
スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードが前記アイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧ（Directed acyclic graph）に変換するグラフ変換処理部と、
前記ＤＡＧのノードの各々に対して、当該ノードから終端ノードまでの辺スコアの和が最大になるような経路の辺スコアの和である最大経路スコアを当該ノードについてのヒューリスティック関数値として計算するヒューリスティック関数計算部と、
入力された、論理関数によって表現された前記アイテムの組み合わせに関する制約を表現する二分決定グラフであるＢＤＤ（Binary Decision Diagram）と、前記ＤＡＧと、前記ヒューリスティック関数計算部により計算されたＤＡＧのヒューリスティック関数値とに基づいて、前記制約を満たす前記ナップサック問題の解を計算する最適解計算部と、
を含み、
前記ＤＡＧのノードｎと前記ＢＤＤのノードｍのペア（ｎ，ｍ）のヒューリスティック関数値を、前記ヒューリスティック関数計算部で計算したノードｎについてのヒューリスティック関数値とし、
前記ペア（ｎ，ｍ）について、前記ノードｎを始点とする各辺により遷移可能な前記ＤＡＧ上のノードｎ’と前記ＢＤＤ上のノードｍ’とのペア（ｎ’，ｍ’）を前記ペア（ｎ，ｍ）から遷移可能なノードペアの候補とし、
前記ＤＡＧの始点ノードｓと前記ＢＤＤのルートノードのペア（ｓ，ｒｏｏｔ）についての評価関数値を、ノードｓについての前記ヒューリスティック関数値として、
前記最適解計算部は、
前記ペア（ｓ，ｒｏｏｔ）から順に、当該ペアから遷移可能なノードペアの候補である候補ノードペアの各々についての評価関数値のうち、前記評価関数値が最も大きい候補ノードペアを優先的に探索することで、前記ＤＡＧの終端ノードｔと前記ＢＤＤの真の結果に対応する終端ノードＴとのペア（ｔ，Ｔ）に至る経路である前記解を計算するものであり、
前記ノードペア（ｎ’，ｍ’）を前記候補ノードペアとしたときの前記評価関数値は、前記ペア（ｎ，ｍ）についての評価関数値から当該ペア（ｎ，ｍ）についてのヒューリスティック関数値を差し引いた値と、前記ペア（ｎ’，ｍ’）のヒューリスティック関数値と、前記ノードｎと前記ノードｎ’とを接続する前記辺スコアと、の和である問題求解装置。
【請求項２】
前記ノードのペア毎に、当該ペアの評価関数値を対応付けて記憶するテーブルＡと、
前記ノードのペアと当該ノードのペアの評価関数値との組が格納され、格納されている組の中から前記評価関数値の最も大きなノードのペアを優先的に抽出する優先度つきキューと、
前記ノードのペアを格納するテーブルＢと、
を有し、
前記優先度つきキューには前記ペア（ｓ，ｒｏｏｔ）とその評価関数値ｆ（ｓ，ｒｏｏｔ）の組が格納され、
前記テーブルＢには前記ペア（ｓ，ｒｏｏｔ）が格納されているものとして、
前記最適解計算部は、前記優先度つきキューから抽出されたノードのペアを（ｎ，ｍ）として、前記ノードｎからの各辺ｅについて、前記辺ｅにより遷移可能な前記ＤＡＧ上のノードｎ’と前記ＢＤＤ上のノードｍ’とのペア（ｎ’，ｍ’）を取得し、当該ペア（ｎ’，ｍ’）についての前記評価関数値を計算する第１の手段と、
前記テーブルＡにおける前記ペア（ｎ’，ｍ’）に対応する評価関数値よりも前記計算された値が大きい場合は、前記第１の手段で計算した値でテーブルＡの前記ペア（ｎ’，ｍ’）に対応する評価関数値を更新する第２の手段と、
前記優先度つきキューに前記ペア（ｎ’，ｍ’）が格納されている場合は前記ペア（ｎ’，ｍ’）に対応する評価関数値ｆ（ｎ’，ｍ’）を、前記第１の手段で計算した評価関数値で更新し、前記優先度つきキューに前記ペア（ｎ’，ｍ’）が格納されていない場合は前記ペア（ｎ’，ｍ’）と前記第１の手段で計算した評価関数値ｆ（ｎ’，ｍ’）との組を前記優先度つきキューに追加する第３の手段と、
前記ペア（ｎ’，ｍ’）を前記テーブルＢに格納する第４の手段と、
前記テーブルＢに格納された結果に基づいて、前記ペア（ｓ，ｒｏｏｔ）から前記ペア（ｔ，Ｔ）までの経路である前記解を計算する第５の手段と、を含み、
前記優先度つきキューが空になるか、または、前記第５の手段が実行されるまで、前記優先度つきキューからノードのペアを抽出し、抽出したノードのペア（ｎ，ｍ）における前記ノードｎが前記ＤＡＧの終端ノードｔでなく、または、前記ノードｍが前記ＢＤＤの偽の結果に対応する終端ノードでない場合に前記第１の手段と、前記第２の手段と、前記第３の手段と、前記第４の手段とを実行させ、または、前記ノードｎが前記ＤＡＧの終端ノードｔであり、かつ、前記ノードｍが前記ＢＤＤの偽の結果に対応する終端ノードである場合に、前記第５の手段を実行させる処理を繰り返す請求項１記載の問題求解装置。
【請求項３】
グラフ変換処理部と、ヒューリスティック関数計算部と、最適解計算部とを含む、問題求解装置における問題求解方法であって、
前記グラフ変換処理部が、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードが前記アイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧ（Directed acyclic graph）に変換するグラフ変換処理ステップと、
前記ヒューリスティック関数計算部が、前記ＤＡＧのノードの各々に対して、当該ノードから終端ノードまでの辺スコアの和が最大になるような経路の辺スコアの和である最大経路スコアを当該ノードについてのヒューリスティック関数値として計算するヒューリスティック関数計算ステップと、
前記最適解計算部が、入力された、論理関数によって表現された前記アイテムの組み合わせに関する制約を表現する二分決定グラフであるＢＤＤ（Binary Decision Diagram）と、前記ＤＡＧと、前記ヒューリスティック関数計算部により計算されたＤＡＧのヒューリスティック関数値とに基づいて、前記制約を満たす前記ナップサック問題の解を計算する最適解計算ステップと、
を含み、
前記ＤＡＧのノードｎと前記ＢＤＤのノードｍのペア（ｎ，ｍ）のヒューリスティック関数値を、前記ヒューリスティック関数計算部で計算したノードｎについてのヒューリスティック関数値とし、
前記ペア（ｎ，ｍ）について、前記ノードｎを始点とする各辺により遷移可能な前記ＤＡＧ上のノードｎ’と前記ＢＤＤ上のノードｍ’とのペア（ｎ’，ｍ’）を前記ペア（ｎ，ｍ）から遷移可能なノードペアの候補とし、
前記ＤＡＧの始点ノードｓと前記ＢＤＤのルートノードのペア（ｓ，ｒｏｏｔ）についての評価関数値を、ノードｓについての前記ヒューリスティック関数値として、
前記最適解計算ステップは、
前記ペア（ｓ，ｒｏｏｔ）から順に、当該ペアから遷移可能なノードペアの候補である候補ノードペアの各々についての評価関数値のうち、前記評価関数値が最も大きい候補ノードペアを優先的に探索することで、前記ＤＡＧの終端ノードｔと前記ＢＤＤの真の結果に対応する終端ノードＴとのペア（ｔ，Ｔ）に至る経路である前記解を計算するものであり、
前記ノードペア（ｎ’，ｍ’）を前記候補ノードペアとしたときの前記評価関数値は、前記ペア（ｎ，ｍ）についての評価関数値から当該ペア（ｎ，ｍ）についてのヒューリスティック関数値を差し引いた値と、前記ペア（ｎ’，ｍ’）のヒューリスティック関数値と、前記ノードｎと前記ノードｎ’とを接続する前記辺スコアと、の和である
問題求解方法。
【請求項４】
前記問題求解装置は、前記ノードのペア毎に、当該ペアの評価関数値を対応付けて記憶するテーブルＡと、
前記ノードのペアと当該ノードのペアの評価関数値との組が格納され、格納されている組の中から前記評価関数値の最も大きなノードのペアを優先的に抽出する優先度つきキューと、
前記ノードのペアを格納するテーブルＢと、
を有し、
前記優先度つきキューには前記ペア（ｓ，ｒｏｏｔ）とその評価関数値ｆ（ｓ，ｒｏｏｔ）の組が格納され、
前記テーブルＢには前記ペア（ｓ，ｒｏｏｔ）が格納されているものとして、
前記最適解計算ステップは、前記優先度つきキューから抽出されたノードのペアを（ｎ，ｍ）として、前記ノードｎからの各辺ｅについて、前記辺ｅにより遷移可能な前記ＤＡＧ上のノードｎ’と前記ＢＤＤ上のノードｍ’とのペア（ｎ’，ｍ’）を取得し、当該ペア（ｎ’，ｍ’）についての前記評価関数値を計算する第１のステップと、
前記テーブルＡにおける前記ペア（ｎ’，ｍ’）に対応する評価関数値よりも前記計算された値が大きい場合は、前記第１のステップで計算した値でテーブルＡの前記ペア（ｎ’，ｍ’）に対応する評価関数値を更新する第２のステップと、
前記優先度つきキューに前記ペア（ｎ’，ｍ’）が格納されている場合は前記ペア（ｎ’，ｍ’）に対応する評価関数値ｆ（ｎ’，ｍ’）を、前記第１のステップで計算した評価関数値で更新し、前記優先度つきキューに前記ペア（ｎ’，ｍ’）が格納されていない場合は前記ペア（ｎ’，ｍ’）と前記第１のステップで計算した評価関数値ｆ（ｎ’，ｍ’）との組を前記優先度つきキューに追加する第３のステップと、
前記ペア（ｎ’，ｍ’）を前記テーブルＢに格納する第４のステップと、
前記テーブルＢに格納された結果に基づいて、前記ペア（ｓ，ｒｏｏｔ）から前記ペア（ｔ，Ｔ）までの経路である前記解を計算する第５のステップと、を含み、
前記優先度つきキューが空になるか、または、前記第５のステップが実行されるまで、前記優先度つきキューからノードのペアを抽出し、抽出したノードのペア（ｎ，ｍ）における前記ノードｎが前記ＤＡＧの終端ノードｔでなく、または、前記ノードｍが前記ＢＤＤの偽の結果に対応する終端ノードでない場合に前記第１のステップと、前記第２のステップと、前記第３のステップと、前記第４のステップとを実行させ、または、前記ノードｎが前記ＤＡＧの終端ノードｔであり、かつ、前記ノードｍが前記ＢＤＤの偽の結果に対応する終端ノードである場合に、前記第５のステップを実行させる処理を繰り返す請求項３記載の問題求解方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載の問題求解装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、組み合わせ最適化問題のための問題求解装置、方法、及びプログラムに関するものである。
【背景技術】
【０００２】
０−１ナップサック問題とは、Ｎ個のアイテムの集合｛１，．．．，Ｎ｝について、それぞれのコストｃｉが非負整数、スコアｗｉ（ｉ＝１，２，．．．，Ｎ）が実数、そしてコストの合計の上限値Ｌが非負整数で与えられたときに、アイテムの集合｛１，．．．，Ｎ｝の可能な部分集合のうち、
【０００３】
【数１】
0006497705.tif 000002
【０００４】
を満たしつつ、Σｉ∈Ｓｗｉを最大化するような解Ｓを見つける組合せ最適化問題である。
【０００５】
ここで、アイテムの組合せに関する離散的な制約とは、たとえば「アイテム１を解Ｓに含む場合には、アイテム３は解に含んではならない」や、「アイテム１、３、５、及び７のうち少なくともひとつは解に含まなければならない」といった、論理式で表現可能な制約である。
【０００６】
従来より、０−１ナップサック問題は行をアイテム番号とし、列をアイテムのコストとするような表にスコアを埋めていく操作として求解できることが知られている。
【０００７】
また、この表に代えて有向非巡回グラフを用いて求解する方法も知られている。当該方法では、表を埋める操作に代わって有向非巡回グラフの最長路を探索によって見つける操作を行う。しかし、これらの従来法は高速に求解可能である一方、アイテムの組合せに関する制約を取り扱うことができなかった。
【０００８】
さらに、アイテムの組合せに関する離散的な制約が与えられた０−１ナップサック問題の解を求める方法がある（非特許文献１）。当該手法では、前述の方法同様に有向非巡回グラフ上の探索を行うだけでなく、それに加えて、論理関数によって表現されたアイテムの組み合わせに関する制約を二分決定グラフ（Binary Decision Diagram:以後ＢＤＤとする）とよばれるデータ構造を用いて表現することによって、制約付きの０−１ナップサック問題を解くことができる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Masaaki Nishino et.al.,  “BDD-constrained search: a unified approach for constrained shortest path problems”, In Proc. of AAAI-15
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、上述した非特許文献１の方法では、ＢＤＤを用いた従来法制約付き０−１ナップサック問題を求解できる一方で、制約を表現するためのＢＤＤが大きくなると処理に時間がかかるという問題がある。また、一般に、制約が複雑になるほどＢＤＤは大きくなる傾向があるため、複雑な制約のもとで問題を解くのには不向きであるという問題がある。
【００１１】
本発明では、上記問題点を解決するために成されたものであり、制約が付加された０−１ナップサック問題の解を高速に求めることができる問題求解装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、第１の発明に係る問題求解装置は、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードが前記アイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧ（Directed acyclic graph）に変換するグラフ変換処理部と、前記ＤＡＧのノードの各々に対して、前記ノードから終端ノードまでの辺のスコアの和が最大になるような経路のスコアの和である最大経路スコアを計算するヒューリスティック関数計算部と、入力された、論理関数によって表現された前記アイテムの組み合わせに関する制約を表現する二分決定グラフであるＢＤＤ（Binary Decision Diagram）と、前記ＤＡＧと、前記ヒューリスティック関数計算部により計算されたＤＡＧの各ノードの最大経路スコアとに基づいて、前記制約を満たす前記ナップサック問題の解を計算する最適解計算部と、を含んで構成されている。
【００１３】
第２の発明に係る問題求解方法は、グラフ変換処理部と、ヒューリスティック関数計算部と、最適解計算部とを含む、問題求解装置における問題求解方法であって、前記グラフ変換処理部は、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードが前記アイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧ（Directed acyclic graph）に変換し、前記ヒューリスティック関数計算部は、前記ＤＡＧのノードの各々に対して、前記ノードから終端ノードまでの辺のスコアの和が最大になるような経路のスコアの和である最大経路スコアを計算し、前記最適解計算部は、入力された、論理関数によって表現された前記アイテムの組み合わせに関する制約を表現する二分決定グラフであるＢＤＤ（Binary Decision Diagram）と、前記ＤＡＧと、前記ヒューリスティック関数計算部により計算されたＤＡＧの各ノードの最大経路スコアとに基づいて、前記制約を満たす前記ナップサック問題の解を計算する。
【００１４】
第１及び第２の発明によれば、グラフ変換処理部により、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードがアイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧ（Directed acyclic graph）に変換し、ヒューリスティック関数計算部により、ＤＡＧのノードの各々に対して、ノードから終端ノードまでの辺のスコアの和が最大になるような経路のスコアの和である最大経路スコアを計算し、最適解計算部により、入力された、論理関数によって表現されたアイテムの組み合わせに関する制約を表現する二分決定グラフであるＢＤＤ（Binary Decision Diagram）と、ＤＡＧと、ヒューリスティック関数計算部により計算されたＤＡＧの各ノードの最大経路スコアとに基づいて、制約を満たすナップサック問題の解を計算する。
【００１５】
このように、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードがアイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧに変換し、ＤＡＧのノードの各々に対して、最大経路スコアを計算し、入力された、ＢＤＤと、ＤＡＧと、計算されたＤＡＧの各ノードの最大経路スコアとに基づいて、制約を満たすナップサック問題の解を計算することにより、制約が付加された０−１ナップサック問題の解を高速に求めることができる。
【００１６】
また、第１及び第２の発明において、前記ＤＡＧは、各辺ｅに、前記辺ｅのスコアに応じたラベルが付加されており、前記最適解計算部は、前記ＤＡＧのノードｎと前記ＢＤＤのノードｍとの組み合わせ（ｎ，ｍ）についての評価関数ｆ（ｎ，ｍ）の各々の値を格納するテーブルＡを初期化し、前記ＤＡＧの始点ノードｓと前記ＢＤＤのルートノードｒｏｏｔとの組み合わせ（ｓ，ｒｏｏｔ）について、前記ＤＡＧの始点ノードｓについての前記最大経路スコアに基づいて前記組み合わせ（ｓ，ｒｏｏｔ）の評価関数ｆ（ｓ，ｒｏｏｔ）の値を計算し、前記組み合わせ（ｓ，ｒｏｏｔ）と対応づけて優先度つきキューに格納すると共に、前記評価関数ｆ（ｓ，ｒｏｏｔ）の値を前記テーブルＡに格納し前記優先度つきキューから前記評価関数ｆ（ｎ，ｍ）の値が最大となる前記組み合わせ（ｎ，ｍ）を抽出し、前記抽出された前記組み合わせ（ｎ，ｍ）の前記ＤＡＧのノードｎが終端ノードでなく、又は前記組み合わせの前記ＢＤＤのノードｍが偽でない場合には、前記抽出した組み合わせ（ｎ，ｍ）の前記ＤＡＧのノードｎからの各辺ｅについて、前記辺ｅに付加されているラベルと前記組み合わせ（ｎ，ｍ）の前記ＢＤＤのノードｍとに基づいて、前記辺ｅにより遷移する前記ＤＡＧのノードｎ’と、前記ＢＤＤのノードｍから遷移可能な前記ＢＤＤのノードｍ’との組み合わせ（ｎ’，ｍ’）を取得し、前記取得した組み合わせ（ｎ’，ｍ’）について、前記ＤＡＧのノードｎ’についての前記最大経路スコアと、前記組み合わせ（ｓ，ｒｏｏｔ）から前記抽出した組み合わせ（ｎ，ｍ）まで到達する経路における最大経路スコアと、前記辺ｅに付加されているスコアとに基づいて、前記取得した組み合わせ（ｎ’，ｍ’）の評価関数ｆ（ｎ’，ｍ’）の値を計算し、前記取得した組み合わせ（ｎ’，ｍ’）の評価関数ｆ（ｎ’，ｍ’）の値が、前記テーブルＡに格納されている前記評価関数ｆ（ｎ’，ｍ’）の値よりも大きい場合に、前記テーブルＡに格納されている前記評価関数ｆ（ｎ’，ｍ’）の値を更新し、かつ、前記優先度つきキューに格納されている評価関数ｆ（ｎ’，ｍ’）の値を更新し、又は前記優先度つきキューに前記評価関数ｆ（ｎ’，ｍ’）の値を格納し、前記優先度つきキューから抽出された前記評価関数ｆ（ｎ，ｍ）の値が最大となる組み合わせ（ｎ，ｍ）の前記ＤＡＧのノードｎが終端ノードであり、かつ前記ＢＤＤのノードｍが真となるまで、前記優先度つきキューから前記評価関数ｆ（ｎ，ｍ）の値が最大となる組み合わせ（ｎ，ｍ）を抽出する処理と、前記テーブルＡを更新し、かつ、前記優先度つきキューを更新し、又は前記優先度つきキューに前記評価関数ｆ（ｎ’，ｍ’）の値を格納する処理とを繰り返し、繰り返し処理の過程に基づいてバックトラッキング処理を行い、前記制約を満たす前記ナップサック問題の解を計算してもよい。
【００１７】
また、本発明のプログラムは、コンピュータを、上記の問題求解装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
以上説明したように、本発明の問題求解装置、方法、及びプログラムによれば、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードがアイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧに変換し、ＤＡＧのノードの各々に対して、最大経路スコアを計算し、入力された、ＢＤＤと、ＤＡＧと、計算されたＤＡＧの各ノードの最大経路スコアとに基づいて、制約を満たすナップサック問題の解を計算することにより、制約が付加された０−１ナップサック問題の解を高速に求めることができる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態に係る問題求解装置の機能的構成を示すブロック図である。
【図２】論理関数及びＢＤＤの一例を示す図である。
【図３】インスタンス及びＤＡＧの一例を示す図である。
【図４】本実施形態に係る問題求解装置における問題求解処理ルーチンを示すフローチャートである。
【図５】本実施形態に係る問題求解装置におけるＤＡＧ変換処理ルーチンを示すフローチャートである。
【図６】本実施形態に係る問題求解装置におけるナップサック問題計算処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００２１】
＜本発明の実施形態に係る問題求解装置の構成＞
次に、本発明の実施形態に係る問題求解装置の構成について説明する。図１に示すように、本実施形態に係る問題求解装置１００は、ＣＰＵと、ＲＡＭと、後述する各種処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この問題求解装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部９０とを含んで構成されている。
【００２２】
入力部１０は、ナップサック問題のインスタンスを受け付ける。ここで、ナップサック問題のインスタンスとは、Ｎ個のアイテムｉの各々についてのコストｃｉとスコアｗｉとの組、及び合計コストの上限値Ｌからなる。
【００２３】
また、入力部１０は、ナップサック問題の各アイテムｉが入力変数に対応するような制約を表す論理関数ｆ（ｘ１，．．．，ｘＮ）を表現したＢＤＤを受け付ける。ここで、ＢＤＤは論理関数を有向非巡回グラフとして表現する二分決定グラフのデータ構造であり、例えば図２（ａ）に示す論理関数は、図２（ｂ）のようなＢＤＤとして表現される。図２（ｂ）中の丸いノードは分岐ノードとよばれ、ラベルが与えられ、実線、又は破線で指された二種類の子ノードを持つ。また、ｘ１がアイテム１に対応し、ｘ２がアイテム２に対応するということになる。
【００２４】
分岐ノードのラベルは、論理関数のいずれかの入力変数に対応する。実線で指された子ノードは１−子ノードと呼び、破線で指された子ノードは０−子ノードとよぶ。図２（ｂ）中の四角いノードは終端ノードとよばれ、１−終端ノード（図２（ｂ）中Τ）と、０−終端ノード(図２（ｂ）中⊥)の二種類の終端ノードが存在する。なお、計算機中では図２（ｃ）のように、ＢＤＤの各ノードについて、ラベル、０−子ノードのアドレス、及び１−子ノードのアドレスを格納したテーブルによって表現される。また、図２（ｂ）中のＴを真の結果とし、図２（ｂ）中の⊥を偽の結果とする。
【００２５】
演算部２０は、グラフ変換処理部２２と、ヒューリスティック関数計算部２４と、最適解計算部２６とを含んで構成されている。
【００２６】
グラフ変換処理部２２は、入力部１０において受け付けたナップサック問題のインスタンスに基づいて、当該ナップサック問題を、有向非巡回グラフ上での最長経路探索問題へと変換する。具体的には、入力部１０において受け付けたナップサック問題のインスタンスが、図３（ａ）に示すような場合、図３（ｂ）に示すような、辺にスコアを付加した有向非巡回グラフ（Directed acyclic graph:以後、ＤＡＧとする。）に変換する。
【００２７】
ヒューリスティック関数計算部２４は、グラフ変換処理部２２において取得したＤＡＧに基づいて、当該ＤＡＧに含まれるノードｎの各々について、実数を返すようなヒューリスティック関数ｈ（ｎ）の値を計算する。ここで、関数ｈ（ｎ）は、ノードｎからゴールである終端ノードｔまで遷移する場合の、遷移する辺に付加されたスコアの総和が最大となる最大経路スコアの見積もりを与えるものである。
【００２８】
最適解計算部２６は、グラフ変換処理部２２において取得したＤＡＧと、ヒューリスティック関数計算部２４において取得したＤＡＧに含まれるノードｎの各々のヒューリスティック関数ｈ（ｎ）の値と、入力部１０において受け付けたＢＤＤと、メモリ（図示省略）に記憶されている空の優先度つきキューＱ、テーブルＡ、及びテーブルＢとに基づいて、当該ＢＤＤにより制約が追加された、当該ＤＡＧが表すナップサック問題の最適解を計算し、出力部９０から出力する。
【００２９】
ここで、優先度つきキューＱは、ＤＡＧに含まれるノードｎとＢＤＤに含まれるノードｍとのペア（ｎ，ｍ）を受け取り、評価関数ｆ（ｎ，ｍ）の値が大きなペア（ｎ，ｍ）から順に出力することができるものである。また、優先度つきキューＱは、格納されているペア（ｎ，ｍ）に紐づく評価関数ｆ（ｎ，ｍ）の値を更新できるものとする。
【００３０】
また、テーブルＡは、ＤＡＧに含まれるノードｎとＢＤＤに含まれるノードｍとのペア（ｎ，ｍ）を受け取り、評価関数ｆ（ｎ，ｍ）の値を返すテーブルである。また、テーブルＢは、ノードの遷移に関する情報を格納するテーブルである。
【００３１】
＜本発明の実施形態に係る問題求解装置の作用＞
次に、本発明の実施形態に係る問題求解装置１００の作用について説明する。問題求解装置１００は、入力部１０によって、ナップサック問題のインスタンスと、ＢＤＤとを受け付けると、問題求解装置１００によって、図４に示す問題求解処理ルーチンが実行される。
【００３２】
まず、図４に示す問題求解処理のステップＳ１０で、入力部１０において受け付けたナップサック問題のインスタンスに基づいて、当該ナップサック問題に対応する辺スコア付き有向巡回グラフに変換する。当該ステップＳ１０のＤＡＧ変換処理ルーチンを図５において詳述する。
【００３３】
図５のＤＡＧ変換処理におけるステップＳ１１０では、入力部１０において受け付けたナップサック問題のインスタンスに含まれる各アイテム番号ｉ＝１，．．．，Ｎの各々と、合計コストの上限値Ｌまでの各非負の整数ｊ＝０，．．．，Ｌの各々との全てのペアに対応したノード（ｉ，ｊ）を作成し、グラフを作成する。
【００３４】
次に、ステップＳ１２０で、ステップＳ１１０において取得したグラフの始点に対応するノードｓと、当該グラフの終点に対応するノードｔとを作成し、当該グラフに追加する。
【００３５】
次に、ステップＳ１３０で、ステップＳ１２０において取得したグラフのノードｓからノード（１，ｃ１）へと結ぶ辺を追加し、当該辺のスコアをｗ１に設定する。また、当該辺にラベルｚ１を対応づける。
【００３６】
次に、ステップＳ１４０で、ステップＳ１３０において取得したグラフのノードｓからノード（１，０）へと結ぶ辺を追加し、当該辺のスコアを０に設定する。また、当該辺にラベルｌ１を対応づける。
【００３７】
次に、ステップＳ１５０で、ステップＳ１４０において取得したグラフの各ｊに対応するノード（Ｎ，ｊ）の各々について、当該ノード（Ｎ，ｊ）からノードｔへと結ぶ辺を追加し、当該辺のスコアを０に設定する。
【００３８】
次に、ステップＳ１６０で、ステップＳ１５０において取得したグラフの条件「
【００３９】
【数２】
0006497705.tif 000003
【００４０】
、かつ
【００４１】
【数３】
0006497705.tif 000004
【００４２】
」を満たすノード（ｉ，ｊ）の各々について、ノード（ｉ−１，ｊ−ｃｉ）からノード（ｉ，ｊ）へと結ぶ辺を追加し、当該辺のスコアをｗｉに設定し、当該辺にラベルｚｉを対応づける。
【００４３】
次に、ステップＳ１７０で、ステップＳ１６０において取得したグラフの条件「
【００４４】
【数４】
0006497705.tif 000005
【００４５】
」を満たすノード（ｉ，ｊ）の各々について、ノード（ｉ−１，ｊ）からノード（ｉ，ｊ）へと結ぶ辺を追加し、当該辺のスコアを０に設定し、当該辺にラベルｌｉを対応づける。
【００４６】
次に、ステップＳ１８０で、ステップＳ１７０において取得したグラフのノードｓから到達可能なノードの集合から導出される誘導グラフを作成する。ここで、誘導グラフとは、ノードｓを始点とするノードの全てを含んだグラフのことをいう。
【００４７】
次に、ステップＳ１８５で、ステップＳ１８０において取得した誘導グラフにノードｔを含むか否かを判定する。誘導グラフにノードｔを含む場合には、ＤＡＧ変換処理は、ステップＳ１９０へ移行する。一方、誘導グラフにノードｔを含まない場合には、ＤＡＧ変換処理は、図４に示す問題求解処理へ移行し、問題求解処理ルーチンを終了する。
【００４８】
次に、ステップＳ１９０で、ステップＳ１８０において取得した誘導グラフを出力して、ＤＡＧ変換処理ルーチンを終了する。
【００４９】
図４に示す問題求解処理のステップＳ２０で、ステップＳ１０において取得したＤＡＧに基づいて、動的計画法に従って、当該ＤＡＧの各ノードｎに対して、当該ノードｎから終端ノードｔまでの、辺スコアの和（経路長）が最大となるような経路の最大経路スコアを計算し、ヒューリスティック関数ｈ（ｎ）の値として取得する。なお、ノードｎがノードｔと一致する場合には、経路のスコアは０である。また、動的計画法を用いることにより、有向非巡回グラフの全ノードに対して最大経路スコアの計算を効率的に計算できる。
【００５０】
次に、ステップＳ３０で、入力部１０において受け付けたＢＤＤと、ステップＳ１０において取得したＤＡＧと、ステップＳ２０において取得したヒューリスティック関数ｈ（ｎ）とに基づいて、当該ＢＤＤの制約を満たす０−１ナップサック問題の解を計算する。当該ステップＳ３０のナップサック問題計算処理を図６において詳述する。
【００５１】
図６に示すナップサック問題計算処理ルーチンのステップ２１０で、メモリ（図示省略）から、空の優先度つきキューＱ、テーブルＡ、及びテーブルＢを読み込む。
【００５２】
次に、ステップＳ２１２で、ステップＳ２１０において取得したテーブルＡを、ＤＡＧに含まれるノードｎとＢＤＤに含まれるノードｍとの全てのペアに対して、十分に小さな値を返すように、各ペアの評価関数ｆ（ｎ，ｍ）の値を初期化する。
【００５３】
次に、ステップＳ２１４で、ステップＳ２１０において取得した優先度つきキューＱに、ステップＳ１０において取得したＤＡＧの始点ノードｓと入力部１０において受け付けたＢＤＤのルートノード（以後、ノードｒооｔとする）とのペアについて、当該ペアと、ステップＳ２０において取得した当該ペアのヒューリスティック関数ｈ（ｓ）の値とを格納する。ここで、ヒューリスティック関数ｈ（ｓ）の値とは、始点ノードｓにおける最大経路スコアの見積もりの値である。
【００５４】
次に、ステップＳ２１６で、ステップＳ２０において取得したノードｓとノードｒооｔとのペアについての評価関数ｆ（ｓ，ｒооｔ）の値を、ステップＳ１０において取得したＤＡＧと、ステップＳ２０において取得した当該ペアのヒューリスティック関数ｈ（ｓ）とに基づいて、下記（１）式に従って、計算し、当該計算した結果で、テーブルＡを更新する。
【００５５】
【数５】
0006497705.tif 000006
【００５６】
ここで、ｇ（ｎ，ｍ）は、状態（ｓ，ｒооｔ）から（ｎ，ｍ）に到達するまでのスコア最大の経路の合計スコアであり、ｇ（ｓ，ｒｏоｔ）＝０である。
【００５７】
次に、ステップＳ２１８で、テーブルＡと、優先度つきキューＱとに基づいて、優先度つきキューＱから評価関数ｆ（ｎ，ｍ）の値を最大とするペア（ｎ，ｍ）を１つ抽出する。
【００５８】
次に、ステップＳ２２０で、ステップＳ２１８において抽出したペア（ｎ，ｍ）について、ｎ＝終点に対応するノードｔかつ、ｍ＝終端ノードＴである場合には、ナップサック問題計算処理はステップＳ２４６へ移行する。一方、ペア（ｎ，ｍ）について、ｎ＝ノードｔ以外であり、又はｍ＝終端ノードＴ以外である場合には、ナップサック問題計算処理はステップＳ２２２へ移行する。
【００５９】
次に、ステップＳ２２２では、ステップＳ１０において取得したＤＡＧにおいてステップＳ２１８において取得したペア（ｎ，ｍ）のノードｎを特定し、ノードｎを始点とする辺ｅの各々のうち、処理対象となる辺ｅを決定する。
【００６０】
次に、ステップＳ２２４で、処理対象となる辺ｅについて、入力部１０において取得したＢＤＤと、ステップＳ１０において取得したＤＡＧとに基づいて、ＢＤＤ上のノードｍから遷移可能なノードｍ’を求める。ここで、ｍ’は、下記（２）式に従って求められる。
【００６１】
【数６】
0006497705.tif 000007
【００６２】
ここで、ｖは辺ｅのラベルを表す。そのため、ｖはｚｉ、又はｌｉの何れかとなる。ｆоｌｌｗＢＤＤ（ｖ，ｍ）は、ＢＤＤの変数ｍとＤＡＧにおける処理対処となる辺ｅのラベルｖを受け取り、ｍから変数順序がｘｉと等しいかそれ以上であるノードに辿り着くまで、ｍから「０−子」ノードに順に遷移する。なお、ノードｍ自体が、ｘｉと等しいかそれ以上である場合には、ノードは遷移しない。
【００６３】
そして、ＢＤＤ上の辿りついた変数順序がｘｉと等しいかそれ以上であるノードのラベルがｘｉであり、かつｖ＝ｚｉで有る場合には、当該ノードの「１−子」に対応するノードをｍ’のノードとして抽出し、当該ノードのラベルがｘｉであり、かつｖ＝ｌｉで有る場合には、当該ノードの「０−子」に対応するノードをｍ’のノードとして抽出する。一方、ＢＤＤ上の辿りついた変数順序がｘｉでない場合には、当該ノードをｍ’のノードとして抽出する。
【００６４】
次に、ステップＳ２２６で、処理対象の辺ｅの終点のノードｎ’と、ステップＳ２１８において取得したノードのペア（ｎ，ｍ）の評価関数ｆ（ｎ，ｍ）の値と、ステップＳ２０において取得したヒューリスティック関数ｈ（ｎ）の値と、ステップＳ２０において取得したノードｎ’のヒューリスティック関数ｈ（ｎ’）の値と、ステップＳ１０において取得したＤＡＧから求まる処理対処となる辺ｅのスコアｗ（ｅ）とに基づいて、ｆ（ｎ’，ｍ’）を下記（３）式に従って計算する。なお、ｇ（ｎ，ｍ）は、ｆ（ｎ，ｍ）からｈ（ｎ）の値を引いたものである。
【００６５】
【数７】
0006497705.tif 000008
【００６６】
次に、ステップＳ２２８で、ステップＳ２２６において取得した評価関数ｆ（ｎ’，ｍ’）の値が、テーブルＡに格納されているＡ（ｎ’，ｍ’）の値よりも大きいか否かを判定する。評価関数ｆ（ｎ’，ｍ’）の値が、テーブルＡに格納されているＡ（ｎ’，ｍ’）の値よりも大きい場合には、ナップサック問題計算処理は、ステップＳ２３０へ移行する。一方、評価関数ｆ（ｎ’，ｍ’）の値が、テーブルＡに格納されているＡ（ｎ’，ｍ’）の値以下である場合には、ナップサック問題計算処理は、ステップＳ２４０へ移行する。
【００６７】
次に、ステップＳ２３０で、ステップＳ２２６において取得した評価関数ｆ（ｎ’，ｍ’）の値で、テーブルＡに格納されているＡ（ｎ’，ｍ’）の値を更新する。
【００６８】
次に、ステップＳ２３２で、ステップＳ２１８において取得したペア（ｎ，ｍ）と、ステップＳ２２４、及びステップＳ２２６において取得したノードｍ’、及びノードｎ’とに基づいて、テーブルＢに、Ｂ（ｎ’，ｍ’）＝（ｎ，ｍ）を格納する。
【００６９】
次に、ステップＳ２３４で、優先度つきキューＱにステップＳ２２４、及びステップＳ２２６において取得したノードｍ’、及びノードｎ’の組み合わせの（（ｎ’，ｍ’），ｆ（ｎ’，ｍ’））が含まれているか否かを判定する。（（ｎ’，ｍ’），ｆ（ｎ’，ｍ’））が含まれている場合には、ナップサック問題計算処理は、ステップＳ２３８へ移行する。（（ｎ’，ｍ’），ｆ（ｎ’，ｍ’））が含まれていない場合には、ナップサック問題計算処理は、ステップ２３６へ移行する。
【００７０】
ステップＳ２３６で、優先度つきキューＱに、ステップＳ２２４、及びステップＳ２２６において取得したノードｍ’、及びノードｎ’と、ステップＳ２２６において取得した評価関数ｆ（ｎ’，ｍ’）の値とに基づいて、（（ｎ’，ｍ’），ｆ（ｎ’，ｍ’））を格納する。
【００７１】
ステップＳ２３８で、優先度つきキューＱに格納されている（（ｎ’，ｍ’），ｆ（ｎ’，ｍ’））について、評価関数ｆ（ｎ’，ｍ’）の値を、ステップＳ２２６において取得した評価関数ｆ（ｎ’，ｍ’）の値に更新する。
【００７２】
次に、ステップＳ２４０で、ステップＳ２２２において特定したノードｎを始点とする辺ｅの全てについて、ステップＳ２２４〜ステップＳ２３６、又はステップＳ２３８についての処理を終了したか否かを判定する。当該ノードｎを始点とする全ての辺ｅについて、ステップＳ２２４〜ステップＳ２３６、又はステップＳ２３８についての処理を終了している場合には、ナップサック問題計算処理は、ステップ２４２へ移行する。一方、当該ノードｎを始点とする全ての辺ｅについて、ステップＳ２２４〜ステップＳ２３６、又はステップＳ２３８までの処理を終了した場合には、ナップサック問題計算処理は、ステップ２２２へ移行し、処理対象となる辺ｅを変更し、ステップＳ２２４〜ステップＳ２４０までの処理を繰り返す。
【００７３】
次に、ステップＳ２４２で、優先度つきキューＱが空であるか否かを判定する。優先度つきキューＱが空である場合には、最適解なしとして、ナップサック問題計算処理ルーチンを終了し、問題求解処理ルーチンを終了する。一方、優先度つきキューＱが空でない場合には、ナップサック問題計算処理ルーチンは、ステップＳ２１８へ移行し、ステップＳ２１８からの処理を繰り返す。
【００７４】
ステップＳ２４６で、テーブルＢに基づいて、バックトラッキング処理を行う。具体的には、テーブルＢを用いて（ｎ，ｍ）←Ｂ（ｎ，ｍ）を、（ｎ，ｍ）＝（ｓ，ｒооｔ）となるまで繰り返し計算し、出現した（ｎ，ｍ）の全てを記録することで、ノードｓからノードｔまでの制約を満たす最大経路スコアの経路を取得する。なお、ここで得られた最大経路スコアの経路が当該ナップサック問題の最適解となる。また、最適解を取得したらナップサック問題計算処理ルーチンを終了する。
【００７５】
図４に示す問題計算処理ルーチンのステップＳ４０では、ステップＳ３０において取得した最適解を出力部９０から出力して、問題求解処理ルーチンを終了する。
【００７６】
以上説明したように、本実施形態に係る問題求解装置によれば、スコアとコストとを持つ複数のアイテムから、合計コストの上限値Ｌ以下でスコアを最大化するアイテムの組み合わせを選択するナップサック問題を、各ノードがアイテムを表し、かつ、各辺にスコアを付加した辺スコア付き有向非巡回グラフであるＤＡＧに変換し、ＤＡＧのノードの各々に対して、最大経路スコアを計算し、入力された、ＢＤＤと、ＤＡＧと、計算されたＤＡＧの各ノードの最大経路スコアとに基づいて、制約を満たすナップサック問題の解を計算することにより、制約が付加された０−１ナップサック問題の解を高速に求めることができる。
【００７７】
また、０−１ナップサック問題に制約が追加された問題を、グラフの最長経路長を用いたヒューリスティック関数を用いて探索順序を工夫することによって、高速に制約が追加された０−１ナップサック問題の解を求めることができる。
【００７８】
また、制約がない状態で、０−１ナップサック問題を解いた結果を、探索順序を決めるためのヒントとして用いることで、最適解が見つかるまでの探索ステップ数を減らして、高速な解の発見を実現することができる。
【００７９】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００８０】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【００８１】
１０   入力部
２０   演算部
２２   グラフ変換処理部
２４   ヒューリスティック関数計算部
２６   最適解計算部
９０   出力部
１００ 問題求解装置
【図１】
0006497705.tif 000009
【図２】
0006497705.tif 000010
【図３】
0006497705.tif 000011
【図４】
0006497705.tif 000012
【図５】
0006497705.tif 000013
【図６】
0006497705.tif 000014