Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

[freimatz]

Zitat von Delphi-Laie:

Zitat von mariusbenz:

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

Zitat von Delphi-Laie:

Zitat von mariusbenz:

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

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 von Delphi-Laie:

Zitat von mariusbenz:

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.