Wie gruppiert man ähnliche Elemente in einem Array mit weniger Komplexität?

Question

nehmen wir eine rechteckige Anordnung, die ganzzahlige Werte wie diese haben:

A = [[1,1,2,2,2], 
    [1,2,2,2,1], 
    [1,3,3,3,1]] 

, wie die gleichen ganzzahlige Werte zu einer Gruppe, die miteinander zu verschiedenen Clustern verbunden ist? Die Clustergröße ist unbekannt.

Required Ausgang (Verschiedene Cluster der gleichen ganze Zahl, die miteinander verbunden sind):

Group 1 : A[0,0],A[0,1],A[1,0],A[2,0] 
Group 2 : A[0,2],A[0,3],A[0,4],A[1,1],A[1,2],A[1,3] 
Group 3 : A[1,4],A[2,4] 
Group 4 : A[2,1],A[2,2],A[2,3] 

Welches ist die am besten geeigneten Algorithmus für das Erledigen der gleiche ist. Ist es möglich, maschinelles Lernen für dieses Problem zu verwenden?

Answer 1

Jeder Graph Suchalgorithmus (BFS oder DFS) reicht.

Vertices des Graphen sind die Elemente der Matrix und Kanten bestehen zwischen benachbarten Elementen, so dass jeder Vertex 2 bis 4 Nachbarn hat.

Erstellen Sie eine Hilfsmatrix der gleichen Größe, die die Anzahl der Cluster für jedes Element und einen anderen Wert (z. B. -1) für Elemente speichert, die sich noch nicht in einem Cluster befinden. Nun, um die Cluster zu erhalten, durchlaufen Sie alle Elemente der Matrix. Wenn Sie ein Element finden, das sich noch nicht in einem Cluster befindet, führen Sie ein BFS oder DFS aus, um seine verbundene Komponente mit gleichen Werten zu finden, wobei alle diese Werte in der Hilfsmatrix durch die Nummer des neuen Clusters markiert werden.

Die Komplexität ist O (Anzahl der Elemente), die gleiche wie nur zum Lesen oder Schreiben der Matrix.