Das Brückenrätsel

Vier Wanderer kommen in stockdunklerNacht zu einer verfallenen alten Brücke, die sie überqueren müssen. Die Brücke ist morsch und hat zahlreiche Löcher im Boden, denen man besser ausweichen sollte um nicht abzustürzen. Außerdem kann sie nicht mehr als zwei Personen gleichzeitig tragen.

Unsere Wanderer besitzen nur eine einzige Taschenlampe, ohne diese kann man die Überquerung nicht wagen. Wenn also zwei Personen die Brücke passieren, muss eine davon wieder umkehren, um die Lampe zurückzubringen.

Der erste Wanderer benötigt eine Minute zur Überquerung der Brücke, der zweite benötigt zwei Minuten, der dritte ist schon etwas erschöpft und braucht fünf Minuten, der vierte benötigt sogar zehn Minuten.

Die Frage ist nun: in welcher Reihenfolge sollten die Wanderer die Brücke überqueren, damit die ganze Aktion möglichst wenig Zeit in Anspruch nimmt?

Eine Möglichkeit wird Dir sicher schnell einfallen: der erste Wanderer ist am flinksten, also könnte er alle anderen der Reihe nach hinübergeleiten.
So etwa: zuerst gehen 1 und 2, dann kommt 1 zurück (2 würde länger brauchen) und geht mit 3 hinüber, kehrt nochmals um und holt schließlich Wanderer 4.
Das braucht 2+1+5+1+10 = 19 Minuten.

Geht es vielleicht noch schneller?

Aufgabe:

Schreibe ein Programm, das alle Möglichkeiten durchspielt und das Ergebnis (oder die Ergebnisse) mit der geringsten Zeit ausgibt.
Der Aufruf soll solve([1,2,5,10]) sein, damit wir später mit anderen Zahlen und einer anderen Zahl von Wanderern experimentieren können!

Forschung:

Wir erhalten zwei Lösungen. Worin unterscheiden sie sich? Kann man die Lösung in Form eines allgemeinen 'Prinzipes' formulieren?
Kann man die Einzelzeiten so ändern, dass sich mehr oder weniger optimale Lösungen ergeben?
Hängt die Zahl der Lösungen von der Anzahl der Wanderer ab?
Wie verhält sich die Laufzeit (etwa bei 6 oder 7 Wanderern), wenn man den cutoff nicht durchführt?
Wie ändert man das Programm, damit ausschließlich die optimalen Lösungen angezeigt werden, und nicht alle im Lauf der Zeit momentan besten? Hängt das mit der Sortierung der Eingabeliste zusammen?

Wenn Du nicht weiterkommst, gibt es hier eine Beispiellösung in unserer üblichen 'Bottom-Up'-Programmierweise.

Beachte, dass die Listen häufig als Kopien [:] erzeugt werden müssen. Da Python (wie auch Java,...) diesen Datentyp immer als Referenz übergibt, würde sonst an späterer Stelle unsere noch in Arbeit befindliche Liste verändert und zerstört werden!

Alternative: nach jeder neuen Überquerungsmöglichkeit werden die Wanderer explizit wieder an ihren Ursprungsort zurückgebracht. Das ergibt eine wunderbar symmetrische Funktion, wie wir sie von unseren Brettspiel-Programmen mit künstlicher Intelligenz kennen:
     Für alle möglichen Züge:
          Zug durchführen
          Auswertung/Rekursion
          Zug zurücknehmen
Du schreibst dazu die Funktionen cross und goback praktischerweise so um, dass sie eine beliebige Zahl von Personen bearbeiten können (Liste oder Tupel).