Pat
J-GLOBAL ID：201903016971792708
集合分割問題求解装置、方法、及びプログラム
Inventor：
,
,
Applicant, Patent owner：
,
Agent (1)：
特許業務法人太陽国際特許事務所
Gazette classification：公開公報
Application number (International application number)：2017139319
Publication number (International publication number)：2019021052
Application date： Jul. 18, 2017
Publication date： Feb. 07, 2019
Summary：
【課題】集合分割問題の近似解を効率的に求めることができるようにする。【解決手段】局所探索実行部14が、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す。深さ優先探索実行部16は、計算された違反度が閾値以下となったときに、解候補に基づいて、厳密被覆問題を作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める。そして、局所探索実行部14は、深さ優先探索実行部16により求められた解と、解候補に含まれる、2以上の部分集合に含まれる要素を含む部分集合以外の部分集合とに基づいて、集合分割問題の近似解を求める。【選択図】図1
Claim (excerpt)：
要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す局所探索実行部と、
前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、2以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、2以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める深さ優先探索実行部と、
を含む集合分割問題求解装置。
IPC (3)：
G06F 16/00
, G06F 17/10
, G06N 99/00
G06F17/30 220Z
, G06F17/30 210D
, G06F17/30 419A
, G06F17/10 Z
, G06N99/00 180
