4

Following problem:

An engine (for instance a car) starts its journey on a straight road. Its consumption is directly proportional to the distance (for instance 480 km uses one unit of fuel and thus 48km uses a tenth unit of fuel). This engine can transport at most one unit of fuel.

At the start point is a supply of n0 fuel units. At different points on the route, are fuel depots (for instance n1 @ d1, n2 @ d2 etc.) and the driver can unload fuel anywhere on the route. For instance, with the values 480 km for one unit, the driver could drive for 160km create a depot with 1/3 units of fuel and drive back to the starting point to refuel his engine.

I'm looking for an algorithm (or some ideas to find one) to find the maximum distance that can be achieved depending on the starting fuel and the depots on the route.

Burkhard
  • 14,596
  • 22
  • 87
  • 108
  • so basically a unit is not atomic and can be split. – UmNyobe Dec 11 '12 at 13:04
  • Just to make sure, the depots do not need to be empty after all? And by maximum distance, you don't mean the distance travelled, but the distance from starting point? – jimpic Dec 11 '12 at 13:09
  • @jimpic: yes, the distance from starting point. And the depot do not need to be empty at the end. – Burkhard Dec 11 '12 at 13:12
  • This reminds me of the Dijkstra's algorithm for shortest path. Possibly can be adapted to consider long distance. Also have a look at a similar question here http://stackoverflow.com/questions/10462736/graph-dijkstra-for-the-single-source-longest-path. – walters Dec 11 '12 at 13:16
  • 2
    Is there only fuel at the starting point in the beginning? Or might the other depots already have some? – jimpic Dec 11 '12 at 13:34
  • There is also n1 units at a distance d1, n2 units at a distance d2, etc. Sorry, english is not my native language. – Burkhard Dec 11 '12 at 19:51

2 Answers2

1

By intuition a greedy algorithm should be optimal, ie by maximizing the amount of fuel available at each depot, you are maximizing the possible route. This is just my opinion, and I assume that "anywhere on the route" is "actually at any depot".

How will a greedy algorithm work? At each point of time, you have only two decision to take : "move forward" or "go back to the previous depot to refill". The greedy will always move back as long as it will increase the current depot reserve.

UmNyobe
  • 22,539
  • 9
  • 61
  • 90
  • I think there's some ambiguity in the question. However, it does talk about "creating" a depot, which makes it sound like fuel can be unloaded at any point and not just at existing depots. – NPE Dec 11 '12 at 15:37
  • @NPE: that's right and it was imho the most difficult part to solve. – Burkhard Dec 13 '12 at 06:42
1

I think that you could also "invert" the "<=" comparison used in your a*, dijkstra method.

Or add a logic parameter (best, worst) path.

So you can keep the same path search without repeated code.

AndreDurao
  • 5,600
  • 7
  • 41
  • 61