Эта публикация цитируется в
1 статье
Математика
Подход к решению псевдогеометрической версии задачи коммивояжера
С. Б. Макаркин,
Б. Ф. Мельников,
М. А. Тренина Тольяттинский государственный университет, Тольятти
Аннотация:
Актуальность и цели. Задача коммивояжера является примером математической модели, которая, будучи созданной для одной предметной области, находит свое применение и во многих других областях. Псевдогеометрическая версия этой проблемы более адекватно описывает множество ее частных случаев, встречающихся в большинстве предметных областей, чем значительно более распространенная геометрическая версия. Цель работы: применить разработанные подходы для решения геометрической версии задачи коммивояжера для ее так называемой псевдогеометрической версии.
Материалы и методы. Для решения псевдогеометрической задачи коммивояжера рассматривается несколько случайно сгенерированных перестановок всего множества точек, и для каждой из них применяется алгоритм псевдовосстановления их расположения. Выбор единственного варианта расположения каждой точки возможен после решения оптимизационной задачи, заключающейся в повороте сгенерированного множества точек на некоторый угол и смещении на некоторый вектор.
Результат. Сформулированы различные метрики и изучены их свойства, на основании которых разработан эвристический алгоритм локального поиска.
Выводы. Применение описанных в настоящей работе метрик и эвристического алгоритма локального поиска позволило повысить эффективность геометрического метода решения псевдогеометрической задачи коммивояжера.
Ключевые слова:
задача коммивояжера, геометрическая версия, псевдогеометрическая версия, геометрический подход, метрика, эвристические алгоритмы.
УДК:
004.23