Решение задачи коммивояжёра методом статистических испытаний при использовании сложных цепей Маркова
https://doi.org/10.26907/2541-7746.2024.4.639-650
Аннотация
Предложен метод решения задачи коммивояжёра (ЗК) с применением аппарата N -сложных цепей Маркова (N -ЦМ), последовательность состояний которых имитирует путь через N пунктов, каждый из пунктов посещается только один раз. Для каждого из пунктов задана вероятность перехода в один из l следующих пунктов, l < N . Выполнен анализ сложности реализации каждого из этапов предложенного метода в зависимости от заданных значений N и l. Получены оценки сложности генератора N -ЦМ на основе композиции конечного детерминированного автомата и вероятностного автомата без памяти. Сложность генератора N -ЦМ характеризуется объёмом множеств входов, внутренних состояний и выходов, а также объёмом памяти, требуемой для реализации функций переходов и выходов указанных автоматов. Даны оценки времени задержки функционирования генератора N -ЦМ. Рассчитаны вероятность генерирования допустимых путей, т. е. удовлетворяющих решению ЗК, и объём памяти, требуемой для хранения количества допустимых путей.
Ключевые слова
задача коммивояжёра,
метод решения,
сложная цепь Маркова,
статистическое испытание,
оценка сложности
Об авторе
С. В. Шалагин
Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ
Россия
Россия
Сергей Викторович Шалагин, доктор технических наук, доцент, профессор
кафедра компьютерных систем
420111; ул. Карла Маркса, д. 10; Казань
Список литературы
1. Little J.D.C., Murty K.G., Sweeney D.W., Karel C. An algorithm for the traveling salesman problem // Oper. Res. 1965. V. 11, No 6. P. 94–107. doi: 10.1287/opre.11.6.972.
2. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // Автомат. телемех. 1989. № 9. С. 3–33.
3. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные методы // Автомат. телемех. 1989. № 10. С. 3–29.
4. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. приближённые алгоритмы // Автомат. телемех. 1989. № 11. С. 3–26.
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. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний (Монте-Карло) и его реализация на цифровых вычислительных машинах. М.: Гос. изд-во физ.-матем. лит., 1961. 228 с.
7. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973. 312 с.
8. Kemeny J., Snell J. 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. V. 24. Hoboken, NJ: Wiley, 1990. 654 p. URL: https://books.google.ru/books?id=0GUGAQAAIAAJ.
10. Альпин Ю.А., Захаров В.М. Теоретико-автоматный метод описания и моделирования случайных процессов // Вероятн. мет. кибернет. 1983. Т. 19. С. 10–16.
11. Гремальский A.A., Андроник С.М. Генератор случайного марковского процесса. 1987. Номер патента: 1453403. URL: https://patents.su/5-1453403-generator-sluchajjnogo-markovskogo-processa.html.
12. Гремальский A.A., Андроник С.М. Генератор случайного марковского процесса. 1987. Номер патента: 1481755. URL: https://patents.su/5-1481755-generator-sluchajjnogo-markovskogo-processa.html.
13. Гремальский A.A. Генератор случайного марковского процесса. 1988. Номер патента: 1531093. URL: https://patents.su/6-1531093-generator-sluchajjnogo-markovskogo-processa.html.
14. Юминов О.Б., Ирисов М.В., Дзюин С.В. Генератор n-связной марковской последовательности. 1988. Номер патента: 1550501. URL: https://patents.su/2-1550501-generator-n-svyaznojj-markovskojj-posledovatelnosti.html.
15. Добрыдень В.А. Устройство для моделирования марковских процессов. 1975. Номер патента: 526909. URL: https://patents.su/6-526909-ustrojjstvo-dlya-modelirovaniya-markovskikh-processov.html.
16. Захаров В.М., Нурутдинов Ш.Р., Шалагин С.В. Полиномиальное представление цепей Маркова над полем Галуа // Вестн. КГТУ им. А.Н. Туполева. 2001. № 3. С. 27–31.
17. Захаров В.М., Шалагин С.В., Гумиров А.И. Аппаратно-программный модуль генератора марковских последовательностей на основе программируемых логических интегральных схем // Вестн. КГТУ им. А.Н. Туполева. 2022. Т. 78, № 4. С. 164–172.
18. Захаров В.М., Шалагин С.В., Эминов Б.Ф. Автоматные марковские модели над конечным полем. Казань: Спец. фонд управл. цел. капит. для разв. Казан. нац. исслед. техн. ун-та им. А.Н. Туполева, 2022. 328 с. URL: https://disk.yandex.ru/i/PxXZClzIRdDnzQ.
19. Захаров В.М., Шалагин С.В., Гумиров А.И. Генератор дискретной случайной величины с заданным законом распределения в архитектуре ПЛИС/FPGA // Вестн. ДГУ. Сер. 1: Ест. науки. 2023. Т. 38, № 3. С. 28–33. doi: 10.21779/2542-0321-2023-38-3-28-33.
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. V. 1. Ser.: Wiley Series in Probability and Statistics. New York, NY: Wiley, 1957. 669 p. URL: https://archive.org/details/introductiontopr0001will/mode/2up.
22. Шалагин С.В. Cложность вычисления нелинейных полиномиальных функций над полем GF(22) на ПЛИС/FPGA // Поиск эффективных решений в процессе создания и реализации научных разработок в российской авиационной и ракетно-космической промышленности : Междунар. науч.-практ. конф. Т. II. Казань, Изд-во Казан. гос. техн. ун-та, 2014. С. 661–664.
Рецензия
Для цитирования:
Шалагин С.В. Решение задачи коммивояжёра методом статистических испытаний при использовании сложных цепей Маркова. Ученые записки Казанского университета. Серия Физико-математические науки. 2024;166(4):639-650. https://doi.org/10.26907/2541-7746.2024.4.639-650
For citation:
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
Просмотров:
118
Послать статью по эл. почте 