Оптимальная маршрутизация по ориентирам в нестационарных сетях

doi:10.17223/20710410/37/10

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Оптимальная маршрутизация по ориентирам в нестационарных сетях	639 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/37/10

#нестационарные сети

#оптимальная маршрутизация

#ALT, двухэтапный алгоритм

Title: Оптимальная маршрутизация по ориентирам в нестационарных сетях
Title: Optimal routing by landmarks in the time-dependent networks
Creator: Быкова, Валентина Владимировна
|
Солдатенко, Александр Александрович
Date: 2017
DOI: 10.17223/20710410/37/10
Description: Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Сеть представляется ориентированным графом G = (V, E), в котором для каждой дуги (x, у) £ E определены две функции: wxy (t) — время, необходимое для передвижения по дуге (x, у), и Fxy (t) — время прибытия в вершину у при условии, что старт из вершины x осуществлён в момент времени t. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут или кратчайший путь между этими вершинами. В работе задача TDSP исследована для полиномиально разрешимого случая, когда функции прибытия являются монотонными. Двухфазный алгоритм ALT (A* with Landmarks & Triangle) —один из современных алгоритмов, способных быстро решать задачу TDSP на графах большой размерности. В работе определено и доказано достаточное условие корректности алгоритма ALT для задачи TDSP: сеть должна отвечать неравенству треугольника, заданного для промежутков времени передвижения по узлам сети. Особенность предложенного неравенства треугольника — его определение через «оптимистичные» веса дуг, когда возможно беспрепятственное движение по дугам. Показано, что это неравенство треугольника верно всегда, если веса дуг заданы отношениями длин дуг к скорости передвижения по ним и справедливо неравенство треугольника для расстояний между узлами сети.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2017. № 37. С. 114-123
Language: rus

Created: 22-09-2017

890 Visitors

698 Hits

207 Downloads

Журналы ТГУ Оптимальная маршрутизация по ориентирам в нестационарных сетях