Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

[mariusbenz]

Hallo,

vorweg: Ich suche nur nach einem zuverlässigen Algorithmus.
Hier mal die Aufgabenstellung (vereinfacht):

Input:
Ein 2-dimesionales Array mit Zahlenwerten, z.B.
1360 2610 2610 2610
1360 2610 2610 1360 1360

Verarbeitung/Ziel:
die Zahlen so sortieren, dass insgesamt möglichst wenige Wechsel entstehen. „Insgesamt“ heißt, dass die vorhergehende und die nachfolgende Zeilen mitberücksichtigt werden sollen, also beim Zeilenwechsel möglichst kein Wechsel des Wertes auftritt. Die Werte können dabei nur innerhalb einer Zeile verschoben werden.
Die Abarbeitung erfolgt von links nach rechts und von oben nach unten (also so wie man es hier in Textform liest).

Output:
Das sortierte 2-dimesionale Array mit Zahlenwerten, z.B.
1360 2610 2610 2610
2610 2610 1360 1360 1360

-> Die Anzahl der "Wertewechsel" wurde von 4 auf 2 reduziert


Ich habe hier mal ein Beispiel mit echten Daten (zur Vereinfachung als Buchstaben) eines möglichen Inputs (pro Zeile können theoretisch ca. 10 verschiedene Werte stehen)
aabb
bbaa
cddd
eeec
eeef
eeef
eeef
eeef
eeef
eeef
gghe
iiig

Dann bin ich mal hingegangen und habe das Vorkommen eines jeden Buchstaben in ein Array gepackt, das sähe dann so aus
Grafik Array_Vorkommen.png

Mit folgendem Algorithmus könnte man dann dieses neue Array abarbeiten:
1. Es werden nur die Felder mit "1" betrachtet
2. In einer Spalte kann man "springen", jedes Feld darf aber nur ein Mal "besucht" werden.
3. Wenn alle Felder einer Spalte besucht wurden, muss man nach rechts in die nächste Spalte. -> Dabei nach Möglichkeit nicht die Zeile wechseln.

Darstellung, in welcher Reihenfolger die Felder abgearbeitet werden sollten: Grafik Array_Reihenfolge.png

Nach diesen Regeln würde man z.B. folgenden Output generieren (pro Spalte hier eine Zeile):
ab
ba
dc
ce
ef
fe
ef
fe
ef
fe
ehg
gi

was dann auf folgendes erweitert werden könnte und gleichzeitig das optimal sortierte Array wäre
aabb
bbaa
dddc
ceee
eeef
feee
eeef
feee
eeef
feee
ehgg
giii


Ich hoffe ich konnte die Aufgabenstellung anhand dieses Beispiel gut genug erklären.
Kennt ihr dafür einen Algorithmus?
Ist mein Ansatz über das Array "Vorkommen eines Wertes" ein richtiger Ansatz? Gibt es einen Algorithmus, um in diesem Array einen "Pfad" nach den oben beschriebenen Regeln (besonders Regel 3) zu finden?
Das Problem bei beiden Ansätzen dürfte ja sein, dass man ggf. zurückspringen und die bisherige Sortierung komplett über den Haufen werfen muss, um die optimale Sortierung zu erzielen.

[freimatz]

Nein, Sorry, ich versteh es nicht. Was sind denn Zuschnittbilder? Und was sind das für Paletten? Bei uns in der Firma gibt es auch Paletten, da wird nichts geschnitten. Und was man bei z.B. Euro-Paletten schneidet wüsste ich auch nicht.
Und was bedeuten die Zahlen? Länge, Breite, Höhe?
Und wie hoch ist die Anzahl der Bilder?

[mariusbenz]

Zitat von freimatz:

Nein, Sorry, ich versteh es nicht. Was sind denn Zuschnittbilder? Und was sind das für Paletten? Bei uns in der Firma gibt es auch Paletten, da wird nichts geschnitten. Und was man bei z.B. Euro-Paletten schneidet wüsste ich auch nicht.
Und was bedeuten die Zahlen? Länge, Breite, Höhe?
Und wie hoch ist die Anzahl der Bilder?

Schade, dass du dich an der für die eigentliche Aufgabe unwichtigsten Stelle aufgehalten hast. Ich habe die Aufgabenstellung nun neu formuliert.

[jobo]

Ich verstehe es auch nicht.
Wie erklärt sich der Wandel zwischen Beispielwerten im ersten Beispiel und im 2?
Aus 2 zeilen mit 4-5 Werten werden 15 Zeilen mit 1 Wert, oder ist abcd = 4 Werte?

Auch die Regeln von Dir kann ich nicht mit den Bildern und den Werten unter einen Hut kriegen.

[mariusbenz]

Die beiden Beispiele sind unterschiedlich.
Jeder Buchstabe steht für eine Zahl, z.B. a = 1360, b = 2500, etc.

Aber ich muss das morgen wohl nochmal neu formulieren...

[Sherlock]

Sieh es positiv, jede neue Formulierung des Problems könnte Dich selbst auf die Lösung bringen.

Sherlock

[Delphi-Laie]

Zitat von mariusbenz:

Ich suche nur nach einem zuverlässigen Algorithmus.

Gib es auch unzuverlässige Algorithmen?

Soweit ich die Anfrage verstand, geht es um das Sortieren zweidimensionaler Arrays.

Dazu suchte ich auch schon mal, fand aber nichts. Offensichtlich ist das spezieller als das Sortieren "linearer" Datenmengen.

Eigene Beschäftigung zeigte mir, daß das auch deutlich anspruchsvoller als "lineares Sortieren" ist. Einfach in beiden Dimensionen, abwechselnd und ggf. wiederholt zu sortieren, reicht ggf. nicht - das wäre / ist nämlich unzuverlässig.

Eine Beruhigung kann ich jetzt schon geben: Ein zweidimensionaler Sortieralgorithmus wäre / ist garantiert zuverlässig, denn ein unzulässiger Sortieralgorithmus ist keiner!

[Schokohase]

Zitat von Delphi-Laie:

Soweit ich die Anfrage verstand, geht es um das Sortieren zweidimensionaler Arrays.

Darum geht es eigentlich gar nicht.

Jeder Block/Zeile hat mehrere unterschiedliche gültige Anordungen wo es nun gilt ein Optimum zu finden.

Sortieren - Nein
Array - eindimensional (der Block/die Zeile) aber unerheblich, mittels Permutation iterieren wir über die möglichen Anordnungen und wird bei der Lösungssuche als Einheit betrachtet
Array - die Auflistung der Blöcke ist auch eindimensional und bleibt statisch - also auch unerheblich

Ok, ganz am Schluß kommt es darauf an, bei welcher Konstellation es die wenigsten Wechsel gibt ...

[Jumpy]

Mal ein anderer Ansatz (Bruteforce?), muss nicht unbedingt sinnvoller sein:

1. Man sortiert zunächst jeden Block für sich, so dass gleiche "Buchstaben"/"Größen" zusammen stehen.
2. Anschließend bildet man eine Liste aller Kombinationen von Permutationen in allen Blöcken.
3. Dann ermittelt man, bei welcher Kombination die wenigsten Wechsel stattfanden.
4. Für "Stabilität" müsste man bei mehreren Konfigurationen mit gleich wenig Wechseln, ein weiteres Kriterium angeben, das diese gewichtet?

[Sherlock]

Zitat von Delphi-Laie:

Gib es auch unzuverlässige Algorithmen?

Ja, meine

Sherlock