Journal of Computational and Engineering Mathematics
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


J. Comp. Eng. Math.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Journal of Computational and Engineering Mathematics, 2017, том 4, выпуск 3, страницы 49–54
DOI: https://doi.org/10.14529/jcem170306 (Mi jcem99) 		 
Short Notes

An approximation algorithm for the maximum traveling salesman problem
[Приближенный алгоритм решения задачи коммивояжера на максимум]

A. Yu. Evnin, N. I. Yusova

South Ural State University, Chelyabinsk, Russian Federation
PDF полного текста (1266 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.14529/jcem170306
Аннотация: Задача коммивояжера состоит в следующем: учитывая список городов и расстояние между каждой парой городов, необходимо составить самый короткий маршрут, по которому каждый город посещается ровно один раз и маршрут заканчивается в том городе, к котором начинался. Это NP-сложная проблема в комбинаторной оптимизации, важной в исследовании операций и теоретической информатике. Задача коммивояжера – одна из самых известных и исследуемых проблем в информатике. В статье описывается приближенный алгоритм решения задачи коммивояжера на максимум, основанный на двух известных полиномиальных алгоритмах. Точность данного алгоритма составляет 25/33.
Ключевые слова: гамильтонов цикл, задача коммивояжера, приближенный алгоритм, 2-фактор, паросочетание, оценка точности.
Поступила в редакцию: 16.05.2017
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.161
MSC: 05C85
Язык публикации: английский
Образец цитирования: A. Yu. Evnin, N. I. Yusova, “An approximation algorithm for the maximum traveling salesman problem”, J. Comp. Eng. Math., 4:3 (2017), 49–54
Цитирование в формате AMSBIB
\RBibitem{EvnYus17}
\by A.~Yu.~Evnin, N.~I.~Yusova
\paper An approximation algorithm for the maximum traveling salesman problem
\jour J. Comp. Eng. Math.
\yr 2017
\vol 4
\issue 3
\pages 49--54
\mathnet{http://mi.mathnet.ru/jcem99}
\crossref{https://doi.org/10.14529/jcem170306}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3708704}
\elib{https://elibrary.ru/item.asp?id=30289927}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/jcem99
  • https://www.mathnet.ru/rus/jcem/v4/i3/p49
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Journal of Computational and Engineering Mathematics
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024