Erkennen, wenn ein Graph in zwei oder mehr verbundene Komponenten aufgeteilt wurde
Ich habe ein Informatikproblem, über das ich in letzter Zeit viel nachgedacht habe, und ich würde mich dafür interessieren, das Feedback anderer zu hören:
Nehmen wir an, Sie haben eine 3D-Blockwelt (wie bei Minecraft). Die Welt ist "stabil", wenn für jeden Block ein solider Pfad von diesem Block zur untersten Reihe von Blöcken existiert. Wenn die Welt erzeugt wird, ist es garantiert stabil, aber wenn Spieler herumgehen und die Blöcke ausgraben, könnten sie die Welt instabil machen. Zum Beispiel könnte der Spieler den Stamm eines Baumes ausgraben, in diesem Fall würde die Spitze des Baumes in der Luft schweben, und somit ist die Welt instabil.
Ziel ist es, schnell herauszufinden, ob die Welt infolge einer Grabung instabil wird und welche Würfel entfernt werden sollten, um die Welt in einen stabilen Zustand zu versetzen. Der Algorithmus sollte schnell sein und im Kontext einer Welt funktionieren, in der viele Ausgrabungen stattfinden, von denen die meisten die Welt nicht instabil machen.
Eine naive Annäherung wäre, jeden benachbarten Würfel nach einer Grabung zu nehmen und einen Weg zum Grund der Erde zu finden. Wenn Sie von keinem der Nachbarn einen Pfad nach unten finden können, ist die Welt jetzt instabil (und Sie erfahren auch, welche Cubes als Teil des Prozesses entfernt werden sollen). Dies fällt auseinander, wenn der Weg zum Grund sehr lang ist. Es ist ziemlich einfach, ein Beispiel zu finden, wo dies rechenintensiv wird (Stellen Sie sich vor, Sie entfernen die Spitze eines großen, gewundenen Turms).
Dieses Problem kann man sich als ein Graphproblem vorstellen, bei dem man schnell erkennen will, ob ein einzelner Scheitelpunkt den Graphen in zwei oder mehr Komponenten aufteilen kann.
Ich bin interessiert zu hören, ob jemand andere Ideen hat, wie man dieses Problem lenkbar machen kann.
4 Antworten
Link / Schnitt-Struktur kann Ihnen helfen. Daniel Sleator , einer der Autoren dieser Struktur teilte seine Lösung dem ähnlichen Problem mit. Schauen Sie sich Kommentare zu codeforces.ru an, die Sie möglicherweise nützlich finden.
Ich würde hier meine Idee schreiben. Lassen Sie uns einen Eckpunkt unter der unteren Ebene erstellen. Dieser Eckpunkt ist der Keller Ihres Gebäudes. Verbinde basement_vertex mit allen Scheitelpunkten auf der untersten Ebene. Ausführen der Tiefensuche (DFS) vom Kellerscheitelpunkt aus. Dieser dfs erzeugt einen verwurzelten Baum. Dieser Baum sollte die Basis (Anfangsphase) eines Link-Cut-Baums sein.
AKTUALISIEREN
Link-Cut Trees funktioniert nur, wenn das gegebene Diagramm ein Baum ist. Für jedes Diagramm müssen wir das dynamische Verbindungsproblem lösen. Hier weitere Informationen zum Problem der dynamischen Verbindung.
Sie können den so genannten Flood-fill -Algorithmus in Betracht ziehen, um Knoten zu markieren und festzustellen, ob die Mitgliedschaften identisch sind .
Hier ist eine einfache Grafik. Wir haben den ursprünglichen Graphen G, und dann entfernen wir jeweils einen Würfel, um die Graphen H und I zu erhalten.
Das Paket igraph eignet sich hervorragend zum Testen der Verbindung von Graphen. In dem obigen Testbeispiel sind G und H in Ordnung, aber das Entfernen der Kante (3,5) bewirkt, dass die Zugehörigkeit zu 5, 6,7 sich von der des Knotens 1, des "Erdknotens", unterscheidet. (Im dritten Diagramm, Diagramm I, sollten Sie die Würfel 5, 6 und 7 entfernen.)
Verwenden Sie in der R-Sprache die Bibliothek "igraph"
%Vor% clusters ist eine Funktion, die mit dem igraph-Paket geliefert wird. Und sein Wert membership zeigt die Beschriftungen jedes Knotens im Graphen an. Wenn ein Knoten (Würfel in Ihrem Fall) einen anderen Mitgliedschaftswert als der "Erdknoten" hat, dann ist er nicht mit dem Boden verbunden und sollte entfernt werden.
Ich würde in Erwägung ziehen, zu speichern, wenn jeder Block "unstable-if-dug" ist, auch bekannt als cut-vertex oder biconnected component . Dann können Sie es in konstanter Zeit nachsehen, wenn Sie darauf klicken.
Grundsätzlich besteht die Idee darin, sofort wissen zu können, ob es stabil ist. Dann berechnen Sie den Graph neu, während Sie auf Ihre nächste Benutzereingabe warten. Die Benutzererfahrung ist flüssiger, und wenn jemand nicht schnell auf sehr klickt, sollten sie niemals eine Verlangsamung bemerken.
Sie können die all Schnittpunkte eines Graphen in O (n) -Zeit mit einem DFS finden.
Aus der Wikipedia auf biconnected components :
Die Idee ist, eine Tiefensuche durchzuführen, während die folgenden Informationen beibehalten werden:
- die Tiefe jedes Eckpunkts in der Tiefe-zuerst-Suche-Struktur (sobald sie besucht wird)
- für jeden Vertex v, die niedrigste Tiefe der Nachbarn aller Nachkommen von v im Depth-First-Search-Baum, Lowpoint genannt.
Der Tiefpunkt von v kann nach dem Besuch aller Nachkommen von v ... als Minimum von:
berechnet werden
- die Tiefe von v
- die Tiefe aller Nachbarn von v (neben dem Elternteil von v im Tiefensuchbaum)
- Der Tiefpunkt aller untergeordneten Elemente von v in der Tiefensuche.
Die wichtigste Tatsache ist, dass ein Nicht-Null-Vertex v ein Schnittpunkt (oder Artikulationspunkt) ist, der genau dann zwei bikonnezierte Komponenten trennt, wenn ein untergeordnetes
yvon vorhanden istvso dasslowpoint(y) ≥ depth(v).Der Wurzelknoten muss separat behandelt werden: Er ist ein Schnittpunkt, wenn und nur wenn er mindestens zwei Kinder hat.
Eine einfache Lösung ist die Verwendung von BFS (Breitensuche), um zu prüfen, ob alle unmittelbaren Nachbarn des entfernten Knotens (Minecraft-Block) zur selben verbundenen Komponente gehören.
Der erste Nachbar wird beschriftet und dann werden alle anderen überprüft, ob sie sich mit einem markierten Knoten verbinden.
Hier ist mein getesteter Code (C #):
%Vor%Das 'nodeNeighbors' Wörterbuch enthält Nachbarindizes für jeden Knoten.
Im schlimmsten Fall müssen wir so viele BFS-Iterationen ausführen wie die Länge des längsten Pfads zwischen zwei benachbarten Knoten.
Eine schnellere Methode besteht darin, jeden unmittelbaren Nachbarn mit einer eindeutigen numerischen Bezeichnung zu versehen und dann die Kennzeichnung Verbundener Komponenten durchzuführen. Wir können eine parallele BFS-Suche für jedes Label ausführen und jedes Mal beenden, wenn zwei Labels übereinstimmen und wir Union-Operationen für die zugrundeliegende Union-Find-Struktur ausführen.
Die gesamte Suche kann beendet werden, wenn so viele Union-Operationen ausgeführt werden, wie es anfängliche Labels minus eins gibt, d. h. alle Labels gehören zu derselben Komponente.
Eine weitere Verbesserung der Geschwindigkeit wäre es, mehrere "Samen" zu erzeugen, die gleichmäßig um den Entfernungspunkt verteilt sind. Jeder Seed ist ein Knoten mit einer eindeutigen Bezeichnung. Dies garantiert, dass die Komponenten schneller miteinander verbunden werden.
Sie können die Suche auch nach einer bestimmten Anzahl von Wiederholungen (z. B. 10 000) beenden, da dies bedeutet, dass die Würfel in einer sehr großen Entfernung verbunden sind und der Spieler nicht einmal eine Trennung findet.
Die Suche kann nach diesem Punkt auch im Hintergrund ausgeführt werden.
Tags und Links algorithm graph-theory