Версии алгоритма «луковой шелухи» для псевдогеометрической версии задачи коммивояжёра с малой дисперсией - Мельников, Борис Феликсович (Компьютерные инструменты в образовании, 2023)
Мы продолжаем рассматривать псевдогеометрическую задачу коммивояжера. В частности, мы рассматриваем несколько вспомогательных алгоритмов, необходимых для реализации различных версий алгоритма «луковой шелухи». Мы не нашли в~литературе точного описания конкретных версий алгоритмов для геометрической версии (впрочем, в этом нет необходимости,поскольку исходные версии этих алгоритмов необходимо реализовать для псевдогеометрической версии), поэтому мы начинаем работу с геометрической версии.Случайная генерация данных для вычислительных экспериментов соответствовала решаемой проблеме:для каждого из нескольких вариантов размерности задачи были проведены некоторые вычислительные эксперименты со случайно сгенерированными входными данными. Были рассчитаны следующие характеристики полученных результатов: среднее количество результирующих контуров для геометрического варианта; отношение решения с контурами к оптимальному решению; отношение решения псевдогеометрической версии, соответствующее порядку точек геометрической версии, к геометрическому решению. Полученные результаты вычислительных экспериментов в целом приблизительно соответствуют ожидаемым значениям.
Keywords: оптимизационные проблемы, задача коммивояжера, эвристические алгоритмы, алгоритм «луковой шелухи», алгоритмы реального времени, Си