ニューロコンピュータAN1における組合せ最適化問題の解法と問題点

スポンサーリンク

概要

論文の詳細を見る
Hopfieldニューラルネットワーク(以下HNNと呼ぶ)により、巡回セールスマン問題等のNP困難な問題の近似解が得られたことで、組合せ最適化問題へのHNNの応用が盛んに行われている。しかし、問題を写像したエネルギ関数は一般に極値を持ち、しかもその極値が問題に対してどのような意味を持つのかについては論じられていないため、組合せ最適化問題への応用は試行錯誤的な要素を含んでいる。本稿ではエネルギ関数の極値の特徴化という目的から、グラフの頂点をHNNのニューロンと1対1に対応させることによりネットワークを簡単にした上で、ケーススタディとして最大独立点集合問題を取り上げる。そして、そのエネルギ関数の極小値が極大独立点集合に対応することを示す。
一般社団法人情報処理学会の論文
1989-10-16

著者

関連論文

もっと見る

スポンサーリンク