4551
правка
Разработка алгоритмов для применения в больших сетях: различия между версиями
Перейти к навигации
Перейти к поиску
Разработка алгоритмов для применения в больших сетях (посмотреть исходный код)
Версия от 13:02, 15 января 2019
, 15 января 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
'''Второй подход (дополнительный граф)''' | '''Второй подход (дополнительный граф)''' | ||
Первая работа в рамках этого подхода [10] представляет новую технику иерархической декомпозиции, получившую название многоуровневого графа. Многоуровневый граф M представляет собой орграф, определяемый последовательностью подмножеств V, множество E которого расширено посредством дополнения несколькими уровнями ребер. Это позволяет в ходе ответа на запрос эффективно строить подграф M, значительно меньшего размера по сравнению с G, в котором расстояние по кратчайшему пути между любыми двумя вершинами равно расстоянию по кратчайшему пути между теми же вершинами в графе G. Дальнейшие улучшения этого подхода были недавно предложены в работе [1]. Дальнейшим развитием первоначальной идеи стало введение многоуровневых графов с наложениями [5]. В таком графе иерархия декомпозиции не определяется информацией, относящейся к конкретной области применения, как это было в случае [9, 10]. | |||
Альтернативная техника иерархической декомпозиции под названием иерархии магистралей была предложена в [7]. Этот подход использует свойство изначально присущих системе иерархий, которым обладают дорожные сети материального мира, и вычисляет иерархию более крупноблочных представлений входного графа. Затем алгоритм поиска кратчайших путей рассматривает главным образом именно эти крупноблочные представления, размер которых намного меньше, что способствует значительному сокращению времени выполнения запроса. Пересмотр и улучшение этого метода были произведены в работе [8]. Мощное сочетание иерархии магистралей с идеями из статьи [3] было рассмотрено в [2]. | |||
'''Вопросы моделирования''' | |||
Моделирование исходной задачи поиска наилучшего пути (или оптимального маршрута) на большой сети при помощи задачи о кратчайшем пути в подходящим образом определенном подграфе с соответствующими стоимостями ребер также играет важную роль в сокращении времени выполнения запросов. Вопросы моделирования были досконально исследованы в работе [6]. В этой статье было проведено первое экспериментальное сравнение двух значимых подходов (растянутого по времени и зависящего от времени), а также предложены новые расширения подходов с целью реалистичности моделирования. Кроме того, было предложено несколько новых эвристик для ускорения выполнения запросов. | |||
== Применение == | |||