Einzelnen Beitrag anzeigen

Schokohase
(Gast)

n/a Beiträge
 
#15

AW: Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

  Alt 17. Sep 2019, 10:54
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

Geändert von Schokohase (17. Sep 2019 um 11:05 Uhr)
  Mit Zitat antworten Zitat