Эксперт КНИТУ-КАИ выступил на научном семинаре «Методы моделирования»
Профессор кафедры компьютерных систем КНИТУ-КАИ, доктор технических наук Сергей Шалагин своим видением решение знаменитой «задачи коммивояжера». Для этого он предлагает использовать метод статистических испытаний при использовании сложных цепей Маркова. Доклад был представлен на республиканском научном семинаре «Методы моделирования».
«Предложен метод решения этой задачи с применением аппарата N-сложных цепей Маркова (N-ЦМ). Последовательность состояний цепей Маркова имитирует путь через N пунктов, каждый из которых посещается только один раз. Задана вероятность перехода каждого из пунктов, выполнен анализ сложности реализации каждого из этапов предложенного метода в зависимости от тех или иных параметров. Получены оценки сложности генератора N-ЦМ на основе композиции конечного детерминированного автомата и вероятностного автомата без памяти», - отметил Сергей Шалагин.
Для справки: Задача коммивояжера (или TSP – travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
