|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
МАТЕМАТИКА
Маршрутизация перемещений при динамических ограничениях: задача “на узкие места”
А. Г. Ченцовab, А. А. Ченцовa a Институт математики и механики им. Н. Н. Красовского УрО РАН, 620990, Россия, г. Екатеринбург, ул. С. Ковалевской, 16
b Уральский федеральный университет, 620002, Россия, г. Екатеринбург, ул. Мира, 19
Аннотация:
Рассматривается усложненный вариант задачи маршрутизации “на узкие места”, а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также “текущие” ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм “полного” решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана.
Ключевые слова:
маршрут, трасса, условия предшествования, динамическое программирование.
Поступила в редакцию: 27.02.2016
Образец цитирования:
А. Г. Ченцов, А. А. Ченцов, “Маршрутизация перемещений при динамических ограничениях: задача “на узкие места””, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 26:1 (2016), 121–140
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vuu523 https://www.mathnet.ru/rus/vuu/v26/i1/p121
|
Статистика просмотров: |
Страница аннотации: | 383 | PDF полного текста: | 115 | Список литературы: | 78 |
|