Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

[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.