巡回セールスマン問題における解の分岐

参考文献7件

書誌事項

タイトル別名
  • Bifurcations in traveling salesman problem

この論文をさがす

説明

アナログホップフィールドモデルおよびボルツマンマシンの平均場近似モデルにおいてはアニーリングする際にエネルギー関数の対称性に応じた解の分岐が起きる。本報告では、巡回セールスマン問題を課題として、この分岐現象について述べる。巡回セールスマン問題は巡回対称性と反転対称性という二種の対称性を持ち、これらが分岐の構造に影響を与える。次に、これら分岐の構造によって、平均場アニーリングのアルゴリズムとしての性質が分かることを示す。結果として、平均場アニーリングは一般に「準」最適解を求めるアルゴリズムであり、非決定論的性質を有する。最後にこれらの性質を踏まえて、修正アルゴリズムを提案する。
In the analog Hopfield network and the mean field theory (MFT) of the Boltzmann machine, bifurcations of solutions occur during the course of the annealing procedure. In this report, we investigate the bifurcation processes of MFT solutions when MFT is applied to traveling salesman problems (TSPs). A TSP has two types of symmetries, i.e., cyclic and reverse. These symmetries affect the bifurcation structure. Next, some features of the MFT annealing procedure, which are dependent on the bifurcation processes, are shown. The MFT annealing has "non-deterministic" and "non-optimal" properties, which implies some procedural limitations. To overcome these, we also propose a couple of modified algorithms.

収録刊行物

参考文献 (7)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1573950402236649344
  • NII論文ID
    110003233034
  • NII書誌ID
    AN10091178
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