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

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

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



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






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


Тр. ИММ УрО РАН, 2015, том 21, номер 3, страницы 309–317 (Mi timm1222)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов

А. Г. Ченцовab, М. Ю. Хачайba, Д. М. Хачайb

a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург

Аннотация: Исследуется задача обхода мегаполисов с фиксированным числом “входов” и специальным образом заданными отношениями предшествования, являющаяся естественным обобщением классической задачи коммивояжера (TSP). Для поиска оптимального решения задачи приводится схема динамического программирования, эквивалентная методу поиска кратчайшего пути в подходящем бесконтурном ориентированном взвешенном графе. Обосновываются условия, при которых трудоемкость алгоритма полиномиально, в частности, линейно зависит от числа мегаполисов.

Ключевые слова: задача коммивояжера (tsp), $np$-трудная задача, динамическое программирование, отношения предшествования.

Полный текст: PDF файл (185 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2016, 295, suppl. 1, 38–46

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.16 + 519.85
Поступила в редакцию: 11.05.2015

Образец цитирования: А. Г. Ченцов, М. Ю. Хачай, Д. М. Хачай, “Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов”, Тр. ИММ УрО РАН, 21, № 3, 2015, 309–317; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38–46

Цитирование в формате AMSBIB
\RBibitem{CheKhaKha15}
\by А.~Г.~Ченцов, М.~Ю.~Хачай, Д.~М.~Хачай
\paper Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов
\serial Тр. ИММ УрО РАН
\yr 2015
\vol 21
\issue 3
\pages 309--317
\mathnet{http://mi.mathnet.ru/timm1222}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468113}
\elib{http://elibrary.ru/item.asp?id=24156736}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2016
\vol 295
\issue , suppl. 1
\pages 38--46
\crossref{https://doi.org/10.1134/S0081543816090054}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=WOS:000394441400005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85010430812}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timm1222
  • http://mi.mathnet.ru/rus/timm/v21/i3/p309

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. М. Ю. Хачай, Е. Д. Незнахина, “Приближенные схемы для обобщенной задачи коммивояжера”, Тр. ИММ УрО РАН, 22, № 3, 2016, 283–292  mathnet  crossref  mathscinet  elib; M. Yu. Khachai, E. D. Neznakhina, “Approximation Schemes for the Generalized Traveling Salesman Problem”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 97–105  crossref  isi
    2. M. Khachay, K. Neznakhina, “Polynomial time solvable subclass of the generalized traveling salesman problem on grid clusters”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 346–355  crossref  mathscinet  isi  scopus
    3. Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov, “Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions”, Ural Math. J., 4:2 (2018), 43–55  mathnet  crossref  mathscinet
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:218
    Полный текст:50
    Литература:29
    Первая стр.:23
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020