Reisen mit dem effizientesten Weg

Ein Freund von mir hat mir tatsächlich eine sehr interessante Frage zum Thema Informatik gestellt, und ich habe lange daran festgehalten.

Das Problem ist: Sie müssen reisen $1000$km. Die einzige Tankstelle befindet sich am Startpunkt. Ihre maximale Kraftstofftankkapazität reicht gerade aus$50$ Wenn Sie km unterwegs sind, dürfen Sie Kraftstoffe mitten auf der Reise "begraben" und für später aufbewahren.

Zum Beispiel können Sie reisen $20$ km zuerst und begraben $10$ Dort Kraftstoff im Wert von km und dann wieder tanken, damit Sie das nächste Mal den Kraftstoff abrufen können $10$ km treibt dich an und erreicht damit weiter.

Sie müssen den effizientesten Weg finden, um das Ziel zu erreichen.

Was ich mir vorgestellt habe, ist die dynamische Programmierung. Sie müssen jedoch davon ausgehen, dass die zurückgelegte Strecke vor jedem Auftanken eine Ganzzahl in Kilometern ist. Andernfalls ist es schwierig, dies mit DP zu tun. Ich habe noch keine lineare Programmierung versucht , aber ich denke es ist möglich.

Hast du eine Idee, wie es geht? Oder irgendwelche Hinweise?

Am wichtigsten ist, um welche Art von CS-Problem handelt es sich? ist es NP schwer? Ist es maschinell lösbar oder eher ein mathematisches Problem?

Noch ein paar Gedanken:

• Da es sich um einen kontinuierlichen Weg handelt, ist die Frage, ob es sich um NP handelt, vielleicht etwas albern, aber ich bin immer noch sehr neugierig.
• $1000$ und $50$ könnte absichtlich ausgewählt werden, um komplexe Berechnungen zu vermeiden.
• Gibt es eine gierige Lösung? Ich kann mir noch keine vorstellen.
• Ich denke jetzt, dass es eher ein mathematisches Musterfindungsproblem ist, obwohl mein Freund behauptet, es sei ein cs-Problem, also entscheide ich mich, diesen Beitrag beizubehalten.

Und wenn Sie wissenschaftliche Artikel oder Lehrbücher dazu haben, sagen Sie mir bitte, ich weiß gar nicht, wo ich anfangen soll.

Die Grundidee ist zu machen $n$Fahrten, Rückkehr zum Start und Auftanken auf allen außer der letzten Fahrt. Bei jeder vorletzten Fahrt lassen Sie etwas Kraftstoff auf einer neuen Müllkippe. Sie möchten wissen, wie weit Sie auf der letzten Reise gehen können. Um die Berechnung zu vereinfachen, sagen wir, dass ein voller Tank 1 (Einheit) Kraftstoff enthält und diese Menge eine Entfernung von 1 (andere Einheit) Entfernung ergibt.

Beispiel 1 ($n = 1$Ausflug). Trivial: Fahren Sie, bis Ihnen der Kraftstoff ausgeht. Zurückgelegte Strecke$D(1)=1$.

Beispiel 2 ($n=2$). Auf der ersten Reise reisen$x$ Entfernung, so haben Sie $1-x$verbleibender Kraftstoff. Lassen Sie gerade genug Kraftstoff auf Deponie 1, damit Sie zum Start zurückkehren können. Verlassen$1-2x$bei Dump 1 wird den Trick machen. Gehen Sie auf der zweiten Fahrt, beginnend mit einem vollen Tank, zur ersten Müllkippe (mit$x$ Füllen Sie Ihren Tank auf (nehmen Sie $x$ von der Müllkippe verlassen $1-3x$) und fahren, bis Ihnen der Kraftstoff ausgeht. Um die Entfernung zu maximieren, muss der Speicherauszug leer sein$1-3x=0$, damit $x=1/3$. Die Gesamtstrecke, die Sie zurücklegen, beträgt$D(2)=1+1/3$.

Der allgemeine Fall . Mit$n$ Reisen, werden Sie Dump 1 treffen $2n-1$ mal Dump 2 $2n-3$ mal Dump 3 $2n-5$Zeiten und so weiter. Um die Müllkippen auf der letzten Fahrt zu leeren, platzieren wir Müllhalde 1 in einiger Entfernung$1/(2n-1)$Dump 2 in weiterem Abstand $1/(2n-3)$, und so weiter. Dann wird die letzte Reise abdecken

$$D(n) = 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}$$ Wenn wir das definieren $m$-te harmonische Zahl , $$H_m=1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5} + \dotsm + \frac{1}{m}$$ dann ist es bekannt $H_m\approx\ln m$ und wir können unsere Distanz schreiben $$\begin{align} D(n) &= 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}\\ & = \left(1 + \frac{1}{2}+\frac{1}{3}+ \dotsm + \frac{1}{2n-1}\right)-\left(\frac{1}{2}+\frac{1}{4}+ \dotsm + \frac{1}{2n-2}\right)\\ &=H_{2n-1}-\frac{1}{2}H_{n-1} \end{align}$$ Dies erfordert eine Menge von Fahrten (und Kraftstoff), die in der gewünschten Entfernung exponentiell sind. Zum Beispiel, um eine Strecke von zu gehen$2$, es wird dauern $n=8$ Ausflüge und eine Strecke von zu gehen $5$ werde nehmen $3093$ Reisen.

Dies (und eine Variante) ist als Jeep-Problem bekannt und wird hier ausführlicher behandelt .