平面巡回セールスマン問題の高速な近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
平面上に与えられた点をすべてを通過し最初の点に戻ってくる最も短い巡回路を求める問題の, 非常に高速なアルゴリズムについて述べる.本アルゴリズムは非常に単純なアルゴリズムなので実装が簡単である.また, n個の点が与えられたときにO(nlogn)時間, O(n)領域で計算を行う.アルゴリズムは, 平面を分割し, 点をソートして分割領域内の順路を求め, 各領域内の順路をつなぎ合わせる構成をとる.ランダムに点が分布するときは確率的に定数近似アルゴリズムである.このアルゴリズムをKarpの分割アルゴリズム, Lin-Kernighanの局所探索, Aroraの近似スキームなどと比較した結果, 実行時間は最も速く精度は同じかより良いという結果が得られた.
- 一般社団法人情報処理学会の論文
- 2000-09-21
著者
関連論文
- BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 文字列パターン照合のための損失のあるデータ圧縮
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)
- 表面実相ロボットの実相シーケンスの決定に対する巡回セールスマン問題のアルゴリズムの適用
- 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
- テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
- 生物配列の局所マルチプルアラインメントの計算困難性
- 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
- Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
- K語近接相関パタンの高速発見アルゴリズム
- On Approximation Algorithms for Local Multiple Alignment (合同研究会"AIシンポジウム'99"(第10回))
- 文字列相関パタンの分類精度最大化問題について
- 省スペースな線形時間文法圧縮アルゴリズム
- DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- Minimum Multiset Covering 問題の近似アルゴリズムについて
- 平面巡回セールスマン問題の高速な近似アルゴリズム
- 無矛盾最小OBDD問題の近似困難性について