2000-HPC-82-27 クラスタリングによる抽象化を用いた巡回セールスマン問題の分散処理解法
スポンサーリンク
概要
- 論文の詳細を見る
巡回セールスマン問題のような大規模組み合せ最適化問題を扱う場合, 分割統治の戦略を再帰的に適用することが考えられる.本論文で述べるアルゴリズムは分割統治の戦略を用いず, この問題を帰納的に解く.すなわち, (1)与えられた問題に対して最も単純な問題を設定し, それを解く.(2)κ-1番目までの解が選られたならば, それを利用してk番目の解を解き, 徐々に元の問題に近づく, ということである.この戦略では問題を分割する必要がないため, 解の全体像を考慮しながら, 計算することが可能である.本論文では, 最も抽象度の高い問題から徐々に元の問題に近づく戦略による巡回セールスマン問題の逐次計算機による解法と並列計算機による解法について述べ, その性能を実験的に評価する.
- 一般社団法人情報処理学会の論文
- 2000-08-03
著者
関連論文
- 仮説生成に基づく分散型問題解決
- 俯瞰可能迷路の代数的構造(Semi-Ring)による数学的モデル化と成功経路導出アルゴリズム
- 初期視覚モデルと眼球運動
- 初期視覚モデルと錯視 : ラプラシアン・ガウシアンに関する一考察
- 超多重解像度に基づく錯視の情報処理モデル
- 網膜における多重解像度と錯視 : ミューラー・リヤー錯視の場合
- 複雑さの制御による問題解決 : 大規模巡回セールスマン問題の求解
- 2000-HPC-82-27 クラスタリングによる抽象化を用いた巡回セールスマン問題の分散処理解法
- 文脈自由文法を用いた日本語誤り検出・訂正手法の提案
- マルチプロセッサシステムによる並行探索 : 仮説検証法の場合
- エッジ検出に基づく曲率計算
- 帰納的アルゴリズムに基づく巡回セールスマン問題の解法
- 並列処理に適した縦続的問題分解