An iterative algorithm to eliminate edges for traveling salesman problem based on a new binomial distribution

摘要

Traveling salesman problem (TSP) is one of the extensively studied NP-hard problems. The recent research showed that the TSP on sparse graphs could be resolved in the relatively shorter computation time than that on the complete graph \(K_{n}\). This paper updates a previous probability model for the optimal Hamiltonian cycle edges according to the frequency quadrilaterals in \(K_{n}\). A new binomial distribution for TSP is rebuilt to show the probability that an edge e has the frequency 5 in a frequency quadrilateral. Based on the binomial distribution, an iterative algorithm is designed to compute the sparse graphs for TSP. There are two steps at each computation cycle. Firstly, N frequency quadrilaterals containing an edge e in the input graph is chosen to compute the average frequency \(\bar {f}(e)\) with the frequency quadrilaterals where e has the frequency 5. Secondly, half edges with the small values \(\bar {f}(e)\) are eliminated. The two steps are repeated until a sparse graph is computed. The computation time of the algorithm is \(O(Nn^{2})\). For the TSP instances in the TSPLIB, the experimental results illustrated that the sparse graphs with the \(O(n\log _{2} n)\) edges are computed and the original optimal solution is preserved. The experiments means the optimal Hamiltonian cycle edges have the bigger average frequency \(\bar {f}(e)\) in \(K_{n}\) and the subgraphs of \(K_{n}\) so they are preserved in the computation process.