Ermittlung von Clustern in einer Matrix

[Gravitar]

Hi,

ich versuche gerade in einer 2dimensionalen Matrix (13 x 17) Cluster von gleichwertigen oder ähnlichen Zahlen zu finden. Dabei ist leider nur das Vertauschen von ganzen Spalten oder von ganzen Zeilen erlaubt.

Eine Tabelle wird danach bewertet, wie viele Nachbarn (max 8) jeder einzelnen Zelle gleiche Werte bzw. ähnliche Werte enthalten.

Bisher schlage ich mich zum Testen von zufällig gefüllten Matrixen von 10x10 herum.

Der Ansatz, über reines ausprobieren (permutieren) weiterzukommen scheitert an der astronomischen Zahl der Möglichkeiten (10! x 10!). Im Moment habe ich einfach mal die Spalten permutiert. Dass dauert schon 8 Sekunden!!! Wenn ich dass dann noch 3 Mio. mal für die Zeilen mache kann man sich die Wartezeit ausrechnen:cry:

Das Sortieren der Spalten/Zeilen nach den jeweiligen Summen bringt auch keine wirkliche Verbesserung. Z.T. verschlechtert sich die Bewertung der Matrix sogar im Vergleich zur zufällig gefüllten Ausgangsmatrix.

Gibt es hier irgendein hyperschlauen Algorithmus der einem da weiterhilft?

[mkinzler]

Du musst die möglichen "Züge" bewerten

[BUG]

Noch mal anders formuliert:

Eingabe: 2-dimensionales Array.

Du hast eine Bewertungsfunktion für das Array, die alle Bewertung von Zellen addiert.
Die Zellen werden um so höher gewertet, je näher die Nachbarzellen an ihrem Wert liegen.

Ausgabe: Array, dass genau die gleichen Zahlen wie die Eingabe enthält, aber mithilfe von Zeilen- und Spaltenvertauschung sortiert ist, das die Array-Bewertung maximal ist.

Soweit richtig?

Was ändert sich die Bewertung einer Zelle denn, wenn diese am Rand liegt, eventuell zerstört das aktuell den Sortierungsansatz.


EDIT:
mkinzlers Ansatz hat erstmal den Vorteil, dass die Ausgabe nie schlechter ist als die Eingabe.

[FredlFesl]

Blöd nur, wenn es sich hierbei um ein NP-komplettes Problem handelt. Dann bringen Zugbewertungen nicht viel. Da hilft dann nur ausprobieren.
Eventuell kommt man mit einer Heuristik weiter.

Muss es die optimale Lösung sein?
Wenn ja, wie sieht die aus?
Sind eng zusammenhängende Zahlen in der Mitte besser, als am Rand?
Sind ALLE 'Cluster' zu finden, oder nur der zu einer bestimmten Zahl oder nur alle Elemente mit einem maximalen von X?

Könnte man eine Chaossuche anwenden?
Dabei werden max N zufällige 'Züge' durchgeführt. Ist das Ergebnis besser als das Original, wird das Ergebnis als Original behandelt und von Vorne angefangen.

Ich glaub zumindest, das das "Chaossuche" ist.

[Gravitar]

Zitat:

Zitat von FredlFesl (Beitrag 1108443)

Blöd nur, wenn es sich hierbei um ein NP-komplettes Problem handelt. Dann bringen Zugbewertungen nicht viel. Da hilft dann nur ausprobieren.

Ja, irgendwie habe ich das blöde Gefühl, dass es sich um NP-vollständig (oder übersetzt = sauschwer) handelt

Zitat:

Zitat von FredlFesl (Beitrag 1108443)

Eventuell kommt man mit einer Heuristik weiter.

Muss es die optimale Lösung sein?
Wenn ja, wie sieht die aus?
Sind eng zusammenhängende Zahlen in der Mitte besser, als am Rand?
Sind ALLE 'Cluster' zu finden, oder nur der zu einer bestimmten Zahl oder nur alle Elemente mit einem maximalen von X?

Na optimal ist dann ja kaum drin. Eine Lösung in der Nähe würde mir schon reichen. Leider weiss ich auch nicht wie die optimale Lösung aussieht.

Grundsätzlich können mehrere Cluster vorkommen. Am Rand oder in der Mitte ist egal.

Zitat:

Zitat von FredlFesl (Beitrag 1108443)

Könnte man eine Chaossuche anwenden?
Dabei werden max N zufällige 'Züge' durchgeführt. Ist das Ergebnis besser als das Original, wird das Ergebnis als Original behandelt und von Vorne angefangen.

Ich glaub zumindest, das das "Chaossuche" ist.

Ja, so etwas ähnliches habe ich mal beim Travelsman-Problem gesehen. Dort wurden am Anfang zufällige Routenänderungen vorgenommen und mit der Zeit wurden die Veränderungspotentiale immer mehr verkleinert, so dass im Vergleich zur vorherigen Lösung nur noch immer geringer werdende Veränderungen zugelassen wurden.

Nur nach einer besseren Lösung zu suchen, als bisher, führt leider in die Falle, da sogenannte lokale Optima eine optimale Lösung verhindern.

Die Frage ist jedoch, wie ich das Veränderungspotential mit der Zeit minimiere. Evtl. könnte ich ja den Abstand der zu tauschenden Spalten bzw. Zeilen immer mehr reduzieren. Mhmm..... hört sich eigentlich gar nicht so schlecht an:gruebel: Ich denke, dass probiere ich mal aus.

Danke für den Denkanstoss:thumb:

[FredlFesl]

Ich würde das Veränderungspotential nicht verkleinern, sondern vielleicht mit einer gaus'schen Verteilung arbeiten, sodaß kleine Veränderungen wesentlich häufiger vorkommen, als große...

Dann wäre dein Problem der lokalen Maxima auch erledigt, denn irgendwann hüpft der Algorithmus aus einem lokalen Maximum wieder raus, nämlich genau dann, wenn zufällig eine ziemlich große Veränderung eintritt (und diese dann besser ist).

Eine weitere Vorgehensweise wäre noch, den Baum bis zu einer Tiefe X zu traversieren. Dabei sollten jedoch die einzelnen Stände gespeichert werden. Bevor nun eine Konstellation weiter untersucht wird, prüfst Du, ob diese Matrix, bzw. eine der Rotationen oder Spiegelungen nicht schon vorher analysiert wurde. Wenn ja, kannst Du dir weitere Arbeit schenken. Das dürfte den Aufwand schon mal drastisch senken, denn es gibt ja pro Matrix 4 Rotationen, 2 Spiegelungen und alle Kombinationen davon.

Vielleicht kannst Du mit dem Baumtraversieren zunächst die 'beste' Lösung (für max X Züge) finden und setzt die Baumtraversierung bei dem 'best of X' wieder an, wobei Du die bereits besuchten Stellungen natürlich nicht verwirfst, denn sonst würdest Du ja auch wieder rückwärts suchen, also in die Richtung, aus der Du gerade gekommen bist.

So könntest Du dich langsam zu einem brauchbaren Ergebnis hangeln.

Leider wird der Index recht groß, aber wozu hat man schließlich RAM, Datenbanken und TByte-Platten.