|
Труды Института математики и механики УрО РАН, 2015, том 21, номер 3, страницы 309–317
(Mi timm1222)
|
|
|
|
Эта публикация цитируется в 19 научных статьях (всего в 19 статьях)
Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов
А. Г. Ченцовab, М. Ю. Хачайba, Д. М. Хачайb a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
Аннотация:
Исследуется задача обхода мегаполисов с фиксированным числом “входов” и специальным образом заданными отношениями предшествования, являющаяся естественным обобщением классической задачи коммивояжера (TSP). Для поиска оптимального решения задачи приводится схема динамического программирования, эквивалентная методу поиска кратчайшего пути в подходящем бесконтурном ориентированном взвешенном графе. Обосновываются условия, при которых трудоемкость алгоритма полиномиально, в частности, линейно зависит от числа мегаполисов.
Ключевые слова:
задача коммивояжера (tsp), $np$-трудная задача, динамическое программирование, отношения предшествования.
Поступила в редакцию: 11.05.2015
Образец цитирования:
А. Г. Ченцов, М. Ю. Хачай, Д. М. Хачай, “Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов”, Тр. ИММ УрО РАН, 21, № 3, 2015, 309–317; Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 38–46
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1222 https://www.mathnet.ru/rus/timm/v21/i3/p309
|
Статистика просмотров: |
Страница аннотации: | 342 | PDF полного текста: | 79 | Список литературы: | 59 | Первая страница: | 23 |
|