Überprüfen Sie, ob einige Elemente in einer Matrix zusammenhängend sind
Ich muss ein sehr kleines Python-Programm schreiben, das überprüft, ob eine Gruppe von Koordinaten alle miteinander verbunden sind (durch eine Linie, nicht diagonal). Die nächsten 2 Bilder zeigen was ich meine. Im linken Bild sind alle farbigen Gruppen zusammenhängend, im rechten Bild nicht:
Ich habe dieses Stück Code schon gemacht, aber es scheint nicht zu funktionieren und ich bin ziemlich festgefahren, irgendwelche Ideen, wie ich das beheben kann?
%Vor% Dies ist ein Referenzmaterial, das True zurückgeben soll:
und dies sollte False :
Beide Tests funktionieren, aber wenn ich versuche, sie mit verschiedenen Zahlen zu testen, scheitern die Funktionen.
4 Antworten
Um zu prüfen, ob etwas verbunden ist, müssen Sie normalerweise disjunkte Set-Datenstrukturen verwenden. Zu den effizienteren Varianten gehören die gewichtete schnelle Vereinigung, die gewichtete schnelle Vereinigung mit Pfadkomprimierung.
Hier ist eine Implementierung Ссылка , die Sie an Ihre Bedürfnisse anpassen können. Auch die Implementierung, die in dem Buch "Design und Analyse von Computeralgorithmen" von A. Aho gefunden wurde, ermöglicht es Ihnen, den Namen der Gruppe anzugeben, der Sie zwei verbundene Elemente hinzufügen. Ich denke, das ist die Modifikation, nach der Sie suchen (Es beinhaltet nur 1 zusätzliches Array, das die Gruppennummern verfolgt).
Als Nebenbemerkung, da disjunkte Sätze normalerweise für Arrays gelten, sollten Sie nicht vergessen, dass Sie eine N-mal-N-Matrix als ein Array der Größe N * N darstellen können.
EDIT: habe gerade gemerkt, dass mir nicht klar war, was du zuerst gefragt hast, und ich habe bemerkt, dass du auch erwähnt hast, dass diagonale Komponenten nicht verbunden sind, in diesem Fall ist der Algorithmus wie folgt:
0) Überprüfen Sie, ob alle Elemente auf dieselbe Gruppe verweisen.
1) Iteriere durch das Array von Paaren, die Koordinaten in der fraglichen Matrix darstellen.
2) Machen Sie für jedes Paar eine Menge von Paaren, die die folgende Formel erfüllen:
%Vor%'entry' bezieht sich auf das Element, auf das sich die äußere for-Schleife bezieht.
3) Überprüfen Sie, ob sich alle Sätze überschneiden. Das kann man tun, indem man die Mengen, die man betrachtet, "vereinigt", am Ende, wenn man mehr als 1 Menge erhält, dann sind die Elemente nicht zusammenhängend.
Die Komplexität ist O (n ^ 2 + n ^ 2 * log (n)).
Beispiel:
(0,4), (1,2), (1,4), (2,2), (2,3)
0) überprüfen Sie, dass alle in derselben Gruppe sind:
alle gehören zur Gruppe 5.
1) mach Sätze:
set1: (0,4), (1,4)
set2: (1,2), (2,2)
set3: (0,4), (1,4) // Hier nehmen wir an, dass die Mengen sortiert sind, anders als das sollte (1,4), (0,4)
seinset4: (1,2), (2,2), (2,3)
set5: (2,2), (2,3)
2) Überlappung prüfen:
set1 überschneidet sich mit set3, so erhalten wir:
set1 ': (0,4), (1,4)
set2 überschneidet sich mit set4 und set 5, also erhalten wir:
satz2 ': (1,2), (2,2), (2,3)
Wie Sie sehen können, überlagern sich set1 'und set2' nicht, daher erhalten Sie zwei disjunkte Mengen, die sich in derselben Gruppe befinden. Die Antwort ist also 'false'.
Beachten Sie, dass dies ineffizient ist, aber ich habe keine Ahnung, wie man es effizienter macht, aber das beantwortet Ihre Frage.
Die Logik in Ihrer verbundenen Funktion scheint falsch zu sein. Sie erstellen eine Todo-Variable, ändern aber niemals ihren Inhalt. Du suchst immer nach Nachbarn um den gleichen Startpunkt.
Versuchen Sie stattdessen diesen Code:
%Vor% todo ist eine Menge aller Punkte, die wir noch überprüfen müssen.
done ist eine Menge aller Punkte, von denen wir herausgefunden haben, dass sie mit dem Startpunkt 4-verbunden sind.
Ich würde dieses Problem anders angehen ... wenn Sie fünf genau suchen, heißt das:
- Jede Koordinate in der Linie muss benachbart zu einer anderen Koordinate in der Linie sein, da alles andere bedeutet, dass die Koordinate nicht verbunden ist.
- Mindestens drei der Koordinaten müssen zwei oder mehr Koordinaten in der Linie benachbart sein, da alles weniger und die Gruppen getrennt sind.
Sie können also nur die Nachbarn der Koordinate ermitteln und prüfen, ob beide Bedingungen erfüllt sind.
Hier ist eine grundlegende Lösung:
%Vor%Es ist keine allgemeine Lösung oder Vereinigungslogik erforderlich. :) Beachten Sie, dass es jedoch spezifisch für das Fünf-in-einer-Linie-Problem ist.