Vergleich zweier Graphen
Ich muss viele Graphen vergleichen (bis zu einigen Millionen Graphenvergleichen) und ich frage mich, was der schnellste Weg ist.
Die Scheitelpunkte von Graphen können bis zu 8 Nachbarn / Kanten haben und der Scheitelpunkt kann den Wert 0 oder 1 haben. Der rotierte Graph ist immer noch derselbe Graph und jeder Graph hat die gleiche Anzahl von Scheitelpunkten.
Graph kann so aussehen:
Im Moment vergleiche ich Graphen, indem ich einen Eckpunkt aus dem ersten Graphen nehme und ihn mit jedem Eckpunkt aus dem zweiten Graphen vergleiche. Wenn ich einen identischen Knoten finde, dann überprüfe ich, ob die Nachbarn beider Knoten identisch sind und wiederhole dies, bis ich weiß, ob die Graphen identisch sind oder nicht.
Dieser Ansatz ist zu langsam. Ohne die Graphen zu verwerfen, die sicher anders sind, dauert es mehr als 40 Sekunden, um mehrere tausend Graphen mit ungefähr einhundert Vertices zu vergleichen.
Ich habe darüber nachgedacht, für jeden Graphen einen eindeutigen Wert zu berechnen und dann nur die Werte zu vergleichen. Ich habe versucht, dies zu tun, aber es ist mir nur gelungen, Werte zu finden, die, wenn sie gleich sind, Graphen gleich sein können und wenn die Werte verschieden sind, dann sind die Graphen auch anders Wenn mein Programm diese Werte vergleicht, berechnet es alles in etwa 2,5 Sekunden (was immer noch zu langsam ist).
Und was ist der beste / schnellste Weg, diesem Graph einen Eckpunkt hinzuzufügen und Kanten zu aktualisieren? Momentan speichere ich dieses Diagramm in std::map< COORD, Vertex > , weil ich denke, dass die Suche nach einem Vertex einfacher / schneller ist.
COORD ist die Scheitelpunktposition auf dem Spielbrett (die Positionen der Scheitelpunkte sind beim Vergleich von Graphen irrelevant) und Scheitelpunkt ist:
Und dieser Graph repräsentiert den aktuellen Board-Zustand von Gomoku mit Wrapping an Board-Kanten und Board-Größe n * n, wobei n bis zu 2 ^ 16 sein kann.
Ich hoffe, ich habe beim Schreiben nicht zu viele Fehler gemacht. Ich hoffe, dass mir jemand helfen kann.
4 Antworten
Zuerst müssen Sie jeden Graphen in eine konsistente Darstellung bringen, der natürliche Weg dazu besteht darin, eine geordnete Darstellung des Graphen zu erstellen.
Die erste Ordnungsebene wird durch Gruppierung nach der Anzahl der Nachbarn erreicht.
Jede Gruppe von Knoten mit der gleichen Anzahl von Nachbarn wird dann sortiert, indem ihre Nachbarwerte (die 0 und 1 sind) auf eine Binärzahl abgebildet werden, die dann verwendet wird, um eine Reihenfolge unter den Gruppenknoten durchzusetzen.
Dann können Sie eine Hash-Funktion verwenden, die über jeden Knoten jeder Gruppe in der geordneten Form iteriert. Der Hashwert kann dann verwendet werden, um eine beschleunigte Suche bereitzustellen.
Das Problem, das Sie zu lösen versuchen, heißt graph isomorphism .
Das Problem liegt in NP (obwohl nicht bekannt ist, ob es NP-Complete ist) und es wurde kein Polynomialzeitalgorithmus dafür gefunden.
Der von Ihnen beschriebene Algorithmus scheint eine exponentielle Zeit zu haben.
Ich entschuldige mich, weil ich noch nicht in der Lage bin, mich zu äußern. Dies ist keine exakte Antwort, sondern ein möglicher Optimierungsvorschlag.
Ich würde empfehlen, Memoization zu versuchen (speichern Sie alle Vertex-Paare, die sich als unterschiedlich erweisen), so dass Sie beim nächsten Vergleich dieser beiden Vertices einfach eine einfache Suche und Antwort durchführen. Je nach Art der Grafiken kann dies die Leistung verbessern (oder verschlechtern).
Sie haben selbst herausgefunden, dass man Isomorphie überprüfen kann, indem man ein bord mit allen n * n Verschiebungen mal 8 Umdrehungen des anderen prüft und so O(n^3) complexity hat.
Dies kann auf O(n^2) reduziert werden. Lassen Sie uns nur in eine Richtung wechseln, indem Sie die x -Achse verschieben. Dann müssen wir nur den richtigen y -offset finden. Dazu verketten wir die Elemente für beide Graphen wie folgt:
Wir erhalten zwei Arrays der Größe n und wir müssen prüfen, ob es sich um eine zyklische Permutation des anderen handelt. Dazu verketten wir Array a mit sich selbst und suchen nach dem anderen.
Wenn zum Beispiel die beiden Arrays a=0301202 und b=0203012 sind, suchen wir nach 0203012 in 03012020301202 mit KMP oder ähnlichem, was in O(n + 2n)=O(n) time läuft (wir können die gesamte Vorverarbeitung seither loswerden das erste Array ist immer das gleiche).
Wenn Sie O(n) x-check mit den n y-shifts und 8 rotations kombinieren, erhalten Sie O(n^2) Gesamtkomplexität, indem Sie O(n) zusätzlichen Speicherplatz verwenden.
Tags und Links algorithm c++ data-structures graph