Версии алгоритма «луковой шелухи» для псевдогеометрической версии задачи коммивояжёра с малой дисперсией

Авторы

  • Борис Феликсович Мельников Центр информационных технологий и систем органов исполнительной власти, Пресненский Вал, д. 19, стр. 1, 123557, Москва, Россия; Российский государственный социальный университет, ул. Вильгельма Пика, д. 4, стр. 1, 129226, Москва, Россия http://orcid.org/0000-0002-6765-6800 (неаутентифицированный)

DOI:

https://doi.org/10.32603/2071-2340-2023-4-30-40

Ключевые слова:

оптимизационные проблемы, задача коммивояжера, эвристические алгоритмы, алгоритм «луковой шелухи», алгоритмы реального времени, Си

Аннотация

Мы продолжаем рассматривать псевдогеометрическую задачу коммивояжера. В частности, мы рассматриваем несколько вспомогательных алгоритмов, необходимых для реализации различных версий алгоритма «луковой шелухи». Мы не нашли в~литературе точного описания конкретных версий алгоритмов для геометрической версии (впрочем, в этом нет необходимости,
поскольку исходные версии этих алгоритмов необходимо реализовать для псевдогеометрической версии), поэтому мы начинаем работу с геометрической версии.

Случайная генерация данных для вычислительных экспериментов соответствовала решаемой проблеме:
для каждого из нескольких вариантов размерности задачи были проведены некоторые вычислительные эксперименты со случайно сгенерированными входными данными. Были рассчитаны следующие характеристики полученных результатов:
среднее количество результирующих контуров для геометрического варианта;
отношение решения с контурами к оптимальному решению;
отношение решения псевдогеометрической версии, соответствующее порядку точек геометрической версии, к геометрическому решению.

Полученные результаты вычислительных экспериментов в целом приблизительно соответствуют ожидаемым значениям.

Биография автора

  • Борис Феликсович Мельников, Центр информационных технологий и систем органов исполнительной власти, Пресненский Вал, д. 19, стр. 1, 123557, Москва, Россия; Российский государственный социальный университет, ул. Вильгельма Пика, д. 4, стр. 1, 129226, Москва, Россия

    Доктор физико-математических наук, профессор Совместного университета МГУ-ППИ в Шэньчжэне, Китай; главный научный сотрудник Центра информационных технологий и систем органов исполнительной власти, Москва

Загрузки

Опубликован

29.12.2023

Выпуск

№ 4 (2023)

Раздел

Алгоритмическая математика и математическое моделирование

Лицензия

Авторский договор

 

Материал публикуется под лицензией:

Creative Commons License

Creative Commons Attribution 4.0 International License.

Как цитировать

[1]
Б. Ф. Мельников, «Версии алгоритма „луковой шелухи“ для псевдогеометрической версии задачи коммивояжёра с малой дисперсией», Компьютерные инструменты в образовании, вып. 4, сс. 30–40, дек. 2023, doi: 10.32603/2071-2340-2023-4-30-40.

Похожие статьи

1-10 из 338

Вы также можете начать расширеннвй поиск похожих статей для этой статьи.

Наиболее читаемые статьи этого автора (авторов)