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

[Uwe Raabe]

Ein paar Gedanken zu dem Problem:

Jede Zeile (außer erster und letzter) hat eine Schnittmenge gemeinsamer Elemente mit der vorhergehenden und nachfolgenden Zeile. Sind diese Schnittmengen disjunkt oder mindestens eine davon leer, bildet diese Zeile die Grenze eines Optimierungsbereichs, bei der sich die angrenzenden Bereiche nicht beeinflussen. Man kann dann den Algorithmus auf die einzelnen Bereiche beschränken.

Es kann sein, daß es mehr als ein gleichwertiges Optimum gibt. Das wirft die Frage auf, ob der Algorithmus deterministisch sein soll - sprich, bei gleichen Eingabedaten immer dasselbe Ergebnis liefert. Eventuell kann man das durch zusätzliche Bedingungen für das Optimum erreichen.

[Schokohase]

So schwer zu verstehen ist es ja nun auch nicht, vor allem weil man zum Suchen nach der Lösung gar nicht alles verstehen muss.

Gegeben sei folgende Menge

Code:

{abababab}{abcabc}{dede}{aceace}

• Die geschweiften Klammern beschreiben einen Block.
• Die Buchstaben innerhalb eines Blocks dürfen beliebig angeordnet werden.
• Die Blöcke dürfen beliebig angeordnet werden.

Ziel ist es eine Reihenfolge der Blöcke zu finden, wo es minimale Wechsel zwischen den Buchstaben gibt.

Die gegebene Menge zeigt im Übrigen das worst-case Szenario wo ständig Wechsel (23 Stück) erfolgen.

Eine mögliche optimale Lösung wäre

Code:

{dd|ee}{ee|cc|aa}{aaaa|bbbb}{bb|aa|cc}

mit 6 Wechseln (markiert durch |)

[Uwe Raabe]

Zitat von Schokohase:

Gegeben sei folgende Menge

Code:

{abababab}{abcabc}{dede}{aceace}

• Die geschweiften Klammern beschreiben einen Block.
• Die Buchstaben innerhalb eines Blocks dürfen beliebig angeordnet werden.
• Die Blöcke dürfen beliebig angeordnet werden.

Ziel ist es eine Reihenfolge der Blöcke zu finden, wo es minimale Wechsel zwischen den Buchstaben gibt.

Sieh mal an, das hatte ich ganz anders verstanden:

• Die geschweiften Klammern beschreiben einen Block.
• Die Buchstaben innerhalb eines Blocks dürfen beliebig angeordnet werden.
• Die Reihenfolge der Blöcke ist vorgegeben.

Ziel ist es eine Reihenfolge der Buchstaben innerhalb jedes Blocks so zu verändern, das es sowohl innerhalb eines Blocks als auch von einem Block zum nächsten möglichst wenige Wechsel gibt.

Eine mögliche Lösung für das genannte Beispiel wäre dann:

Code:

{aaaabbbb}{bbaacc}{ddee}{eeaacc}

[Schokohase]

Ja, da hast du Recht, die Zeilen (Blöcke) sollen anscheinend nicht vertauscht werden.

Dadurch wird es auch einfacher zu lösen.