(57)【要約】【課題】集合分割問題の近似解を効率的に求めることができるようにする。【解決手段】局所探索実行部１４が、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す。深さ優先探索実行部１６は、計算された違反度が閾値以下となったときに、解候補に基づいて、厳密被覆問題を作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める。そして、局所探索実行部１４は、深さ優先探索実行部１６により求められた解と、解候補に含まれる、２以上の部分集合に含まれる要素を含む部分集合以外の部分集合とに基づいて、集合分割問題の近似解を求める。【選択図】図１
2019021052.tif 000002
【特許請求の範囲】
【請求項１】
要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す局所探索実行部と、
前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める深さ優先探索実行部と、
を含む集合分割問題求解装置。
【請求項２】
前記違反度は、各要素について、前記解候補において前記要素が何れの部分集合にも含まれないこと、及び前記要素が２以上の部分集合に含まれることを表す請求項１記載の集合分割問題求解装置。
【請求項３】
前記深さ優先探索実行部は、前記厳密被覆問題の全ての解を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)を、深さ優先探索により構築し、前記ゼロサプレス型二分決定グラフが保持する前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解を求める請求項１又は２記載の集合分割問題求解装置。
【請求項４】
予め定められた終了条件を満たすまで、前記局所探索実行部による処理と、前記深さ優先探索実行部による処理とを繰り返す請求項１〜請求項３の何れか１項記載の集合分割問題求解装置。
【請求項５】
局所探索実行部が、要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返し、
深さ優先探索実行部が、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める
集合分割問題求解方法。
【請求項６】
前記違反度は、各要素について、前記解候補において前記要素が何れの部分集合にも含まれないこと、及び前記要素が２以上の部分集合に含まれることを表す請求項５記載の集合分割問題求解方法。
【請求項７】
前記深さ優先探索実行部が求めることでは、前記厳密被覆問題の全ての解を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)を、深さ優先探索により構築し、前記ゼロサプレス型二分決定グラフが保持する前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解を求める請求項５又は６記載の集合分割問題求解方法。
【請求項８】
コンピュータを、請求項１〜４のいずれか１項に記載の集合分割問題求解装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集合分割問題求解装置、方法、及びプログラムに係り、特に、集合分割問題を解くための集合分割問題求解装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
組合せ最適化問題の一種である、集合分割問題は、Ｍ個の要素からなる全体集合Ｕ = ｛1,...,Ｍ｝、Ｎ個のＵの部分集合
2019021052.tif 000003
から構成される集合Ｓ＝｛ｓ１,ｓ２，．．．，ｓＮ｝および各siに対する非負のコストc(si)が与えられたときに、
2019021052.tif 000004
を満たし、かつすべての
2019021052.tif 000005
であるような
2019021052.tif 000006
に対して
2019021052.tif 000007
を満たすような
2019021052.tif 000008
のうち、コストの総和
2019021052.tif 000009
を最小とするものを見つける問題である。集合分割問題は、
【０００３】
【数１】
2019021052.tif 000010
2019021052.tif 000011
2019021052.tif 000012
【０００４】
としても表現できる。ここでxj はsjが解に含まれたときに1、そうでないと0となる二値変数である。cjはc(sj)の値を表す。aijは，全体集合のi番目の要素がsjに含まれているときに1、そうでないときに0をとる。なお，以下ではx1,...,xNをあわせてＮ次元の二値ベクトルＸとして表現する。また、Ｘへのある値｛0,1｝Nの割当をxとして表現する。
【０００５】
集合分割問題はNP困難であることが知られている。
【０００６】
大規模な集合分割問題の最適解を求めることは一般に非常に困難である。そこで、最適解でなくとも効率的によい解を見つけることが可能な局所探索法に基づく近似解法が用いられている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Shunji Umetani, “Exploiting Variable Associations to Configure Efficient Local Search in Large-Scale Set Partitioning Problems', In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-15), 2015
【発明の概要】
【発明が解決しようとする課題】
【０００８】
局所探索法は高速に探索を実行できるものの、制約条件を満たす解（実行可能解）を効率的に見つけることができないという課題があった。
【０００９】
本発明は、上記の事情に鑑みてなされたもので、集合分割問題の近似解を効率的に求めることができる集合分割問題求解装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明に係る集合分割問題求解装置は、要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す局所探索実行部と、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める深さ優先探索実行部と、を含んで構成されている。
【００１１】
本発明に係る集合分割問題求解方法は、局所探索実行部が、要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返し、前記深さ優先探索実行部が、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める。
【００１２】
本発明に係るプログラムは、コンピュータを、上記発明に係る集合分割問題求解装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１３】
以上説明したように、本発明に係る集合分割問題求解装置、方法、及びプログラムによれば、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返し、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求めることにより、集合分割問題の近似解を効率的に求めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態に係る集合分割問題求解装置の機能的な構成の一例を示すブロック図である。
【図２】本発明の実施形態に係るプログラムによる処理の流れの一例を示すフローチャートである。
【図３】本発明の実施形態に係るプログラムにおける深さ優先探索処理の流れの一例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、図面を参照して、本発明を実施するための形態の一例について詳細に説明する。
【００１６】
[本発明の実施形態の概要]
本実施形態においては、集合分割問題の解の制約に対する違反度を導入し、局所探索法を実行しつつ、解の制約に対する違反度がしきい値以下になった場合に、深さ優先探索に基づく解法に切り替えることによって探索を高速化する。局所探索法によって解の大部分を求めてから、深さ優先探索法に切り替えることによって、集合分割問題の解を高速に発見する。
【００１７】
ここで、集合分割問題の解の制約に対する違反度について説明する。ある解xが与えられたときに、yiを
【００１８】
【数２】
2019021052.tif 000013
【００１９】
と定義する。xがすべての制約条件を満たすときには、すべてのiについてyi=0を満たす。このとき、違反度Ｖ（ｘ）を以下の式で表わす。
【００２０】
【数３】
2019021052.tif 000014
【００２１】
上記の式に示すように、違反度Ｖ（ｘ）は、各要素ｘiについて、解候補ｘに当該要素ｘiが何れの部分集合にも含まれないこと、及び当該要素ｘiが２以上の部分集合に含まれることを表している。
【００２２】
＜本実施形態に係る集合分割問題求解装置の構成＞
図１は、本発明の実施形態に係る集合分割問題求解装置１０の機能的な構成の一例を示すブロック図である。
【００２３】
図１に示すように、集合分割問題求解装置１０は、問題入力部１２と、局所探索実行部１４と、深さ優先探索実行部１６と、計算結果出力部１８と、を備えている。
【００２４】
本実施形態に係る集合分割問題求解装置１０は、ＣＰＵ（Central Processing Unit）、ＲＡＭ(Random Access memory)、ＲＯＭ(Read Only Memory)、及びＨＤＤ(Hard Disk Drive)等を備えたコンピュータとして構成される。ＲＯＭには、本実施形態に係る集合分割問題求解処理を実行するためのプログラムが記憶されている。なお、プログラムは、ＨＤＤに記憶されていてもよい。
【００２５】
上記のプログラムは、例えば、集合分割問題求解装置１０に予めインストールされていてもよい。プログラムは、不揮発性の記憶媒体に記憶して、又は、ネットワークを介して配布して、集合分割問題求解装置１０に適宜インストールすることで実現してもよい。なお、不揮発性の記憶媒体の例としては、ＣＤ-ＲＯＭ(Compact Disc Read Only Memory)、光磁気ディスク、ＤＶＤ-ＲＯＭ(Digital Versatile Disc Read Only Memory)、フラッシュメモリ、メモリカード等が挙げられる。
【００２６】
ＣＰＵは、ＲＯＭに記憶されているプログラムを読み込んで実行することにより、集合分割問題求解装置１０の各部として機能する。
【００２７】
問題入力部１２は、集合分割問題を外部より受け取る。具体的には、aij(i∈｛1,...,M｝、ｊ∈｛1,...,Ｎ｝)及びｃj（ｊ＝1,...,Ｎ）を入力として受け取る。
【００２８】
局所探索実行部１４は、問題入力部１２より入力された集合分割問題に対して局所探索法を実行する。
【００２９】
具体的には、局所探索実行部１４は、要素の全体集合Ｕを、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、集合分割問題の制約条件の違反度を計算することを繰り返す。
【００３０】
局所探索法は、あるx1,. ..,xNへの値の割当を初期解として、そこから割当を部分的に変更することで、よりよい実行可能解を得るための方法である。
【００３１】
また、局所探索実行部１４は、探索の進み具合に相当する、集合分割問題の制約条件の違反度が閾値以下となった場合に、深さ優先探索実行部１６を用いて部分問題に対する深さ優先探索を実行する。
【００３２】
深さ優先探索実行部１６は、局所探索実行部１４より解候補を受け取り、集合分割問題の部分問題を作成し、集合分割問題の部分問題に対する深さ優先探索を実行して、部分問題に対する最適解を得て、最適解から求まる集合分割問題の近似解を局所探索実行部１４に返却する処理を実行する。
【００３３】
具体的には、深さ優先探索実行部１６は、計算された違反度が閾値以下となったときに、解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む部分集合との和集合を全体集合とする厳密被覆問題を、集合分割問題の部分問題として作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解と、解候補に含まれる、２以上の部分集合に含まれる要素を含む部分集合ではない部分集合とに基づいて、集合分割問題の近似解を求める。
【００３４】
ここで、深さ優先探索実行部１６は、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める際には、厳密被覆問題の全ての解を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)を、深さ優先探索により構築し、ゼロサプレス型二分決定グラフが保持する厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める。
【００３５】
予め定められた終了条件を満たすまで、局所探索実行部１４による処理と、深さ優先探索実行部１６による処理とを繰り返す。
【００３６】
計算結果出力部１８では、局所探索実行部１４で最終的に得られた集合分割問題に対する近似解を外部に出力する。
【００３７】
＜本実施形態に係る集合分割問題求解装置の作用＞
次に集合分割問題求解装置１０による処理の流れを図２の処理フローを用いて説明する。
【００３８】
まず、ステップＳ０１で問題入力部１２にて外部から集合分割問題を受け取る。
【００３９】
次に、ステップＳ０２で、上記非特許文献１に代表される、集合分割問題に対する局所探索法を実行する。局所探索アルゴリズムではある割当xから、その一部の要素の値を変更して別の割当x′を得て、Σcixiの値が改善されたならば解候補を更新することを繰り返して問題を解く。ステップＳ０２で局所探索を実行し、解候補が更新されたならば、次にステップＳ０３へ進み、更新後の解候補における違反度V(x)の値を計算し、あらかじめ定めたしきい値以下であったならば、ステップＳ０４に遷移する。しきい値より大きい場合には、上記ステップＳ０２に遷移し、局所探索を繰り返す。
【００４０】
ステップＳ０４で深さ優先探索を実行する。詳細については後述する。ステップＳ０５で、現在の探索が、予め定められた終了条件を満たしているならば現在の解候補を集合分割問題の近似解として出力して処理を終了する。終了条件としては、例えば、上記非特許文献１であるように、ある解候補とその一つ前に得られた解候補とのコストを比較して、コストの低下の度合いがあるしきい値を下回ったときに探索を終了するなどの方法が考えられる。
【００４１】
次にステップＳ０４の深さ優先探索処理について、図３の処理フローを用いて説明する。
【００４２】
深さ優先探索処理は，厳密被覆問題とよばれる離散アルゴリズムの問題に対するすべての解の集合を保持する、ゼロサプレス型二分決定グラフ(ＺＤＤ)を構築する処理を実行し、その後に構築されたＺＤＤを用いて、集合分割問題の部分問題に対する解を求める。その後に求まった部分問題の解を用いて元の集合分割問題の解を求めて処理を終了する。厳密被覆問題とは、集合分割問題における目的関数を削除した問題である。すなわち、全体集合ＵとＵの部分集合の集合Ｓとが与えられた場合に、式（２）、（３）を満たすようなx1,...,ｘNをすべて求める問題である。まずステップＳ１０１で、集合分割問題の部分問題であるような厳密被覆問題を作成する。
【００４３】
ステップＳ１０１の具体的な手順は以下の（手順１）〜（手順２Ａ）、又は（手順１）〜（手順２Ｂ）である。
【００４４】
（手順１）現在の解候補xに対して、Ｕの要素の集合Ｉ- = ｛i∈｛1,...,Ｍ｝|yi<0｝とＩ+=｛i∈｛1,...,Ｍ｝|yi>0｝を取り出す。また、インデックスの集合
2019021052.tif 000015
および
2019021052.tif 000016
を用意する。
【００４５】
（手順２Ａ）全体集合をＵ′=Ｉ−∪ＩＪ、Ｕの部分集合の集合を
2019021052.tif 000017
とするような厳密被覆問題を作成する。
【００４６】
なお、上記の（手順２Ａ）で生成されるＵ′,Ｓ′は、以下の（手順２Ｂ）で作成されるものに置き換えてもよい。
【００４７】
（手順２Ｂ）全体集合をＵ′=Ｉ−∪ＩJ、Ｕの部分集合の集合を
2019021052.tif 000018
とするような厳密被覆問題を作成する。
【００４８】
以上の具体的な手順で作成された厳密被覆問題に対し、ステップＳ１０２で、非特許文献２の手法を適用することで、厳密被覆問題のすべての解の集合を保持するＺＤＤを構築する。
【００４９】
例えば、二値行列として表現されている厳密被覆問題のインスタンスの入力を受け付ける。ここで、二値行列は、｜Ｓ′｜行、｜Ｕ′｜列からなり、各列番号が全体集合Ｕ′に含まれる各要素に対応し、各行ベクトルが、部分集合の集合Ｓ′に含まれる各要素に対応している。そして、二値行列に基づいて、選択される列番号を１とする行番号の各々に対し、行番号を解に含めたときに得られる厳密被覆問題の部分問題を求め、求められた厳密被覆問題の部分問題を再帰的に解いて、部分問題の解を表すＺＤＤの根ノードを得ることにより、厳密被覆問題の全ての解の集合を保持するＺＤＤを構築する。
【００５０】
[非特許文献２] Masaaki Nishino, Norihito Yasuda, Shinichi Minato, and Masaaki Nagata, “Dancing with Decision Diagrams: a Combined Approach to Exact Cover", In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), 2017
【００５１】
なお、上記非特許文献２の手法以外の手法を用いて、厳密被覆問題のすべての解の集合を保持するＺＤＤを構築するようにしてもよい。
【００５２】
次に、ステップＳ１０３で、厳密被覆問題のすべての解の集合を保持するＺＤＤに対して、非特許文献３に記載されているAlgorithm Bを実行することにより、厳密被覆問題の解のうち、コストの和を最小にする最適解を求める。
【００５３】
[非特許文献３] Donald E. Knuth, “The Art of Computer Programming Volume 4A: Combinatorial Algorithms, Part 1", Addison-Wesley, 2011
【００５４】
そして、見つかった最適解（Ｕの部分集合）をＴとすると、Ｕの部分集合
2019021052.tif 000019
は元の集合分割問題に対する実行可能解となっている。そこで、
2019021052.tif 000020
を集合分割問題の近似解として出力して、深さ優先探索処理を終了する。
【００５５】
以上説明したように、本発明の実施形態に係る集合分割問題求解装置によれば、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、集合分割問題の制約条件の違反度を計算することを繰り返し、計算された違反度が閾値以下となったときに、解候補に基づいて、厳密被覆問題を作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解と、解候補に含まれる、２以上の部分集合に含まれる要素を含む部分集合以外の部分集合とに基づいて、集合分割問題の近似解を求めることにより、集合分割問題の近似解を効率的に求めることができる。
【００５６】
以上、実施形態として集合分割問題求解装置及び方法を例示して説明した。実施形態は、コンピュータを、集合分割問題求解装置における各部として機能させるためのプログラムの形態としてもよい。実施形態は、このプログラムを記憶したコンピュータが読み取り可能な記憶媒体の形態としてもよい。
【００５７】
その他、上記実施形態で説明した集合分割問題求解装置の構成は、一例であり、主旨を逸脱しない範囲内において状況に応じて変更してもよい。
【００５８】
また、上記実施形態で説明したプログラムの処理の流れも、一例であり、主旨を逸脱しない範囲内において不要なステップを削除したり、新たなステップを追加したり、処理順序を入れ替えたりしてもよい。
【００５９】
また、上記実施形態では、プログラムを実行することにより、実施形態に係る処理がコンピュータを利用してソフトウェア構成により実現される場合について説明したが、これに限らない。実施形態は、例えば、ハードウェア構成や、ハードウェア構成とソフトウェア構成との組み合わせによって実現してもよい。
【符号の説明】
【００６０】
１０ 集合分割問題求解装置
１２ 問題入力部
１４ 局所探索実行部
１６ 深さ優先探索実行部
１８ 計算結果出力部
【図１】
2019021052.tif 000021
【図２】
2019021052.tif 000022
【図３】
2019021052.tif 000023