Reisen mit dem effizientesten Weg

7

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 1000km. Die einzige Tankstelle befindet sich am Startpunkt. Ihre maximale Kraftstofftankkapazität reicht gerade aus50 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.

HenryHey
quelle
3
Mein erster Gedanke ist, dass die A * -Suche bei diesem Problem wahrscheinlich recht gut funktioniert.
Pseudonym

Antworten:

5

Die Grundidee ist zu machen nFahrten, 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=1Ausflug). Trivial: Fahren Sie, bis Ihnen der Kraftstoff ausgeht. Zurückgelegte StreckeD(1)=1.

Beispiel 2 (n=2). Auf der ersten Reise reisenx Entfernung, so haben Sie 1xverbleibender Kraftstoff. Lassen Sie gerade genug Kraftstoff auf Deponie 1, damit Sie zum Start zurückkehren können. Verlassen1- -2xbei Dump 1 wird den Trick machen. Gehen Sie auf der zweiten Fahrt, beginnend mit einem vollen Tank, zur ersten Müllkippe (mitx 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 sein1- -3x=0, damit x=1/.3. Die Gesamtstrecke, die Sie zurücklegen, beträgtD.(2)=1+1/.3.

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

D.(n)=1+13+15++12n- -1
Wenn wir das definieren m-te harmonische Zahl ,
Hm=1+12+13+14+15++1m
dann ist es bekannt Hmlnm und wir können unsere Distanz schreiben
D(n)=1+13+15++12n1=(1+12+13++12n1)(12+14++12n2)=H2n112Hn1
Dies erfordert eine Menge von Fahrten (und Kraftstoff), die in der gewünschten Entfernung exponentiell sind. Zum Beispiel, um eine Strecke von zu gehen2, 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 .

Rick Decker
quelle
1
Ich habe ein einfaches Java-Programm gemacht, um dies auszuführen, um eine Distanz von 5 zu erreichen, es braucht 3093 Fahrten, nette Fakten :). Und um diese 1000 km lange Reise zu absolvieren, sind mehr als nötig1048Reisen.
HenryHey