バイナリニューロンを用いたグラフ分割解法の研究

• 玉置 康裕

  大阪大学大学院基礎工学研究科情報数理系専攻

• 船曵 信生

  大阪大学大学院基礎工学研究科情報数理系専攻

• 西川 清史

  大阪大学大学院基礎工学研究科情報数理系専攻

書誌事項

タイトル別名

• A Binary Neural Network Algorithm for the Graph Partitioning Problem

抄録

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

収録刊行物

• 電子情報通信学会技術研究報告. NC, ニューロコンピューティング

  電子情報通信学会技術研究報告. NC, ニューロコンピューティング 96 (430), 49-56, 1996-12-14

  一般社団法人電子情報通信学会

キーワード

• グラフ分割問題
• NP困難問題
• ニューラルネットワーク
• Shaking 項
• 動作方程式
• KL法
• FM法

詳細情報

• CRID: 1573950402237117056
• NII論文ID: 110003232939
• NII書誌ID: AN10091178
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles