17: Wichtelrouten / Elf Routing

  • Programmiert.

    Erst einmal alle Werte mühsam eingetragen, und dann folgende Strategie verwendet:


    1) Alle Wege für Ralph finden, auf welchen er von NP bis NP genau 204 Minuten benötigt (mit einer beschränkten Tiefensuche, er bewegt sich also von Knoten zu Knoten bis er es entweder schafft oder die Zeit überschreitet).

    So erhält man 14 mögliche Routen für Ralph (7 wenn man diejenigen, die sich nur in der Richtung unterscheiden, nicht doppelt zählt).


    2) Es ist hoffentlich jedem klar, dass Ralph auf seinem Weg genau 143 Geschenke einsammeln MUSS. Daher habe ich für jede der gefundenen Routen überprüft, ob sich aus den Geschenkanzahlen der einzelnen Knotenpunkte die Summe 143 bilden lässt. Wenn das nicht der Fall war, kann er die Route nicht nehmen weil er seinen Rucksack nicht vollbekommt.


    Und hier ist der Code ( Enrico Bortoletto you asked for it, here it is :p )

    Falls das jemand ausprobieren möchte:

    1) Eine .html Datei mit Folgendem Inhalt erstellen

    2) Die 3 Punkte durch das JavaScript ersetzen

    3) Datei im Browser öffnen

    4) Konsole öffnen um Ausgabe zu sehen (F12 --> auf den Reiter Console)

  • Ich habe das auch programmiert und alle Wege bis maximal 204 Minuten ausgegeben. Abbruchbedingung war die Zeitüberschreitung. Allerdings habe ich Wege sofort verworfen, wenn weniger als 143 Briefe hätten eingesammelt werden können. Das ergab nur 2 * 3 = 6 Wege von 204 Min. Dauer:

    Code
    1. 204 Min., 7 Postämter, 204 Briefe maximal: 0, 4, 3, 2, 6, 10, 11, 8, 0
    2. 204 Min., 6 Postämter, 167 Briefe maximal: 0, 4, 3, 2, 10, 8, 9, 0
    3. 204 Min., 6 Postämter, 187 Briefe maximal: 0, 4, 3, 2, 10, 11, 9, 0
    4. 204 Min., 7 Postämter, 204 Briefe maximal: 0, 8, 11, 10, 6, 2, 3, 4, 0
    5. 204 Min., 6 Postämter, 167 Briefe maximal: 0, 9, 8, 10, 2, 3, 4, 0
    6. 204 Min., 6 Postämter, 187 Briefe maximal: 0, 9, 11, 10, 2, 3, 4, 0

    Mit Excel-Hilfe - da ich damit zuerst Wege gesucht hatte - habe ich dann auf Wege mit möglichen 143 Briefen reduziert.


    Aus der ersten Liste 2 * 2 = 4 Wege à 174 Minuten:

    Code
    1. 174 Min., 5 Postämter, 143 Briefe maximal: 0, 4, 1, 5, 7, 9, 0
    2. 174 Min., 6 Postämter, 162 Briefe maximal: 0, 5, 1, 4, 3, 6, 8, 0
    3. 174 Min., 6 Postämter, 162 Briefe maximal: 0, 8, 6, 3, 4, 1, 5, 0
    4. 174 Min., 5 Postämter, 143 Briefe maximal: 0, 9, 7, 5, 1, 4, 0

    Diese habe ich von Hand kombiniert:

    Code
    1. 204 Min., 7 Postämter, 204 Briefe maximal: 0, 4, 3, 2, 6, 10, 11, 8, 0
    2. 174 Min., 5 Postämter, 143 Briefe maximal: 0, 4, 1, 5, 7, 9, 0
  • Ich bin hier eher heuristisch vorgegangen. Ich habe mir überlegt, dass die beiden in sehr unterschiedlichen "Gebieten" die Briefe abholen müssen, da sonst die Wege zeitlich zu lang werden. Jetzt gab es für mich zwei prinzipielle Einteilungsmöglichkeiten "links - rechts" bzw. "oben - unten". Da die Briefe der Station 2 und 4 wohl eher nicht vom selben "Postboten" abgeholt werden können ( 76 + 61 = 137 ==> 2 + 4 = 6 ==> Summe 143), denn sonst müsste der zweite Bote zu den Stationen 1 und 10 reiten (was sehr viel Zeit kostet), sollte der eine Bote die Briefe der Station 4 und der andere die der Station 2 abholen. Dies legt eine Aufteilung in "oben - unten" nahe. Dann habe ich die möglichst "zeitsparenden" Routen kombiniert und bin relativ schnell auf eine 204 Minuten Route mit exakt 143 Briefen für Ralph gekommen. Die Route von Stefan dauerte dann 174 Minuten.

    Also etwas Heuristik und etwas Improvisation führt auch ohne Programmierung zum Ziel. :)