Minimum Maximal Matching 問題のニューラルネットワーク解法の提案

• 梅谷 俊治

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

• 船曵 信生

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

• 西川 清史

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

書誌事項

タイトル別名

• A Neural Network Algorithm for the Minimum Maximal Matching Problem

抄録

グラフG=(V,E)の辺の部分集合M(⊆E)で, Mのどの2辺も隣り合わないとき, MをGのマッチングと呼ぶ. 本論文では, 極大かつ要素数最小のマッチングを求める最小極大マッチング問題に対して, ニューラルネットワークを用いた並列解法を提案する. 本問題は一般にNP完全であることが知られている. 本解法では, 頂点数Nのグラフに対し, N×Nの2次元ニューラルネットワークを用いる. 解精度向上のため, 各頂点がマッチングに含まれないことを表す対角線上のニューロンを発火しやすくする項を動作方程式に与えている. ランダムグラフを用いたシミュレーションにより, Greedy解法, Simulated Annealing解法より本解法の解精度が優れていることを示す.

収録刊行物

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

  電子情報通信学会技術研究報告. NC, ニューロコンピューティング 96 (393), 17-24, 1996-11-29

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

キーワード

• 最小極大マッチング
• ニューラルネットワーク
• バイナリーニューロン
• NP完全
• グラフ

詳細情報

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