Эта публикация цитируется в 1 статье

Решение задачи коммивояжёра методом статистических испытаний при использовании сложных цепей Маркова

С. В. Шалагин

Казанский национальный исследовательский технический университет им. А.Н. Туполева — КАИ, г. Казань, 420111, Россия

Аннотация: Предложен метод решения задачи коммивояжёра (ЗК) с применением аппарата $N$-сложных цепей Маркова ($N$-ЦМ), последовательность состояний которых имитирует путь через $N$ пунктов, каждый из пунктов посещается только один раз. Для каждого из пунктов задана вероятность перехода в один из $l$ следующих пунктов, $l < N$. Выполнен анализ сложности реализации каждого из этапов предложенного метода в зависимости от заданных значений $N$ и $l$. Получены оценки сложности генератора $N$-ЦМ на основе композиции конечного детерминированного автомата и вероятностного автомата без памяти. Сложность генератора $N$-ЦМ характеризуется объёмом множеств входов, внутренних состояний и выходов, а также объёмом памяти, требуемой для реализации функций переходов и выходов указанных автоматов. Даны оценки времени задержки функционирования генератора $N$-ЦМ. Рассчитаны вероятность генерирования допустимых путей, т. е. удовлетворяющих решению ЗК, и объём памяти, требуемой для хранения количества допустимых путей.

Ключевые слова: задача коммивояжёра, метод решения, сложная цепь Маркова, статистическое испытание, оценка сложности.

УДК: 519.854.2: 519.245: 519.217.2

Поступила в редакцию: 15.08.2024
Принята в печать: 05.10.2024

DOI: 10.26907/2541-7746.2024.4.639-650