- 著者
-
玉木 久夫
土屋 裕希
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)
- 巻号頁・発行日
- vol.111, pp.121-128, 2007-03-09
- 参考文献数
- 15
平面ユークリッド距離巡回セールスマン問題に対する分割統治法アルゴリズムを提案する。このアルゴリズムは、まず与えられた点集合のドローネ三角形分割を求め、その全域閉小路を再帰的に求める。巡回路をハミルトン閉路から全域閉小路に緩和したのは解の存在を保証するためである。部分解の統合においては、部分解に属す辺とその他のドローネ辺をあわせて統合グラフを構成し、その上の最適解を線形刻み分割を用いた動的計画法により求める。このアルゴリズムの実行時間は分割の幅wを固定したとき、O(nlogn)である。