Optimizing with Attractor Combinatorial Complexity of the Traveling Salesman Problem
Weiqi Li · Research Square · 2024
Abstract This paper studies combinatorial complexity of the Traveling Salesman Problem (TSP) from the attractor perspective. In order to find the exact optimal tour for a TSP instance, a kind of exhaustive search is unavoidable. However, the combinatorial explosion of possible tours in the solution space makes an exhaustive search algorithm infeasible for large instances. How can we reduce the search space efficiently and effectively to make an exhaustive search algorithm feasible? This is the question this paper aims to answer. The TSP has a data structure, through which its complexity can be exponentially reduced by a polynomial-time algorithm. This paper describes the complexity reducibility of the TSP from the attractor perspective of dynamical systems. A local search algorithm can be used to reduce the search space from the entire solution space to a much smaller attractor for an exhaustive search. The results show that the TSP might not be as complex as we have expected. Mathematics Subject Classification (2020) 05A15 · 05C05 · 05C30 ·37A50 · 37N40 · 68Q17 · 68Q25 · 68W40 · 90C27