Abstract:
Traveling salesman problem (TSP) is one famous NP-complete problem which is usually represented as a weighted complete graph Kn. However, the weights on edges cannot show valid information for finding most of the edges and paths in optimal Hamiltonian cycle (OHC). Thus, the algorithms have to enumerate the possible Hamiltonian cycles and compare them for finding an OHC. In this talk, we present another representation called frequency graph for TSP. The frequency graph is computed with the optimal paths with given endpoints in Kn. We will illustrate the sufficient and necessary conditions for the edges in optimal Hamiltonian cycle based on frequency graphs. According to the conditions, one can find at least half of the OHC edges. Moreover, the frequencies on edges are helpful to accelerate the algorithms for resolving TSP. The experimental results are provided to demonstrate the frequency properties related to the OHC edges for TSP. |