(57)【要約】      （修正有）【課題】様々な制約下での劣モジュラ関数の最大化問題に対する近似解を効率的に計算することができる計算装置、方法及びプログラムを提供する。【解決手段】計算装置１０は、頂点集合と辺集合とにより定義される無向グラフＧ、頂点集合上で定義される劣モジュラ関数ｆ及び前記無向グラフにおける予め定められた制約を満たす部分グラフの集合を示す実行可能集合Ｆの入力を受け付ける入力部１２と、入力を受け付けた実行可能集合Ｆを保持し、１つの根ノード及び２つの終端ノードを含むノード集合並びに枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフ（ＺＤＤ）を構築するＺＤＤ構築部１４と、構築されたＺＤＤにて前記劣モジュラ関数を最大化する部分グラフを近似解として計算する近似解計算部１６と、を備える。【選択図】図１
2018085017.tif 000002
【特許請求の範囲】
【請求項１】
頂点集合と辺集合とにより定義される無向グラフ、前記頂点集合上で定義される劣モジュラ関数、及び前記無向グラフにおける予め定められた制約を満たす部分グラフの集合を示す実行可能集合の入力を受け付ける入力部と、
前記入力部により入力を受け付けた実行可能集合を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフを構築するＺＤＤ構築部と、
前記ＺＤＤ構築部により構築されたゼロサプレス型二分決定グラフにて前記劣モジュラ関数を最大化する前記部分グラフを近似解として計算する近似解計算部と、
を備えた計算装置。
【請求項２】
前記近似解計算部は、前記根ノードに近いノードから順に、前記劣モジュラ関数を最大化する前記根ノードから当該ノードまでのパスであって、前記パスが表す前記無向グラフの各頂点に対応する前記劣モジュラ関数を最大化するパスを確定させることにより、前記近似解を計算する請求項１に記載の計算装置。
【請求項３】
前記入力部は、前記実行可能集合として、予め定められた複数の制約の各々に対する、前記制約を満たす部分グラフの集合を示す実行可能集合の各々の入力を受け付け、
前記ＺＤＤ構築部は、前記実行可能集合の各々に対して、前記ゼロサプレス型二分決定グラフを構築し、
前記近似解計算部は、前記実行可能集合の各々に対して、近似解を計算する請求項１又は２に記載の計算装置。
【請求項４】
前記ＺＤＤ構築部は、同一の実行可能集合に対して、同一の前記ゼロサプレス型二分決定グラフを構築する請求項３に記載の計算装置。
【請求項５】
入力部と、ＺＤＤ構築部と、近似解計算部と、を備えた計算装置における計算方法であって、
前記入力部が、頂点集合と辺集合とにより定義される無向グラフ、前記頂点集合上で定義される劣モジュラ関数、及び前記無向グラフにおける予め定められた制約を満たす部分グラフの集合を示す実行可能集合の入力を受け付けるステップと、
前記ＺＤＤ構築部が、前記入力部により入力を受け付けた実行可能集合を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフを構築するステップと、
前記近似解計算部が、前記ＺＤＤ構築部により構築されたゼロサプレス型二分決定グラフにて前記劣モジュラ関数を最大化する前記部分グラフを近似解として計算するステップと、
を含む計算方法。
【請求項６】
コンピュータを、請求項１〜４のいずれか１項に記載の計算装置の各部として機能させるための計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算装置、方法、及びプログラムに係り、特に、センシング等の分野において現れる劣モジュラ関数の最大化問題に対する近似解を計算するための計算装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
劣モジュラ関数の最大化問題とは、「ある集合の中から、特定の制約を満たしつつ多くの情報を含む部分集合を選択する」という文脈で頻繁に現れる問題である。一例として、図８に示すように、センサを積んだロボットをある地点（頂点ｓ）からある地点（頂点ｔ）まで移動させ、センシングを行うことを考える。
【０００３】
図８は、センサを積んだロボットの移動経路を設計する問題の説明に供する模式図である。
図８において、ロボットに積める燃料は限られているため、移動可能な距離は制限されているものとする。この問題は，与えられたグラフ上でロボットが移動するパス（経路）を探す問題として表現できる（例えば、非特許文献１を参照）。
【０００４】
図８に示す各頂点（黒丸又は白丸で示される点）はロボットがセンシングを行うことのできる地点を表し、各辺はロボットが移動可能な道を表している。簡単のため１つの辺の長さを全て「１」とし、全長「４」以下の頂点ｓから頂点ｔへの移動経路を設計する場合について考える。
【０００５】
この場合、解の１つとして太線のような経路が存在する。ロボットがこの経路を通った場合、黒丸で示される頂点においてセンシングを行うことができる。センシングを行った頂点の集合に対して得られた情報量を出力する関数は、多くの場合で劣モジュラ関数とみなすことができる。
【０００６】
従って、このような問題は、頂点ｓから頂点ｔへのある長さ以下のパスとなるように中継する頂点を選ぶという制約（パス制約）の下で、劣モジュラ関数を最大化する問題と見ることができる。このパス制約下での劣モジュラ関数の最大化問題に対しては、例えば、非特許文献１や非特許文献２等に記載された近似解の計算技術が提案されている。
【０００７】
また、上述の問題設定では、１台のロボットの移動経路を求めることを考えたが、実際にセンシングを行う場合には、複数台のロボットを用いる場合も多々あると考えられる。これに対して、非特許文献１では、１台のロボットの移動経路の計算手順を繰り返し用いることで、複数のロボットの移動経路の設計問題に対しても適用可能な計算技術が提案されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】A. Singh, A. Krause, C. Guestrin, and W. J. Kaiser, "Efficient informative sensing using multiple robots", J. Mach. Learn. Res., 34:707-755, 2009.
【非特許文献２】H. Zhang, and Y. Vorobeychik, "Submodular Optimization with Routing Constraints", In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
パス制約下での劣モジュラ関数の最大化問題に対しては、上述のような近似解の計算法が知られているが、一方で、既存技術では扱えない制約下での劣モジュラ関数の最大化問題も数多く存在する。
【００１０】
例えば、上述のパス制約に加えて、特定の頂点については必ず通らなければならないという制約や、一部の頂点については辿ることのできる順序が決まっているという制約等を追加したものは、通常のパス制約以上に複雑な制約となる。このような様々な制約下での劣モジュラ関数の最大化問題に対して適用可能な既存技術が知られていない。
【００１１】
一方、上述のパス制約下の劣モジュラ関数の最大化問題に対する既存技術は、近似解の計算に要する計算量が多くなるという課題がある。例えば、一時間ごとの環境の変化をセンシングしたい場合には、一時間毎にロボットの移動経路を計算する必要がある。しかし、既存技術では必要となる計算量が多すぎるため、例えば、一度の移動経路の計算に一日以上かかってしまうという状況に陥る可能性がある。このように、頻繁なセンシングを行うためにロボットが移動するパスを繰り返し計算したい場合には、既存技術を適用できなくなる可能性がある。
【００１２】
また、上記の２つの課題は、上述のロボットを複数台用いてセンシングを行う場合でも同様に生じ得る。すなわち、各ロボットの移動について、パス制約に別の制約が追加されている複雑な制約下での劣モジュラ関数の最大化問題に対して適用可能な既存技術が存在しない。また、各ロボットがパス制約の下で動く場合でも、各ロボットの移動経路を頻繁に計算したい場合等において、既存技術では計算量が多すぎるために適用できない可能性がある。
【００１３】
本発明は、上記の事情に鑑みてなされたもので、様々な制約下での劣モジュラ関数の最大化問題に対する近似解を効率的に計算することができる計算装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、第１の発明に係る計算装置は、頂点集合と辺集合とにより定義される無向グラフ、前記頂点集合上で定義される劣モジュラ関数、及び前記無向グラフにおける予め定められた制約を満たす部分グラフの集合を示す実行可能集合の入力を受け付ける入力部と、前記入力部により入力を受け付けた実行可能集合を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフを構築するＺＤＤ構築部と、前記ＺＤＤ構築部により構築されたゼロサプレス型二分決定グラフにて前記劣モジュラ関数を最大化する前記部分グラフを近似解として計算する近似解計算部と、を備える。
【００１５】
第２の発明に係る計算方法は、入力部と、ＺＤＤ構築部と、近似解計算部と、を備えた計算装置における計算方法であって、前記入力部が、頂点集合と辺集合とにより定義される無向グラフ、前記頂点集合上で定義される劣モジュラ関数、及び前記無向グラフにおける予め定められた制約を満たす部分グラフの集合を示す実行可能集合の入力を受け付けるステップと、前記ＺＤＤ構築部が、前記入力部により入力を受け付けた実行可能集合を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフを構築するステップと、前記近似解計算部が、前記ＺＤＤ構築部により構築されたゼロサプレス型二分決定グラフにて前記劣モジュラ関数を最大化する前記部分グラフを近似解として計算するステップと、を含む。
【００１６】
第１及び第２の発明によれば、入力部は、頂点集合と辺集合とにより定義される無向グラフ、頂点集合上で定義される劣モジュラ関数、及び無向グラフにおける予め定められた制約を満たす部分グラフの集合を示す実行可能集合の入力を受け付ける、ＺＤＤ構築部は、入力部により入力を受け付けた実行可能集合を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)であって、１つの根ノード及び２つの終端ノードを含むノード集合、並びに、枝集合により有向グラフとして定義されるゼロサプレス型二分決定グラフを構築する。近似解計算部は、ＺＤＤ構築部により構築されたゼロサプレス型二分決定グラフにて劣モジュラ関数を最大化する部分グラフを近似解として計算する。
【００１７】
また、第１の発明に係る計算装置は、前記近似解計算部が、前記根ノードに近いノードから順に、前記劣モジュラ関数を最大化する前記根ノードから当該ノードまでのパスであって、前記パスが表す前記無向グラフの各頂点に対応する前記劣モジュラ関数を最大化するパスを確定させることにより、前記近似解として計算してもよい。
【００１８】
また、第１の発明に係る計算装置は、前記入力部が、前記実行可能集合として、予め定められた複数の制約の各々に対する、前記制約を満たす部分グラフの集合を示す実行可能集合の各々の入力を受け付け、前記ＺＤＤ構築部が、前記実行可能集合の各々に対して、前記ゼロサプレス型二分決定グラフを構築し、前記近似解計算部が、前記実行可能集合の各々に対して、近似解を計算するようにしてもよい。
【００１９】
また、第１の発明に係る計算装置は、前記ＺＤＤ構築部が、同一の実行可能集合に対して、同一のゼロサプレス型二分決定グラフを構築してもよい。
【００２０】
このように、任意の部分グラフの制約の下での劣モジュラ関数の最大化問題に対して、近似解を計算することが可能となる。その結果、例えば、センサを搭載したロボットの移動経路を設計する場合等に現れる劣モジュラ関数の最大化問題に対して、既存手法では扱うことのできなかった複雑な制約下での近似解を計算することができる。
【００２１】
また、制約の情報をゼロサプレス型二分決定グラフ（ＺＤＤ）として保持し、その上での劣モジュラ関数の最大化問題を解くという手順で近似解を計算する。従って、同一制約下で異なる劣モジュラ関数を何度も最大化する場合には、一度作成したＺＤＤを再利用することで、高速に近似解を計算することができる。その結果、例えば、既存手法が適用できないような頻度でロボットを用いてセンシングを行う場合等でも、毎回のロボットの移動経路を計算することが可能となる。
【００２２】
また、複数の部分グラフを解とする問題に対しても適用することができる。例えば、複数のロボットを用いてセンシングを行う場合の移動経路を計算する問題等に対しても、上記と同様に近似解を計算することができる。
【００２３】
本発明に係る計算プログラムは、コンピュータを、第１の発明に係る計算装置の各部として機能させるためのプログラムである。
【発明の効果】
【００２４】
以上説明したように、本発明に係る計算装置、方法、及びプログラムによれば、様々な制約下での劣モジュラ関数の最大化問題に対する近似解を効率的に計算することができる。
【図面の簡単な説明】
【００２５】
【図１】第１の実施形態に係る計算装置の機能的な構成の一例を示すブロック図である。
【図２】第１の実施形態に係る計算プログラムによる処理の流れの一例を示すフローチャートである。
【図３】実施形態に係る無向グラフの一例を示す模式図である。
【図４】実施形態に係るＺＤＤの一例を示す模式図である。
【図５】実施形態に係る近似解を計算するアルゴリズムの一例を示す図である。
【図６】第２の実施形態に係る計算装置の機能的な構成の一例を示すブロック図である。
【図７】第２の実施形態に係る計算プログラムによる処理の流れの一例を示すフローチャートである。
【図８】センサを積んだロボットの移動経路を設計する問題の説明に供する模式図である。
【発明を実施するための形態】
【００２６】
以下、図面を参照して、本発明を実施するための形態の一例について詳細に説明する。
【００２７】
[第１の実施形態]
図１は、第１の実施形態に係る計算装置１０の機能的な構成の一例を示すブロック図である。
図１に示すように、計算装置１０は、入力部１２と、ＺＤＤ構築部１４と、近似解計算部１６と、出力部１８と、を備えている。なお、ＺＤＤとは、Zero-suppressed Binary Decision Diagramの略であり、ゼロサプレス型二分決定グラフを意味する。
【００２８】
本実施形態に係る計算装置１０は、ＣＰＵ（Central Processing Unit）、ＲＡＭ(Random Access memory)、ＲＯＭ(Read Only Memory)、及びＨＤＤ(Hard Disk Drive)等を備えたコンピュータとして構成される。ＲＯＭには、本実施形態に係る計算処理を実行するための計算プログラムが記憶されている。なお、計算プログラムは、ＨＤＤに記憶されていてもよい。
【００２９】
上記の計算プログラムは、例えば、計算装置１０に予めインストールされていてもよい。計算プログラムは、不揮発性の記憶媒体に記憶して、又は、ネットワークを介して配布して、計算装置１０に適宜インストールすることで実現してもよい。なお、不揮発性の記憶媒体の例としては、ＣＤ-ＲＯＭ(Compact Disc Read Only Memory)、光磁気ディスク、ＤＶＤ-ＲＯＭ(Digital Versatile Disc Read Only Memory)、フラッシュメモリ、メモリカード等が挙げられる。
【００３０】
ＣＰＵは、ＲＯＭに記憶されている計算プログラムを読み込んで実行することにより、計算装置１０の各部として機能する。
【００３１】
本実施形態に係る計算装置１０は、既存技術では扱うことのできなかった様々な制約下での劣モジュラ関数の最大化問題を、統一的に扱うものである。上述のパス制約や、それ以上に複雑な様々な制約を満たす解は、いずれも与えられた無向グラフ上の何らかの部分グラフとなる。従って、計算装置１０は、任意の部分グラフの制約下での劣モジュラ関数の最大化問題を解くための計算装置として構築されている。これにより、既存手法では扱えなかった複雑な制約を扱うことが可能となる。
【００３２】
任意の部分グラフ制約下での劣モジュラ関数の最大化問題を解くためには、制約を満たす部分グラフの集合（以下、実行可能集合という。）を効率的に保持することが重要となる。本実施形態では、実行可能集合をＺＤＤとして保持し、ＺＤＤ上での劣モジュラ関数の最大化問題を近似的に解くことで、与えられた問題に対する近似解を得る。多くの実用上の問題において、ＺＤＤのサイズは実行可能集合のサイズに比べて非常に小さくなり、ＺＤＤ上での近似解の探索は、実行可能集合の全体での解の探索よりも遥かに高速で効率的に行うことができる。以下、本第１の実施形態に係る計算装置１０が備える各部について説明する。
【００３３】
入力部１０は、無向グラフＧ、劣モジュラ関数ｆ、及び実行可能集合
2018085017.tif 000003
の入力を受け付ける。無向グラフＧは、頂点集合Ｖと辺集合Ｅとにより定義され、無向グラフＧにおける辺はエッジともいう。すなわち、無向グラフＧは、（Ｖ、Ｅ）で表される。
【００３４】
劣モジュラ関数ｆは、頂点集合Ｖ上で定義される関数である。より具体的には、劣モジュラ関数ｆは、引数となる、頂点集合Ｖの少なくとも一部の頂点に対して得られる情報量を出力する単調な関数として示される。実行可能集合
2018085017.tif 000004
は、無向グラフＧにおける予め定められた制約を満たす部分グラフの集合として示される。
【００３５】
ＺＤＤ構築部１４は、入力部１２により入力を受け付けた実行可能集合
2018085017.tif 000005
を保持するＺＤＤを構築する。ＺＤＤは、有向グラフＺとして定義される。有向グラフＺ、すなわち、ＺＤＤは、ノード集合Ｎと枝集合Ａとによって定義される。これらＮ、Ａの要素はそれぞれ「ノード」、「枝」と呼ぶことにし、無向グラフＧ＝（Ｖ、Ｅ）における「頂点」、「辺」と区別する。この場合、ＺＤＤは、（Ｎ、Ａ）で表される。ノード集合Ｎは、１つの根ノード及び２つの終端ノードを含む。ノード集合Ｎのうち２つの終端ノード以外の各ノードが頂点集合Ｖの頂点又は辺集合Ｅの辺でラベル付けされている。このＺＤＤの構築方法については後述する。
【００３６】
近似解計算部１６は、ＺＤＤ構築部１８により構築されたＺＤＤにて劣モジュラ関数ｆを最大化する部分グラフを近似解として計算する。この近似解の計算方法についても後述する。
【００３７】
出力部１８は、近似解計算部１６で計算された近似解を出力する。出力部１８には、近似解を表示可能なディスプレイや、近似解を印刷可能なプリンタ、等が適用される。
【００３８】
本第１の実施形態では、単一の解を持つ問題に対する近似解の計算装置１０について説明する。この問題は、一例として、センシングを行う１台のロボットの移動経路を計算する問題として示される。
【００３９】
上述の無向グラフＧ（＝（Ｖ、Ｅ））、頂点集合Ｖ上で定義された劣モジュラ関数ｆ、及び実行可能集合
2018085017.tif 000006
が与えられた場合、計算装置１０は、次のような劣モジュラ関数ｆの最大化問題（以下、問題（１）という。）に対する近似解を計算する。
【００４０】
【数１】
2018085017.tif 000007
【数２】
2018085017.tif 000008
【００４１】
但し、Ｖ（Ｘ）⊆Ｖは、辺集合Ｅに含まれる辺部分集合Ｘの端点に対応する頂点からなる集合を表す。
2018085017.tif 000009
は、制約を満たす部分グラフの全体からなる実行可能集合を表す。なお、２Ｅは辺集合Ｅの冪集合を表す。
【００４２】
例えば、図８に示すように、センサを積んだロボットの頂点ｓから頂点ｔへの長さ「４」以下の移動経路を求める問題について考える。この場合、無向グラフＧは、頂点集合と辺集合とによって定義されるセンシング対象エリア全体を示すグラフとして示される。劣モジュラ関数ｆは、ロボットが経由した頂点に対して得られた情報量を出力する関数として示される。実行可能集合
2018085017.tif 000010
は、無向グラフＧ上の長さ「４」以下の頂点ｓから頂点ｔへのパス全体の集合として示される。
【００４３】
実行可能集合
2018085017.tif 000011
は、無向グラフＧ上の部分グラフからなる任意の集合を表すことができる。このため、既存技術では扱うことのできない、パス制約よりも複雑な制約を満たす集合を扱うことができる。
【００４４】
次に、図２を参照して、本第１の実施形態に係る計算装置１０の作用を説明する。なお、図２は、本第１の実施形態に係る計算プログラムによる処理の流れの一例を示すフローチャートである。
本第１の実施形態に係る計算装置１０は、操作者の操作により計算処理の実行が指示されると、ＣＰＵがＲＯＭに記憶されている計算プログラムを読み出して実行する。
【００４５】
まず、図２のステップ１００では、入力部１２が、劣モジュラ関数ｆ、無向グラフＧ、及び実行可能集合
2018085017.tif 000012
の各々の入力を受け付ける。但し、実行可能集合
2018085017.tif 000013
は、部分グラフの集合の全体を直接与える必要はなく、後述のＺＤＤの構築に必要な情報（例えば、無向グラフＧ上の長さ「４」以下のｓ-ｔパスの集合）を与えればよい。
【００４６】
ステップ１０２では、ＺＤＤ構築部１４が、入力部１２により入力を受け付けた実行可能集合
2018085017.tif 000014
の全体を保持するＺＤＤを構築する。このＺＤＤは、例えば、参考文献（鈴木浩史，湊真一，ＺＤＤを用いたグラフ列挙索引化における頂点インデックスの追加(特集「人工知能・機械学習技術の他分野への応用」および一般)，人工知能基本問題研究会, 101:41-46, 2016.）に記載の方法を適用して構築することができる。
【００４７】
ここで、ＺＤＤの性質について説明する。ＺＤＤは、ノード集合Ｎ及び枝集合Ａを含む有向グラフＺ（＝（Ｎ、Ａ））として定義され、ただ１つの根ノードｒ∈Ｎと、２つの終端ノード０，１∈Ｎと、を有している。２つの終端ノード０，１以外の各ノードｎ∈Ｎ＼｛０，１｝は、ｌａｂｅｌ(ｎ)∈Ｅ∪Ｖによってラベル付けされており、各ノードｎからは、０-枝、及び、１-枝、と呼ばれる二本の枝が出ている。
【００４８】
図３は、本実施形態に係る無向グラフＧの一例を示す模式図である。
図４は、本実施形態に係るＺＤＤの一例を示す模式図である。
図４に示すＺＤＤは、図３に示す無向グラフＧに対して構築したＺＤＤの一例である。
【００４９】
図３に示す無向グラフＧは、頂点集合Ｖ及び辺集合Ｅによって以下のように定義されている。但し、ｖ１〜ｖ３は頂点を示し、ｅ１〜ｅ３は辺を示す。
【００５０】
Ｖ：＝｛ｖ１、ｖ２、ｖ３｝、Ｅ：＝｛ｅ１、ｅ２、ｅ３｝
【００５１】
一方、図４に示すＺＤＤは、実行可能集合
2018085017.tif 000015
を、図３に示す無向グラフＧ上の頂点ｖ１から頂点ｖ３へのパス全体（すなわち、
2018085017.tif 000016
）とした場合に、実行可能集合
2018085017.tif 000017
を保持するために構築されたものである。
【００５２】
図４に示すＺＤＤにおいて、終端ノード０，１以外の各ノードｎは、Ｅ∪Ｖ＝｛ｖ１，ｖ２，ｖ３，ｅ１，ｅ２，ｅ３｝のいずれかでラベル付けされている。根ノードｒは、辺ｅ１でラベル付けされている。また、各ノードｎからは、０-枝（点線）と、１-枝（実線）が出ている。
【００５３】
次に、ＺＤＤ上の任意の二点間を結ぶパスＲ⊆Ａに対して、ＥＲ⊆Ｅ及びＶＲ⊆Ｖを次のように定義する。
【００５４】
【数３】
2018085017.tif 000018
【００５５】
すなわち、ＥＲでは、パスＲが１-枝を通った場合、通った当該１-枝の親側のノードｎ′が辺ラベルならば、その辺ラベルをＥＲに加えるという手順で構成される。同様に、ＶＲでは、パスＲが１-枝を通った場合、通った当該１-枝の親側のノードｎ′が頂点ラベルならば、その頂点ラベルをＶＲに加えるという手順で構成される。
【００５６】
一方、ＺＤＤ上の根ノードｒから終端ノード１へのパスＲの集合を、
2018085017.tif 000019
とする。なお、２Ａは枝集合Ａの冪集合である。この場合、各パス
2018085017.tif 000020
について定義されるＥＲ及びＶＲは、各Ｘ∈
2018085017.tif 000021
及びＶ（Ｘ）⊆Ｖと１対１で対応する。
【００５７】
例えば、図４に示すＺＤＤの場合、ｅ１でラベル付けされた根ノードｒから終端ノード１へのパスＲは、下記に示す２つである。
【００５８】
【数４】
2018085017.tif 000022
【００５９】
上記の定義に従うと、以下のようになる。
【００６０】
【数５】
2018085017.tif 000023
【００６１】
従って、図４に示すＺＤＤ上のパスＲは、図３に示す無向グラフＧ上の頂点ｖ１から頂点ｖ３への二つのパスと対応していることが分かる。すなわち、ＺＤＤは、実行可能集合
2018085017.tif 000024
を、根ノードｒから終端ノード１へのパス全体の集合
2018085017.tif 000025
として保持する。
【００６２】
次に、ステップ１０４では、近似解計算部１６が、ＺＤＤ上のパス
2018085017.tif 000026
の中で、ｆ（ＶＲ）の値を近似的に最大化するパス
2018085017.tif 000027
を計算する。簡単のために、任意のＺＤＤ上のパスＲ⊆Ａについて、ｆ（ＶＲ）をｆ（Ｒ）と記載する。この場合、以下のＺＤＤ上のパス制約の下で劣モジュラ関数ｆの最大化問題（以下、問題（２）という。）を近似的に解くことになる。
【００６３】
【数６】
2018085017.tif 000028
【００６４】
図５は、本実施形態に係る近似解を計算するアルゴリズムの一例を示す図である。
本実施形態においては、図５に示すアルゴリズムに基づいて、近似解計算部１６が上記の問題（２）に対する近似解を計算する。
【００６５】
まず、第２行目では、集合Ｕ（＝Ｎ＼｛ｒ｝）の任意の親ノードｎ′と子ノードｎに対して、親ノードｎ′が子ノードｎよりも前に来るように集合Ｕの要素を並び替えるトポロジカルソートを行う。なお、集合Ｕは、根ノードｒと終端ノード１との間に含まれるノードｎの集合である。
【００６６】
第４行目以降では、上記トポロジカルソートで並び替えた結果、根ノードｒに近いノードｎから順に、根ノードｒからノードｎまでのパスを確定させる。具体的には、ノードｎの親ノードの中から、
2018085017.tif 000029
を最大化する親ノードｎ’を選択し、根ノードｒから親ノードｎ’までのパス
2018085017.tif 000030
に、親ノードｎ’からノードｎまでの枝（ｎ’，ｎ）を加えて、根ノードｒからノードｎまでのパス
2018085017.tif 000031
とし、集合Ｕから、ノードｎを削除する。そして、最終的に得られた根ノードｒから終端ノード１までのパス
2018085017.tif 000032
を解
2018085017.tif 000033
として出力する。得られた解
2018085017.tif 000034
は、上記問題（２）に対する（１-ｃ）-近似解となる。但し、ｃ∈[０，１]は、以下の式で定義される単調な劣モジュラ関数ｆの曲率である。
【００６７】
【数７】
2018085017.tif 000035
【００６８】
最後に、ステップ１０６では、近似解計算部１６が、ステップ１０４で得られた解
2018085017.tif 000036
に対して、辺集合
2018085017.tif 000037
を計算し、計算した辺集合
2018085017.tif 000038
を、出力部１８を介して出力する。この辺集合
2018085017.tif 000039
は、上記問題（１）に対する（１-ｃ）-近似解となることが保証される。
【００６９】
ここで、計算装置１０は、ＺＤＤを一度構築すれば実行可能集合
2018085017.tif 000040
の情報をすべて保持することができる。このため、同一の制約下で異なる劣モジュラ関数ｆを繰り返し最大化する場合には、一度構築したＺＤＤを再利用し、ＺＤＤ上での探索を行うだけで近似解を計算することが可能となる。
【００７０】
例えば、上述のように、頻繁なセンシングを行うためにロボットの移動経路を繰り返し計算する場合、センシング対象となるエリアの地理的な状況は変わらないため、実行可能集合
2018085017.tif 000041
は変化しない。一方で、各頂点をセンシングすることによって得られる情報量は時間帯等によって変わり得るため、最大化する劣モジュラ関数ｆは変化し得る。このような状況下において、計算装置１０は、計算毎に、劣モジュラ関数ｆの入力を受け付けるが、１回目の経路計算の際に構築したＺＤＤを２回目以降の計算で再利用できるため、効率的に計算することができる。
【００７１】
[第２の実施形態]
上記の第１の実施形態では、単一の解を持つ問題の近似解を計算する計算装置１０について説明したが、本第２の実施形態では、複数の解を持つ問題の近似解を計算する計算装置２０について説明する。この問題は、一例として、複数のロボットの移動経路を計算する問題として示される。
【００７２】
図６は、第２の実施形態に係る計算装置２０の機能的な構成の一例を示すブロック図である。
図６に示すように、本第２の実施形態に係る計算装置２０は、入力部２２と、ＺＤＤ構築部２４と、近似解計算部２６と、暫定解処理部２８と、出力部３０と、を備えている。
【００７３】
上述の第１の実施形態に係る計算装置１０は、１つの部分グラフを解として計算するものであるが、本第２の実施形態に係る計算装置２０は、非特許文献１に記載された技術の場合と同様に、複数の部分グラフを計算する問題に対して適用されるものである。例えば、上述したような複雑な制約下で複数台のロボットの移動経路を計算する問題に対しても、計算装置２０を適用することができる。
【００７４】
以下のようにして、複数の解を持つ問題に対する近似解を計算する計算装置２０を構築する。すなわち、与えられた無向グラフＧ（＝（Ｖ，Ｅ））及び単調な劣モジュラ関数ｆに対して、次のような問題（以下、問題（３）という。）の近似解を計算する計算装置２０を考える。
【００７５】
【数８】
2018085017.tif 000042
【００７６】
但し、Ｍ（Ｍは２以上の整数）は解の個数を表し、
2018085017.tif 000043
はｉ番目の解の実行可能集合を表す。
【００７７】
上記の問題（３）は、一例として、複数台のロボットの移動経路を計算する問題として示される。例えば、２台のロボットを用いてセンシングを行う問題において、１台目のロボットは頂点ｓ１から頂点ｔ１まで総移動距離Ｌ１以下で移動し、２台目のロボットは頂点ｓ２から頂点ｔ２まで総移動距離Ｌ２以下で移動する場合を考える。この場合、Ｍ＝２であり、i＝１，２について、実行可能集合
2018085017.tif 000044
は、総移動距離Ｌｉ以下の頂点ｓｉから頂点ｔｉへのパス全体を表す集合となる。以下、本第２の実施形態に係る計算装置２０が備える各部について説明する。
【００７８】
図６に示すように、入力部２２は、無向グラフＧ、劣モジュラ関数ｆ、及び複数の実行可能集合
2018085017.tif 000045
の入力を受け付ける。つまり、入力部２２は、予め定められた複数の制約の各々に対する、制約を満たす部分グラフの集合を示す実行可能集合
2018085017.tif 000046
の各々の入力を受け付ける。
【００７９】
ＺＤＤ構築部２４は、入力部２２により入力を受け付けた複数の実行可能集合
2018085017.tif 000047
の各々に対してＺＤＤを構築する。以下、実行可能集合
2018085017.tif 000048
を保持するためのＺＤＤを
2018085017.tif 000049
という。
【００８０】
近似解計算部２６は、複数の実行可能集合
2018085017.tif 000050
の各々に対して、ＺＤＤ構築部２４により構築された
2018085017.tif 000051
にて劣モジュラ関数ｆを最大化する部分グラフを近似解として計算する。近似解計算部２６では、ｉ＝１，…，Ｍの順に、図５に示すアルゴリズムを用いて、
2018085017.tif 000052
上での近似解を計算する。但し、ｉ番目の回の計算の際に、既に得られた１番目からｉ-１番目までの解の情報を、後述の手順で利用する必要がある。そのための処理を暫定解処理部２８により行う。
【００８１】
出力部３０は、各ｉ毎に近似解計算部２６で計算して得られた近似解を出力する。
【００８２】
次に、図７を参照して、本第２の実施形態に係る計算装置２０の作用を説明する。なお、図７は、本第２の実施形態に係る計算プログラムによる処理の流れの一例を示すフローチャートである。
本第２の実施形態に係る計算装置２０は、操作者の操作により計算処理の実行が指示されると、ＣＰＵがＲＯＭに記憶されている計算プログラムを読み出して実行する。
【００８３】
まず、図７のステップ１１０では、入力部２２が、劣モジュラ関数ｆ、無向グラフＧ、及び複数の実行可能集合
2018085017.tif 000053
の各々の入力を受け付ける。
【００８４】
ステップ１１２では、ＺＤＤ構築部２４が、複数の実行可能集合の各
2018085017.tif 000054
に対して、ＺＤＤとしての
2018085017.tif 000055
を、上述のステップ１０２で説明した手順と同様の手順で構築する。このとき、
2018085017.tif 000056
となる組が存在する場合、
2018085017.tif 000057
となるため、
2018085017.tif 000058
の一方のみを構築すれば良い。特に、Ｍ台のロボットが全て頂点ｓからスタートして頂点ｔに移動する場合等では、各ロボットの移動距離の制約が同一であれば、
2018085017.tif 000059
となるため、構築するＺＤＤは１つだけでよい。
【００８５】
ステップ１１４では、近似解計算部２６が、ＺＤＤ構築部２４により構築された
2018085017.tif 000060
に基づいて、ｉ＝１，…，Ｍの順に、図５に示すアルゴリズムを用いて、
2018085017.tif 000061
上での近似解を計算する。以下では、この近似解を
2018085017.tif 000062
と記載する。
2018085017.tif 000063
を計算する段階では、既に
2018085017.tif 000064
は確定しているため、
2018085017.tif 000065
は必ず最終的な解に含まれる。このことを考慮して、
2018085017.tif 000066
を計算する際には、下記に示す任意のＳ⊆Ｖについて定義される単調な劣モジュラ関数
2018085017.tif 000067
を最大化することを考える。
【００８６】
2018085017.tif 000068
但し、
2018085017.tif 000069
【００８７】
すなわち、ステップ１１４では、近似解計算部２６が、ｉ＝１，…，Ｍの順に、
2018085017.tif 000070
及び
2018085017.tif 000071
に対して、図５に示すアルゴリズムを適用し、近似解
2018085017.tif 000072
を計算する。
【００８８】
ステップ１１６では、暫定解処理部２８が、ステップ１１４において近似解計算部２６が近似解
2018085017.tif 000073
を計算する際に必要となる、
2018085017.tif 000074
についての情報の処理を行う。すなわち、暫定解処理部２８は、上記の
2018085017.tif 000075
に対応する
2018085017.tif 000076
（但し、ｉ＝１の場合は空集合）を計算し、計算結果を近似解計算部２６に渡す。近似解計算部２６は、暫定解処理部２８から受け取った
2018085017.tif 000077
に基づいて、
2018085017.tif 000078
を計算する。また、暫定解処理部２８は、近似解計算部２６において新たな
2018085017.tif 000079
が計算される度に、
2018085017.tif 000080
に対する
2018085017.tif 000081
を計算し、
2018085017.tif 000082
を保持する。
【００８９】
ステップ１１８では、近似解計算部２６が、ステップ１１６で得られた各
2018085017.tif 000083
から
2018085017.tif 000084
を計算し、計算した
2018085017.tif 000085
を、出力部３０を介して出力する。最終的に得られる解
2018085017.tif 000086
は、上記問題（３）に対する（１−ｃ）／（２−ｃ）-近似解となることが保証される。また、
2018085017.tif 000087
が成り立つ場合は、この近似比の保証はさらに改善され、（１−ｅ−１＋ｃ）-近似解となることが保証される。
【００９０】
なお、複数のロボットを用いて頻繁にセンシングを行うような場合でも、第１の実施形態と同様に、計算毎に、劣モジュラ関数ｆの入力を受け付けるが、ＺＤＤの再利用を行うことができる。すなわち、各ロボットの移動経路が満たす制約が共通である場合には、共通の制約に対してＺＤＤを一度構築すれば、以降の計算では改めてＺＤＤ を構築する必要はない。特に、全てのロボットが同じ制約下で動く場合は、各ロボットの移動経路の計算においても同一のＺＤＤを利用することができる。このため、計算毎に、劣モジュラ関数ｆの入力を受け付けるが、複数のロボットの移動経路を繰り返し計算するために必要なＺＤＤは１つのみでよい。
【００９１】
以上、実施形態として計算装置及び計算方法を例示して説明した。実施形態は、コンピュータを、計算装置における各部として機能させるための計算プログラムの形態としてもよい。実施形態は、この計算プログラムを記憶したコンピュータが読み取り可能な記憶媒体の形態としてもよい。
【００９２】
その他、上記実施形態で説明した計算装置の構成は、一例であり、主旨を逸脱しない範囲内において状況に応じて変更してもよい。
【００９３】
また、上記実施形態で説明した計算プログラムの処理の流れも、一例であり、主旨を逸脱しない範囲内において不要なステップを削除したり、新たなステップを追加したり、処理順序を入れ替えたりしてもよい。
【００９４】
また、上記実施形態では、計算プログラムを実行することにより、実施形態に係る処理がコンピュータを利用してソフトウェア構成により実現される場合について説明したが、これに限らない。実施形態は、例えば、ハードウェア構成や、ハードウェア構成とソフトウェア構成との組み合わせによって実現してもよい。
【符号の説明】
【００９５】
１０、２０    計算装置
１２、２２    入力部
１４、２４    ＺＤＤ構築部
１６、２６    近似解計算部
１８、３０    出力部
２８   暫定解処理部
【図１】
2018085017.tif 000088
【図２】
2018085017.tif 000089
【図３】
2018085017.tif 000090
【図４】
2018085017.tif 000091
【図５】
2018085017.tif 000092
【図６】
2018085017.tif 000093
【図７】
2018085017.tif 000094
【図８】
2018085017.tif 000095