Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум Full article
Journal |
Дискретный анализ и исследование операций
ISSN: 1560-7542 |
||||
---|---|---|---|---|---|
Output data | Year: 2020, Volume: 27, Number: 3, Pages: 28–52 Pages count : 25 | ||||
Tags | гамильтонов цикл; задача коммивояжёра; задача нескольких коммивояжёров; приближённый алгоритм; гарантированная оценка точности | ||||
Authors |
|
||||
Affiliations |
|
Abstract:
В 2005 г. Капланом и др. был разработан полиномиальный алгоритм с гарантированной оценкой точности 2/3 для несимметричного случая задачи коммивояжёра на максимум. В 2014 г. Глебов, Замбалаева и Скретнева получили алгоритм с такой же оценкой точности и кубической оценкой временной сложности для несимметричного случая задачи о двух коммивояжёрах на максимум, где требуется найти два рёберно не пересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном n-вершинном ориентированном графе. Целью настоящей работы является построение аналогичного алгоритма для более общей задачи об m коммивояжёрах на максимум в несимметричном случае и обоснование для этого алгоритма оценки точности, асимптотически стремящейся к 2/3 с ростом m, и оценки временной сложности O(mn^3). Ил. 2, библиогр. 29. © А. Н. Глебов, С. Г. Токтохоева, 2020
Cite:
Глебов А.Н.
, Токтохоева С.Г.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2020. Т.27. №3. С.28–52.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2020. Т.27. №3. С.28–52.
Translated:
Glebov A.N.
, Toktokhoeva S.G.
A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP
Journal of Applied and Industrial Mathematics. 2020. V.14. N3. P.456-469. DOI: 10.1134/S1990478920030059 Scopus OpenAlex
A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP
Journal of Applied and Industrial Mathematics. 2020. V.14. N3. P.456-469. DOI: 10.1134/S1990478920030059 Scopus OpenAlex
Dates:
Submitted: | Dec 2, 2019 |
Accepted: | May 25, 2020 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований