O(N)方法による対称巡回セールス員問題の高精度解

概要

論文の詳細を見る
This study reports a new approach for obtaining a near-optimal solution of the symmetric traveling salesman problem (symmetric TSP). The approach is formed with two ways of optimization, a critical state method and an m-step 8S-opt, characterizing O(N) computational complexity both in running time and in storage space. The approach predicts computational time limits for obtaining a tour of the salesman because of running in O(N) complexity. Moreover this requires no searching for parameters for each problem. The critical state method for constructing a feasible tour precisely states the structure of phase transitions in symmetric TSP, indicating a field of information physics. The m-step 8S-opt improves this tour effectively through a weak-symmetric approach. Using standard PC, we have systematically proved the high efficiency of the new approach through 27 instances from TSPLIB as real-world problems, covering small to large-scale problems exhibiting no uniform distributions. For the instances, the excess amount over optimum shows 6.5% on average, and even only 10.4% at worst.
東海大学の論文