(57)【要約】【課題】木制約付きナップサック問題を高速に解くことができるようにする。【解決手段】ｎ番目のノードについて、各容量ｃに対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和がｃと等しくなる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、根付き部分木の価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の根付き部分木について、価値の和の最大値を計算して記憶部３１に記憶し、記憶した各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、容量の和がｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、当該ｎ−１番目のノードを含まない根付き部分木とのうち、部分木の価値の和が最大となる根付き部分木を再帰的に計算する。【選択図】図１
2016024522.tif 000002
【特許請求の範囲】
【請求項１】
価値と容量を持つノードの各々から構成される木構造から、容量制限Ｃ以下で価値を最大化する根付き部分木を選択する木制約付きナップサック問題を解決する問題解決装置であって、
前記木構造を構成する各ノードを、前記木構造の根からの深さ優先の順序で並べ替えるソート部と、
前記ソート部により並べ替えられた各ノードの順序に従って、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の前記根付き部分木について、各ノードの価値の和の最大値を計算して記憶部に記憶する最適値計算部と、
前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記容量制限Ｃ以下となる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を出力するバックトラック部とを含み、
前記最適値計算部は、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を計算するとき、各成長段階の前記根付き部分木について前記記憶部に記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる前記ｎ−１番目のノードを含まない根付き部分木とのうち、前記部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算する
問題解決装置。
【請求項２】
前記最適値計算部は、以下の（１）式を用いて、前記記憶部に記憶された、前記ｎ番目のノード及び前記容量ｃの組み合わせの各々に対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を格納する配列を初期化し、
前記ｎ番目のノード及び前記容量ｃの組み合わせの各々について、以下の（２）式を用いて、前記組み合わせに対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、前記記憶部に記憶された前記配列に格納する請求項１記載の問題解決装置。
【数１】
2016024522.tif 000010
ただし、Ａ［ｎ］は、ｎ番目のノードを表し、関数ｃａｐ（Ａ［ｎ］）は、ｎ番目のノードの容量を表し、ｐ（Ａ［ｎ］）は、ｎ番目のノードの価値を表し、関数ｎｅｘｔ＿ｕｎｄｅｓｃ（ｈ）は、ｈ＋１番目以降のノードのうち、ｈ番目のノードの子孫でない最初のノードのインデックスを返す関数を表す。
【請求項３】
価値と容量を持つノードの各々から構成される木構造から、容量制限Ｃ以下で価値を最大化する根付き部分木を選択する木制約付きナップサック問題を解決する問題解決装置における問題解決方法であって、
ソート部が、前記木構造を構成する各ノードを、前記木構造の根からの深さ優先の順序で並べ替えるステップと、
最適値計算部が、前記ソート部により並べ替えられた各ノードの順序に従って、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の前記根付き部分木について、各ノードの価値の和の最大値を計算して記憶部に記憶するステップと、
バックトラック部が、前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記容量制限Ｃ以下となる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を出力するステップとを含み、
前記最適値計算部によって計算するステップは、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を計算するとき、各成長段階の前記根付き部分木について前記記憶部に記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる前記ｎ−１番目のノードを含まない根付き部分木とのうち、前記部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算する
問題解決方法。
【請求項４】
前記最適値計算部によって計算するステップは、以下の（４）式を用いて、前記記憶部に記憶された、前記ｎ番目のノード及び前記容量ｃの組み合わせの各々に対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を格納する配列を初期化し、
前記ｎ番目のノード及び前記容量ｃの組み合わせの各々について、以下の（５）式を用いて、前記組み合わせに対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、前記記憶部に記憶された前記配列に格納する請求項３記載の問題解決方法。
【数２】
2016024522.tif 000011
ただし、Ａ［ｎ］は、ｎ番目のノードを表し、関数ｃａｐ（Ａ［ｎ］）は、ｎ番目のノードの容量を表し、ｐ（Ａ［ｎ］）は、ｎ番目のノードの価値を表し、関数ｎｅｘｔ＿ｕｎｄｅｓｃ（ｈ）は、ｈ＋１番目以降のノードのうち、ｈ番目のノードの子孫でない最初のノードのインデックスを返す関数を表す。
【請求項５】
コンピュータを、請求項１又は２に記載の問題解決装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、問題解決装置、方法、及びプログラムに係り、特に、木制約付きナップサック問題を解決する問題解決装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来より、容量Ｃのナップサック、及び個々のノードがアイテムに対応するノード数Ｎの木が与えられ、アイテムの容量、価値がそれぞれｃｉ，ｐｉである時、ナップサックの容量Ｃを超えない範囲で価値を最大化する根付き部分木を選択する問題が知られている。この問題は木制約付きナップサック問題(Ｔｒｅｅ Ｋｎａｐｓａｃｋ Ｐｒｏｂｌｅｍ）と呼ばれ、ＬＡＴＮ（Ｌｏｃａｌ Ａｃｃｅｓｓ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｎｅｔｗｏｒｋ）、文書要約、文圧縮などの応用技術に利用される。
【０００３】
木制約付きナップサック問題は以下の整数計画問題として定式化される。
【０００４】
【数１】
2016024522.tif 000003
【０００５】
ｘｉ＝１の場合、ｉ番目のアイテムが根付き部分木のノードとして選択されることを示す。（１）式は、価値を最大化するための目的関数であり、（２）式、及び（３）式が制約である。（２）式は選択された根付き部分木に含まれるアイテムの容量の和がナップサックの容量Ｃを超えないことを保証する。（３）式は選択されたアイテムが根付き部分木であることを保証する。なお、ｐａｒｅｎｔ（ｉ）とはｉ番目のノードの親のアイテムＩＤである。最適解は、分枝限定法(汎用ＩＬＰソルバを利用)、動的計画法を用いて得ることができる（非特許文献１、２）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Lukes, J. A.“Efficient algorithm for the partitioning of trees.” IBM Journal of Research and Development, 18(3), 217-224.(1974)
【非特許文献２】Morita, H., Sasano, R., Takamura, H. and Okumura, M. “Subtree Extractive Summarization via SubmodularMaximization.” Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, 1023-1032.(2013)
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１、２に記載の分枝限定法は探索木を枝狩りしつつ解を列挙する手法であるため、ナップサックの容量Ｃ、木のノード数（アイテム数）Ｎによっては効率的に解を得ることができない。さらに、用いるＩＬＰソルバプログラムによって処理速度が大きく異なるという問題がある。また、これまでに提案された動的計画法は計算量がＯ（ＮＣ２） であるため、Ｃの値によっては計算効率が悪いという問題もある。
【０００８】
本発明は、上記問題点を解決するために成されたものであり、木制約付きナップサック問題を高速に解くことができる問題解決装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、第１の発明に係る問題解決装置は、価値と容量を持つノードの各々から構成される木構造から、容量制限Ｃ以下で価値を最大化する根付き部分木を選択する木制約付きナップサック問題を解決する問題解決装置であって、前記木構造を構成する各ノードを、前記木構造の根からの深さ優先の順序で並べ替えるソート部と、前記ソート部により並べ替えられた各ノードの順序に従って、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の前記根付き部分木について、各ノードの価値の和の最大値を計算して記憶部に記憶する最適値計算部と、を含んで構成されており、前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記容量制限Ｃ以下となる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を出力するバックトラック部とを含み、前記最適値計算部は、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を計算するとき、各成長段階の前記根付き部分木について前記記憶部に記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる前記ｎ−１番目のノードを含まない根付き部分木とのうち、前記部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算する。
【００１０】
また、第１の発明に係る問題解決装置において、前記最適値計算部は、以下の（５）式を用いて、前記記憶部に記憶された、前記ｎ番目のノード及び前記容量ｃの組み合わせの各々に対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を格納する配列を初期化し、前記ｎ番目のノード及び前記容量ｃの組み合わせの各々について、以下の（６）式を用いて、前記組み合わせに対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、前記記憶部に記憶された前記配列に格納してもよい。
【００１１】
【数２】
2016024522.tif 000004
【００１２】
ただし、Ａ［ｎ］は、ｎ番目のノードを表し、関数ｃａｐ（Ａ［ｎ］）は、ｎ番目のノードの容量を表し、ｐ（Ａ［ｎ］）は、ｎ番目のノードの価値を表し、関数ｎｅｘｔ＿ｕｎｄｅｓｃ（ｈ）は、ｈ＋１番目以降のノードのうち、ｈ番目のノードの子孫でない最初のノードのインデックスを返す関数を表す。
【００１３】
第１の発明に係る問題解決方法は、価値と容量を持つノードの各々から構成される木構造から、容量制限Ｃ以下で価値を最大化する根付き部分木を選択する木制約付きナップサック問題を解決する問題解決装置における問題解決方法であって、ソート部が、前記木構造を構成する各ノードを、前記木構造の根からの深さ優先の順序で並べ替えるステップと、最適値計算部が、前記ソート部により並べ替えられた各ノードの順序に従って、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の前記根付き部分木について、各ノードの価値の和の最大値を計算して記憶部に記憶するステップと、バックトラック部が、前記最適値計算部によって繰り返し計算された計算過程に基づいて、前記容量制限Ｃ以下となる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を出力するステップとを含んで実行することを特徴としており、前記最適値計算部によって計算するステップは、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、前記根付き部分木の各ノードの価値の和が最大となる根付き部分木を計算するとき、各成長段階の前記根付き部分木について前記記憶部に記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる前記ｎ−１番目のノードを含まない根付き部分木とのうち、前記部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算する。
【００１４】
また、第１の発明に係る問題解決方法において、前記最適値計算部によって計算するステップは、以下の（８）式を用いて、前記記憶部に記憶された、前記ｎ番目のノード及び前記容量ｃの組み合わせの各々に対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を格納する配列を初期化し、前記ｎ番目のノード及び前記容量ｃの組み合わせの各々について、以下の（９）式を用いて、前記組み合わせに対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、前記記憶部に記憶された前記配列に格納してもよい。
【００１５】
【数３】
2016024522.tif 000005
【００１６】
ただし、Ａ［ｎ］は、ｎ番目のノードを表し、関数ｃａｐ（Ａ［ｎ］）は、ｎ番目のノードの容量を表し、ｐ（Ａ［ｎ］）は、ｎ番目のノードの価値を表し、関数ｎｅｘｔ＿ｕｎｄｅｓｃ（ｈ）は、ｈ＋１番目以降のノードのうち、ｈ番目のノードの子孫でない最初のノードのインデックスを返す関数を表す。
【００１７】
また、第１の本発明に係るプログラムは、コンピュータを、上記の第１の発明に係る問題解決装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
本発明の問題解決装置、方法、及びプログラムによれば、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の根付き部分木について、各ノードの価値の和の最大値を計算して記憶部に記憶し、各成長段階の根付き部分木について記憶部に記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含まない根付き部分木とのうち、部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算することで、木制約付きナップサック問題を高速に解くことができる、という効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態に係る問題解決装置の構成を示すブロック図である。
【図２】価値と容量を持つノードの各々から構成される木構造の概念図である。
【図３】二次元配列Ｓ、Ｂに格納する各要素を決定するアルゴリズムを示す図である。
【図４】二次元配列Ｓの各要素の例を示す概念図である。
【図５】二次元配列Ｂの各要素の例を示す概念図である。
【図６】バックトラックのアルゴリズムを示す図である。
【図７】本発明の実施の形態に係る問題解決装置における問題解決処理ルーチンを示すフローチャートである。
【図８】本発明の実施の形態に係る問題解決装置における最大価値計算処理ルーチンを示すフローチャートである。
【図９】本発明の実施の形態に係る問題解決装置における兄弟要素決定処理ルーチンを示すフローチャートである。
【図１０】本発明の実施の形態に係る問題解決装置におけるバックトラック処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
＜本発明の実施の形態に係る問題解決装置の構成＞
【００２２】
本発明の実施の形態に係る問題解決装置の構成について説明する。図１に示すように、本発明の実施の形態に係る問題解決装置１００は、ＣＰＵと、ＲＡＭと、後述する問題解決処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この問題解決装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００２３】
入力部１０は、アイテムをノードとした、価値と容量を持つノードの各々から構成される木構造と、容量制限Ｃとを入力として受け付ける。
【００２４】
演算部２０は、ソート部３０と、記憶部３１と、最適値計算部３２と、バックトラック部３４とを含んで構成されている。
【００２５】
ソート部３０は、入力部１０で受け付けた木構造を構成する各ノードを、木構造の根からの深さ優先の順序で並べ替える。例えば、図２に示す木構造を構成する各ノードをソート部が受け取るとノードをプレオーダでソートし、ソートされた配列Ａ＝（ｖ９，ｖ１，ｖ２，ｖ５，ｖ３，ｖ４，ｖ６，ｖ７，ｖ８）を最適値計算部３２へ渡す。また、図２の各ノードの左上に付された数値が、各ノードのインデックスを示す。
【００２６】
記憶部３１には、（Ｎ＋１）×（Ｃ＋１）の二次元配列であって、根付き部分木に含まれる各ノードの価値の和の最大値を各要素に格納する二次元配列Ｓ、並びに、根付き部分木を得るための情報として各ノードのインデックス及びタイプを各要素に格納する二次元配列Ｂが記憶されている。
【００２７】
最適値計算部３２は、ソート部３０により並べ替えられた各ノードの順序に従って、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の根付き部分木について、各ノードの価値の和の最大値を計算して記憶部３１の配列Ｓに記憶する。また、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を計算するとき、各成長段階の根付き部分木について記憶部３１の配列Ｓに記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含まない根付き部分木とのうち、部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算する。
【００２８】
具体的には、最適値計算部３２は、まず、以下の（１１）式を用いて、記憶部３１に記憶された、ｎ番目のノード及び容量ｃの組み合わせの各々に対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を格納する配列Ｓを初期化する。ただし、１≦ｎ≦Ｎ＋１、０≦ｃ≦Ｃである。なお、容量制限Ｃ及び容量ｃは共に整数である。二次元配列Ｓの要素Ｓ［ｎ］［ｃ］には、配列Ａのｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量がｃと等しくなるｎ−１番目のノードを含む根付き部分木と、当該ｎ−１番目のノードを含まない根付き部分木とのうち、部分木の各ノードの価値の和が最大となる根付き部分木の最大値が格納される。
【００２９】
【数４】
2016024522.tif 000006
【００３０】
次に、最適値計算部３２は、以下の（１２）式の再帰式を用いて、ｎ番目のノード及び容量ｃの組み合わせの各々について、当該組み合わせに対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、記憶部３１に記憶された配列に格納していく。（１２）式では、上記Ｓ［ｎ］［ｃ］に格納される根付き部分木の最大値について、（ａ）ｎ−１番目のノードを含む根付き部分木、又は（ｂ）ｎ−１番目のノードを含まない根付き部分木の中から選択している。（１２）式の１行目がｎ−１番目のノードを含む根付き部分木の各ノードの価値の和のスコアに、２、３行目がｎ−１番目のノードを含まない根付き部分木の各ノードの価値の和のスコアに対応している。
【００３１】
【数５】
2016024522.tif 000007
【００３２】
ここで、Ａ［ｎ］は、ｎ番目のノードを表し、関数ｃａｐ（Ａ［ｎ］）は、ｎ番目のノードの容量を表し、ｐ（Ａ［ｎ］）は、ｎ番目のノードの価値を表している。
【００３３】
また、関数ｐｒｅｖ（ｎ）は関数ｎｅｘｔ＿ｕｎｄｅｓｃ（）の値がｎとなる配列Ａのインデックスを返す関数であり、以下（１３）式で定義する。
【００３４】
【数６】
2016024522.tif 000008
【００３５】
関数ｎｅｘｔ＿ｕｎｄｅｓｃ（ｈ）は、ｈ＋１番目以降のノードのうち、ｈ番目のノードの子孫でない最初のノードのインデックスを返す関数を表す。例えば、配列Ａの部分配列Ａ[ｈ＋１，．．．，Ｎ］からＡ［ｈ］の子孫ではない最初のノードのインデックスを返す。仮に、部分配列Ａ［ｈ＋１，．．．，Ｎ］にＡ［ｈ］の子孫でないノードが存在しなかった場合は、ｎｅｘｔ＿ｕｎｄｅｓｃ（ｈ）＝Ｎ＋１とする。例えば、配列Ａにおいて、ｈ＝２とすると、Ａ［２］＝ｖ１であるから、その子孫はｖ２，ｖ３，ｖ４，ｖ５となる。そこでＡ［３，．．．，９］からこれらの子孫を削除すると（ｖ６，ｖ７，ｖ８）が得られる。よって、ｎｅｘｔ＿ｕｎｄｅｓｃ（２）は、ｖ６の配列Ａにおけるインデックスである７を返す。同様にｎｅｘｔ＿ｕｎｄｅｓｃ（４）、ｎｅｘｔ＿ｕｎｄｅｓｃ（６）も７であることから、ｐｒｅｖ（７）の場合、ｈ番目のノードは｛２，４，６｝となる。
【００３６】
ここで、根付き部分木に含まれる各ノードの価値の和の最大値を格納する二次元配列Ｓ、及び根付き部分木を得るための情報を格納する二次元配列Ｂに対する各要素を効率的に決定するためのアルゴリズムを、図３のＡｌｇｏｒｉｔｈｍ１に示す。
【００３７】
Ａｌｇｏｒｉｔｈｍ１では、まず、アルゴリズムの１行目で木構造を構成する各ノードをプレオーダでソートし、配列Ａに格納する。そして、３から３５行目で、（Ｎ＋１）×（Ｃ＋１）の二次元配列Ｓ、及びＢの各要素を決定する。
【００３８】
具体的には、二次元配列Ｓ、及びＢの初期化を行う（図３の３から８行目）。そして、スタックｓｉｂｌｉｎｇｓに値Ｎ＋１を積み（９行目）、Ｓ［１］［０］の要素を０とする（１０行目）。
【００３９】
次に、ｎ（２≦ｎ≦Ｎ＋１）について、１１行目からの繰り返し処理によって、０≦ｃ≦Ｃに対し、二次元配列Ｓ、及びＢの各要素の値を決定する。
【００４０】
そして、ｃ−ｃａｐ（Ａ［ｎ−１］）の容量がゼロ以上、かつＳ［ｎ−１］［ｃ−ｃａｐ（Ａ［ｎ−１］）］の価値のスコアがゼロ以上の場合、Ｓ［ｎ］［ｃ］よりもＳ［ｎ］［ｃ−ｃａｐ（Ａ［ｎ−１］）］＋ｐ（Ａ［ｎ−１］）が大きいならばＳ［ｎ］［ｃ］にＳ［ｎ−１］［ｃ−ｃａｐ（Ａ［ｎ−１］）］＋ｐ（Ａ［ｎ−１］）の価値のスコアを代入する（１３から１８行目）。そして、Ｂ［ｎ］［ｃ］にインデックスとタイプを表すタプル（ｎ−１，ＤＩＡＧＯＮＡＬ）を格納する。タイプがＤＩＡＧＯＮＡＬの場合、プレオーダインデックスが１からｎ−１番目までのノードを使って構成される、容量の和がｃである、各ノードの価値の和を最大化する根付き部分木に、プレオーダインデックスｎ−１番目のノードが利用されたことを示す。
【００４１】
次に、スタックｓｉｂｌｉｎｇｓの一番上の値がｎ−１であるならば、それを取り除く（２０から２１行目）。そして、ノードＡ［ｎ−１］の右側に存在する兄弟のうち最左の兄弟のプレオーダインデックスをｋとする。ノードＡ［ｎ−１］の右側に兄弟がいない場合は、スタックｓｉｂｌｉｎｇｓの一番上に積まれたインデックスをｋとし、そうでなければ、ｋをスタックｓｉｂｌｉｎｇｓへ積む（２３から２８行目）。
【００４２】
そして、０≦ｃ≦Ｃに対し、Ｓ［ｋ］［ｃ］、及びＢ［ｋ］［ｃ］の各要素を決定する。Ｓ［ｎ−１］［ｃ］がＳ［ｋ］［ｃ］よりも大きければＳ［ｋ］［ｃ］にＳ［ｎ−１］［ｃ］の価値のスコアを格納し、Ｂ［ｋ］［ｃ］にインデックスとタイプを表すタプル（ｎ−１，ＵＰＲＩＧＨＴ）を格納する（２９から３４行目）。タイプがＵＰＲＩＧＨＴの場合、プレオーダインデックスが１からｋ−１番目までのノードを使って構成される、容量の和がｃと等しくかつ各ノードの価値の和を最大化する根付き部分木に対し、プレオーダインデックスｎ−１番目のノードが利用されていないことを示す。
【００４３】
上記図２に示す木構造を構成する各ノードに対して、ノードの容量ｃ、及び価値ｐが表１のとおり与えられたとき、ナップサックの容量制限Ｃ＝１０とすると、二次元配列Ｓ対して、ｎ番目のノード及び容量ｃの組み合わせの各々について、各ノードの価値の和の最大値を格納した場合、図４のようになる。また、二次元配列Ｂに対して、ｎ番目のノード及び容量ｃの組み合わせの各々について、根付き部分木を得るための情報を格納すると図５のようになる。
【００４４】
【表１】
2016024522.tif 000009
【００４５】
バックトラック部３４は、最適値計算部３２によって繰り返し計算された計算過程に基づいて、容量制限Ｃ以下となる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を出力部５０に出力する。
【００４６】
ここで、最適値計算部で生成した二次元配列Ｓ、及びＢを用いて容量制限Ｃ以下でアイテムの価値の和を最大化する根付き部分木を得るバックトラックのアルゴリズムを図６のＡｌｇｏｒｉｔｈｍ２に示す。
【００４７】
最適値計算部３２による計算により、容量制限Ｃ以下で各ノードの価値の和を最大化する根付き部分木のスコアは、記憶部３１に記憶された二次元配列ＳのＮ＋１行目に格納されている。よって、まず容量制限Ｃ以下で価値の和を最大化する根付き部分木のスコアを格納するＳのＮ＋１行目における列を決定し、決定した列をｍａｘ＿ｉｄｘとする（３行目）。そして、二次元配列ＢのＮ＋１の行、ｍａｘ＿ｉｄｘの列から順にバックトラックを行う（９から１８行目）。ｎを行、ｍを列として、初期位置は、ｎがＮ＋１の行、ｍがｍａｘ＿ｉｄｘの列から開始し、Ｂ［ｎ］［ｍ］に格納されているタプルのタイプがＤＩＡＧＯＮＡＬであれば、当該インデックスｋを配列ｔｒｅｅへプッシュする。そして、ｎにｋを代入し、ｍにｍ−ｃａｐ（Ａ［ｋ］）を代入する。タプルのタイプがＵＰＲＩＧＨＴであれば、ｎにｋを代入する。このように根付き部分木の最大スコアを記録するＳの要素に対応するＢの要素からその値を決定するために利用したノードをたどる。つまり、タプルのタイプがＤＩＡＧＯＮＡＬである場合のみ、当該インデックスを配列にプッシュすることで最適根付き部分木を得ることができる。
【００４８】
図４の二次元配列Ｓでは、容量制限Ｃ＝１０以下の根付き部分木に含まれる各ノードの価値の和の最大値は１４である。そこで、図５の二次元配列Ｂに対応するＢ［１０］［１０］よりバックトラックをスタートする。最適根付き部分木はプレオーダインデックスが９，８，７，３，２，１のノードからなる根付き部分木なので、ｖ１，ｖ２，ｖ６，ｖ７，ｖ８，ｖ９を選び、出力部５０に出力する。
【００４９】
＜本発明の実施の形態に係る問題解決装置の作用＞
【００５０】
次に、本発明の実施の形態に係る問題解決装置１００の作用について説明する。入力部１０において価値と容量を持つノードの各々から構成される木構造と、容量制限Ｃとを受け付けると、問題解決装置１００は、図７に示す問題解決処理ルーチンを実行する。
【００５１】
まず、ステップＳ１００では、入力部１０において受け付けた各ノードをソートして、木構造の根からの深さ優先の順序でプレオーダ順にソートして並べ替える。
【００５２】
次に、ステップＳ１０２では、ステップＳ１００で並べ替えた各ノードの数を、Ｎの値として設定する。
【００５３】
ステップＳ１０４では、記憶部３１に記憶された、二次元配列Ｓ及び二次元配列Ｂを初期化する。
【００５４】
ステップＳ１０６では、スタックｓｉｂｌｉｎｇｓの初期値としてＮ＋１を積む。
【００５５】
ステップＳ１０８では、記憶部３１に記憶された二次元配列Ｓの要素Ｓ［１］［０］に０を格納する。
【００５６】
ステップＳ１１０では、ｎに１を代入する。
【００５７】
ステップＳ１１２では、ｎがＮ以下かを判定し、Ｎ以下であればステップＳ１１４へ移行し、Ｎ以下でなければステップＳ１３２へ移行する。
【００５８】
ステップＳ１１４では、ｎにｎ＋１を代入する。
【００５９】
ステップＳ１１６では、ｎ番目のノードと、容量ｃとの組み合わせの各々について、上記（１２）式の１行目に従って、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、記憶部３１に記憶された二次元配列Ｓの各要素として格納する。
【００６０】
ステップＳ１１８では、スタックｓｉｂｌｉｎｇｓの一番上の値はｎ−１であるか否かを判定し、ｎ−１であればステップＳ１２０へ移行し、ｎ−１でなければステップＳ１２２へ移行する。
【００６１】
ステップＳ１２０では、スタックｓｉｂｌｉｎｇｓの一番上に積まれた値を取り除く。
【００６２】
ステップＳ１２２では、ノードＡ［ｎ−１］の右側に存在する兄弟のうち最左の兄弟のプレオーダインデックスをｋに代入する。
【００６３】
ステップＳ１２４では、ｋがＮＵＬＬであるか否か（ノードＡ［ｎ−１］の右側に兄弟がいないか）を判定し、ＮＵＬＬであればステップＳ１２６へ移行し、ＮＵＬＬでなければステップＳ１２８へ移行する。
【００６４】
ステップＳ１２６では、ｋにスタックｓｉｂｌｉｎｇｓの一番上に積まれたインデックスの値を代入する。
【００６５】
ステップＳ１２８では、ｋをスタックｓｉｂｌｉｎｇｓへ積む。
【００６６】
ステップＳ１３０では、上記ステップＳ１２２又はＳ１２６で得たｋに基づいて、各容量ｃについて、上記（１２）式の２行目、３行目に従って、Ｓ［ｋ］［ｃ］、及びＢ［ｋ］［ｃ］の各要素を決定し、ステップＳ１１２へ戻って処理を繰り返す。
【００６７】
ステップＳ１３２では、上記各ステップの処理によって繰り返し計算された計算過程に基づいて、容量制限Ｃ以下となる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を出力部５０に出力して、処理を終了する。
【００６８】
上記ステップＳ１１６は、図８に示す最大価値計算処理ルーチンによって実現される。
【００６９】
以下に説明する最大価値計算処理ルーチンによって、上記（１２）式の１行目の再帰式に従って、ｎ番目のノード及び容量ｃの組み合わせの各々について、当該組み合わせに対する、各ノードの価値の和の最大値Ｓ［ｎ］［ｃ］を計算して、記憶部３１に記憶された配列に格納していく。
【００７０】
図８のステップＳ２００は、容量ｃの値をｃ＝０とする。
【００７１】
次に、ステップＳ２０２では、容量ｃは容量制限Ｃ以下かを判定し、容量制限Ｃ以下であればステップＳ２０４へ移行し、容量制限Ｃ以下でなければ処理を終了する。
【００７２】
ステップＳ２０４では、ｃ−ｃａｐ（Ａ［ｎ−１］）が０以上であり、かつＳ［ｎ］［ｃ−ｃａｐ（Ａ［ｎ−１］）］が０以上であるかを判定し、条件を満たしていればステップＳ２０６へ移行し、条件を満たしていなければステップＳ２１２へ移行する。
【００７３】
ステップＳ２０６では、Ｓ［ｎ］［ｃ］よりＳ［ｎ−１］［ｃ−ｃａｐ（Ａ［ｎ−１］）］＋ｐ（Ａ［ｎ−１］）が大きいかを判定し、条件を満たしていればステップＳ２０８へ移行し、条件を満たしていなければステップＳ２１２へ移行する。
【００７４】
ステップＳ２０８では、Ｓ［ｎ］［ｃ］にＳ［ｎ−１］［ｃ−ｃａｐ（Ａ［ｎ−１］）］＋ｐ（Ａ［ｎ−１］）の価値のスコアを代入する。
【００７５】
ステップＳ２１０では、Ｂ［ｎ］［ｃ］にインデックスとタイプを表すタプル（ｎ−１、ＤＩＡＧＯＮＡＬ）を格納する。
【００７６】
そして、ステップＳ２１２では、容量ｃの値をｃ＝ｃ＋１とし、ステップＳ２０２へ戻って、容量ｃが容量制限Ｃ以下でなくなるまで処理を繰り返す。
【００７７】
上記ステップＳ１３０は、図９に示す兄弟要素決定処理ルーチンによって実現される。
以下に説明する兄弟要素決定処理ルーチンによって、上記（１２）式の２行目、３行目に従って、容量ｃの各々について、Ｓ［ｋ］［ｃ］を計算して、記憶部３１に記憶された配列に格納していく。
【００７８】
図９のステップＳ３００は、容量ｃの値をｃ＝０とする。
【００７９】
次に、ステップＳ３０２では、容量ｃは容量制限Ｃ以下かを判定し、容量制限Ｃ以下であればステップＳ３０４へ移行し、容量制限Ｃ以下でなければ処理を終了する。
【００８０】
ステップＳ３０４では、Ｓ［ｋ］［ｃ］よりＳ［ｎ−１］［ｃ］が大きいかを判定し、条件を満たしていればステップＳ３０６へ移行し、条件を満たしていなければステップＳ３１０へ移行する。
【００８１】
ステップＳ３０６では、Ｓ［ｋ］［ｃ］に、上記最大価値計算処理ルーチンで記憶部３１に記憶された二次元配列Ｓに要素として格納したＳ［ｎ−１］［ｃ］の価値のスコアを代入する。
【００８２】
ステップＳ３０８では、Ｂ［ｎ］［ｃ］にインデックスとタイプを表すタプル（ｎ−１、ＵＰＬＩＧＨＴ）を格納する。
【００８３】
ステップＳ３１０では、容量ｃの値をｃ＝ｃ＋１とし、ステップＳ３０２へ戻って、容量ｃが容量制限Ｃ以下でなくなるまで処理を繰り返す。
【００８４】
上記ステップＳ１３２は、図１０に示すバックトラック処理ルーチンによって実現される。
【００８５】
図１０のステップＳ４００は、根付き部分木の各ノードの価値の和が最大となる根付き部分木の各ノードのインデックスを格納する配列ｔｒｅｅを作成し、行ｎの初期値をＮ＋１に設定する。
【００８６】
次に、ステップＳ４０２では、容量制限Ｃ以下で価値の和を最大化する根付き部分木のスコアを格納するＳのＮ＋１行目における列ｋを決定し、決定したｋをｍａｘ＿ｉｄｘとする。
【００８７】
ステップＳ４０４では、Ｓ［Ｎ＋１］［ｍａｘ＿ｉｄｘ］に格納された価値のスコアをｍａｘ＿ｖａｌに格納する。
【００８８】
ステップＳ４０６では、ステップＳ４０４で価値のスコアが格納されたｍａｘ＿ｖａｌの値が０未満であるかを判定し、０未満であれば処理を終了し、０未満でなければステップＳ４０８へ移行する。
【００８９】
ステップＳ４０８では、列ｍにｍａｘ＿ｉｄｘの値を代入する。
【００９０】
ステップＳ４１０では、ｎ＝１でなく、かつｍ＝０でないかを判定し、条件を満たしていればステップＳ４１２へ移行し、条件を満たしていなければ、後述する繰り返し処理で、配列ｔｒｅｅにプッシュされたインデックスの各ノードを、各ノードの価値の和が最大となる根付き部分木を構成する各ノードとして出力部５０に出力して、処理を終了する。
【００９１】
ステップＳ４１２では、Ｂ［ｎ］［ｍ］に格納しているインデックス及びタイプを（ｋ，ｔｙｐｅ）にそれぞれ代入する。
【００９２】
ステップＳ４１４では、ステップＳ４１２で代入されたｔｙｐｅがＤＩＡＧＯＮＡＬであるかを判定し、ＤＩＡＧＯＮＡＬであればステップＳ４１６へ移行し、ＤＩＡＧＯＮＡＬでなければステップＳ４２２へ移行する。
【００９３】
ステップＳ４１６では、配列ｔｒｅｅへ、ステップＳ４１２で代入されたインデックスｋをプッシュする。
【００９４】
ステップＳ４１８では、ｎにインデックスｋの値を代入する。
【００９５】
ステップＳ４２０では、ｍにｍ−ｃａｐ（Ａ［ｋ］）を代入し、ステップＳ４１０へ戻って処理を繰り返す。
【００９６】
ステップＳ４２２では、ｎにｋを代入し、ステップＳ４１０へ戻って、処理を繰り返す。
【００９７】
以上説明したように、本発明の実施の形態に係る問題解決装置によれば、ｎ番目のノードについて、各容量ｃ（０≦ｃ≦Ｃ）に対し、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなる根付き部分木のうち、根付き部分木の各ノードの価値の和が最大となる根付き部分木を繰り返し計算することにより、根付き部分木の各ノードの価値の和が最大となる根付き部分木を漸次的に成長させ、各成長段階の根付き部分木について、各ノードの価値の和の最大値を計算して記憶部３１の配列Ｓに記憶し、各成長段階の根付き部分木について記憶部３１に記憶した、各ノードの価値の和の最大値を呼び出して、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含む根付き部分木と、ｎ番目のノードを追加できる根付き部分木であって、かつ、各ノードの容量の和が容量ｃと等しくなるｎ−１番目のノードを含まない根付き部分木とのうち、部分木の各ノードの価値の和が最大となる根付き部分木を再帰的に計算することで、木制約付きナップサック問題を高速に解くことができる。
【００９８】
また、図３のＡｌｇｏｒｉｔｈｍ１から明らかなように本発明は容量Ｃ＋１の配列をＮ＋１個用意し、値を決めるだけなので、その計算量はＯ（ＮＣ）である。
【００９９】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【０１００】
１０   入力部
２０   演算部
３０   ソート部
３１   記憶部
３２   最適値計算部
３４   バックトラック部
５０   出力部
１００ 問題解決装置
【図１】
2016024522.tif 000012
【図７】
2016024522.tif 000013
【図８】
2016024522.tif 000014
【図９】
2016024522.tif 000015
【図１０】
2016024522.tif 000016
【図２】
2016024522.tif 000017
【図３】
2016024522.tif 000018
【図４】
2016024522.tif 000019
【図５】
2016024522.tif 000020
【図６】
2016024522.tif 000021