Все или ничего - быстрый эвристический алгоритм кратчайшего пути (параллельный?)

Question

Я ищу хороший способ найти кратчайший путь между двумя точками в сети (направленной, циклической, взвешенной) из миллиардов узлов.По сути, мне нужен алгоритм, который обычно очень быстро находит решение, даже если его худший случай ужасен.

Я открыт для параллельных или распределенных алгоритмов, хотя он должен иметь смысл с размеромнабор данных (алгоритм, который будет работать с CUDA на видеокарте, должен обрабатываться кусками).Я не планирую использовать ферму компьютеров для этого, но потенциально несколько макс.

Answer 1

Поиск в Google дает вам много хороших ссылок .Первая ссылка сама говорит о параллельных реализациях двух алгоритмов кратчайшего пути.

И, говоря о реализации на CUDA, вы должны помнить, что миллиарды узлов = гигабайты памяти.Это обеспечило бы ограничение на количество узлов, которые вы можете использовать для каждой карты (для оптимальной производительности) одновременно.Максимальная емкость видеокарты , представленной на рынке, составляет около 6 ГБ.Это может дать вам оценку количества карт, которые вам могут понадобиться (не обязательно количество машин).

Answer 2

Вы можете использовать поиск по единой стоимости.Этот алгоритм поиска найдет оптимальное решение во взвешенном графе.Если я правильно помню, сложность поиска (пространство и время) равна b ^ (C * / e + 1), где b обозначает ветвление, C * - оптимальная стоимость пути к вашей цели, а e - средняя стоимость пути.

И есть еще то, что называется двунаправленным поиском, когда вы начинаете с поиска с начального состояния и состояния цели, и, надеюсь, обе исходные точки пересекаются где-то посередине графика:)

Answer 3

Посмотрите на алгоритм Дикстры. Как правило, он выполняет оптимизированный поиск в несколько глубин до тех пор, пока не будет гарантированно найден кратчайший путь. Первый найденный путь может быть самым коротким, но вы не можете быть уверены, что другие ветви поиска не закончатся на более коротком расстоянии.

Answer 4

Я обеспокоен тем, что, если ваш график каким-то образом не раскладывается в памяти, вы не получите большой выгоды от использования CUDA по сравнению с хорошо настроенным параллельным алгоритмом на процессоре. Проблема в том, что хождение по «совершенно неупорядоченным» графикам приводит к множеству случайных обращений к памяти.

Когда у вас есть 32 CUDA-потока, работающих вместе параллельно, но их доступ к памяти является случайным, инструкция выборки должна быть сериализована. Поскольку алгоритм поиска не выполняет много сложных математических вычислений, выбор памяти - это то место, где вы, вероятно, потеряете большую часть своего времени.