A Nearest Neighbor Method with a Frequency Graph for Traveling Salesman Problem

摘要

Travelling salesman problem (TSP) is one of the famous discrete optimization problems. Due to its NP-completeness, the exact methods are not found till now. Here we use a nearest neighbor method to search the approximations with a frequency graph. The frequency graph is computed with a set of local optimal paths derived from a weighted graph. The frequencies on the edges represent the number of edges emulated from the set of local optimal paths. We believe the local optimal paths have more intersections of edges with the best circuit than the general paths do with it. Hence the edges with big frequencies may be included by the best circuit. To reduce the complexity, we use the local optimal paths with four vertices to compute the frequency graphs. These local optimal paths are computed with a four-vertex-three-line inequality. After a frequency graph is computed, we use a nearest neighbor method to find the approximations with it. The experimental results illustrate the nearest neighbor method is able to find the better approximations with the frequency graphs than those with the weighted graphs.