Показать сокращенную информацию
Оптимальная маршрутизация по ориентирам в нестационарных сетях
Автор | Быкова, Валентина Владимировна | |
Автор | Солдатенко, Александр Александрович | |
Дата внесения | 2019-07-01T07:27:36Z | |
Дата, когда ресурс стал доступен | 2019-07-01T07:27:36Z | |
Дата публикации | 2017-10 | |
Библиографическое описание | Быкова, Валентина Владимировна. Оптимальная маршрутизация по ориентирам в нестационарных сетях [Текст] / Валентина Владимировна Быкова, Александр Александрович Солдатенко // Prikladnaya Diskretnaya Matematika. — 2017. — № 37. — С. 114-123 | |
ISSN | 20710410 | |
URI (для ссылок/цитирований) | http://vestnik.tsu.ru/pdm | |
URI (для ссылок/цитирований) | https://elib.sfu-kras.ru/handle/2311/110990 | |
Описание | Текст статьи не публикуется в открытом доступе в соответствии с политикой журнала. | |
Аннотация | Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Сеть представляется ориентированным графом G=(V,E), в котором для каждой дуги (x,y) ∈ E определены две функции: wxy(t) – время, необходимое для передвижения по дуге (x,y), и Fxy(t) – время прибытия в вершину y при условии, что старт из вершины x осуществлён в момент времени t. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут или кратчайший путь между этими вершинами. В работе задача TDSP исследована для полиномиально разрешимого случая, когда функции прибытия являются монотонными.Двухфазный алгоритм ALT (A∗∗ with Landmarks & Triangle) – один из современных алгоритмов, способных быстро решать задачу TDSP на графах большой размерности. В работе определено и доказано достаточное условие корректности алгоритма ALT для задачи TDSP: сеть должна отвечать неравенству треугольника, заданного для промежутков времени передвижения по узлам сети. Особенность предложенного неравенства треугольника – его определение через “оптимистичные” веса дуг, когда возможно беспрепятственное движение по дугам. Показано, что это неравенство треугольника верно всегда, если веса дуг заданы отношениями длин дуг к скорости передвижения по ним и справедливо неравенство треугольника для расстояний между узлами сети. | |
Тема | нестационарные сети | |
Тема | оптимальная маршрутизация | |
Тема | корректность алгоритма ALT | |
Название | Оптимальная маршрутизация по ориентирам в нестационарных сетях | |
Тип | Journal Article | |
Тип | Journal Article Preprint | |
Страницы | 114-123 | |
ГРНТИ | 27.45 | |
Дата обновления | 2019-07-01T07:27:36Z | |
DOI | 10.17223/20710410/37/10 | |
Институт | Институт математики и фундаментальной информатики | |
Подразделение | Кафедра высшей математики № 1 | |
Журнал | Prikladnaya Diskretnaya Matematika | |
Квартиль журнала в Scopus | Q3 | |
Квартиль журнала в Web of Science | без квартиля |