特許

J-GLOBAL ID：201903016971792708

集合分割問題求解装置、方法、及びプログラム

発明者： 西野 正彬 ,  鈴木 潤 ,  梅谷 俊治
出願人/特許権者： 日本電信電話株式会社 ,  国立大学法人大阪大学
代理人 (1件)： 特許業務法人太陽国際特許事務所
公報種別：公開公報
出願番号（国際出願番号）：特願2017-139319
公開番号（公開出願番号）：特開2019-021052
出願日： 2017年07月18日
公開日（公表日）： 2019年02月07日
要約：

【課題】集合分割問題の近似解を効率的に求めることができるようにする。【解決手段】局所探索実行部14が、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す。深さ優先探索実行部16は、計算された違反度が閾値以下となったときに、解候補に基づいて、厳密被覆問題を作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める。そして、局所探索実行部14は、深さ優先探索実行部16により求められた解と、解候補に含まれる、2以上の部分集合に含まれる要素を含む部分集合以外の部分集合とに基づいて、集合分割問題の近似解を求める。【選択図】図1

請求項（抜粋）：

要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す局所探索実行部と、 前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、2以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、2以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める深さ優先探索実行部と、 を含む集合分割問題求解装置。

IPC (3件)：

G06F 16/00 ,  G06F 17/10 ,  G06N 99/00

FI (5件)：

G06F17/30 220Z ,  G06F17/30 210D ,  G06F17/30 419A ,  G06F17/10 Z ,  G06N99/00 180

Fターム (1件)：

5B056BB91