Solving the traveling salesman problem by statistical testing using complex Markov chains
https://doi.org/10.26907/2541-7746.2024.4.639-650
Abstract
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.
About the Author
S. V. Shalagin
Kazan National Research Technical University named after A.N. Tupolev – KAI
Russian Federation
Russian Federation
420111; Kazan
References
1. Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem. Oper. Res., 1965., vol. 11, no. 6, pp. 94–107. doi: 10.1287/opre.11.6.972.
2. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Issues in the theory. Autom. Remote Control, 1989, vol. 50, no. 9, pp. 1147–1173.
3. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Exact methods. Autom. Remote Control, 1989, vol. 50, no. 10, pp. 1303–1324.
4. Melamed I.I., Sergeev S.I., Sigal I.Kh. The traveling salesman problem. Approximate algorithms. Autom. Remote Control, 1989, vol. 50, no. 11, pp. 1459–1479.
5. Luu Q.T., Aibin M. Traveling Salesman Problem: Exact solutions vs. heuristic vs. approximation algorithms. Baeldung, 2024. URL: https://www.baeldung.com/cs/tsp-exact-solutions-vs-heuristic-vs-approximation-algorithms.
6. Buslenko N.P., Shreider Ju.A. Metod statisticheskikh ispytanii (Monte-Karlo) i ego realizatsiya na tsifrovykh mashinakh [The Statistical Test Method (Monte Carlo) and Its Use on Digital Computers]. Moscow, Gos. Izd. Fiz.-Mat. Lit., 1961. 228 p. (In Russian)
7. Sobol’ I.M. Chislennye metody Monte-Karlo [Numerical Monte Carlo Methods]. Moscow, Nauka, 1973. 312 p. (In Russian)
8. Kemeny J.G., Snell J.L. Finite Markov Chains. Ser.: The University Series in Undergraduate Mathematics. Kelley J.L., Halmos P.R. (Eds.). Princeton, NJ, D. Van Nostrand Co., 1960. 210 p. URL: https://archive.org/details/finitemarkovchai0000unse.
9. Doob J.L. Stochastic Processes. Ser.: Wiley Classics Library. Vol. 24. Hoboken, NJ, Wiley, 1990. 654 p. URL: 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., 1983, vol. 19, pp. 10–16. (In Russian)
11. Gremal’skii A.A., Andronik S.M. Stochastic Markov process generator. Patent USSR no. 1453403, 1987. URL: https://patents.su/5-1453403-generator-sluchajjnogo-markovskogo-processa.html. (In Russian)
12. Gremal’skii A.A., Andronik S.M. Stochastic Markov process generator. Patent USSR no. 1481755, 1987. URL: https://patents.su/5-1481755-generator-sluchajjnogo-markovskogo-processa.html. (In Russian)
13. Gremal’skii A.A. Stochastic Markov process generator. Patent USSR no. 1531093, 1988. URL: https://patents.su/6-1531093-generator-sluchajjnogo-markovskogo-processa.html. (In Russian)
14. Yuminov O.B., Irisov M.V., Dzyuin S.V. N-state Markov chain generator. Patent USSR no. 1550501, 1988. URL: https://patents.su/2-1550501-generator-n-svyaznojj-markovskojj-posledovatelnosti.html. (In Russian)
15. Dobryden’ V.A. A device for modeling Markov processes. Patent USSR no. 526909, 1975. URL: https://patents.su/6-526909-ustrojjstvo-dlya-modelirovaniya-markovskikh-processov.html. (In Russian)
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, pp. 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, 2022, vol. 78, no. 4, pp. 164–172. (In Russian)
18. Zakharov V.M., Shalagin S.V., Eminov B.F. Avtomatnye markovskie modeli nad konechnym polem [Automata Markov Models over a Finite Field]. Kazan, Spets. Fond Upr. Tselevym Kap. Razvit. Kazan. Nats. Issled. Tekh. Univ. im. A.N. Tupoleva, 2022. 328 p. URL: https://disk.yandex.ru/i/PxXZClzIRdDnzQ. (In Russian)
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, 2023, vol. 38, no. 3, pp. 28–33. doi: 10.21779/2542-0321-2023-38-3-28-33. (In Russian)
20. Rice J.A. Mathematical Statistics and Data Analysis. Belmont, CA, Thomson Brooks/Cole, 2007. 698 p. URL: https://archive.org/details/mathematicalstat0000rice_c1o8_3ed.
21. Feller V. An Introduction to Probability Theory and Its Applications. Vol. 1. Ser.: Wiley Series in Probability and Statistics. New York, NY, Wiley, 1957. 669 p. URL: https://archive.org/details/introductiontopr0001will/mode/2up.
22. Shalagin S.V. The complexity of computing nonlinear polynomial functions over the GF(22) field on PLD/FPGA. Poisk effektivnykh reshenii v protsesse sozdaniya i realizatsii nauchnykh razrabotok v rossiiskoi aviatsionnoi i raketno-kosmicheskoi promyshlennosti : Mezhdunar. nauch.-prakt. konf. [Exploring Effective Solutions for the Development and Implementation of Scientific Innovations in Russia’s Aviation and Space Industry : Proc. Int. Sci. Pract. Conf.]. Vol. II. Kazan, Izd. Kazan. Gos. Tekh. Univ., 2014, pp. 661–664. (In Russian)
Review
For citations:
Shalagin S.V. Solving the traveling salesman problem by statistical testing using complex Markov chains. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2024;166(4):639-650. (In Russ.) https://doi.org/10.26907/2541-7746.2024.4.639-650
Views:
117
Email this article 