Ich versuche ein Problem zu lösen, das auf einem 2D-Array basiert. Dieses Array enthält verschiedene Arten von Elementen (von insgesamt 3 möglichen Arten). Nehmen wir die Art als X, Y, Z an.
Das Array scheint ungefähr so zu sein. Beachten Sie, dass es immer vollständig gefüllt wäre. Das Diagramm dient zur Illustration.
%Vor%Ich versuche, Gruppen von Elementen zu erstellen, die nebeneinander platziert sind. Zum Beispiel kann Satz1 Elemente des Typs X umfassen, die sich befinden in: (0,1), (1,1), (2,2), (2,3), (1,4). Ähnlich kann set2 Elemente des Typs Y umfassen, die sich in (3,4), (3,3), 4,3) befinden.
Problem: Wenn ein Punkt im Array angegeben wird, muss er in der Lage sein, alle Elemente zur entsprechenden Menge hinzuzufügen und sicherzustellen, dass es keine zwei Mengen gibt, die dasselbe Element enthalten. Beachten Sie, dass ein Set nur erstellt wird, wenn mehr als 2 benachbarte Elemente desselben Typs gefunden werden.
Wenn außerdem eine bestimmte Teilmenge von Elementen entfernt wird, werden mehr Elemente hinzugefügt, um die entfernten Elemente zu ersetzen. Das Array muss dann erneut durchlaufen werden, um neue Mengen zu erstellen oder die vorhandenen zu ändern.
Lösung: Ich implementierte eine rekursive Lösung, so dass sie über alle angrenzenden Elemente von beispielsweise Element X (0,1) iterieren würde. Beim Iterieren über die 8 möglichen benachbarten Elemente würde es sich dann rekursiv aufrufen, wenn ein Typ X auftrat.
Diese Art von Lösung ist zu brutal und ineffizient, besonders in dem Fall, in dem einige Elemente durch neue von möglicherweise unterschiedlichen Typen ersetzt werden. In einem solchen Fall muss fast das gesamte Array erneut iteriert werden, um Sätze zu erstellen / modifizieren und sicherzustellen, dass kein einziges Element in mehr als einer Menge existiert.
Gibt es einen Algorithmus, um diese Art von Problem effizient zu lösen? Ich brauche Hilfe bei einigen Ideen / Vorschlägen oder Pseudocodes.
[EDIT 5/8/2013: Zeitliche Komplexität festgelegt. (O (a (n)) ist im Wesentlichen konstante Zeit!)]
Im Folgenden bedeutet "verbundene Komponente" die Menge aller Positionen, die voneinander durch einen Pfad erreichbar sind, der nur horizontale, vertikale oder diagonale Bewegungen zwischen benachbarten Positionen mit der gleichen Art von Elementen zulässt. Z.B. Ihr Beispiel {(0,1), (1,1), (2,2), (2,3), (1,4)} ist eine verbundene Komponente in Ihrer Beispieleingabe. Jede Position gehört zu genau einer verbundenen Komponente.
Wir werden eine Union / Find-Datenstruktur erstellen, die für jede Position verwendet wird (x, y ) ein numerisches "label" mit der Eigenschaft, dass genau dann, wenn zwei beliebige Positionen (x, y) und (x ', y') zur gleichen Komponente gehören, sie das gleiche Label haben. Insbesondere unterstützt diese Datenstruktur drei Operationen:
set(x, y, i) setzt das Label für Position (x, y) auf i. find(x, y) gibt das Label zurück, das der Position (x, y) zugeordnet ist. union(Z) , für einen Satz von Labels Z, werden alle Labels in Z zu einem einzigen Label k kombinieren, in dem Sinne, dass zukünftige Aufrufe von find(x, y) an einer beliebigen Position (x, y), die zuvor ein Label in Z hatte, jetzt sind k zurückgeben. (Im Allgemeinen wird k eines der Labels sein, die bereits in Z sind, obwohl das eigentlich nicht wichtig ist.)% Co_de% gibt auch das neue "Master" Label, k. Wenn es insgesamt n = width * height-Positionen gibt, kann dies in O (n * a (n)) -Zeit erfolgen, wobei a () die extrem langsam wachsende inverse Ackermann-Funktion ist. Für alle praktischen Eingabegrößen ist dies dasselbe wie O (n).
Beachten Sie, dass, wenn zwei Vertices nebeneinander liegen, vier mögliche Fälle auftreten:
union(Z) diagonale Kante) \ diagonale Kante) Wir können den folgenden Durchlauf verwenden, um die Bezeichnungen für jede Position (x, y) zu bestimmen:
Nach dem Aufruf von / an einer beliebigen Position (x, y) erfahren Sie, zu welcher Komponente es gehört. Wenn Sie Anfragen des Formulars "Welche Positionen gehören zu der verbundenen Komponente mit Position (x, y)" schnell beantworten können? Erstellen Sie dann eine Hashtabelle der Listen find(x, y) und führen Sie einen zweiten Durchlauf über das Eingabearray durch, wobei Sie jedes (x, y) an die Liste posInComp anhängen. Dies kann alles in linearer Zeit und Raum geschehen. Um nun eine Abfrage für eine bestimmte Position (x, y) zu beantworten, rufen Sie einfach posInComp[find(x, y)] auf, um die Position dieser Position zu finden, und listen Sie dann die Positionen in lab = find(x, y) auf.
Um mit "zu kleinen" Komponenten umzugehen, schauen Sie sich einfach die Größe von posInComp[lab] an. Wenn es 1 oder 2 ist, dann gehört (x, y) nicht zu einer "groß genug" -Komponente.
Letztendlich benötigt all diese Arbeit effektiv lineare Zeit, also wird es blitzschnell sein, wenn Ihr Eingabe-Array nicht riesig ist. Es ist also durchaus sinnvoll, nach der Änderung des Input-Arrays von Grund auf neu zu berechnen.
In Ihrer Situation würde ich mich mindestens auf zwei verschiedene Arrays verlassen:
%Vor%Es könnte möglich sein, mehr unterstützende Arrays wie zum Beispiel eines mit den minimalen / maximalen X / Y-Werten für jeden Satz zu erstellen, um die Analyse zu beschleunigen (obwohl es sowieso ziemlich schnell wäre, wie unten gezeigt) / p>
Sie erwähnen keine Programmiersprache, aber ich gebe einen Beispielcode (C #) ein, weil dies der beste Weg ist, den Punkt zu erklären. Bitte verstehen Sie es nicht als Vorschlag für den besten Weg, um fortzufahren (persönlich mag ich Dictionaries / Lists nicht zu sehr; obwohl ich denke, dass sie eine gute grafische Möglichkeit bieten, einen Algorithmus zu zeigen, sogar für unerfahrene C # -Nutzer). Dieser Code soll nur einen Ansatz zur Datenspeicherung / -abfrage darstellen; Der beste Weg, um die optimale Leistung zu erzielen, hängt von der Zielsprache und weiteren Problemen ab (z. B. Dataset-Größe) und Sie müssen darauf achten.
Dabei ist isSurroundingPoint eine Funktion, die prüft, ob beide Punkte nahe beieinander liegen:
Sie können sich die region growing Algorithmen ansehen, die für die Bildsegmentierung verwendet werden. Diese Algorithmen beginnen von einem Startpixel und wachsen eine zusammenhängende Region, in der alle Pixel in der Region eine Eigenschaft besitzen.
In Ihrem Fall befinden sich benachbarte "Pixel" im selben Bildsegment, wenn sie dieselbe Bezeichnung haben (dh die Art des Elements X, Y oder Z)
Ich schrieb etwas , um Objekte eines bestimmten Typs für ein anderes SO zu finden Frage. Im folgenden Beispiel werden zwei weitere Typen hinzugefügt. Jede erneute Wiederholung würde die gesamte Liste erneut untersuchen. Die Idee ist, die Liste der Punkte für jeden Typ getrennt zu verarbeiten. Die Funktion solve gruppiert alle verbundenen Punkte und löscht sie vor dem Auflisten der nächsten Gruppe aus der Liste. areConnected prüft die Beziehung zwischen den Koordinaten der Punkte, da wir nur Punkte eines Typs testen. In dieser verallgemeinerten Version können die Typen ( a b c ) alles Mögliche sein (Strings, Zahlen, Tupel usw.), solange sie übereinstimmen.
btw - hier ist ein Link zu einem JavaScript-Beispiel für j_random_hackers grandiosen Algorithmus: Ссылка
Haskell-Code:
%Vor%Beispielausgabe:
%Vor%Tags und Links algorithm arrays set multidimensional-array