最小極大マッチング問題のニューラルネットワーク並列解法の提案
スポンサーリンク
概要
- 論文の詳細を見る
グラフG=(V, E)の辺の部分集合M(⊆E)で、Mのどの2辺も隣り合わないとき、MをGのマッチングと呼ぶ。本論文では、極大かつ要素数最小のマッチングを求める最小極大マッチング問題に対して、ニューラルネットワークを用いた並列解法を提案する。本問題は一般にNP完全であることが知られている。本解法では、頂点数Nのグラフに対し、N×Nの2次元ニューラルネットワークを用いる。頂点がマッチングに含まれないことを表す対角線上のニューロンが、制約条件を満たすときのみ発火するように働きかける項を導入することによって、収束率および解精度の向上を図っている。ランダムグラフを用いたシミュレーションにより、Greedy解法、Simulated Annealing解法より本解法の解精度が優れていることを示す。
- 一般社団法人情報処理学会の論文
- 1998-03-15
著者
-
梅谷 俊治
大阪大学大学院情報科学研究科
-
西川 清史
大阪大学大学院基礎工学研究科情報数理系専攻
-
梅谷 俊治
大阪大学大学院基礎工学研究科情報数理系専攻
-
船曳 信生
大阪大学大学院基礎工学研究科情報数理系専攻
-
西川 清史
大阪大学大学院基礎工学研究科
-
西川 清史
大阪大学大学院基礎光学研究科情報数理系専攻
関連論文
- 第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 不良の原因設備および工程の特定に関する研究(生産管理)
- 無線通信網における信頼度制約通信経路割当問題に対するニューラルネットワーク併用2段階解法の提案
- 安定結婚問題のニューラルネットワーク解法の提案
- FPGA間配線問題に対するニューロンフィルタアルゴリズムの提案
- 切出し・詰込み問題に対する実用的解法
- SSOR 2007ルポ(情報の窓)
- カッティングストック問題に対する線形計画法に基づく局所探索法の提案(組合せ最適化(2))
- カッティングストック問題におけるパターン生成法について(組み合わせ最適化(2))
- 段取り替え数最小化を考慮したカッティングストック問題の定式化と近似解法 (最適化のための連続と離散数理)
- パターン数最小化を目的とするカッテイングストック問題について
- マルチキャスト・パケット交換方式におけるユニキャストおよびマルチキャスト問題のニューラルネットワーク解法
- ニューラルネットワークによるマルチキャスト・パケット・スイッチ制御アルゴリズムの研究
- プレスブルカー文真偽判定アルゴリズムのためのBDDの応用とそれを用いた回路検証 (電子システムの設計技術と設計自動化)
- 巡回セールスマン問題の遺伝的アルゴリズムに対する凸包の応用
- 大型計算機センタの役割
- マルチコンテキストFPGAのためのコンテキスト分割アルゴリズムの実例による評価
- マルチコンテキストFPGAのためのコンテキスト分割アルゴリズムの実例による評価
- マルチコンテキストFPGAのためのコンテキスト分割アルゴリズムの実例による評価
- 遺伝的プログラミングを用いた関数合成アルゴリズムの改良法の提案
- SMIL風シナリオ群からのQoSを考慮したプロトコル合成
- SMIL風シナリオ群からのQoSを考慮したプロトコル合成
- マキシマムニューロンを用いたN-Queen問題の準同期並列解法の提案
- N-Queen問題を対象としたニューラルネットワーク解法の並列アルゴリズムに関する研究
- ニューラルネットワークによるN-Queen問題の解法
- FPGA配線問題に対する貪欲法とニューラルネットワークを併用した3段階アルゴリズムの提案
- セルラー通信網のあるチャンネル割当問題に対するマキシマムニューラルネットワーク解法の提案
- 動的再構成可能FPGAの設計とそれへの並列アルゴリズムの実装
- 太陽光発電・蓄電池を用いた住宅規模での電力最適運用計画 (最適化手法の理論と応用の繋がり)
- メタヒューリスティクス事始め : まずは局所探索法から(はじめようメタヒューリスティクス)