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

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