複雑さの制御による問題解決 : 大規模巡回セールスマン問題の求解
スポンサーリンク
概要
- 論文の詳細を見る
本論文は、帰納的アルゴリズムと呼ばれる一種のメタヒューリステックスについて述べる。本アルゴリズムはナップサック問題や数百都市から成る巡回セールスマン問題(略して、TSP)等組合せ最適化問題に適用され、良好な結果を得ている。本論文では、数万都市より成る大規模なTSPへの適用を目指す。組合せ的爆発を抑えるため、問題の複雑さの制御という視点が導入される。複雑さの制御は抽象化とスコープの設定によって実現される。帰納的アルゴリズムは三つのパラメータを含む。本アルゴリズムがこれらのパラメータに対して安定であることおよび各パラメータに対する推奨値が示される。また、85,900都市問題を含むベンチマーク問題(TSP.LIB)に対する実験結果が示される。
- 社団法人電子情報通信学会の論文
- 1997-05-22
著者
関連論文
- 仮説生成に基づく分散型問題解決
- 俯瞰可能迷路の代数的構造(Semi-Ring)による数学的モデル化と成功経路導出アルゴリズム
- 初期視覚モデルと眼球運動
- 初期視覚モデルと錯視 : ラプラシアン・ガウシアンに関する一考察
- 超多重解像度に基づく錯視の情報処理モデル
- 網膜における多重解像度と錯視 : ミューラー・リヤー錯視の場合
- 複雑さの制御による問題解決 : 大規模巡回セールスマン問題の求解
- 2000-HPC-82-27 クラスタリングによる抽象化を用いた巡回セールスマン問題の分散処理解法
- マルチプロセッサシステムによる並行探索 : 仮説検証法の場合
- エッジ検出に基づく曲率計算
- 帰納的アルゴリズムに基づく巡回セールスマン問題の解法
- 並列処理に適した縦続的問題分解