Solving the traveling salesman problem by statistical testing using complex Markov chains

S. V. Shalagin

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 166 (2024) no. 4, pp. 639-650

Résumé

A method was proposed for solving the traveling salesman problem (TSP) using $N$-complex Markov chains ($N$-MC), the state sequence of which simulates a path through $N$ points, each visited only once. Transition probabilities from each point to one of the next $l$ points were set, where $l N$. The complexity of implementing all stages of the method, depending on the values of $N$ and $l$, was analyzed. Estimates of the complexity of the $N$-MC generator were obtained based on the composition of a finite deterministic automaton and a probabilistic memoryless automaton. The complexity of the $N$-MC generator is characterized by the volume of input sets, internal states, and outputs, as well as the amount of memory required to implement the transition and output functions of the automata. The delay time of the $N$-MC generator operation was also estimated. The probability of generating valid paths, i.e., those resolving TSP, and the memory requirements for storing valid paths were calculated.

Détail

Keywords: traveling salesman problem, method of solving, statistical test, complexity estimate.
Mots-clés : complex Markov chain