modo efficiente per trovare gradi di separazione tra i due nodi di un grafo

Question

Questa è una domanda intervista che ho recentemente trovato su internet:

Come ti trovare il grado di separazione tra due persone su Facebook? Discutere diverse idee, algoritmi e compromessi. (Definizione del grado di saparation: http://en.wikipedia.org/wiki/Six_degrees_of_separation)

Ecco cosa penso a questo proposito:

Gli algoritmi candidati che mi viene in mente sono: ampiezza di ricerca (BFS), ricerca in profondità (DFS) , ricerca con profondità limitata (DLS), ricerca approfondita iterativa (IDS).

Innanzitutto, DFS deve essere preso in considerazione. È molto probabile che anche quando le due persone sono connesse (vale a dire il grado di separazione = 1), l'algoritmo può continuare a cercare lungo un percorso sbagliato per un lungo periodo di tempo.

BFS è garantito per trovare il grado minimo di separazione (poiché il grafico non è ponderato). Supponiamo che il fattore di ramificazione massimo sia b e che il grado effettivo di separazione tra due persone bersaglio sia d, sia la complessità temporale che la complessità spaziale sarebbero O (b^d).

Poiché il massimo grado possibile di separazione è sconosciuto (sebbene non dovrebbe essere troppo superiore a 6), potrebbe non essere una buona idea utilizzare DLS. Tuttavia, IDS sembra essere un'idea migliore di BFS - la complessità del tempo è anche O (b^d) (anche se il tempo effettivo costa un po 'più alto di BFS a causa della visita ripetuta dei nodi intermedi), mentre la sua complessità spaziale è O (bd), che è molto meglio di O (b^d).

Dopo tutto, sceglierei IDS. È una risposta accettabile in un'intervista? Ho commesso qualche errore nell'inferenza di cui sopra? O ci sono soluzioni migliori che mi sono perso?

Grazie in anticipo.

Answer 1

Una soluzione migliore potrebbe essere quella di avviare un BFS da entrambi i nodi contemporaneamente. Qualcosa come il seguente pseudo-codice:

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

La complessità temporale di questo algoritmo è circa O(m^(d/2)) dove m è il grado massimo di tutti i nodi e d è la distanza massima. Rispetto a un semplice BFS con O(m^d), questo può essere molto più veloce nei grandi grafici.

Answer 2

Se stai cercando per il grado di separazione tra due specifici persone, userei Dijkstra's algorithm, che troverà i percorsi più brevi da una sorgente scelto per tutti i nodi raggiungibili.