Ermittlung von Clustern in einer Matrix

[Gravitar]

Zitat von FredlFesl:

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 von FredlFesl:

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 von FredlFesl:

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 Ich denke, dass probiere ich mal aus.

Danke für den Denkanstoss