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:

Zitat von freimatz (Beitrag 1446373)

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:

Zitat von Schokohase (Beitrag 1446426)

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.

[Delphi-Laie]

Zitat:

Zitat von mariusbenz (Beitrag 1446367)

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:

Zitat von Delphi-Laie (Beitrag 1446486)

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:

Zitat von Delphi-Laie (Beitrag 1446486)

Gib es auch unzuverlässige Algorithmen?

Ja, meine :pale:

Sherlock

[Schokohase]

Zitat:

Zitat von Jumpy (Beitrag 1446554)

4. Für "Stabilität" müsste man bei mehreren Konfigurationen mit gleich wenig Wechseln, ein weiteres Kriterium angeben, das diese gewichtet?

Die Stabilität bekommst du durch die Sortierung innerhalb des Blocks.

Nehmen wir mal folgenden Block

Code:

abcdeabcdeabcde

Wenn wir den sortieren, dann erhalten wir

Code:

aaabbbcccdddeee

und das stabil.

Bei der Permutation des Blocks ist nur der Anfang und das Ende interessant. Die Anordnung in der Mitte ist unerheblich.

Code:

aaabbbcccdddeee

oder

Code:

aaacccbbbdddeee

ist für die gesuchte Optimierung gleich.

Die Permutation von diesem intern sortierten Block bekommt man durch folgenden Pseudocode

Code:

parts = block.split() // aaabbbcccdddeee => aaa,bbb,ccc,ddd,eee  
foreach first in parts
  foreach last in parts.except(first)
    permutation = first + parts.except(first).except(last) + last

Und diese Permutation ist stabil.

Code:

aaacccdddeeebbb
aaabbbdddeeeccc
aaabbbccceeeddd
aaabbbcccdddeee
bbbcccdddeeeaaa
bbbaaadddeeeccc
bbbaaaccceeeddd
bbbaaacccdddeee
cccbbbdddeeeaaa
cccaaadddeeebbb
cccaaabbbeeeddd
cccaaabbbdddeee
dddbbbccceeeaaa
dddaaaccceeebbb
dddaaabbbeeeccc
dddaaabbbccceee
eeebbbcccdddaaa
eeeaaacccdddbbb
eeeaaabbbdddccc
eeeaaabbbcccddd

BTW: Die Anzahl der Elemente dieser Permutation ist

Code:

n*(n-1) für n=Anzahl der unterschiedlichen Buchstaben

Für die Optimierung ist der Wechsel innerhalb des Blocks völlig unerheblich, denn diese Wechsel sind immer da, egal wie die Anordnung ist. Man braucht also nur schauen, ob es einen Wechsel zwischen benachbarten Blöcken gibt.

Im Vorfeld kann man dabei schon das theoretisch bestmögliche Ergebnis ermitteln, was man dann als Abbruchkriterium nehmen kann (wenn man nur an einer optimalen Lösung interessiert ist).

Dazu schaut man sich die Blöcke an und ermittelt, ob diese Blöcke überhaupt ohne Wechsel zusammengefügt werden können.

Keine Wechsel zwischen den Blöcken

Code:

abcd
defg
ghij

Keine Optimierung möglich, denn es muss immer zwischen den Blöcken gewechselt werden.

Code:

abc
def
ghi

Natürlich gibt es auch Konstellationen, wo das so ermittelte theoretisch beste Ergebnis nicht erreicht werden kann

Code:

abc
cde
cfg

[freimatz]

Zitat:

Zitat von Delphi-Laie (Beitrag 1446486)

Zitat:

Zitat von mariusbenz (Beitrag 1446367)

Ich suche nur nach einem zuverlässigen Algorithmus.

Gib es auch unzuverlässige Algorithmen?

Ja. Es kommt drauf an was man unter unzuverlässig versteht. Gefragt ist hier eine Lösung mit den wenigsten Wechseln. Unzuverlässig wäre ein Algorithmus der zwar wenig Wechsel hat, aber nicht am wenigsten.
Einen zuverlässigen Algorithmus wird es hier schon geben, zumindest der Brute Force wäre einer.
Es kann jedoch sein, dass dieser Algorithmus nicht brauchbar wäre. Das wäre zum Beispiel der Fall wenn man um einige Wechsel mit je 5 Sekunden zu sparen fünf Stunden benötigt um die optimal Lösung zu finden.
(Das Problem hat auch jedes Navigationsgerät.)

Deswegen fragte ich auch nach der Anzahl der Blöcke. Sind es zum Beispiel maximal 20, dann Brute Force und gut ist.
Wenn es 1000 sind fürchte ich, gibt es keine brauchbare zuverlässige Lösung. Aber meistens reicht auch eine nahezu zuverlässige Lösung.

[Delphi-Laie]

So, ich habe es jetzt hoffentlich verstanden.

Ein Sortieralgorithmus läßt sich m.E. aber nur auf die jeweiligen einzelnen Zeilen anwenden. Danach ist wohl die Zeit für "brute force" gekommen: Die einzelnen Blöcke mit gleich(groß)en Elementen innerhalb der Zeilen so permutieren, daß die Zusatzbedingung ("möglichst wenige Wechsel") erfüllt ist.

[Delphi-Laie]

Zitat:

Zitat von freimatz (Beitrag 1446598)

Zitat:

Zitat von Delphi-Laie (Beitrag 1446486)

Zitat:

Zitat von mariusbenz (Beitrag 1446367)

Ich suche nur nach einem zuverlässigen Algorithmus.

Gib es auch unzuverlässige Algorithmen?

Ja. Es kommt drauf an was man unter unzuverlässig versteht. Gefragt ist hier eine Lösung mit den wenigsten Wechseln. Unzuverlässig wäre ein Algorithmus der zwar wenig Wechsel hat, aber nicht am wenigsten.

