"Matrixzerlegung" einer Matrix mit holonischer Unterstruktur

Bevor ich beginne, muss ich sagen, dass dies für diejenigen mit einem Hintergrund der linearen Algebra NICHT Matrixzerlegung ist, wie Sie es kennen. Bitte lesen Sie die folgenden Abschnitte, um das Problem, das ich lösen möchte, besser zu verstehen.

Hier sind die hervorstechenden Eigenschaften / Definitionen der Matrix und ihrer Submatrizen:

1. Ich habe eine SxP-Matrix, die eine gitterartige Struktur von S.P- "Boxen" bildet. Dies ist die Hauptmatrix .

So sieht die (leere) Hauptmatrix aus. Jedes Quadrat in der Matrix wird einfach als eine Box bezeichnet. Die Matrix kann als eine Art "Spielbrett", z.B. ein Schachbrett. Die vertikale Achse wird unter Verwendung einer Intervallskala (d. H. Reellen Zahlen) gemessen, und die horizontale Achse wird unter Verwendung von monoton ansteigenden nicht-negativen ganzen Zahlen gemessen.

2. Es gibt ein zusätzliches Konzept von Submatrizen (wie zuvor erläutert). Eine Submatrix ist einfach eine Sammlung von Boxen in einer bestimmten Konfiguration und mit spezifischen Nummern und Stücktypen (siehe schwarze und weiße Stücke unten), die den Boxen zugewiesen sind. Ich habe eine endliche Menge dieser Submatrizen - was ich als mein Lexikon oder Vokabular bezeichne zum Ausführen einer gültigen Matrixzusammensetzung / Zerlegungen.

Die "formale" Definition einer Submatrix ist, dass es sich um eine Konfiguration von M Boxen innerhalb der Hauptmatrix handelt, die die Kriterien erfüllen:

• 1 & lt; = M & lt; = 4
die "Lücke" G (d. h. der Abstand) zwischen zwei benachbarten Kästchen erfüllt: 1 & lt; = G & lt; = 2 · (vertikale Einheiten).

Eine vertikale Einheit ist die Lücke zwischen den vertikalen Achsenlinien in der Hauptmatrix. Im Bild unten ist die vertikale Einheit 100.

Das Bild oben zeigt eine einfache Submatrix-Addition. Die Einheiten mit orangen Boardern / Boxen sind Submatrizen - die anerkannten Einheiten, die Teil meines Lexikons sind. Sie werden bemerken, dass ich weitere Anmerkungen in meine Submatrizen eingefügt habe. Dies ist so, weil ich (unter Verwendung der Schachanalogie) zwei Arten von Stücken habe, die ich auf dem Brett verwenden kann. B bedeutet ein schwarzes Stück, und W (nicht im Bild gezeigt), stellt ein weißes Stück dar. Eine erkannte Einheit (oder Lexem / Sub-Matrix) Es gibt eine einfache Äquivalenzbeziehung, die die Konvertierung zwischen einem weißen Stück und einem schwarzen Stück ermöglicht. Diese Beziehung kann verwendet werden, um eine Untermatrix weiter zu zerlegen, um entweder ausschließlich schwarze Stücke, weiße Stücke oder eine Kombination von beiden zu verwenden.

Der Einfachheit halber habe ich auf die Angabe der Äquivalenzbeziehung verzichtet. Wenn jedoch jemand der Meinung ist, dass das gestellte Problem ohne zusätzliche Details nicht "zu schwierig" ist, werde ich den Anwendungsbereich gerne erweitern. Im Moment versuche ich, die Dinge so einfach wie möglich zu halten, um die Leute nicht mit "Informationsüberflutung" zu verwirren.

3. Jedes Feld in einer Untermatrix enthält eine vorzeichenbehaftete Ganzzahl, die die Anzahl der Einheiten eines Elements angibt. Jede "Konfiguration" von Kästchen (zusammen mit ihren mit Vorzeichen versehenen ganzen Zahlen und Stücken, d. H. Schwarzen oder weißen Stücken) wird als eine "erkannte Einheit" bezeichnet.

4. Submatrizen können so in der Hauptmatrix platziert werden, dass sie sich überlappen. Überall dort, wo die "Boxen" überlappen, ist die Anzahl der Einheiten in der resultierenden Submatrix-Box die Summe der Anzahl der Einheiten in den einzelnen Boxen (wie im zweiten Bild oben dargestellt).

Das Problem wird etwas schwierig, weil die oben definierten "anerkannten Einheiten" manchmal mit anderen "anerkannten Einheiten" kombiniert werden, um eine andere "erkannte Einheit" zu bilden - dh die Untermatrizen (dh erkannte Einheiten) sind "holons ". Zum Beispiel kann in dem zweiten Bild oben die erkannte Einheit, die zu der Matrix hinzugefügt wird, selbst weiter in "kleinere" Submatrizen zerlegt werden.

Diese Art holarchy ist ähnlich wie (in der Physikalischen Chemie) Elemente Verbindungen bilden, die dann weitergehen Form immer komplizierter Verbindungen (Aminosäuren, Proteine ​​usw.).

Zurück zu unserem Problem, bei einer Hauptmatrix M möchte ich Folgendes tun können:

ich. Identifizieren Sie die Submatrizen (oder anerkannten Einheiten), die in der Hauptmatrix enthalten sind. Dies ist die erste "Matrixzerlegung". (Hinweis: Eine Submatrix muss die oben genannten Kriterien erfüllen)

ii. Ich möchte für jede identifizierte Submatrix erkennen können, ob sie in 2 oder mehr erkannte Submatrizen zerlegt werden kann. Die Idee besteht darin, die in Schritt 1 gefundenen Submatrizen iterativ zu zerlegen, bis entweder eine spezifizierte Hierarchieebene erreicht ist oder bis wir eine endliche Menge von Submatrizen haben, die nicht weiter zerlegt werden können.

Ich versuche, einen Algorithmus zu finden, der mir hilft, (i) und (ii) oben zu tun.Ich werde die Logik entweder in C ++, Python oder C # (in steigender Präferenzstufe) implementieren, je nachdem, was am einfachsten zu tun ist und / oder in welchem ​​Fall ich Snippets bekomme, um mit der Implementierung des Algorithmus zu beginnen.