バケット手法,Peano曲線を用いた平面マッチング,巡回セールスマン問題に対する近似算法の理論的評価

概要

論文の詳細を見る
平面マッチング問題は、平面上の与えられたn個の点を対にして、対の距離の総和が最小になるようにする問題である。平面巡回セールスマン問題は、平面上のn点をそれぞれ一度づつ通る最小距離の巡回路を求める問題である。これらの問題は、OR、その他の様々な分野において多くの応用を有する(例えば、平面マッチング問題のプロッターの描線順序の効率化問題への応用など)が、ともに大規模な問題を高速に解くのは難しく、そのような問題に対処するための高速な近似算法が提案されている。nが数千、数万の問題でも高速に解き、解の性能もよい近似算法として、四角バケットを用いたO(n)の手間の算法が、伊理、室田、松井(論文中の参考文〔6、7、8〕)により提案され、実際にプロッター作画高速化への応用を通して、その有用性が示されている。一方、最近、Peano曲線を用いたO(n log n)の手間の近似算が、Bartholdi、 Platzman(論文中の参考文献〔3、4、12〕)により提案されている。本論文では、Peano曲線を用いる算法に対してバケット手法を適用することによって、O(n)の手間のPeano曲線順のバケット算法が構成できることに着目し、これらの各種算法の理論的評価の1っとして、最悪の場合の振舞いについて考察する。まず、バケット算法は手間に関して優れているとともに、十分な数のバケット(O(n)個)を用いた場合には、Peano曲線を直接用いた算法と、最悪の場合の振舞いに関しては同じであることを示す。特に、Peano曲線としてSierpinski曲線を用いた算法に関しては、詳細な解析を通して、厳密な評価を行う。ここでの解析は、伊理、室田、松井〔8〕の線形計画問題の双対理論を用いた手法に基づいたものであり、この算法に適用する際の特徴として、2つのバケット内の点の距離の上限の評価に重点が置かれることが上げられる。また、Sierpinski曲線とバケット手法を組み合わせる際には、それ自身、理論的にも興味深い三角バケットが用いられる。Peano曲線としてHilbert曲線を用いた算法の解析も行なう。ここでは、上と同様な手法とともに、Hilbert曲線の再帰的構造から導出される漸化式を用いて解析を行なっている。これらの解析から、最悪の場合の観点からの結論として、Peano曲線及びそれをバケット手法と組み合わせた算法は、伊理、室田、松井〔8〕の推奨するSpiral-rack算法より少し劣ることが示される。
社団法人日本オペレーションズ・リサーチ学会の論文

バケット手法,Peano曲線を用いた平面マッチング,巡回セールスマン問題に対する近似算法の理論的評価

スポンサーリンク

概要

著者

関連論文

スポンサーリンク