14: Ein etwas anderer Weihnachtsstern / A Slightly Different Christmas Star

  • Beneidenswert schnell, da fehlt mir wohl eine Hirnwindung ... kannst du mir die mal leihen 8)

    Hier meine Lösung:

  • Die Lösung ist, dass man die Orte nach absteigender Sortierung ihres Quotienten von Masse/Entfernung anfahren muss. Das zu beweisen ist relativ leicht, wenn man auf die Idee kommt, dass man folgendes zeigen muss: Sei eine Reihenfolge der Orte vorgegeben. Wir prüfen nun, ob es sich lohnt, die beiden in der Reihenfolge benachbarten Orte x und seinen Nachfolger y zu tauschen. Berechnet man jeweils die Gesamtzeit (bin gerade zu faul, das ohne LaTeX hierhin abzutippen), ergibt sich die Formel, dass es sich genau für m(y)/d(y)>m(x)/d(x) lohnt. Nach dem Prinzip von Bubblesort ist das Optimum also die oben behauptete Reihenfolge (D,BK,N,H,M,IE,J,A,L,C,O,G,F) , und sie ist nicht eindeutig, weil B und K denselben Quotienten aufweisen.

    Falls jemand Zugriff auf einen Supercomputer hat, kann er gerne auch mal diesen brute-force Matlab-Code ausführen, der vermutlich auch eine Lösung findet. Die Reduktion von maxInd auf zB 10 findet zumindest eine Teillösung für 10 Orte in angemessener Zeit. myOptInds enthält dabei die behauptete optimale Reihenfolge und dient dementsprechend als Vergleich zu optInds:

  • Wenn man ausrechnen will, wie lange eine bestimmte Route dauert, erhält man eine Summe vieler Produkte aus Gewichts- und Entfernungswerten. Unabhängig von der exakten Route wird der Schlitten immer mit jeder Entfernung multipliziert, und für jeden Punkt wird immer sein Gewicht mit seiner Entfernung multipliziert. Diese konstanten Teile kann man also ignorieren. Wenn man das Problem auf die ersten 5 Punkte reduziert die Route A-B-C-D-E wählt, lässt sich die Dauer der Route also durch die rote Fläche im Bild darstellen: [IMG:https://i.imgur.com/3yafVke.png] Die gelbe Fläche ist konstant und unabhängig von der Route, kann also mitbetrachtet werden.

    Damit geht es nun darum, die Punkte so anzuordnen, dass die gefärbte Fläche - also die Fläche unter den Diagonalen - minimal wird. Dies geschieht, wenn sich die durch die Diagonalen gebildete Kurve an allen Knicken nur nach links krümmt. Dies widerum ist der Fall, wenn sich der Wert Gewicht geteilt durch Entfernung für jeden Punkt der Route immer verkleinert. Auf die Punkte A, B, C, D und E reduziert ergibt sich damit die optimale Route D-B-E-A-C: [IMG:https://i.imgur.com/wvnrqld.png]

    Entsprechend lässt sich das auf alle Punkte erweitern. Da es dabei mehrere Punkte mit gleichem Quotienten gibt, ist die Route nicht eindeutig.

  • Also meine Überlegungen waren:

    Da alle Geschenke (370 t) zu Beginn auf dem Schlitten sind (Gesamtgewicht 400 t am Start), sollte man möglichst schnell Masse verlieren, aber dabei die zurückgelegte Strecke so kurz wie möglich halten.

    Anders formuliert der Quotient m/s sollte möglichst groß sein.

    Die Route mit dem größten Quotienten steht also am Anfang (das ist übrigens D mit 35/72).

    Da zwei Routen exakt den gleichen Quotienten besitzen, nämlich B (38/118) und K (19/59) können diese beiden Routen beliebig getauscht werden, d.h. die optimale Route ist zweideutig (also nicht eindeutig).

    Daher entfallen die ersten fünf Antwortmöglichkeiten.

    Jetzt betrachtet man das Ranking der Quotienten:

    D > B = K > N > H > M > I > E > J > A > L > C > O > G > F

    Somit ist nur N vor H vor L richtig.

    Also ist es Antwort 8.

  • Falls jemand Zugriff auf einen Supercomputer hat, kann er gerne auch mal diesen brute-force Matlab-Code ausführen, der vermutlich auch eine Lösung findet.


    Wenn man deinen O(n*n!) Algorithmus mit DP optimiert kann das ganze auch ohne Supercomputer gelöst werden. Die Laufzeitkomplexität beträgt dann O(n*2^n)