关键词: 旅行商问题(TSP), 最优哈密顿圈(OHC), 频率图, 稀疏图

Abstract: TSP is a challenging problem where the search space for the optimal solution grows exponentially according to the problem size.To reduce the search space for the optimal Hamiltonian cycle,a novel optimization strategy is proposed.This strategy generates a sparse TSP graph based on frequency graphs,significantly reducing the search space of the optimal Hamiltonian cycle and lowering the problem's complexity.Firstly,LOP4s are computed from the weighted complete graph.The frequencies of edges appearing in the LOP4s are then calculated to form a frequency graph.Based on this frequency graph,a sparse graph for TSP is constructed.Initially,AF of all edges is set as the frequency threshold,and edges with frequencies below AF are removed to generate the sparse graph of the first-generation.Subsequently,further edge deletions are performed according to different vertex degree thresholds m ranging from 5 to min{n/4,45}).Specifically,the frequencies of all edges connected to each vertex are summed to determine the corresponding vertex frequency.Vertices are sorted by their frequencies,and the edges having the least frequency and connecting the vertices with the highest-frequency are iteratively deleted in case that the degree of each vertex is no less than m.This process yields multiple sparse graphs of the second-generation.Finally,the sparse graphs of the second-generation are added together,and a dual-frequency is introduced to determine which edges to retain for producing the sparse graph of the third-generation.Experiments conducted on 20 standard TSP datasets demonstrate the algorithm's effectiveness.Results show that the sparse graph of the third-generation retains all edges in the optimal Hamiltonian cycle while it contains a small number of edges in the complete graph,which greatly reduces the search space of the optimal Hamiltonian cycle.Based on the online Concorde system,the optimal Hamiltonian cycles are searched using both the complete graph and the sparse graph.It is observed that the search time based on the sparse graph is shorter than that according to the complete graph.This study provides a new perspective for reducing the difficulty of TSP and lays a foundation for future integration with other heuristic algorithms or machine learning techniques to solve TSP.

Key words: Traveling Salesman Problem(TSP), Optimal Hamiltonian Cycle(OHC), Frequency graph, Sparse graph