Standard

ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ. / Ченцов, Александр Георгиевич; Хачай, Михаил Юрьевич; Хачай, Даниил Михайлович.
в: Труды института математики и механики УрО РАН, Том 21, № 3, 2015, стр. 309-317.

Результаты исследований: Вклад в журнал › Статья › Рецензирование

Harvard

Ченцов, АГ, Хачай, МЮ & Хачай, ДМ 2015, 'ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ', Труды института математики и механики УрО РАН, Том. 21, № 3, стр. 309-317.

APA

Ченцов, А. Г., Хачай, М. Ю., & Хачай, Д. М. (2015). ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ. Труды института математики и механики УрО РАН, 21(3), 309-317.

Vancouver

Ченцов АГ, Хачай МЮ, Хачай ДМ. ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ. Труды института математики и механики УрО РАН. 2015;21(3):309-317.

Author

Ченцов, Александр Георгиевич ; Хачай, Михаил Юрьевич ; Хачай, Даниил Михайлович. / ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ. в: Труды института математики и механики УрО РАН. 2015 ; Том 21, № 3. стр. 309-317.

BibTeX

@article{b35c9f036dd04d47be2c85cf0564d77c,
title = "ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ",
abstract = "Исследуется задача обхода мегаполисов с фиксированным числом {"}входов{"} и специальным образом заданными отношениями предшествования, являющаяся естественным обобщением классической задачи коммивояжера (TSP). Для поиска оптимального решения задачи приводится схема динамического программирования, эквивалентная методу поиска кратчайшего пути в подходящем бесконтурном ориентированном взвешенном графе. Обосновываются условия, при которых трудоемкость алгоритма полиномиально, в частности, линейно зависит от числа мегаполисов.",
author = "Ченцов, {Александр Георгиевич} and Хачай, {Михаил Юрьевич} and Хачай, {Даниил Михайлович}",
year = "2015",
language = "Русский",
volume = "21",
pages = "309--317",
journal = "Труды института математики и механики УрО РАН",
issn = "0134-4889",
publisher = "Институт математики и механики им. Н.Н. Красовского УрО РАН",
number = "3",

}

RIS

TY - JOUR

T1 - ТОЧНЫЙ АЛГОРИТМ С ЛИНЕЙНОЙ ТРУДОЕМКОСТЬЮ ДЛЯ ОДНОЙ ЗАДАЧИ ОБХОДА МЕГАПОЛИСОВ

AU - Ченцов, Александр Георгиевич

AU - Хачай, Михаил Юрьевич

AU - Хачай, Даниил Михайлович

PY - 2015

Y1 - 2015

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

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

UR - https://elibrary.ru/item.asp?id=24156736

M3 - Статья

VL - 21

SP - 309

EP - 317

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 3

ER -

ID: 1787678