A Probability Model Based on Frequency Quadrilaterals for Travelling Salesman Problem

摘要

The research aims to generate a sparse graph for travelling salesman problem so as to reduce its complexity. A probability model based on frequency quadrilaterals is given to show that the average frequency of an edge is 3N if its total frequency is computed with N random frequency quadrilaterals in complete graph K_n. For an edge in the optimal Hamiltonian cycle, the minimum frequency is derived as (3 + 2/n-2)N. It suggests we can throw away the edges with frequency below (3 + 2/n-2) N and still keep the optimal Hamiltonian cycle in the reserved graph. We test the probability model with quitea few Euclidean TSP instances. The results show the threshold (3 + 2/n-2) Nis too small for most of the instances.