Как бы вы изменили BFS, чтобы найти кратчайший путь от A до B, учитывая, что график очень большой?

Question

Что я имею в виду под "очень большим графом", так это то, что каждая вершина имеет 1000 смежных вершин, но если вы посмотрите на окончательное решение, расстояние от А до В составило всего 6 (скажем).

Вв такой ситуации использование базового алгоритма BFS было бы расточительным, поскольку он помещает все 1000 смежных вершин А, а затем в следующем раунде 1000 для каждой из них и т. д. к тому времени, когда я достигну BI, я бы рассмотрел 1000 ^ 6 вершин..

Есть идеи как оптимизировать?Или скорее есть способ?

Answer 1

Одна простая вещь, которую нужно сделать, это работать в обоих направлениях:

На каждом шаге сделать это:

• получить новых соседей nbrsA, ищущих B, если не найден установленnbrsA = новые соседи
• получить новых соседей nbrsB в поисках A, если не найдено, установить nbrsB = новых соседей
• сравнить nbrsA и nbrsB

Если графикбольшой, но с высокой степенью связи, тогда вы сэкономите немало места таким образом, но для сравнения наборов соседей потребуется дополнительное время.

Answer 2

Согласен,

это интересная проблема.Насколько я понимаю, вам могут помочь две вещи:

1. Поиск вперед и назад одновременно.Если бы у вас действительно была минимальная степень 1000, то вам нужно было бы исследовать 1000 ^ d узлов в d-й итерации BFS.Это эффективно уменьшает 1000 ^ (2d) до 2 * 1000 ^ d.

2. В некоторый момент BFS будет слишком дорогим с точки зрения потребления памяти.Чтобы избежать этого, вы можете переключиться на «итеративное углубление»: эмулируйте BFS, выполнив сначала поиск по глубине (ограниченный 1 итерацией), а затем DFS (ограниченный 2 итерациями) и т. Д. Служебные расходы - это небольшая константа (которая, конечнонежелательно), но таким образом вы можете избежать проблем с памятью, обнаруживая узлы в том же порядке, что и BFS.

Answer 3

Вы можете изменить BFS, чтобы использовать алгоритм Dijkstras. BFS и Dijkstras связаны определенным образом, и поэтому эта модификация должна быть приемлемой. И поскольку это был экран телефона, есть много шансов, что они захотят, чтобы вы увидели там отношения.

Answer 4

Верно одно из двух:

Эти 1000 вершин часто используются совместно. Это означает, что как только они будут найдены в первом раунде, они будут игнорироваться во втором раунде, что значительно снизит поле поиска,

OR

Эти 1000 вершин уникальны. Это означает, что у вас есть миллионы или миллиарды узлов, что означает, что вы все еще в ожидаемом масштабе алгоритма.

В любом случае, мало что с этим поделать.