Эффективный способ найти степень разделения между двумя узлами в графе

Question

Этого интервью вопрос, который я недавно нашел в Интернете:

Как бы вы найти степень разделения между двумя людьми на Facebook? Обсудите различные идеи, алгоритмы и компромиссы. (Определение степени saparation: http://en.wikipedia.org/wiki/Six_degrees_of_separation)

Вот что я думаю об этом:

Алгоритмы кандидатов, что я могу думать, являются: поиск в ширину (BFS), поиск в глубину (DFS) , поиск по глубине (DLS), поиск с итерационным углублением (IDS).

Во-первых, DFS следует принимать во внимание. Очень вероятно, что даже когда эти два человека связаны (то есть степень разделения = 1), алгоритм может продолжать поиск по неправильному пути в течение длительного времени.

BFS гарантирует минимальную степень разделения (так как график не взвешен). Предположим, что максимальный коэффициент ветвления равен b, а фактическая степень разделения между двумя целевыми людьми равна d, как временная сложность, так и сложность пространства - O (b^d).

Поскольку максимальная возможная степень разделения неизвестна (хотя она не должна превышать 6), возможно, не рекомендуется использовать DLS. Однако IDS, по-видимому, является лучшей идеей, чем BFS - сложность времени также O (b^d) (хотя фактическое время стоит немного выше, чем BFS из-за повторного посещения промежуточных узлов), тогда как его пространственная сложность равна O (bd), что намного лучше, чем O (b^d).

В конце концов, я бы выбрал IDS. Это приемлемый ответ в интервью? Неужели я ошибся в вышеупомянутом выводе? Или есть какие-то лучшие решения, которые я пропустил?

Заранее спасибо.

Answer 1

Лучшим решением может быть запуск BFS с обоих узлов одновременно. Нечто подобное следующему псевдокода:

nodes1 = (A); 
nodes2 = (B); 
d = 1; 
loop { 
    nodes1 = neighbors(nodes1); 
    if (intersects(nodes1, nodes2)) { 
     return d; 
    } 
    d += 1; 
    nodes2 = neighbors(nodes2); 
    if (intersects(nodes2, nodes1)) { 
     return d; 
    } 
    d += 1; 
} 

Временная сложность этого алгоритма составляет около O(m^(d/2)), где m это максимальная степень всех узлов и d это максимальное расстояние. По сравнению с простой BFS с O(m^d), это может быть намного быстрее на больших графиках.

Answer 2

Если вы ищете степень разделения между двумя конкретными людьми, я бы использовал Dijkstra's algorithm, который будет найти кратчайшие пути из выбранного источника всех достижимых узлов.