A Representation Model for TSP

Traveling salesman problem (TSP) has been proven to be NP-complete and it is regarded for more than half a century. It is often represented as a weighted graph whereas the weighted graph cannot provide enough heuristic information for TSP. We do not know which edges belong to the best solution according to the edges´ weights. Here the frequency graph is introduced as a novel representation model for TSP. The frequency graph includes the law to connect the edges into the optimal Hamiltonian cycle (OHC). Based on the frequency graph, a sparse graph is computed and the search space of the OHC is reduced. Three steps are necessary to convert a complete weighted graph into a sparse graph with small number of edges. The frequency graph is computed with a set of local optimal Hamiltonian paths (LOHPs) at first. A sparse graph is computed according to a defined frequency threshold at the second step. A sparser graph is computed with the former sparse graph at the third step. The average degree of the final sparse graph is bounded to a small number and the search space of TSP is reduced. At last, the representation model is verified with several TSP instances with known optimal solutions.