Skuteczny sposób na znalezienie stopnie separacji między dwoma węzłami na wykresie

Question

To pytanie wywiad, który Niedawno znalazłem w internecie:

Jak znaleźć stopnia oddzielenia pomiędzy dwie osoby na Facebooku? Omów różne pomysły, algorytmy i kompromisy. (Definicja stopnia saparation: http://en.wikipedia.org/wiki/Six_degrees_of_separation)

Oto, co o tym myślę:

algorytmach kandydujących że mogę myśleć to: szerokość-first search (BFS), przeszukiwanie w głąb (DFS) , wyszukiwanie z ograniczeniem głębokości (DLS), wyszukiwanie iteracyjno-pogłębiające (IDS).

Najpierw należy wziąć pod uwagę DFS. Jest bardzo prawdopodobne, że nawet gdy dwie osoby są połączone (tj. Stopień separacji = 1), algorytm może dalej poszukiwać wzdłuż złej ścieżki przez długi czas.

BFS ma zagwarantowany minimalny stopień separacji (ponieważ wykres nie jest ważony). Przyjmijmy, że maksymalny współczynnik rozgałęzienia wynosi b, a rzeczywisty stopień separacji między dwiema osobami docelowymi to d, złożoność czasu i złożoność przestrzeni to O (b^d).

Ponieważ maksymalny stopień separacji nie jest znany (chociaż nie powinien być większy niż 6), może nie być dobrym pomysłem użycie DLS. Jednak IDS wydaje się lepszym pomysłem niż BFS - jego złożoność czasowa to także O (b^d) (chociaż faktyczny koszt czasu jest nieco wyższy niż BFS z powodu wielokrotnego odwiedzania węzłów pośrednich), zaś złożoność przestrzeni jest O (bd), który jest o wiele lepszy niż O (b^d).

W końcu wybrałbym IDS. Czy jest to akceptowalna odpowiedź w wywiadzie? Czy popełniłem jakiś błąd w powyższym wniosku? Czy są jakieś lepsze rozwiązania, które przeoczyłem?

Z góry dziękuję.

Answer 1

Lepszym rozwiązaniem może być jednoczesne uruchomienie BFS z obu węzłów. Coś jak na poniższym pseudo-kod:

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; 
} 

Złożoność czasowa tego algorytmu jest o O(m^(d/2)) gdzie m jest maksymalny poziom wszystkich węzłach i d jest maksymalna odległość. W porównaniu z prostym BFS z O(m^d), może to być dużo szybsze na dużych wykresach.

Answer 2

Jeśli szukasz stopnia oddzielenia pomiędzy dwoma konkretnych ludzi, użyję Dijkstra's algorithm, który znajdzie najkrótsze ścieżki z wybranego źródła do wszystkich osiągalnych węzłów.