Алгоритмы кратчайшего пути, которые используют пространственно-временной компромисс?

Question

Проблема: поиск кратчайших путей в невзвешенном неориентированном графе.

Поиск в ширину может найти кратчайший путь между двумя узлами, но это может занять до O (| V | + | E |) времени. Предварительно вычисленная таблица поиска позволяет отвечать на запросы в течение O (1) времени, но за счет O (| V | ^ 2) места.

Что мне интересно: Существует ли алгоритм, который предлагает пространственно-временной компромисс , который более детализирован? Другими словами, есть ли алгоритм, который:

1. Находит кратчайшие пути за большее время, чем O (1), но быстрее, чем двунаправленный поиск в ширину
2. Использует предварительно вычисленные данные, которые занимают меньше места, чем O (| V | ^ 2)?

С практической стороны: График состоит из 800 000 узлов и считается сетью малого мира. Таблица кратчайших путей для всех пар была бы порядка гигабайтов - в наши дни это не возмутительно, но не соответствует нашим требованиям.

Однако я задаю свой вопрос из любопытства. Что меня не спит ночью - это , а не «как я могу уменьшить количество кеш-пропусков для таблицы поиска для всех пар?», Но «есть ли совершенно другой алгоритм, о котором я никогда не слышал?

Ответ может быть нет, и это нормально.

Answer 1

Кажется, что ваш входной набор должен быть очень большим, если таблица поиска будет слишком большой для хранения на диске. Я предполагаю, что тогда данные не будут помещаться в ОЗУ, а это означает, что любой алгоритм, который вы используете, должен быть настроен так, чтобы минимизировать количество операций чтения и записи. Всякий раз, когда на дисках задействовано пространство == время, потому что запись на диск очень медленная.

Точный алгоритм, который вы должны использовать, зависит от того, какой у вас график. Эта исследовательская работа может быть вам интересна. Полное раскрытие: я сам не читал, но, похоже, это то, что вы ищете.

Edit:

Если граф (почти) соединен, то есть с сетью маленького мира, справочная таблица не может быть меньше V ^ 2. Это означает, что для всех поисков потребуется доступ к диску. Если края помещаются в основную память, возможно, каждый раз будет проще вычислять путь. В противном случае вы можете вычислить путь из таблицы, содержащей длины всех кратчайших путей. Вы можете восстановить путь из этой таблицы.

Ключ должен убедиться, что записи в таблице, которые расположены близко друг к другу в обоих направлениях, также расположены близко друг к другу на диске. Этот шаблон хранения выполняет:

1 2    1   2  5  6
3 4    3   4  7  8
       9  10 13 14
       11 12 15 16

Он также будет хорошо работать с иерархией кеша.

Для вычисления таблицы вы можете использовать модифицированный Floyd-Warshall , где вы обрабатываете данные в блоках. Это позволит вам выполнить вычисления за разумное время, особенно если вы распараллелите его.

Answer 2

Вы должны начать с поиска алгоритма Дейкстры для поиска кратчайшего пути. Алгоритм a * - это вариант, в котором используется эвристика для сокращения времени, необходимого для расчета оптимального маршрута между начальным и целевым узлами (например, евклидово расстояние). Вы можете изменить эту эвристику для производительности или точности.