(57)【要約】【課題】所与のグラフＧに対し、有限時間内にすべての辺素パスを見つけるＺＤＤアルゴリズムを備えるネットワーク設計評価方法、ネットワーク設計評価装置及びプログラムを提供することを目的とする。【解決手段】本発明に係るネットワーク設計評価方法は、所与のグラフについて、指定された頂点ペアごとにフロンティア法によりすべてのパスを抽出し、頂点ペアごとに抽出されたパスを要素とするパス集合をＺＤＤで表現し、ＺＤＤで表現されたすべてのパス集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎ演算を行うことで辺素パスを抽出することとした。【選択図】図６
2019216396.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを頂点と辺で表し、頂点集合と辺集合からなるグラフ及び前記頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアが与えられる条件入力手順と、
前記条件入力手順で与えられた前記頂点ペア毎に、前記辺集合に含まれる少なくとも１つの辺で前記２つの頂点を結ぶパスの集合をフロンティア法で計算するパス集合演算手順と、
前記パス集合演算手順で計算した全ての前記パスの集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎを計算し、前記条件入力手順で与えられた前記グラフに含まれる全ての辺素パスを抽出する辺素パス抽出手順と、
を行うネットワーク設計評価方法。
【請求項２】
頂点と辺で表されたネットワークについて与えられた、頂点集合と辺集合からなるグラフ及び前記頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアを記憶する記憶部と、
前記記憶部が記憶する前記頂点ペア毎に、前記辺集合に含まれる少なくとも１つの辺で前記２つの頂点を結ぶパスの集合をフロンティア法で計算するパス集合演算部と、
前記パス集合演算部が計算した全ての前記パスの集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎを計算し、前記記憶部が記憶する前記グラフに含まれる全ての辺素パスを抽出する辺素パス抽出部と、
を備えるネットワーク設計評価装置。
【請求項３】
請求項１に記載されるネットワーク設計評価方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ネットワークにおける辺素パスを見出すネットワーク設計評価手法、ネットワーク設計評価装置及びプログラムに関する。
【背景技術】
【０００２】
組み合わせ最適化や制約充足問題などの離散数理計画において、ＺＤＤ（Ｚｅｒｏ−ｓｕｐｐｒｅｓｓｅｄ  ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ、二分決定図）が注目されている（例えば、非特許文献１を参照。）。多くの数理計画問題では、制約条件を満たす実行可能領域に対して最適解の探索などを行うため、制約条件のよい表現方法が計算効率のカギを握る。ＺＤＤは、制約条件を過不足なくコンパクトに表現するデータ構造とアルゴリズムである。
【０００３】
ＺＤＤを用いて制約条件を扱うことで、最適化や確率評価を効率的に実行できることが知られている。たとえば、制約条件を満たす実行可能解のうちコスト最小のものを選択したり、システムが実行不可能になる確率を評価することもできる。近年、新たに開発されたフロンティア法（例えば、非特許文献２を参照。）というアルゴリズムにより、ＮＷ（ネットワーク）やグラフによって定義された制約条件をＺＤＤとして扱えるようになった。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】井上武、“ＺＤＤとフロンティア法を取り巻く研究動向”，電子情報通信学会誌、ｖｏｌ．１０１，ｎｏ．３，ｐｐ．２９７−３０１，２０１８．
【非特許文献２】Ｊ．  Ｋａｗａｈａｒａ，  Ｔ．  Ｉｎｏｕｅ，  Ｈ．  Ｉｗａｓｈｉｔａ，  ａｎｄ  Ｓ．  Ｍｉｎａｔｏ，“Ｆｒｏｎｔｉｅｒ−ｂａｓｅｄ  ｓｅａｒｃｈ  ｆｏｒ  ｅｎｕｍｅｒａｔｉｎｇ  ａｌｌ  ｃｏｎｓｔｒａｉｎｅｄ  ｓｕｂｇｒａｐｈｓ  ｗｉｔｈ  ｃｏｍｐｒｅｓｓｅｄ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”，ＩＥＩＣＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｆｕｎｄａｍｅｎｔａｌｓ  ｏｆ  Ｅｌｅｃｔｒｏｎｉｃｓ，  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅｓ，  ｖｏｌ．Ｅ１００．Ａ，  ｎｏ．９，  ｐｐ．１７７３−１７８４，  ２０１７．
【非特許文献３】Ｊ．  Ｋａｗａｈａｒａ，  Ｔ．  Ｓａｉｔｏｈ，  Ｈ．  Ｓｕｚｕｋｉ，  ａｎｄ  Ｒ．  Ｙｏｓｈｉｎａｋａ，“Ｓｏｌｖｉｎｇ  ｔｈｅ  ｌｏｎｇｅｓｔ  ｏｎｅｗａｙ−ｔｉｃｋｅｔ  ｐｒｏｂｌｅｍ  ａｎｄ  ｅｎｕｍｅｒａｔｉｎｇ  ｌｅｔｔｅｒ  ｇｒａｐｈｓ  ｂｙ  ａｕｇｍｅｎｔｉｎｇ  ｔｈｅ  ｔｗｏ  ｒｅｐｒｅｓｅｎｔａｔｉｖｅ  ａｐｐｒｏａｃｈｅｓ  ｗｉｔｈ  ＺＤＤｓ”，ｉｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ，  ２０１７，  ｐｐ．２９４−３０５．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
フロンティア法は、パスや連結性などの主要なグラフ制約を扱うことができる。しかし、辺素パスという制約条件は、アルゴリズムや最適化に関するほとんどの教科書に記載される主要概念でありながら、フロンティア法で扱うことができなかった。
【０００６】
まず、辺素パスについて説明する。頂点集合Ｖ、辺集合Ｅに対し、グラフＧ＝（Ｖ、Ｅ）と、いくつかの頂点ペアＫ＝｛｛ｕ、ｖ｝、・・・｝⊂Ｖ×Ｖが与えられる。本発明では無向グラフを考える。辺素パス制約を満たすには、各頂点ペアＫをつなぐパスが存在するだけでなく、それらのパスは同じ辺を通ってはならない（同じ頂点は通ってよい）。グラフと頂点ペアによって、辺素パスをとれないこともあるし、いくつかのパターンでとれることもある。
【０００７】
図１のＮＷを例に、図２に辺素パスの例を示す。頂点集合Ｖは５つの頂点（黒が１つ、白が２つ、グレイが２つ）からなる。また、辺集合Ｅ＝｛ｅ１、ｅ２、ｅ３、ｅ４、ｅ５、ｅ６｝である。同じ辺を通らないようにして、同色の頂点ペアをパスでつなぐ。図２（ａ）はいずれも辺素パスだが、図２（ｂ）はｅ５でパスが重なっているため辺素になっていない。
【０００８】
辺素パス制約は、ＮＷにおけるリソース競合を表す基本的な概念であり、波長割当やｔｒａｆｆｉｃ  ｅｎｇｉｎｅｅｒｉｎｇなどの基礎をなす。しかし、NWに存在するすべての辺素パスを見つけるには、２｜Ｅ｜個にも及ぶ辺の組み合わせを全て調べなければならず、｜Ｅ｜が数十の小さなグラフでも現実的な時間には完了しないという課題がある。
【０００９】
そこで、本発明は、上記課題を解決するために、所与のグラフＧに対し、有限時間内にすべての辺素パスを見つけるＺＤＤアルゴリズムを備えるネットワーク設計評価方法、ネットワーク設計評価装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明に係るネットワーク設計評価方法は、所与のグラフについて、指定された頂点ペアごとにフロンティア法によりすべてのパスを抽出し、頂点ペアごとに抽出されたパスを要素とするパス集合をＺＤＤで表現し、ＺＤＤで表現されたすべてのパス集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎ演算を行うことで辺素パスを抽出することとした。
【００１１】
具体的には、本発明に係るネットワーク設計評価方法は、
ネットワークを頂点と辺で表し、頂点集合と辺集合からなるグラフ及び前記頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアが与えられる条件入力手順と、
前記条件入力手順で与えられた前記頂点ペア毎に、前記辺集合に含まれる少なくとも１つの辺で前記２つの頂点を結ぶパスの集合をフロンティア法で計算するパス集合演算手順と、
前記パス集合演算手順で計算した全ての前記パスの集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎを計算し、前記条件入力手順で与えられた前記グラフに含まれる全ての辺素パスを抽出する辺素パス抽出手順と、
を行う。
【００１２】
また、本発明に係るネットワーク設計評価装置は、
頂点と辺で表されたネットワークについて与えられた、頂点集合と辺集合からなるグラフ及び前記頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアを記憶する記憶部と、
前記記憶部が記憶する前記頂点ペア毎に、前記辺集合に含まれる少なくとも１つの辺で前記２つの頂点を結ぶパスの集合をフロンティア法で計算するパス集合演算部と、
前記パス集合演算部が計算した全ての前記パスの集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎを計算し、前記記憶部が記憶する前記グラフに含まれる全ての辺素パスを抽出する辺素パス抽出部と、
を備える。
【００１３】
本発明では、辺素パスを１つずつ見つけるのではなく、フロンティア法で頂点ペアごとに辺集合を見つけておき、共通要素を持たない組み合わせＤｉｓｊｏｉｎｔ  Ｊｏｉｎ演算で辺素パスを抽出する。フロンティア法で効率よく辺集合を見つけられるため、有限時間内にＮＷの全ての辺素パスを見出すことができる。従って、本発明は、所与のグラフＧに対し、有限時間内にすべての辺素パスを見つけるＺＤＤアルゴリズムを備えるネットワーク設計評価方法、ネットワーク設計評価装置及びプログラムを提供することができる。
【００１４】
また、本発明に係るプログラムは、前記ネットワーク設計評価方法をコンピュータに実行させるためのプログラムである。前記ネットワーク設計評価方法は、コンピュータとプログラムによって実行でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【発明の効果】
【００１５】
本発明は、所与のグラフＧに対し、有限時間内にすべての辺素パスを見つけるＺＤＤアルゴリズムを備えるネットワーク設計評価方法、ネットワーク設計評価装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】頂点と辺で表現されたネットワークの例である。
【図２】辺素パスの例を説明する図である。（ａ）は辺素パス、（ｂ）は辺素パスではない。
【図３】フロンティア法で見出したパスの集合を説明する図である。（ａ）は白頂点をつなぐパスの集合、（ｂ）はグレー頂点をつなぐパスの集合である。
【図４】ＺＤＤで表現されたパスの集合を説明する図である。（ａ）はΠｗｈｉｔｅを表すＺＤＤ、（ｂ）はΠｇｒａｙを表すＺＤＤである。
【図５】全ての辺素パスをＺＤＤで表現した図である。
【図６】本発明に係るネットワーク設計評価方法を説明するフローチャートである。
【図７】本発明に係るネットワーク設計評価装置を説明するブロック図である。
【発明を実施するための形態】
【００１７】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１８】
図７は、本実施形態のネットワーク設計評価装置を説明するブロック図である。本ネットワーク設計評価装置は、
頂点と辺で表されたネットワークについて与えられた、頂点集合と辺集合からなるグラフ及び前記頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアを記憶する記憶部１１と、
記憶部１１が記憶する前記頂点ペア毎に、前記辺集合に含まれる少なくとも１つの辺で前記２つの頂点を結ぶパスの集合をフロンティア法で計算するパス集合演算部１２と、
パス集合演算部１２が計算した全ての前記パスの集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎを計算し、記憶部１１が記憶する前記グラフに含まれる全ての辺素パスを抽出する辺素パス抽出部１３と、
を備える。
【００１９】
図６は、本ネットワーク設計評価装置が行うネットワーク設計評価方法を説明するフローチャートである。本ネットワーク設計評価方法は、
ネットワークを頂点と辺で表し、頂点集合と辺集合からなるグラフ及び前記頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアが記憶部１１に与えられる条件入力手順Ｓ０１と、
パス集合演算部１２が、条件入力手順Ｓ０１で与えられ、記憶部１１が記憶する前記頂点ペア毎に、前記辺集合に含まれる少なくとも１つの辺で前記２つの頂点を結ぶパスの集合をフロンティア法で計算するパス集合演算手順Ｓ０２と、
辺素パス抽出部１３が、パス集合演算手順Ｓ０２でパス集合演算部１２が計算した全ての前記パスの集合に対してＤｉｓｊｏｉｎｔ  Ｊｏｉｎを計算し、条件入力手順Ｓ０１で与えられ、記憶部１１が記憶する前記グラフに含まれる全ての辺素パスを抽出する辺素パス抽出手順Ｓ０３と、
を行う。
【００２０】
［条件入力手順Ｓ０１］
まず、外部から作業者などにより、頂点と辺で表された評価対象のネットワークについて、頂点集合と辺集合からなるグラフＧ、及び頂点集合に含まれる２つの頂点からなる少なくとも１つの頂点ペアＫが記憶部１１に与えられる。
【００２１】
［パス集合演算手順Ｓ０２］
続いて、頂点ペアＫごとに、非特許文献２に記載されるフロンティア法を用いて、すべてのパスを見つけておく。例として、図３に、白頂点をつなぐ３つのパスと、グレー頂点をつなぐ３つのパスを示す。本実施形態では、パスを「辺の集合」として表す。また、頂点ごとに見つかったパスを「パス集合Π」と呼ぶ。図３に、白、グレーの頂点それぞれのΠｗｈｉｔｅ、Πｇｒａｙを示す。これらのパス集合Πは、図４のＺＤＤとして表現される（ＺＤＤの表記については非特許文献１を参照）。
【００２２】
［辺素パス抽出手順Ｓ０３］
さらに、辺素になるようにパス集合を結合する。２つのパス集合Π１、Π２があったとき、パスＰ∈Π１、Ｐ’∈Π２が共通要素を持たないようにするには、以下のＤｉｓｊｏｉｎｔ  Ｊｏｉｎ演算を行えばよい。
【数１】
2019216396.tif 000003
【００２３】
この演算の実行は、非特許文献３で提案されているＺＤＤアルゴリズムを利用する。辺素パス抽出部は、この演算により、図２に示したすべての辺素パスを抽出し、図５のＺＤＤとして表現して出力する。
【００２４】
［発明によって生じる効果］
本発明のネットワーク設計評価方法で、辺素パスの制約条件をＺＤＤとして表現できるようになった。これにより、組み合わせ最適化や制約充足問題などの離散数理計画を効率的に解けることが期待できる。
【符号の説明】
【００２５】
１１：記憶部
１２：パス集合演算部
１３：辺素パス抽出部
【図１】
2019216396.tif 000004
【図２】
2019216396.tif 000005
【図３】
2019216396.tif 000006
【図４】
2019216396.tif 000007
【図５】
2019216396.tif 000008
【図６】
2019216396.tif 000009
【図７】
2019216396.tif 000010