An einem Güterbahnhof gibt es drei Abstellgleise für Waggons. Auf Gleis A stehen nummerierte, unsortierte Waggons, die so rangiert werden sollen, dass sie anschließend in einer gewünschten Reihenfolge auf Gleis C stehen sollen. Folgende Vorgaben müssen beachtet werden:
-Die Lok kann immer nur einen Waggon ziehen
-Man hat drei Helfer: jeweils einen an den Gleisen A,B und C. Diese Helfer können immer nur die Nummer des ersten Waggons ablesen. Somit ist jeweils nur die Nummer des Wagens an der Spitze eines Abstellgleises bekannt.
-Der Lokführer kann sich genau eine Information merken.
-Gleis B (oder auch später A) kann als Abstellgleis benutzt werden.
Aufgabe: Entwickeln Sie einen Algorithmus, der das Rangierproblem für möglichst alle Waggonkombinationen auf Gleis A lösen kann. Die Waggons sollen am Ende sortiert (nach Nummer) auf Gleis C stehen. Die Einschränkungen aus der Aufgabenstellung bestehen weiterhin. Beschreiben Sie die einzelnen Schritte des Algorithmus.
Danke für eure Hilfe!