(57)【特許請求の範囲】
【請求項１】
複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行い、
下位の階層から上位の階層へと階層を選択し、正規化を行った前記複数の枝重み付き二分決定グラフの各々に対して、選択した前記階層の各節点の分岐の前記重み係数を参照し、該節点からの分岐の重み係数が前記一定の値以下の第１グラフと、該節点からの分岐だけに該一定の値より大きい重み係数を持つ第２グラフとに分解する加法分解を行い、該加法分解により該第２グラフが複数生成された場合、複数の該第２グラフを加算して１つの第３グラフを作成して、該第１グラフと該第３グラフとを新たな複数の枝重み付き二分決定グラフとする処理を行い、
最上位の階層を選択して行われた前記加法分解及び前記処理により得られた新たな複数の二分決定グラフを同時に探索して最適解を求める
処理をコンピュータに行わせる探索処理最適化プログラム。
【請求項２】
前記コンピュータに、
選択した前記階層において、前記節点毎に行った前記加法分解によって生成された前記第２グラフ同士の加算後のサイズが定めた閾値を超えない範囲で該第２グラフを加算する
処理を行わせることを特徴とする請求項１記載の探索処理最適化プログラム。
【請求項３】
前記コンピュータに、
最大化問題の目的関数は、前記枝重み付き二分決定グラフの根へと接続される枝を−１倍した重み付けを行うことで、最小化問題に変換する
処理を行わせることを特徴とする請求項２記載の探索処理最適化プログラム。
【請求項４】
複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行い、
下位の階層から上位の階層へと階層を選択し、正規化を行った前記複数の枝重み付き二分決定グラフの各々に対して、選択した前記階層の各節点の分岐の前記重み係数を参照し、該節点からの分岐の重み係数が前記一定の値以下の第１グラフと、該節点からの分岐だけに該一定の値より大きい重み係数を持つ第２グラフとに分解する加法分解を行い、該加法分解により該第２グラフが複数生成された場合、複数の該第２グラフを加算して１つの第３グラフを作成して、該第１グラフと該第３グラフとを新たな複数の枝重み付き二分決定グラフとする処理を行い、
最上位の階層を選択して行われた前記加法分解及び前記処理により得られた新たな複数の二分決定グラフを同時に探索して最適解を求める
処理をコンピュータが行う探索処理最適化方法。
【請求項５】
複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行う正規化部と、
下位の階層から上位の階層へと階層を選択し、正規化を行った前記複数の枝重み付き二分決定グラフの各々に対して、選択した前記階層の各節点の分岐の前記重み係数を参照し、該節点からの分岐の重み係数が前記一定の値以下の第１グラフと、該節点からの分岐だけに該一定の値より大きい重み係数を持つ第２グラフとに分解する加法分解を行い、該加法分解により該第２グラフが複数生成された場合、複数の該第２グラフを加算して１つの第３グラフを作成して、該第１グラフと該第３グラフとを新たな複数の枝重み付き二分決定グラフとする処理を行う処理部と、
最上位の階層を選択して行われた前記加法分解及び前記処理により得られた新たな複数の二分決定グラフを同時に探索して最適解を求める探索部と
を有する探索処理最適化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、探索処理最適化プログラム、探索処理最適化方法、及び探索処理最適化装置に関する。
【背景技術】
【０００２】
近年、材料費、人件費、消費エネルギーの最小化や生産量、利益の最大化などを目的として組み合せ最適化が利用されている。最適化問題では、論理関数の変数が取り得る値の場合分けを表わした二分決定グラフ（ＢＤＤ：Binary  Decision  Diagram）を用いて最適解を探索する手法が知られている。
【０００３】
各計算機に部分問題の解を表わすＢＤＤを持たせることで、ＢＤＤの演算を高速化する技術や、複数の作業と、作業間を作業から次の作業に切り替えるコストとで表されたグラフネットワークを用いて、切り替えコストに基づく重みの総和が最小の最短路を求める技術等が提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１４−１５４１０７号公報
【特許文献２】特開２０１５−６０５６６号公報
【特許文献３】特開２０１４−１８２７５３号公報
【非特許文献】
【０００５】
【非特許文献１】Takeru  Inoue，Keiji  Takano，Takayuki  Watanabe，Jun  Kawahara，Ryo  Yoshinaka，Akihiro  Kishimoto，Koji  Tsuda，Shin‐ichi  Minato，and  Yasuhiro  Hayashi，“Distribution  Loss  Minimization  with  Guaranteed  Error  Bound，”IEEE  Transactions  on  Smart  Grid，vol．5，issue．1，pp．102‐111，January  2014
【非特許文献２】Lai，Yung‐Te，and  Sarma  Sastry．“Edge‐valued  binary  decision  diagrams  for  multi‐level  hierarchical  verification．”Design  Automation  Conference，  1992．Proceedings．，29th  ACM/IEEE．IEEE，1992
【非特許文献３】Ossowski，Jorn，and  Christel  Baier．“A  uniform  framework  for  weighted  decision  diagrams  and  its  implementation．”International  journal  on  software  tools  for  technology  transfer  10．5  (2008)：  425‐441
【非特許文献４】Masaaki  Nishino，  Norihito  Yasuda，  Shin‐ichi  Minato，  Masaaki  Nagata，“BDD‐Constrained  Search：A  Unified  Approach  to  Constrained  Shortest  Path  Problems，”Twenty‐Ninth  AAAI  Conference  on  Artificial  Intelligence，pp．1219‐1225，2015
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述した技術では、最適解の探索における、ＢＤＤ、グラフネットワーク等を表わすデータ構造の増大について考慮されていない。複数のＢＤＤまたは枝重み付き二分決定グラフ（ＷＤＤ：Weighted  Decision  Diagram）で与えられた問題を解くためにそれらを演算で一つに合成するとデータ構造が増大し過ぎると言った問題がある。
【０００７】
したがって、１つの側面では、本発明は、最適解の探索に係る計算量を削減することを目的とする。
【課題を解決するための手段】
【０００８】
一態様によれば、複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行い、下位の階層から上位の階層へと階層を選択し、正規化を行った前記複数の枝重み付き二分決定グラフの各々に対して、選択した前記階層の各節点の分岐の前記重み係数を参照し、該節点からの分岐の重み係数が前記一定の値以下の第１グラフと、該節点からの分岐だけに該一定の値より大きい重み係数を持つ第２グラフとに分解する加法分解を行い、該加法分解により該第２グラフが複数生成された場合、複数の該第２グラフを加算して１つの第３グラフを作成して、該第１グラフと該第３グラフとを新たな複数の枝重み付き二分決定グラフとする処理を行い、最上位の階層を選択して行われた前記加法分解及び前記処理により得られた新たな複数の二分決定グラフを同時に探索して最適解を求める処理をコンピュータに行わせる探索処理最適化プログラムが提供される。
【０００９】
また、上記課題を解決するための手段として、探索処理最適化方法、及び探索処理最適化装置とすることもできる。
【発明の効果】
【００１０】
最適解の探索に係る計算量を削減できる。
【図面の簡単な説明】
【００１１】
【図１】第１関連技術における二分決定グラフの例を示す図である。
【図２】第１関連技術における最適化問題を最短経路問題として解いた結果例を示す図である。
【図３】第２関連技術におけるグラフ例を示す図である。
【図４】複数のＷＤＤの例を示す図である。
【図５】第１関連技術に基づくＷＤＤを合成と探索範囲の例を示す図である。
【図６】第２関連技術に基づくＷＤＤの探索方法と探索範囲の例を示す図である。
【図７】本実施例における手順ＡにおけるＷＤＤの正規化規則を説明するための図（その１）である。
【図８】本実施例における手順ＡにおけるＷＤＤの正規化規則を説明するための図（その２）である。
【図９】本実施例における手順ＢにおけるＷＤＤの加法分解を説明するための図である。
【図１０】加法分解と加算の組合せによる等価変換を説明するための図である。
【図１１】探索処理最適化装置のハードウェア構成を示す図である。
【図１２】探索処理最適化装置の機能構成例を示す図である。
【図１３】探索処理最適化方法の概要を説明するためのフローチャート図である。
【図１４】等価変換処理の第一例を説明するためのフローチャート図である。
【図１５】等価変換処理の第二例を説明するためのフローチャート図である。
【図１６】正規化後ＷＤＤの例を示す図である。
【図１７】ｘ６に注目して加法分解を行うステップ１ａを説明するための図である。
【図１８】ｘ６に注目した加法分解後にＷＤＤを加算するステップ１ｂを説明するための図である。
【図１９】ｘ５に注目して加法分解を行うステップ２ａを説明するための図である。
【図２０】ｘ５に注目した加法分解後にＷＤＤを加算するステップ２ｂを説明するための図である。
【図２１】ｘ４に注目して加法分解を行うステップ３ａを説明するための図である。
【図２２】ｘ４に注目した加法分解後にＷＤＤを加算するステップ３ｂを説明するための図である。
【図２３】ｘ３に注目して加法分解を行うステップ４ａを説明するための図である。
【図２４】ｘ３に注目した加法分解後にＷＤＤを加算するステップ４ｂを説明するための図である。
【図２５】ｘ２に注目して加法分解を行うステップ５ａを説明するための図である。
【図２６】ｘ２に注目した加法分解後にＷＤＤを加算するステップ５ｂを説明するための図である。
【図２７】ｘ１に注目して加法分解を行うステップ６ａを説明するための図である。
【図２８】ｘ１に注目した加法分解後にＷＤＤを加算するステップ６ｂを説明するための図である。
【図２９】複数のＷＤＤの同時探索による最適解ＷＤＤの例を示す図である。
【図３０】比較結果例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態を図面に基づいて説明する。先ず、目的関数や制約条件が複数の枝重み付き二分決定グラフで与えられた組合せ最適化問題について説明する。
【００１３】
一般に、離散最適化問題、０−１整数計画問題等の組合せ最適化問題とは、最大充足問題やナップサック問題のような、複数の０−１変数に対する最適な値割り当てを求める問題である。組合せ最適化問題は、値割り当てに対する評価値を返す目的関数と、値割り当てが実現可能かを判定する制約条件で構成され、材料費、人件費、消費エネルギーの最小化や生産量、利益の最大化などに広く利用されている。一般にＮＰ困難であり、万能な手法は無いとされている。問題に応じて複数の手法を使い分ける（或いは同時に試す）ことが一般的であり、様々な手法が求められている。
【００１４】
ＢＤＤ（Binary  Decision  Diagram；二分決定グラフ）は、０−１入力変数のみで構成される任意の０−１出力関数を表現可能なデータ構造の一つである。一例として、非特許文献１には、都市の配電網において、停電や短路のない等の妥当な配電経路を実現する全てのＯＮ／ＯＦＦ切替パターンを表わすスイッチ構成にＢＤＤを用いることが記載されている。
【００１５】
ＷＤＤ（Weighted  Decision  Diagram；枝重み付き二分決定グラフ）は、０−１入力変数のみで構成される、任意の実数出力関数を表現可能なデータ構造の一つである。ＥＶＢＤＤ（Edge‐Valued  Binary  Decision  Diagram）も同様である。また、ＢＤＤは、ＷＤＤの特別な場合と見なせる。
【００１６】
ＷＤＤに関して知られている以下の２つの関連技術について概要を説明する。
・第１関連技術として、目的関数が単一のＷＤＤで表現でき、かつ、制約条件が付かない場合の最適解を探索する技術が挙げられる。例として、非特許文献２及び非特許文献３が相当する。
・第２関連技術は、目的関数のグラフと制約条件のグラフとを同時に探索する技術が挙げられる。例として、非特許文献４が相当する。
【００１７】
図１は、第１関連技術における二分決定グラフの例を示す図である。図１では、枝に重み情報が付加された二分決定グラフ２の例を示している。図１において、節点は根から終端の順にレベル付けられる。
【００１８】
各レベルの節点は同じ変数に対応し、図１では、
【数１】
0006701937.tif 000002
に対応する。各節点から出る０枝（破線）と１枝（実線）が変数の値割り当てに対応する。変数の値割り当てが決定されると、根から終端までの経路が定まる。経路上の枝重みを合計して出力値を得る。例えば、経路３は、
（x1，x2，x3，x4，x5，x6）＝（0，0，0，1，0，0）
であり、経路３に対する出力値として、
１＋０＋０＋０＋１＋０  ＝  ２
を得る。
【００１９】
二分決定グラフ２に対してダイクストラ法により、コスト１で到達できる範囲、コスト２で到達できる範囲、・・・と探索範囲を拡大すると、図２に示すように、最適化問題を最短経路問題として解くことができる。
【００２０】
図２は、第１関連技術における最適化問題を最短経路問題として解いた結果例を示す図である。図２では、目的関数が単一のＷＤＤで表現され、かつ、制約条件が付かない場合の結果例を示している。
【００２１】
図３は、第２関連技術におけるグラフ例を示す図である。図３において、非特許文献４によると、枝重み付きのＤＡＧ（Directed  Acyclic  Graph；非巡回有向グラフ）３ａにおいて２頂点間の経路の中で、与えられた制約を満たしつつ枝重みの和が最小となるものを求める。枝の組合せに関する制約がＢＤＤ３ｂで表現されている。
【００２２】
この第２関連技術では、ＤＡＧ３ａとＢＤＤ３ｂとを根から同時に探索し、動的計画法で重複計算を回避する。
【００２３】
ここで、複数のＷＤＤで与えられた問題を解く場合に、複数のＷＤＤを演算で一つに合成することが考えられる。一つに合成しようとすると、演算中または結果のデータ構造が大きくなりすぎることがある。節点数が元のグラフの節点数の積程度に及ぶ場合がある。
【００２４】
複数のＷＤＤを単に演算で一つに合成した場合、最適値に関係のないデータ構造まで構築され、処理時間及びメモリ空間を無駄に浪費してしまう。また、計算機の主記憶に収まらず、処理不能になることも考えられる。
【００２５】
一方、複数のＷＤＤを合成せずに探索を行った場合、データ構造の増加は抑制できるが、必要なタイミングで出力枝の重みが得られるとは限らない等により計算量が増大する。
【００２６】
上述した第１関連技術と第２関連技術について、図４の複数のＷＤＤの例を用いて考察する。図４は、複数のＷＤＤの例を示す図である。図４に示す７個のＷＤＤは、夫々、７個の関数を表わし、以下に、７個の関数の和の最小化について、第１関連技術と第２関連技術の夫々で試みる。この例の７個のＷＤＤでは合計１５節点となる。
【００２７】
図５は、第１関連技術に基づくＷＤＤの合成と探索範囲の例を示す図である。図５において、合成結果７ａは、第１関連技術に基づいて、図４に示す７個のＷＤＤを加算等の演算により一つに合成して得たＷＤＤを示している。探索範囲７ｂは、合成結果７ａに対してダイクストラ法により得られた探索の範囲を示している。
【００２８】
合成結果７ａでは、図４の個々のＷＤＤでは合計１５節点であったのが、２６節点に増大している。このように合成結果７ａを得てしまえば、探索範囲７ｂを定めることができ、効率良く探索可能となる。
【００２９】
図６は、第２関連技術に基づくＷＤＤの探索方法と探索範囲の例を示す図である。図６において、目的関数及び制約条件を含む７個のＷＤＤの集合をＷＤＤ集合８ａで示している。
【００３０】
このＷＤＤ集合８ａにおいて、合成されていない複数のＷＤＤを同時探索する場合について説明する。この場合、最適解を探索しながら二分決定グラフが生成される。探索範囲８ｂは、探索により生成された二分決定グラフを示している。
【００３１】
探索範囲８ｂが生成される過程の一部について説明する。探索範囲８ｂにおいて、レベル１の節点に、各ＷＤＤの最初の節点名を文字列で示し対応付ける。即ち、「ＡＣＥＧＩＫＭ」が、探索範囲８ｂの根となるレベル１の節点に対応付けられる。
【００３２】
０、１の値割り当てに対して同一コストの場合、０、１の値割り当ての順に、各ＷＤＤから次の節点を選択する。次の節点が終端の場合は黒い四角で表す。よって、探索範囲８ｂでは、レベル２において、レベル１から０値割り当ての次の節点には、「■ＤＥＧＩＫＭ」が対応付けられる。レベル１から１値割り当ての次の節点には、「Ｂ■ＥＧＩＫＭ」が対応付けられる。
【００３３】
このようにして、コスト１で到達できる範囲、コスト２で到達できる範囲、・・・と、ダイクストラ法を用いながら探索した経路を追加することでグラフ構造を成長させていくと探索範囲８ｂを得る。ＷＤＤを合成せずに探索した探索範囲８ｂにおいて、部分探索範囲８ｃはＷＤＤを合成した場合には生成されない部分に相当する。第２関連技術では、部分探索範囲８ｃを含むため、部分探索範囲８ｃに余計な処理時間を費やしていると言える。
【００３４】
本実施例では、複数のＷＤＤを合成する際のＷＤＤのデータ構造の増大を抑制することで、最小化問題の計算量を削減する。本実施例における、最小化問題の最適解を求める方法について説明する。本実施例では、主に、以下の手順Ａ、手順Ｂ、そして手順Ｃを行う。
・手順Ａ
各節点から出る枝の重みは０以上かつその一方は０であるようにＷＤＤのデータ構造を正規化する。
（１）目的関数を１以上のＷＤＤで表す。
（２）制約条件がある場合には、それらもＷＤＤで表す。その場合、制約違反は無限大の重みで表す。
（３）最大化問題は、目的関数を−１倍して最小化問題に変換する。
このようにすることで、全てのＷＤＤの和を最小化する問題に単純化する。
【００３５】
次に、
・手順Ｂ
２種類の等価変換を繰り返し行う。
（１）一つのＷＤＤを加法分解して複数のＷＤＤに変換する。
（２）複数のＷＤＤを加算して一つのＷＤＤに変換する。
【００３６】
そして、
・手順Ｃ
等価変換後の複数のＷＤＤを同時に探索して最適解を求める。
（１）複数のＷＤＤを組み合せたグラフの最短路問題を解く。ダイクストラ法を用いて行えば良い。
（２）グラフ構造を作りながら探索する。本実施例では、最適解に必要な部分のみが探索される。
【００３７】
図７及び図８は、本実施例における手順ＡにおけるＷＤＤの正規化規則を説明するための図である。先ず、図７において、目的関数ｆａ及びｆｂを例として、ＷＤＤの正規化について説明する。目的関数ｆａは最大化問題に相当し、目的関数ｆｂは最小化問題に相当する。目的関数ｆａのレベル１の節点「１」への重みが−１倍され最小化問題に変換されている。
【００３８】
目的関数ｆｂの節点「１」から出る枝の重みは、２つの枝とも「０」であるため、節点「１」から出る枝の重みが０以上かつその一方が０である目的関数ｆａを用いて正規化する。
【００３９】
先ず、同じ枝の重み同士を合計した値をその枝の重みとすることで、１つのｆｃを作成する。作成されたｆｃでは、節点「１」への重みは打ち消し合って０（−１＋１）となる。
【００４０】
また、節点「１」から０値割り当ての節点「２」への重み係数は１（１＋０）となり、節点「２」から０値割り当ての終端への重み係数は２（１＋１）となり、節点「２」から１値割り当ての終端への重み係数は０（０＋０）となる。
【００４１】
一方、節点「１」から１値割り当ての節点「２」への重み係数は０（０＋０）となり、節点「２」から０値割り当ての終端への重み係数は２（１＋１）となり、節点「２」から１値割り当ての終端への重み係数は３（３＋０）となる。よって、目的関数ｆａ及びｆｂをを重ね合わせたｆｃを得る。
【００４２】
次に、図８において、目的関数ｆａ及びｆｂを重ね合わせたｆｃの最下層のレベル２の各節点「２」からの２分岐の重み係数を比較し、重み係数が小さい枝の値を、２分岐の重み係数からそれぞれ減算することで、重み係数が小さい方の枝の重み係数を０にする。減算した重み係数は、節点「２」の一層上のレベル１の節点「１」への枝の重み係数に加算する。
【００４３】
この例では、ｆｃの最下層のレベル２の節点「２」のうち、節点「１」から０値割り当ての枝からの節点「２」は、１値割り当ての枝の重み係数が「０」であるため、上の層のレベル１の節点「１」への枝の重み係数に変化はない。
【００４４】
一方、節点「１」から１値割り当ての枝からの節点「２」は、０値割り当ての枝の重み係数「２」と、１値割り当ての枝の重み係数「３」のうち、小さい方の重み係数「２」が、上層のレベル１の節点「１」への枝の重み係数「０」に加算され「２」となる。また、小さい方の重み係数「２」が、同じ節点「２」の１値割り当ての枝の重み係数「３」から減算され「１」となる。ｆｃの各枝に与えられた重み係数は、ｆｄで示されるように変化する。ｆｄでは、最下層のレベル２の各節点「２」から出る枝の重みは０以上かつその一方は０となる。
【００４５】
次に、ｆｄにおいて、同様の重み係数の上の層への持ち上げを行う。具体的には、レベル１の節点「１」に関して、０値割り当ての枝の重み係数「１」と、１値割り当ての枝の重み係数「２」のうち、小さい方の重み係数「１」が、節点「１」への枝の重み係数「０」に加算される。従って、ｆｄはｆｅに変化し、全ての節点からの枝に対して、０以上かつその一方は０であるように正規化されたｆｅを得る。
【００４６】
図９は、本実施例における手順ＢにおけるＷＤＤの加法分解を説明するための図である。図９では、ｆｐを用いて加法分解する例を説明する。先ず、ｆｐをｆｑとｆｒとに分解する。一般に重みの配分は任意である。
【００４７】
節点からの両枝の重み係数が「０」かつ両枝ともに同じ節点に向かう構造部分は省略できる。具体的には、ｆｑでは構造部分９ｇが省略され、ｆｒでは構造部分９ｈ及び９ｋが省略される。つまり、ｆｑではｆｓに変換され、ｆｒはｆｔに変換される。
【００４８】
図１０は、加法分解と加算の組合せによる等価変換を説明するための図である。図１０では、関数ｆ及び関数ｇをＷＤＤで表し、加法分解と加算の組合せによる等価変換について説明する。以下の説明において、各関数のＷＤＤを単に関数名で呼ぶものとする。
【００４９】
関数ｆと関数ｇとを、変数ｘｋで分岐する枝の重みを０にしたものと、変数ｘｋで分岐する枝以外の重みを０にしたものに加法分解する。変数ｘｋで分岐する枝以外の重みを０にしたもの同士を加算する。
【００５０】
図１０において、関数ｆは、図９で説明したように関数ｆ’と関数ｆ’’とに加法分解される。関数ｇのＷＤＤも同様に、関数ｇ’と関数ｇ’’とに加法分解される。関数ｆ’と関数ｇ’とが、変数ｘｋで分岐する枝の重みを０にしたものに相当する。また、関数ｆ’’と関数ｇ’’とが、変数ｘｋで分岐する枝以外の重みを０にしたものに相当する。
【００５１】
そして、加法分解された関数ｆ’’と関数ｇ’’とを加算して関数ｆ’’＋ｇ’’を作成する。加算によって、下位に存在した重み係数が上位の節点の分岐の重み係数に加算され、０及び１値割り当ての両方の枝の重み係数が０となる構造部分が省略される。従って、ＷＤＤのデータ構造の増大を抑止できる。
【００５２】
上述した手順Ａ及び手順Ｂの後、手順Ｃを行うことで、等価変換後の複数のＷＤＤを同時に探索して最適解が求められる。上述した手順Ａ、手順Ｂ、そして手順Ｃを行う探索処理最適化装置１００について説明する。
【００５３】
図１１は、探索処理最適化装置のハードウェア構成を示す図である。図１１において、探索処理最適化装置１００は、コンピュータによって制御される情報処理装置であって、ＣＰＵ（Central  Processing  Unit）１１と、主記憶装置１２と、補助記憶装置１３と、入力装置１４と、表示装置１５と、通信Ｉ／Ｆ（インターフェース）１７と、ドライブ装置１８とを有し、バスＢに接続される。
【００５４】
ＣＰＵ１１は、主記憶装置１２に格納されたプログラムに従って探索処理最適化装置１００を制御するプロセッサに相当する。主記憶装置１２には、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）等が用いられ、ＣＰＵ１１にて実行されるプログラム、ＣＰＵ１１での処理に必要なデータ、ＣＰＵ１１での処理にて得られたデータ等を記憶又は一時保存する。
【００５５】
補助記憶装置１３には、ＨＤＤ（Hard  Disk  Drive）等が用いられ、各種処理を実行するためのプログラム等のデータを格納する。補助記憶装置１３に格納されているプログラムの一部が主記憶装置１２にロードされ、ＣＰＵ１１に実行されることによって、各種処理が実現される。記憶部１３０は、主記憶装置１２及び／又は補助記憶装置１３に相当する。
【００５６】
入力装置１４は、マウス、キーボード等を有し、ユーザが探索処理最適化装置１００による処理に必要な各種情報を入力するために用いられる。表示装置１５は、ＣＰＵ１１の制御のもとに必要な各種情報を表示する。入力装置１４と表示装置１５とは、一体化したタッチパネル等によるユーザインタフェースであってもよい。通信Ｉ／Ｆ１７は、有線又は無線などのネットワークを通じて通信を行う。通信Ｉ／Ｆ１７による通信は無線又は有線に限定されるものではない。
【００５７】
探索処理最適化装置１００によって行われる処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ（Compact  Disc  Read‐Only  Memory）等の記憶媒体１９によって探索処理最適化装置１００に提供される。
【００５８】
ドライブ装置１８は、ドライブ装置１８にセットされた記憶媒体１９（例えば、ＣＤ−ＲＯＭ等）と探索処理最適化装置１００とのインターフェースを行う。
【００５９】
また、記憶媒体１９に、後述される本実施の形態に係る種々の処理を実現するプログラムを格納し、この記憶媒体１９に格納されたプログラムは、ドライブ装置１８を介して探索処理最適化装置１００にインストールされる。インストールされたプログラムは、探索処理最適化装置１００により実行可能となる。
【００６０】
尚、プログラムを格納する記憶媒体１９はＣＤ−ＲＯＭに限定されず、コンピュータが読み取り可能な、構造（structure）を有する１つ以上の非一時的（non‐transitory）な、有形（tangible）な媒体であればよい。コンピュータ読取可能な記憶媒体として、ＣＤ−ＲＯＭの他に、ＤＶＤディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリであっても良い。
【００６１】
図１２は、探索処理最適化装置の機能構成例を示す図である。図１２において、探索処理最適化装置１００は、正規化部４１と、等価変換部４３と、最適解探索部４５とを有する。記憶部１３０は、正規化後ＷＤＤ集合５１、等価後ＷＤＤ集合５３、最適解ＷＤＤ５５等を有する。
【００６２】
正規化部４１は、目的関数と制約条件とを指定した入力データ２９を入力すると、ＷＤＤを作成し、作成したＷＤＤを正規化する。入力データ２９には、２以上の目的関数、及び２以上の制約条件を含んでもよい。正規化部４１は、最大化問題の目的関数に対しては、ＷＤＤの根へと接続される枝に−１倍した重み付けを行うことで、最小化問題に変換する。
【００６３】
正規化部４１は、入力データ２９に制約条件が含まれる場合、制約違反の重みは無限大に設定してＷＤＤで表す。正規化部４１は、作成した複数のＷＤＤに対して、各節点から出る枝の重みは０以上かつその一方は０であるようにＷＤＤのデータ構造を正規化し、記憶部１３０に出力する。正規化後ＷＤＤ集合５１に正規化されたＷＤＤが記憶される。
【００６４】
等価変換部４３は、正規化後ＷＤＤ集合５１に記憶されたＷＤＤに対して、加法分解及び加算により等価変換を行って、記憶部１３０に出力する。等価後ＷＤＤ集合５３に等価変換されたＷＤＤが記憶される。
【００６５】
最適解探索部４５は、等価後ＷＤＤ集合５３に記憶された複数のＷＤＤを同時に探索して最適解を求める。最適解探索部４５は、ダイクストラ法を用いて、最短路問題を解く。本実施例では、最短路問題を解く過程で生成されるグラフ構造は、最適解に必要な節点のみを表わすＷＤＤである。最適解を解くために必要となったＷＤＤが記憶部１３０の最適解ＷＤＤ５５に記憶される。
【００６６】
探索処理最適化装置１００による探索処理最適化方法について説明する。図１３は、探索処理最適化方法の概要を説明するためのフローチャート図である。図１３において、探索処理最適化装置１００の正規化部４１は、入力データ２９を受け付けることにより目的関数と制約条件とを入力する（ステップＳ１０１）。
【００６７】
そして、正規化部４１は、目的関数と制約条件とから複数のＷＤＤを作成し、正規化する正規化処理を行う（ステップＳ１０２）。正規化後ＷＤＤ集合５１が記憶部１３０に記憶される。
【００６８】
次に、等価変換部４３が、正規化ＷＤＤ集合５１に対して等価変換を施す等価変換処理を行う（ステップＳ１０３）。本実施例に係る等価変換処理について後に詳述される。等価後ＷＤＤ集合５３が記憶部１３０に記憶される。
【００６９】
等価変換後、最適解探索部４５は、等価後ＷＤＤ集合５３を用いて、等価変換された複数のＷＤＤを同時に探索して最適な値割り当てを検出して（ステップＳ１０４）、出力する（ステップＳ１０５）。その後、探索処理最適化装置１００による処理は終了する。
【００７０】
次に、本実施例に係る等価変換部４３による等価変換処理について説明する。図１４は、等価変換処理の第一例を説明するためのフローチャート図である。図１４において、正規化後ＷＤＤ集合５１を「ＷＤＤ集合Ｆ」という。ＷＤＤ集合Ｆは、ｆ１、ｆ２、・・・、ｆｎの要素を含んでいる。各ｆｉ、及び以下の説明中のｆ’、ｆ’’、及びｈは、ＷＤＤで表される関数である。
【００７１】
等価変換部４３は、変数番号の列Ｓを決定する（ステップＳ２０１）。変数番号は、ＷＤＤの節点のレベルに相当する。列Ｓは、全ての変数番号を下から順にｎ個を羅列した数列によって表される。又は、任意のｋレベルから降順に変数番号を示した数列で表されてもよい。その他、全ての変数番号からランダムに選択して数列で表しても良い。
【００７２】
等価変換部４３は、列Ｓから先頭の変数番号ｋを取り出して（ステップＳ２０２）、等価変換部４３は、集合Ｇを空に設定し、ｈを定数０を表わすＷＤＤとする初期化を行う（ステップＳ２０３）。列Ｓから先頭の変数番号ｋが削除される。
【００７３】
後述される処理例において、集合Ｇは、注目した節点において、加法分解後により、分岐に重みを持たないグループ（図１７、図１９、図２１、図２３、図２５、及び図２８の上段）に分類された関数の集合を表わす。ｈは、分岐に重みを持つグループ（図１７、図１９、図２１、図２３、図２５、及び図２８の下段）に分類された関数の集合を表わす。
【００７４】
等価変換部４３は、ＷＤＤ集合Ｆから要素を一つ取り出しｆとする（ステップＳ２０４）。ＷＤＤ集合Ｆから取り出したｆが削除される。そして、等価変換部４３は、変数ｘｋで分岐する枝の重みを０にしたｆ’と、それ以外を０にしたｆ’’に、ｆを加法分解する（ステップＳ２０５）。
【００７５】
そして、等価変換部４３は、集合Ｇに要素としてｆ’を加え（ステップＳ２０６）、ｈとｆ’’とを加算した値をｈに設定し（ステップＳ２０７）、ＷＤＤ集合Ｆが空になったか否かを判断する（ステップＳ２０８）。ｈは、後述される処理例において、２以上のｆ’’の場合にｆ’’全てを加算して一つのＷＤＤで表した関数ｆＡ、関数ｆＢ、関数ｆＣ、関数ｆＤ、及び関数ｆＥに相当する。ｆ’’が１つの場合は、ｈは、そのｆ’’自身のＷＤＤとなる。
【００７６】
空になっていない場合（ステップＳ２０８のＮＯ）、等価変換部４３は、ステップＳ２０４へと進み、ＷＤＤ集合Ｆが空になるまで上述した同様の処理を繰り返す。ＷＤＤ集合Ｆが空になった場合（ステップＳ２０８のＹＥＳ）、等価変換部４３は、集合Ｇに要素としてｈを加算してＷＤＤ集合Ｆとする（ステップＳ２０９）。
【００７７】
そして、等価変換部４３は、列Ｓが空か否かを判断する（ステップＳ２１０）。列Ｓが空でない場合（ステップＳ２１０のＮＯ）、等価変換部４３は、ステップＳ２０２へと戻り、上記同様の処理を繰り返す。一方、列Ｓが空の場合（ステップＳ２１０のＹＥＳ）、等価変換部４３は、この等価変換処理を終了する。
【００７８】
図１５は、等価変換処理の第二例を説明するためのフローチャート図である。図１５に示す等価変換処理の第二例では、ＷＤＤが大きくなりすぎると判断したら、加算を抑制し一つのＷＤＤに集約しない。閾値Ｍ単位で、ｆ’’を加算する。図１５中、第一例と同様の処理には同様の符号を付し、その説明を省略する。
【００７９】
ステップＳ２０１〜Ｓ２０６までを行うと、等価変換部４３は、ｈとｆ’’とのサイズの合計が閾値Ｍ未満であるか否かを判断する（ステップＳ２０６ａ）。サイズは、節点の数で示せばよい。
【００８０】
サイズが閾値Ｍ未満である場合（ステップＳ２０６ａのＹＥＳ）、等価変換部４３は、ステップＳ２０７へと進む。一方、サイズが閾値Ｍ以上である場合（ステップＳ２０６ａのＮＯ）、等価変換部４３は、ｈのサイズがｆ’’のサイズ未満であるか否かを更に判断する（ステップＳ２０６ｂ）。
【００８１】
ｈのサイズがｆ’’のサイズより大きい場合（ステップＳ２０６ｂのＹＥＳ）、等価変換部４３は、ｈとｆ’’を交換して（ステップＳ２０６ｃ）、ステップＳ２０６ｄへと進む。一方、ｈのサイズがｆ’’のサイズ以下の場合（ステップＳ２０６ｂのＮＯ）、等価変換部４３は、ステップＳ２０６ｄへと進む。
【００８２】
その後、等価変換部４３は、集合Ｇに要素としてｆ’’を加え（ステップＳ２０６ｄ）、ステップＳ２０８へと進む。ステップＳ２０８〜Ｓ２１０は、第一例と同様であるため、その説明を省略する。ステップＳ２１０の後、等価変換部４３は、等価変換処理を終了する。
【００８３】
サイズが閾値Ｍ以上である場合に、ステップＳ２０６ｂからＳ２０６ｄの制御を行うことで、サイズが閾値Ｍの範囲毎に、分岐する枝以外を０にしたｆ’’の加算が行われる。従って、ｆ’’の加算後のＷＤＤを表わすデータ構造のサイズの増大を抑制できる。
【００８４】
この第二例では、最適解探索部４５による探索の手戻りを許容することになるが、データサイズが急激に増大することを避けることができる。
【００８５】
以下に、７個の関数、即ち、ＷＤＤ（合計１５節点）を例として、本実施例における処理例を説明する。図１６は、正規化後ＷＤＤの例を示す図である。図１６にて、入力データ２９で指定された目的関数及び制約条件をＷＤＤで表した後、正規化した７個のＷＤＤを示す。７個のＷＤＤは、正規化後ＷＤＤ集合５１に相当する。
【００８６】
７個のＷＤＤは、正規化後ＷＤＤ集合５１に相当し、図１４及び図１５ではＷＤＤ集合Ｆに相当する。正規化後ＷＤＤ集合５１（ＷＤＤ集合Ｆ）の各ＷＤＤは、図４で示したＷＤＤと同様であるが、本実施例の説明において、関数ｆ１、ｆ２、・・・、ｆ７で表すものとする。また、各節点はレベル番号を示し、以下の説明において、レベル１、２、・・・、６はｘ１、ｘ２、・・・、ｘ６を表わす。
【００８７】
等価変換処理の第一例において、最下位のレベル６に相当するｘ６から等価変換を行うものとし、以下に処理例を説明する。以下の説明において、等価変換のうち加法分解では、図中の上段に注目した節点（以下、「注目節点」という）からの分岐に重みをもたない関数を分類し、下段に注目節点からの分岐に重みをもつ関数を分類して示す。注目節点が存在しない場合、上段に分類される。
【００８８】
図１７は、ｘ６に注目して加法分解を行うステップ１ａを説明するための図である。図１７において、図１６に示す７個のＷＤＤで表される関数ｆ１〜関数ｆ７のうち、関数ｆ５、関数ｆ６、及び関数ｆ７が加法分解される。
【００８９】
関数ｆ５は、ｘ６を含まないＷＤＤで表される関数ｆ５’と、ｘ６からのＷＤＤで表される関数ｆ５’’とに分解され、夫々、上段及び下段に分類される。また、関数ｆ６は、ｘ６からの分岐に重みをもち、ｘ６の上位レベルのｘ４からの分岐は重みをもたないため、関数ｆ６全体が下段に分類される。関数ｆ７は、加法分解によって、ｘ７を含まないＷＤＤで表される関数ｆ７’と、ｘ７からのＷＤＤで表される関数ｆ７’’とに分解され、夫々、上段及び下段に分類される。
【００９０】
図１８は、ｘ６に注目した加法分解後にＷＤＤを加算するステップ１ｂを説明するための図である。図１８のステップ１ｂでは、図１７において下段に分類された関数ｆ５’’と、関数ｆ６と、関数ｆ７’’とを合成することで、関数ｆ６と、関数ｆ７’’とを加算した関数ｆＡが生成される。生成された関数ｆＡが上段に分類される。
【００９１】
次に、注目節点が一段上のレベル５に上りｘ６からｘ５となり、図１９に示すような加法分解が行われる。
【００９２】
図１９は、ｘ５に注目して加法分解を行うステップ２ａを説明するための図である。図１９において、図１８に示す７個のＷＤＤで表される関数ｆ１〜関数ｆ４、関数ｆ５’、関数ｆ７’、及び関数ｆＡのうち、関数ｆ１、関数ｆ３、及び関数ｆ７’が加法分解される。
【００９３】
関数ｆ１は、ｘ５からの分岐に重みをもち、ｘ５の上位レベルのｘ１からの分岐は重みをもたないため、関数ｆ１全体が下段に分類される。関数ｆ３も同様である。関数ｆ３全体が下段に分類される。
【００９４】
図１８の関数ｆ７’は、加法分解によって、ｘ５を含まないＷＤＤで表される関数ｆ７‐２’と、ｘ５からのＷＤＤで表される関数ｆ７‐２’’とに分解され、夫々、上段及び下段に分類される。関数ｆ７‐２’は上段に分類され、関数ｆ７‐２’’は下段に分類される。
【００９５】
図２０は、ｘ５に注目した加法分解後にＷＤＤを加算するステップ２ｂを説明するための図である。図２０のステップ２ｂでは、図１９において下段に分類された関数ｆ５’’と、関数ｆ６と、関数ｆ７’’とを合成することで、関数ｆ５’’と、関数ｆ６と、関数ｆ７’’とを加算した関数ｆＢが生成される。生成された関数ｆＢが上段に分類される。
【００９６】
次に、注目節点が一段上のレベル４に上りｘ５からｘ４となり、図２１に示すような加法分解が行われる。
【００９７】
図２１は、ｘ４に注目して加法分解を行うステップ３ａを説明するための図である。図２１において、図２０に示す６個のＷＤＤで表される関数ｆ２、関数ｆ４、関数ｆ５’、関数ｆ７−２’、関数ｆＡ、及び関数ｆＢのうち、関数ｆ４が加法分解される。
【００９８】
図２０の関数ｆＡは、加法分解によって、ｘ４の重みを０にしたＷＤＤで表される関数ｆＡ‐２’と、ｘ４からのＷＤＤで表される関数ｆＡ‐２’’とに分解され、夫々、上段及び下段に分類される。
【００９９】
図２２は、ｘ４に注目した加法分解後にＷＤＤを加算するステップ３ｂを説明するための図である。図２２のステップ３ｂでは、図２１において、下段に分類されたＷＤＤは関数ｆＡ‐２’’の１つであるため、合成処理は省略され、そのまま上段に分類される。
【０１００】
次に、注目節点が一段上のレベル３に上りｘ４からｘ３となり、図２３に示すような加法分解が行われる。
【０１０１】
図２３は、ｘ３に注目して加法分解を行うステップ４ａを説明するための図である。図２３において、図２２に示す７個のＷＤＤで表される関数ｆ２、関数ｆ４、関数ｆ５’、関数ｆ７−２’、関数ｆＡ−２’、関数ｆＢ、及び関数ｆＡ−２’’のうち、関数ｆ４及び関数ｆ５’が加法分解される。
【０１０２】
図２２の関数ｆ４は、ｘ３からの分岐に重みをもち、ｘ３の上位レベルのｘ２からの分岐は重みをもたないため、関数ｆ４全体が下段に分類される。また、関数ｆ５’は、ｘ３からの分岐に重みをもつが、ｘ３の上位レベルに節点がないため、関数ｆ３全体が下段に分類される。
【０１０３】
図２４は、ｘ３に注目した加法分解後にＷＤＤを加算するステップ４ｂを説明するための図である。図２４のステップ４ｂでは、図２３において、下段に分類された関数ｆ４と、関数ｆ５’とを合成することで、関数ｆ４と、関数ｆ５’とを加算した関数ｆＣが生成される。生成された関数ｆＣが上段に分類される。
【０１０４】
次に、注目節点が一段上のレベル２に上りｘ３からｘ２となり、図２５に示すような加法分解が行われる。
【０１０５】
図２５は、ｘ２に注目して加法分解を行うステップ５ａを説明するための図である。図２５において、図２４に示す６個のＷＤＤで表される関数ｆ２、関数ｆ４、関数ｆ７−２’、関数ｆＡ−２’、関数ｆＢ、関数ｆＡ−２’’、及び関数ｆＣのうち、関数ｆ２、関数ｆ７−２’、及び関数ｆＢが加法分解される。
【０１０６】
図２４の関数ｆ２は、ｘ２からの分岐に重みをもち、ｘ２の上位レベルのｘ１からの分岐は重みをもたないため、関数ｆ２全体が下段に分類される。また、関数ｆ７−２’は、ｘ２からの分岐に重みをもつが、ｘ２の上位レベルに節点がないため、関数ｆ７−２’全体が下段に分類される。
【０１０７】
関数ｆＢは、ｘ２からの分岐に重みをもたないＷＤＤで表される関数ｆＢ’と、ｘ２からの分岐に重みをもつＷＤＤで表される関数ｆＢ’’とに分解され、夫々、上段及び下段に分類される。
【０１０８】
図２６は、ｘ２に注目した加法分解後にＷＤＤを加算するステップ５ｂを説明するための図である。図２６のステップ５ｂでは、図２５において下段に分類された関数ｆ２と、関数ｆ７−２’と、関数ｆＢとを合成することで、関数ｆ２と、関数ｆ７−２’と、関数ｆＢとを加算した関数ｆＤが生成される。生成された関数ｆＤが上段に分類される。
【０１０９】
次に、注目節点が一段上のレベル１に上りｘ２からｘ１となり、図２７に示すような加法分解が行われる。
【０１１０】
図２７は、ｘ１に注目して加法分解を行うステップ６ａを説明するための図である。図２７において、図２６に示す５個のＷＤＤで表される関数ｆＡ−２’、関数ｆＢ’、関数ｆＡ−２’’、関数ｆＣ、及び関数ｆＤのうち、関数ｆＢ’が加法分解される。
【０１１１】
図２６の関数ｆＢ’は、加法分解によって、ｘ１からの分岐に重みをもたないＷＤＤで表される関数ｆＢ−２’と、ｘ１からの分岐に重みをもつＷＤＤで表される関数ｆＢ−２’’とに分解される。関数ｆＢ‐２’は上段に分類され、関数ｆＢ‐２’’は下段に分類される。
【０１１２】
図２８は、ｘ１に注目した加法分解後にＷＤＤを加算するステップ６ｂを説明するための図である。図２８のステップ６ａでは、図２７において下段に分類された関数ｆＢ‐２’’を、上段に分類されている節点が無く終端と終端への枝のみで表される関数ｆＤと合成するように、２つのＷＤＤを加算して、関数ｆＥを生成する。
【０１１３】
従って、関数ｆＡ−２’、関数ｆＢ‐２’、関数ｆＡ−２’’、関数ｆＣ、及び関数ｆＥの５個のＷＤＤが、等価後ＷＤＤ集合５３の要素となる。この等価後ＷＤＤ集合５３の節点の合計は１６である。また、どの変数からの分岐に関しても、０より大きい重みをもつＷＤＤは高々一つである。即ち、上の階層の変数から順に、最適な値割り当てを手戻り無く選択可能となる。また、単一のＷＤＤに合成した時と同等の結果を得られる。
【０１１４】
このような等価後ＷＤＤ集合５３を用いて、最適解探索部４５は、複数のＷＤＤを同時に探索して、最適解ＷＤＤ５５を生成する。
【０１１５】
図２９は、複数のＷＤＤの同時探索による最適解ＷＤＤの例を示す図である。図２９において、最適解ＷＤＤ５５は、最適解探索部４５が等価後ＷＤＤ集合５３に含まれる複数のＷＤＤを同時に探索して得たＷＤＤである。
【０１１６】
本実施例における最適解ＷＤＤ５５は、図５の探索範囲７ｂと同様の結果を示している。しかしながら、本実施例では、図５に示されるような合成結果７ａを生成することなく、最適解ＷＤＤ５５を得ている点で、第１関連技術と比べてデータ構造の増大を抑制できている。
【０１１７】
また、第２関連技術と同様に複数のＷＤＤを同時探索するものの、第２関連技術と比べて、本実施例では、等価後ＷＤＤ集合５３を用いることで、最適解ＷＤＤ５５を得るまでの計算量を削減することができる。
【０１１８】
発明者は、目的関数のみによる最適解を探索する第１関連技術の場合と、本実施例と、目的関数と制約条件とを同時に探索し単一ＷＤＤを合成する第２関連技術の場合とについて、以下のような比較結果を得た。
【０１１９】
図３０は、比較結果例を示す図である。図３０では、wdd001．wcnfからwdd006．wcnfの６問題についての比較例を示す。wdd001．wcnfは２７変数及び１６２関数を含み、wdd002．cnfは２８変数及び４２０関数を含み、wdd003．wcnfは３６変数及び２３０関数を含み、wdd004．cnfは４０変数及び７４４関数を含み、wdd005．wcnfは４２変数及び１０３５関数を含み、wdd006．wcnfは１３９変数及び７１１関数を含む。
【０１２０】
また、本実施例として、図１５の閾値Ｍを用いた等価変換処理の第二例を採用し、閾値Ｍを「100」、「10000」、及び「∞」（図１４の等価変換処理の第一例に相当する）の各々とした場合の結果を示している。
【０１２１】
図３０（Ａ）では、最適解を探索する処理への入力となる複数のＷＤＤの合計節点数の比較結果を示している。合計節点数では、第１関連技術の場合、本実施例、第２関連技術の場合の順に、増加傾向にある。一例として、wdd001．wcnfでは、第１関連技術の場合で「324」であり、本実施例の閾値Ｍ＝100の場合で「2245」、閾値Ｍ＝10000の場合で「87634」、閾値Ｍ＝∞の場合で「104333」を示し、第２関連技術の場合では「782911」であった。
【０１２２】
wdd001．wcnfに関して、本実施例の合計節点数は第１関連技術の場合の合計節点数より多く、本実施例の合計節点数は第２関連技術の場合の合計節点数より少ない。他の問題においても同様の傾向を示している。
【０１２３】
図３０（Ｂ）では、探索節点数の比較結果を示している。探索節点数では、図３０（Ａ）の合計節点数とは逆の傾向を示している。即ち、第１関連技術の場合、本実施例、第２関連技術の場合の順に、減少傾向にある。一例として、wdd001．wcnfでは、第１関連技術の場合で「59063」であり、本実施例の閾値Ｍ＝100の場合で「7303」、閾値Ｍ＝10000の場合で「1516」、閾値Ｍ＝∞の場合で「78」を示し、第２関連技術の場合では「78」であった。
【０１２４】
wdd001．wcnfに関して、本実施例の探索節点数は第１関連技術の場合の合計節点数より少なく、本実施例の合計節点数は第２関連技術の場合の合計節点数以下である。他の問題においても同様の傾向を示している。
【０１２５】
図３０（Ｃ）では、処理時間（秒）の比較結果を示している。本実施例は、第１関連技術の場合及び第２関連技術の場合の少なくとも一方に対して、処理時間を短縮できている。
【０１２６】
本実施例による処理時間は、閾値Ｍ＝100の場合に、第１関連技術の場合の処理時間と同程度、又は、大幅に短縮できている。また、閾値Ｍ＝100、10000、及び∞の各々において、概ね、効果的に処理時間が短縮されている。
【０１２７】
上述したように、本実施例では、目的関数や制約条件がＷＤＤで与えられた組合せ最適化問題において、問題を解く過程におけるデータ構造の増大を抑制することで、計算量を削減できる。
【０１２８】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、主々の変形や変更が可能である。
【０１２９】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行い、
正規化を行った前記複数の枝重み付き二分決定グラフに対して加法分解を行い、
前記加法分解を行って得た複数の二分決定グラフを同時に探索して最適解を求める
処理をコンピュータに行わせる探索処理最適化プログラム。
（付記２）
前記コンピュータに、
下位の階層から上位の階層へと階層を選択させ、
正規化を行った前記複数の枝重み付き二分決定グラフの各々に対して、選択した前記階層の各節点の分岐の前記重み係数を参照し、該節点からの分岐に重み係数が前記一定の値以下の第１グラフと、該節点からの分岐だけに該一定の値より大きい重み係数を持つ第２グラフとに分解することによって、前記加法分解を行わせる
ことを特徴とする付記１記載の探索処理最適化プログラム。
（付記３）
前記コンピュータに、
前記加法分解により前記第２グラフが複数生成された場合、該複数の第２グラフを加算して１つの前記枝重み付き二分決定グラフを作成する
処理を行わせることを特徴とする付記２記載の探索処理最適化プログラム。
（付記４）
前記コンピュータに、
選択した前記階層において、前記節点毎に行った前記加法分解によって生成された前記第２グラフ同士の加算後のサイズが定めた閾値を超える場合は、閾値単位で第２グラフ同士を加算する
処理を行わせることを特徴とする付記３記載の探索処理最適化プログラム。
（付記５）
前記一定の値は０であることを特徴とする付記１乃至４のいずれか一項記載の探索処理最適化プログラム。
（付記６）
前記複数の枝重み付き二分決定グラフは、１以上の目的関数を表わす枝重み付き二分決定グラフと、１以上の制約条件を表わす枝重み付き二分決定グラフとを含む
ことを特徴とする付記１乃至５のいずれか一項記載の探索処理最適化プログラム。
（付記７）
前記コンピュータに、
最大化問題の目的関数は、前記枝重み付き二分決定グラフの根へと接続される枝を−１倍した重み付けを行うことで、最小化問題に変換する
処理を行わせることを特徴とする付記６記載の探索処理最適化プログラム。
（付記８）
複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行い、
正規化を行った前記複数の枝重み付き二分決定グラフに対して加法分解を行い、
前記加法分解を行って得た複数の二分決定グラフを同時に探索して最適解を求める
処理をコンピュータが行う探索処理最適化方法。
（付記９）
複数の枝重み付き二分決定グラフの各々に対して、各節点からの二分岐の重み係数を比較し、重み係数が小さい枝の値を、該二分岐の各枝の重み係数からそれぞれ引くことで、該重み係数が小さい枝の重み係数が一定の値になる様にし、該重み係数が小さい枝の値を一つ上の階層の節点の分岐に加える正規化を行う正規化部と、
正規化を行った前記複数の枝重み付き二分決定グラフに対して加法分解を行う変換部と、
前記加法分解を行って得た複数の二分決定グラフを同時に探索して最適解を求める探索部と
を有する探索処理最適化装置。
【符号の説明】
【０１３０】
２９          入力データ
４１          正規化部
４３          等価変換部
４５          最適解探索部
５１          正規化後ＷＤＤ集合
５３          等価後ＷＤＤ集合
５５          最適解グラフ構造
１００        探索処理最適化装置
１３０        記憶部
【図１】
0006701937.tif 000003
【図２】
0006701937.tif 000004
【図３】
0006701937.tif 000005
【図４】
0006701937.tif 000006
【図５】
0006701937.tif 000007
【図６】
0006701937.tif 000008
【図７】
0006701937.tif 000009
【図８】
0006701937.tif 000010
【図９】
0006701937.tif 000011
【図１０】
0006701937.tif 000012
【図１１】
0006701937.tif 000013
【図１２】
0006701937.tif 000014
【図１３】
0006701937.tif 000015
【図１４】
0006701937.tif 000016
【図１５】
0006701937.tif 000017
【図１６】
0006701937.tif 000018
【図１７】
0006701937.tif 000019
【図１８】
0006701937.tif 000020
【図１９】
0006701937.tif 000021
【図２０】
0006701937.tif 000022
【図２１】
0006701937.tif 000023
【図２２】
0006701937.tif 000024
【図２３】
0006701937.tif 000025
【図２４】
0006701937.tif 000026
【図２５】
0006701937.tif 000027
【図２６】
0006701937.tif 000028
【図２７】
0006701937.tif 000029
【図２８】
0006701937.tif 000030
【図２９】
0006701937.tif 000031
【図３０】
0006701937.tif 000032