7
$\begingroup$

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time.

The problem is: you have to travel $1000$ km. The only gas station is at the starting point. Your maximum fuel tank capacity is just enough for $50$ km traveling, you are allowed to "bury" fuels in the middle of the journey and save it for later.

For example you can travel $20$ km first, and bury $10$ km worth of fuel there, and then go back to refuel, so next time you can retrieve the $10$ km fuels you left and reach further with it.

You need to find the most efficient way to reach the destination.

What I thought of is using dynamic programming, however you have to assume the distance you travel before each time you do refueling is an integer in terms of kilometers, else you it is hard to do it with DP, I have not try linear programming yet, but I think it is possible.

Do you have any idea how to do it? Or any hints?

Most importantly what type of cs problem is it? is it NP hard? Is it solvable by machine or is it more of a mathematical problem?

Some more thoughts:

  • Since it is a continuous path, asking whether if it is NP might be bit silly, but I am still very curious.
  • $1000$ and $50$ might be deliberately picked to avoid complex computation.
  • Is there a greedy solution? I cannot think of any just yet.
  • I now think it more of a mathematical pattern finding problem, though my friend claims it is a cs problem, so I am decide to keep this post.

And if you have any scientific articles or textbooks related to this please tell me, I do not know where to start in the first place.

$\endgroup$
  • 3
    $\begingroup$ My first thought is that A* search will probably do quite well on this problem. $\endgroup$ – Pseudonym Jan 20 '15 at 20:53
5
$\begingroup$

The basic idea is to make $n$ trips, returning to the start and refueling on all but the last trip. On each trip but the last, you'll leave some fuel at a new dump. You want to know how far you can go on the last trip. To make calculations easy, we'll say that a full tank contains 1 (unit) of fuel and that amount will take you a distance of 1 (other unit) of distance.

Example 1 ($n = 1$ trip). Trivial: drive until you run out of fuel. Distance covered $D(1)=1$.

Example 2 ($n=2$). On the first trip, travel $x$ distance, so you'll have $1-x$ fuel remaining. Leave just enough fuel at dump 1 to allow you to return to the start. Leaving $1-2x$ at dump 1 will do the trick. On the second trip, starting with a full tank, go to the first dump (using $x$ of your fuel), top off your tank (taking $x$ from the dump, leaving $1-3x$) and drive until you run out of fuel. To maximize the distance we'll need the dump to be empty so $1-3x=0$, so $x=1/3$. The total distance you'll cover will be $D(2)=1+1/3$.

The general case. With $n$ trips, you'll hit dump 1 $2n-1$ times, dump 2 $2n-3$ times, dump 3 $2n-5$ times, and so on. To empty the dumps on the last trip, we'll place dump 1 at a distance $1/(2n-1)$, dump 2 at a further distance $1/(2n-3)$, and so on. Then the last trip will cover $$ D(n) = 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1} $$ If we define the $m$-th harmonic number, $$ H_m=1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5} + \dotsm + \frac{1}{m} $$ then it's well known that $H_m\approx\ln m$ and we can write our distance $$\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}$$ This will take an amount of trips (and fuel) that are exponential in the desired distance. For example, to go a distance of $2$, it will take $n=8$ trips and to go a distance of $5$ will take $3093$ trips.

This (and a variant) is known as the jeep problem and is covered in more detail here.

$\endgroup$
  • 1
    $\begingroup$ I made a simple java program to run this, to go a distance of 5, it needs 3093 trips, nice facts :). And to complete that 1000 km journey it takes more than $10^{48}$ trips. $\endgroup$ – HenryHey Dec 19 '15 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.