Ярлыки концентратора
В информатике метки узлов или алгоритм маркировки узлов — это метод ускорения , который потребляет гораздо меньше ресурсов, чем таблица поиска, но при этом чрезвычайно быстр для поиска кратчайших путей между узлами в графе , который может представлять, например, дорожные сети. . [1]
Этот метод позволяет максимум с помощью двух операторов SELECT и анализа двух строк вычислить кратчайший путь между двумя вершинами графа.Для графа, ориентированного как граф дорог, этот метод требует предварительного вычисления двух таблиц из структур, построенных с использованием метода сжимающих иерархий . В конце концов, эти две вычисленные таблицы будут иметь столько строк, сколько узлов присутствует в графе. Для каждой строки (каждого узла) будет рассчитываться метка.
Метка — это строка, содержащая информацию о расстоянии между текущим узлом (узлом строки) и всеми остальными узлами, до которых можно добраться при поиске по возрастанию в относительной многоуровневой структуре. Преимущество этих расстояний в том, что все они представляют собой кратчайшие пути.
Таким образом, для будущих запросов поиск кратчайшего пути начнется с источника в первой таблице и пункта назначения во второй таблице, откуда он будет искать в метках общие узлы с соответствующей информацией о расстоянии. Только наименьшая сумма расстояний будет сохранена как результат кратчайшего пути.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Иттай Абрахам, Дэниел Деллинг, Эндрю В. Голдберг, Ренато Ф. Вернек, «Алгоритм маркировки на основе узлов для кратчайших путей в дорожных сетях» , Microsoft Research Silicon Valley, 1065 La Avenida, Mountain View, CA 94043, США, 2010 .