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

Bibliographie

[1] Little J.D.C., Murty K.G., Sweeney D.W., Karel C., “An algorithm for the traveling salesman problem”, Oper. Res., 11:6 (1965), 94–107 | DOI

[2] Melamed I.I., Sergeev S.I., Sigal I.Kh., “The traveling salesman problem. Issues in the theory”, Autom. Remote Control, 50:9 (1989), 1147–1173

[3] Melamed I.I., Sergeev S.I., Sigal I.Kh., “The traveling salesman problem. Exact methods”, Autom. Remote Control, 50:10 (1989), 1303–1324

[4] Melamed I.I., Sergeev S.I., Sigal I.Kh., “The traveling salesman problem. Approximate algorithms”, Autom. Remote Control, 50:11 (1989), 1459–1479

[5] Luu Q.T., Aibin M., Traveling Salesman Problem: Exact solutions vs. heuristic vs. approximation algorithms, Baeldung, , 2024 https://www.baeldung.com/cs/tsp-exact-solutions-vs-heuristic-vs-approximation-algorithms

[6] Buslenko N.P., Shreider Ju.A., The Statistical Test Method (Monte Carlo) and Its Use on Digital Computers, Gos. Izd. Fiz.-Mat. Lit., M., 1961, 228 pp. (In Russian)

[7] Sobol' I.M., Numerical Monte Carlo Methods, Nauka, M., 1973, 312 pp. (In Russian)

[8] Kemeny J., Snell J., Finite Markov Chains, The University Series in Undergraduate Mathematics, eds. Kelley J.L., Halmos P.R., D. Van Nostrand Co., Princeton, NJ, 1960, 210 pp. https://archive.org/details/finitemarkovchai0000unse

[9] Doob J.L., Stochastic Processes, Wiley Classics Library, 24, Wiley, Hoboken, NJ, 1990, 654 pp. https://books.google.ru/books?id=0GUGAQAAIAAJ

[10] Al'pin Yu.A., Zakharov V.M., “An automata-theoretic approach to the description and modeling of stochastic processes”, Veroyatn. Metody Kibern., 19 (1983), 10–16 (In Russian)

[11] Gremal'skii A.A., Andronik S.M., Stochastic Markov process generator, Patent USSR: 1453403, 1987 (In Russian) https://patents.su/5-1453403-generator-sluchajjnogo-markovskogo-processa.html

[12] Gremal'skii A.A., Andronik S.M., Stochastic Markov process generator, Patent USSR: 1481755, 1987 (In Russian) https://patents.su/5-1481755-generator-sluchajjnogo-markovskogo-processa.html

[13] Gremal'skii A.A., Stochastic Markov process generator, Patent USSR: 1531093, 1988 (In Russian) https://patents.su/6-1531093-generator-sluchajjnogo-markovskogo-processa.html

[14] Yuminov O.B., Irisov M.V., Dzyuin S.V., N-state Markov chain generator, Patent USSR no. 1550501, 1988 (In Russian) https://patents.su/2-1550501-generator-n-svyaznojj-markovskojj-posledovatelnosti.html

[15] Dobryden' V.A., A device for modeling Markov processes, Patent USSR: 526909, 1975 (In Russian) https://patents.su/6-526909-ustrojjstvo-dlya-modelirovaniya-markovskikh-processov.html

[16] Zakharov V.M., Nurutdinov Sh.R., Shalagin S.V., “Polynomial representation of Markov chains over a Galois field”, Vestn. KGTU im. A.N. Tupoleva, 2001, no. 3, 27–31 (In Russian)

[17] Zakharov V.M., Shalagin S.V., Gumirov A.I., “Hardware and software module of the Markov sequence generator based on programmable logic integrated circuits”, Vestn. Kazan. Gos. Tekh. Univ. im. A.N. Tupoleva, 78:4 (2022), 164–172 (In Russian)

[18] Zakharov V.M., Shalagin S.V., Eminov B.F., Automata Markov Models over a Finite Field, Spets. Fond Upr. Tselevym Kap. Razvit. Kazan. Nats. Issled. Tekh. Univ. im. A.N. Tupoleva, Kazan, 2022, 328 pp. (In Russian) https://disk.yandex.ru/i/PxXZClzIRdDnzQ

[19] Zakharov V.M., Shalagin S.V., Gumirov A.I., “Discrete random variable generator with the given distribution law in FPGA-architecture”, Vestn. DGU. Ser. 1: Estestv. Nauki, 38:3 (2023), 28–33 (In Russian) | DOI

[20] Rice J.A., Mathematical Statistics and Data Analysis, Thomson Brooks/ Cole, Belmont, CA, 2007, 698 pp. https://archive.org/details/mathematicalstat0000rice_c1o8_3ed

[21] Feller V., An Introduction to Probability Theory and Its Applications, v. 1, Wiley Series in Probability and Statistics, Wiley, New York, NY, 1957, 669 pp. https://archive.org/details/introductiontopr0001will/mode/2up

[22] Shalagin S.V., “The complexity of computing nonlinear polynomial functions over the $GF(2^2)$ field on PLD/FPGA”, Exploring Effective Solutions for the Development and Implementation of Scientific Innovations in Russia's Aviation and Space Industry, Proc. Int. Sci. Pract. Conf., v. II, Izd. Kazan. Gos. Tekh. Univ., Kazan, 2014, 661–664 (In Russian)