We need to refuel and we don't know where the nearest gas station is. We are at a crossing which looks like: ← ↑ →. What is the best strategy to find the gas station? Our "range of view" = 0 and we know that there is one gas station at one of these roads. There are no other crosses and there are only these three roads. We should find the most optimal strategy for every proportion of our fuel range and x = distance to station (which we don't know).

  • 2
    $\begingroup$ do you mind driving through grass, fences, and other private property? :P $\endgroup$ – Quintec Dec 17 '17 at 21:34
  • $\begingroup$ I'd whip out my GPS ^^ $\endgroup$ – RnRoger Dec 17 '17 at 21:35
  • 1
    $\begingroup$ So… you can only drive on roads, the roads only meet at the one spot, and you can't see a gas station until you reach it? Isn’t that just random choice? $\endgroup$ – Ry- Dec 17 '17 at 21:39

I think that without knowing more information about either how far the gas station is away, or what the likelihood of station placement vs distance is, you can't do any better than choosing a random road and driving along it until either you find the station or you run out of fuel.

If you had further information your strategy might change. For example if the station is at a fixed distance D:

  • If remaining fuel range < D: you can't get there. Why even bother
  • If D < remaining fuel range < 3D: choose randomly for a 1/3 chance
    (no point driving past distance D).
  • If 3D < remaining fuel range < 5D: choose randomly, drive distance D on random road, if nothing by distance D go back and try 2nd road for a 2/3 chance.
  • If 5D < remaining fuel range : choose randomly, drive distance D on
    random road, if nothing by distance D go back and try 2nd road, and
    then 3rd road, for a 100% chance of eventually finding fuel.

Distance not known but uniformly distributed in range (0 ..D) :

  • If remaining fuel range F < 3D: drive distance F/6 in one direction, if no luck, return and try up to F/6 in another direction, finally F/3 in the third direction. Chance of finding fuel is 2F/9D.
  • If remaining fuel range 3D < F < 5D: drive distance (F-1)/4 in one direction, repeat in a second direction if no luck, and finally go distance D in third direction with remaining fuel. Chance of success is 2/3 + (F-3D)/6D.

Distance not known but non-uniformly distributed:

  • Depends on the specific distribution - further information needed.

I think this problem is ill posed, and here is why. I would like to hear any feedback about errors in my reasoning.

Let's say you have enough gas to drive d miles.

  • If the gas station is at most d/5 miles away, the optimal strategy is to explore d/5 miles down each road, guaranteeing success.

  • If the the gas station is between d/5 and d/3 miles away, the best strategy is to randomly choose 2/3 roads and explore d/3 down both of them; P(success) = 2/3.

  • If the gas station is between d/3 and d miles away, the best strategy is to explore d miles down a randomly chosen road; P(success) = 1/3.

Since the optimal strategy depends on the distance to the gas station, and that distance is unknown, it is impossible to optimize.


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