グラフ分割問題に対するバイナリーニューロンを用いたニューラルネットワーク解法

スポンサーリンク

概要

論文の詳細を見る
グラフ分割問題とは, 各グループに属する頂点重みの総和を上限以下として, グループ間の辺重みの総和が最小となる各頂点の分割を求めるNP困難問題である. 本論文では, グラフ2分割問題に対して, バイナリーニューロンを用いたニューラルネットワーク解法を提案する. 本ニューラルネットワークでは, 頂点および辺の重みなしグラフおよび重み付きグラフの双方に適用可能なエネルギー関数を定義している. また, 解精度向上のため, Shaking項を動作方程式に導入している. 本解法の解探索能力の評価のため, KernighanとLinの提案したKL法, FiducciaとMattheysesの提案したFM法と共に, ランダムグラフを対象としたシミュレーションを行う. シミュレーションの結果, 本解法で得られた解が最も優れていることを示す.
社団法人電子情報通信学会の論文
1997-09-25

著者

関連論文

もっと見る

スポンサーリンク