Das ist aber kein Algorithmus, der die Aufgabenstellung löst! Der ist also nicht nur unzuverlässig, sondern hinsichtlich des Zielens unbrauchbar/untauglich/nutzlos/wertlos o.ä..

[mariusbenz]

Hallo nochmal,

ich habe das Thema etwas ruhen lassen, deshalb melde ich mich jetzt erst wieder.
Da unsere Azubis diesen Algorothmus später umsetzen sollen, habe ich sie mit etwas Unterstützung erst mal selbst grübeln lassen.

Ich bin auf jeden Fall froh, dass Uwe und Schokohase die Aufgabe trotz fehlender Umformulierung verstanden haben.

Evtl. werden wir es auch mal mit BruteForcing probieren, therotisch kämen bis zu 60 Blöcke je 13 Werten zu Stande, in der Praxis wären es aber grob 20 Blöcke mit je 5 Werten.
Ebenso sind wir schon auf Uwes Idee mit der gemeinsamen Schnittmenge gekommen.

Den Ansatz (der mit den Bildern beschrieben ist) habe ich übrigens komplett verworfen, leider kann ich nun den Post aber nicht mehr bearbeiten.

[jfheins]

Ich hatte da noch eine Idee: Vielleicht könnten man das Problem als Graph umformulieren und dann über einen Standard-Algorithmus zur Lösung kommen.

Jeden Block kann man als Paar von Knoten auffassen, mit dem Anfangs- und Endbuchstaben. Die Pfade zwischen den beiden Knoten geben an, welche Kombinationen möglich sind. Vom zweiten Knoten gehen dann wieder viele Pfade zum ersten Knoten des nächsten Blocks.

Es ergeben sich sehr viele Pfade, die daher nach Möglichkeit nicht am Anfang alle erstellt werden sollten. Jeder Pfad hat dann ein Gewicht (0/1) je nachdem, ob die Buchstaben identisch sind. (Im Bild: Rot=1)

[Delphi-Laie]

Zitat:

Zitat von mariusbenz (Beitrag 1447245)

Evtl. werden wir es auch mal mit BruteForcing probieren, therotisch kämen bis zu 60 Blöcke je 13 Werten zu Stande, in der Praxis wären es aber grob 20 Blöcke mit je 5 Werten.

Schon bei 20, erst recht bei 60 Blöcken fällt brute force wegen der sehr stark wachsenden Fakultätsfunktion aus.

[Jumpy]

Zitat:

Zitat von Delphi-Laie (Beitrag 1447275)

Zitat:

Zitat von mariusbenz (Beitrag 1447245)

Evtl. werden wir es auch mal mit BruteForcing probieren, therotisch kämen bis zu 60 Blöcke je 13 Werten zu Stande, in der Praxis wären es aber grob 20 Blöcke mit je 5 Werten.

Schon bei 20, erst recht bei 60 Blöcken fällt brute force wegen der sehr stark wachsenden Fakultätsfunktion aus.

Wahrscheinlich richtig, aber wenn man zunächst die Zahl der Permutationen pro Block auf die Interessanten reduziert, wie von Schokohase vorgeschlagen und dann die 60 Blöcke in z.B. 5er Pakete zerlegt, oder immer da eine Paketgrenze macht, wo zw. zwei Blöcken wegen komplett verschiedener Inhalte eh keine Optimierung möglich ist, und dann auf die Pakete die Brute-Force-Methode anwendet, könnte das was werden.
Nur wäre es dann eigentlich nicht mehr pur Brute Force :).

[Delphi-Laie]

In meinem vorherigen Beitrage war ich unvollständig: Ich meinte natürlich, die Fakultätsfunktion wegen der Permutation(senumeration).

Soeben schaute ich mir Schokohases Beitrag eingehend an. Ich weiß nicht, was mit "stabil" gemeint ist. Stabil i.S. der Sortierung? Das ist eine beliebige Sortierung nicht per se, sondern es muß explizit ein stabiler Sortieralgorithmus gewählt werden! Diese "Sortierstabilität" war nach meiner Erinnerung in der Ausgangsproblemstellung nicht gefordert. Sie zu gewährleisten, ist jedoch mit der Wahl eines geeigneten, entsprechenden Sortieralgorithmus' leicht möglich.

Ja, und natürlich werden Blöcke bei diesen Permutationen als Elemente behandelt, d.h., daß innerhalb dieser Blöcke keinerlei Elementebewegungen stattfinden. Die Blöcke werden zeilenweise permutiert. Ist die Anzahl der Blöcke in der ersten Zeile a1, in der zweiten a2 usw. so dürfte die bei Brutforce abzuarbeitenden Gesamanzahl maximal a1!*a2!*... betragen. Das kann schnell heftig werden.

[Schokohase]

@Delphi-Laie

Ein Sortieralgorithmus (egal welcher) sollte egal wie immer so ein Ergebnis raushauen

Code:

aaabbbcccdddeee

sonst ist es kein Sortieralgorithmus. Einen echten stabilen Sortieralgorithmus braucht man hier gar nicht, weil es hier in diesem Anwendungsfall doch völlig egal ist, ob

Code:

aaabbbcccdddeee

oder

Code:

aaabbbcccdddeee

bei der Sortierung herauskommt.

(Wie, sie haben den Unterschied nicht bemerkt? Doch, sehen sie genau hin, das 2. a war vorher das 1. a also nicht stabil)

Oder anders gesagt, brauchen wir eigentlich keinen Sortieralgorithmus, sondern einen stabilen Gruppierungsalgorithmus, der gleiche Zeichen immer auf die gleiche Art zusammenfasst.