Spezieller Sortieralgorithmus bzw. Pfadfindealgorithmus gesucht

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