Minimum Maximal Matching問題のニューラルネットワーク解法の提案
スポンサーリンク
概要
- 論文の詳細を見る
グラフG=(V,E)の辺の部分集合M(⊆E)で, Mのどの2辺も隣り合わないとき, MをGのマッチングと呼ぶ. 本論文では, 極大かつ要素数最小のマッチングを求める最小極大マッチング問題に対して, ニューラルネットワークを用いた並列解法を提案する. 本問題は一般にNP完全であることが知られている. 本解法では, 頂点数Nのグラフに対し, N×Nの2次元ニューラルネットワークを用いる. 解精度向上のため, 各頂点がマッチングに含まれないことを表す対角線上のニューロンを発火しやすくする項を動作方程式に与えている. ランダムグラフを用いたシミュレーションにより, Greedy解法, Simulated Annealing解法より本解法の解精度が優れていることを示す.
- 社団法人電子情報通信学会の論文
- 1996-11-29
著者
-
梅谷 俊治
大阪大学大学院情報科学研究科
-
西川 清史
大阪大学大学院基礎工学研究科情報数理系専攻
-
梅谷 俊治
大阪大学大学院基礎工学研究科情報数理系専攻
-
船曵 信生
大阪大学大学院基礎工学研究科情報数理系専攻
-
西川 清史
大阪大学大学院基礎工学研究科
-
西川 清史
大阪大学大学院基礎光学研究科情報数理系専攻
関連論文
- 第23回企業事例交流会ルポ(情報の窓)
- 2-D-2 顧客の需要量が不確実な状況下における配送計画問題の研究(整数計画)
- 統計的機械翻訳におけるフレーズ対応最適化を利用したN-best翻訳候補のリランキング
- 最小極大マッチング問題のニューラルネットワーク並列解法の提案
- 組合せ最適化問題に対する離散値ニューラルネットワーク解法の安定性の一考察
- Minimum Maximal Matching問題のニューラルネットワーク解法の提案
- 複数の制御部を持つ同期式順序回路の一設計検証法
- 複数モジュールにより構成される回路仕様に対する効率的な形式的検証法
- 複数モジュールにより構成される回路仕様に対する効率的な形式的検証法
- ニューロ・GAによるデータ転送路最適化問題解法の提案
- 代数的手法を用いた複数の制御部を持つ同期式順序回路に対する設計および検証支援系の開発
- 代数的手法によるPCIバスコントローラの設計検証
- シストリックアレーによる回路設計の正しさの一証明法
- 代数的手法を用いた同期式順序回路の設計支援機能の統合
- 無線通信網の通信経路割当て問題を対象としたグリーディニューラルネットワーク解法の提案
- マルチキャストパケット交換方式におけるワンショットスケジューリング問題のニューラルネットワーク解法
- N-Queen問題を対象としたマキシマムニューロンモデルの競合解消方式の提案
- グラフ分割問題に対するバイナリーニューロンを用いたニューラルネットワーク解法
- 無線通信網の通信経路割当問題に対するグリーディ・ニューラルネットワーク解法の提案
- マキシマム・ニューラルネットワークによる無線通信網の通信経路選択法の提案
- マキシマムニューロンを用いた安定結婚問題のニューラルネットワーク解法
- 巡回セールスマン問題を対象としたニューロンフィルタの提案
- N-Queen問題を対象としたニューラルネットワークの半同期式更新方式の提案
- ニューラルネットワークによるセルラー通信網のチャンネル割当問題の一解法の研究
- バイナリニューロンを用いたグラフ分割解法の研究
- 巡回セールスマン問題の従来アルゴリズムの評価と新しいニューラルネットワークアルゴリズムの提案
- N-Queen問題を対象としたマキシマムニューロンモデルの"Winner-take-all"方式に関する研究
- 無線通信網における通信経路選択問題のマキシマム・ニューロンを用いたニューラルネットワーク解法の提案
- マキシマムニューロンを用いたN-Queen問題のニューラルネット解法の提案
- グラフ分割問題に対するニューラルネットワーク解法の提案
- ウインドウ付きマルチキャスト・パケット交換方式におけるワンショット・スケジューリング問題のニューラルネット解法
- Integer programming for a phrase alignment problem on statistical machine translation (21世紀の数理計画--最適化モデルとアルゴリズム--RIMS研究集会報告集)
- Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns (Captivation of Convexity : Fascination of Nonconvexity)
- 段取り替え制約付きカッティングストック問題に対する列生成法を用いた局所探索法の提案(組合せ(1))
- 複数の制御部を持つ同期式順序回路に対する不変式の形式的検証法 (機能論理設計, アーキテクチャ設計支援と一般)
- 1-D-8 紙管製造工程における1次元カッティングストック問題(離散アルゴリズム(3))
- 切出し・詰込み問題とその応用 : (3)多角形詰込み問題(OR研究の最前線)
- 切出し・詰込み問題とその応用 : (2)長方形詰込み問題(OR研究の最前線)
- 切出し・詰込み問題とその応用 : (1)1次元資材切出し問題(OR研究の最前線)
- カッティングストック問題に対する線形計画法に基づく局所探索法の提案 (最適化の数理とアルゴリズム)
- 2-A-15 不良の原因設備および工程の特定に関する研究(生産管理)
- 安定結婚問題のニューラルネットワーク解法の提案
- FPGA配線問題に対する貪欲法とニューラルネットワークを併用した3段階アルゴリズムの提案
- 切出し・詰込み問題に対する実用的解法
- SSOR 2007ルポ(情報の窓)
- カッティングストック問題に対する線形計画法に基づく局所探索法の提案(組合せ最適化(2))
- カッティングストック問題におけるパターン生成法について(組み合わせ最適化(2))
- 段取り替え数最小化を考慮したカッティングストック問題の定式化と近似解法 (最適化のための連続と離散数理)
- パターン数最小化を目的とするカッテイングストック問題について
- マルチキャスト・パケット交換方式におけるユニキャストおよびマルチキャスト問題のニューラルネットワーク解法
- ニューラルネットワークによるマルチキャスト・パケット・スイッチ制御アルゴリズムの研究
- 貪欲法とGAを併用したデータ転送路資源最適化問題解法の提案
- 大型計算機センタの役割
- FPGAの論理ブロックの端子割当問題の定式化と2段階離散最適化法の提案
- マキシマムニューロンを用いたN-Queen問題の準同期並列解法の提案
- N-Queen問題を対象としたニューラルネットワーク解法の並列アルゴリズムに関する研究
- ニューラルネットワークによるN-Queen問題の解法
- チャネル割当問題を対象とした拡張マキシマムニューラルネットワーク解法の提案
- 遺伝的プログラミングを用いた関数合成アルゴリズムの一改良法の提案
- 太陽光発電・蓄電池を用いた住宅規模での電力最適運用計画 (最適化手法の理論と応用の繋がり)
- 複数の制御部を持つ同期式順序回路に対する不変式の形式的検証法 (機能論理設計, アーキテクチャ設計支援と一般)
- メタヒューリスティクス事始め : まずは局所探索法から(はじめようメタヒューリスティクス)