著者

久保 典弘 村本 勝洋 下薗真一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.84, pp.49-56, 2000-09-21

---

平面上に与えられた点をすべてを通過し最初の点に戻ってくる最も短い巡回路を求める問題の,非常に高速なアルゴリズムについて述べる.本アルゴリズムは非常に単純なアルゴリズムなので実装が簡単である.また,n個の点が与えられたときにO(n log n)時間,O(n)領域で計算を行う.アルゴリズムは,平面を分割し,点をソートして分割領域内の順路を求め,各領域内の順路をつなぎ合わせる構成をとる.ランダムに点が分布するときは確率的に定数近似アルゴリズムである.このアルゴリズムをKarpの分割アルゴリズム,Lin-Kernighanの局所探索,Aroraの近似スキームなどと比較した結果,実行時間は最も速く精度は同じかより良いという結果が得られた.We present a quite simple, fast and practical algorithm to find a short cyclic tour that visits a set of points distributed on the plane. The algorithm runs in O(n log n) time with O(n) space, and is simple enough to easily implement on resource restricted machines. It constructs a tour essentially by axis-sorts of the points and takes a kind of the 'fixed dissection strategy.' We show that the algorithm is a 'probabilistic' constant-ratio approximation algorithm for uniform random distributions. We made computational comparisons of our algorithm, Karp's partitioning, Lin-Kernighan local search, Arora's PTAS, etc. The results indicate that in running time our algorithm overwhelms existing ones, and the average approximation ratio is better or competitive.