最大クリーク問題に対するk-opt局所探索法の改良

金原 一歩  片山 謙吾  岡野 傑士  尾崎 亮  西原 典孝  舩曵 信生  

誌名
電子情報通信学会論文誌 A   Vol.J101-A   No.10   pp.260-264
発行日: 2018/10/01
Online ISSN: 1881-0195
DOI: 
論文種別: レター
専門分野: 
キーワード: 
可変深度探索,  局所探索,  組合せ最適化,  

本文: PDF(599KB)
>>論文を購入


あらまし: 
最大クリーク問題に対する従来のk-opt局所探索法(KLS)の探索過程において,より大きなクリークの探索に取りこぼしが生じる場合があることを示し,その問題点を解消する探索プロセスを導入した改良KLSを提案する.従来KLSとの探索性能の比較実験の結果から,改良KLSは辺密度の高いグラフ例題に対して特に有効であることを示す.