effiziente Art und Weise Grad der Trennung zwischen zwei Knoten in einem Graphen zu finden

Question

Dies ist ein Interview Frage, die ich vor kurzem im Internet gefunden:

Wie würden Sie den Grad der Trennung zwischen zwei Personen auf Facebook finden? Diskutieren Sie verschiedene Ideen, Algorithmen und Kompromisse. (Definition des Grades der saparation: http://en.wikipedia.org/wiki/Six_degrees_of_separation)

Hier ist, was ich darüber nachdenke:

Die Kandidaten Algorithmen, die ich denken kann, sind: Breitensuche (BFS), Tiefensuche (DFS) Tiefenlimitierte Suche (DLS), iterative Tiefensuche (IDS).

Zuerst sollte DFS berücksichtigt werden. Es ist sehr wahrscheinlich, dass selbst dann, wenn die zwei Personen verbunden sind (d. H. Der Grad der Trennung = 1), der Algorithmus für eine lange Zeit auf einem falschen Weg weiter suchen kann.

BFS garantiert garantiert den Mindestgrad der Trennung (da der Graph nicht gewichtet ist). Angenommen, der maximale Verzweigungsfaktor ist b und der tatsächliche Grad der Trennung zwischen zwei Zielpersonen ist d, sowohl die Zeitkomplexität als auch die Raumkomplexität wären O (b^d).

Da der maximal mögliche Trennungsgrad unbekannt ist (obwohl er nicht zu hoch als 6 sein sollte), ist es möglicherweise keine gute Idee, DLS zu verwenden. IDS scheint jedoch eine bessere Idee als BFS zu sein - es ist Zeit, dass Komplexität auch O (b^d) ist (obwohl die tatsächliche Zeit ein bisschen höher ist als BFS aufgrund wiederholter Besuche von Zwischenknoten), während ihre Platzkomplexität O ist (bd), was viel besser ist als O (b^d).

Schließlich würde ich IDS wählen. Ist das eine akzeptable Antwort in einem Interview? Habe ich irgendeinen Fehler in der obigen Schlussfolgerung gemacht? Oder gibt es bessere Lösungen, die ich vermisst habe?

Vielen Dank im Voraus.

Answer 1

Eine bessere Lösung könnte sein, ein BFS von beiden Knoten gleichzeitig zu starten. So etwas wie die folgenden Pseudo-Code:

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

Die Zeitkomplexität dieses Algorithmus ist etwa O(m^(d/2)) wo m der maximale Grad aller Knoten und d ist die maximale Entfernung. Im Vergleich zu einem einfachen BFS mit O(m^d) kann dies in großen Diagrammen viel schneller sein.

Answer 2

Wenn Sie nach dem Grad der Trennung zwischen zwei spezifischen Menschen suchen, würde ich Dijkstra's algorithm verwenden, die die kürzesten Wege von einer gewählten Quelle zu allen erreichbaren Knoten finden wird.