RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2017, номер 37, страницы 114–123 (Mi pdm589)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Вычислительные методы в дискретной математике

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

В. В. Быкова, А. А. Солдатенко

Сибирский федеральный университет, г. Красноярск, Россия

Аннотация: Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением задачи о кратчайшем пути в графе. Сеть представляется ориентированным графом $G=(V,E)$, в котором для каждой дуги $(x,y)\in E$ определены две функции: $w_{xy}(t)$ – время, необходимое для передвижения по дуге $(x,y)$, и $F_{xy}(t)$ – время прибытия в вершину $y$ при условии, что старт из вершины $x$ осуществлён в момент времени $t$. Такую сеть называют нестационарной, а наименьшее время передвижения из стартовой вершины в целевую интерпретируют как оптимальный маршрут или кратчайший путь между этими вершинами. В работе задача TDSP исследована для полиномиально разрешимого случая, когда функции прибытия являются монотонными. Двухфазный алгоритм ALT (A$^*$ with Landmarks & Triangle) – один из современных алгоритмов, способных быстро решать задачу TDSP на графах большой размерности. В работе определено и доказано достаточное условие корректности алгоритма ALT для задачи TDSP: сеть должна отвечать неравенству треугольника, заданного для промежутков времени передвижения по узлам сети. Особенность предложенного неравенства треугольника – его определение через “оптимистичные” веса дуг, когда возможно беспрепятственное движение по дугам. Показано, что это неравенство треугольника верно всегда, если веса дуг заданы отношениями длин дуг к скорости передвижения по ним и справедливо неравенство треугольника для расстояний между узлами сети.

Ключевые слова: нестационарные сети, оптимальная маршрутизация, корректность алгоритма ALT.

DOI: https://doi.org/10.17223/20710410/37/10

Полный текст: PDF файл (667 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.7

Образец цитирования: В. В. Быкова, А. А. Солдатенко, “Оптимальная маршрутизация по ориентирам в нестационарных сетях”, ПДМ, 2017, № 37, 114–123

Цитирование в формате AMSBIB
\RBibitem{BykSol17}
\by В.~В.~Быкова, А.~А.~Солдатенко
\paper Оптимальная маршрутизация по ориентирам в~нестационарных сетях
\jour ПДМ
\yr 2017
\issue 37
\pages 114--123
\mathnet{http://mi.mathnet.ru/pdm589}
\crossref{https://doi.org/10.17223/20710410/37/10}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm589
  • http://mi.mathnet.ru/rus/pdm/y2017/i3/p114

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. А. Солдатенко, “Алгоритм оптимальной маршрутизации в мультисервисных телекоммуникационных сетях”, ПДМ. Приложение, 2018, № 11, 122–127  mathnet  crossref
    2. A. Soldatenko, V. Bykova, “Optimal routing in multi-service networks”, 2018 International Scientific Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon), IEEE, 2018  isi
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:102
    Полный текст:43
    Литература:17
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020