ay2306's blog

By ay2306, history, 6 years ago, In English

I studied about greedy algorithms and found that all we have to do is try a locally optimal solution and hope it turns out to be globally optimal. But my problem is how to find a locally optimal solution when logic I am developing is already taking global optimal solution.

For example, I was working on some greedy example and came across this question. In this question my local optimal approach was that I will check if Current fuel can travel out of the forest, if not then refuel but then it bombed me with a limitation of availability fuel at a stop so I was now deep struck into thinking how to solve it. So doesn't this require a solution where local optimal won't work because we need to have a knowledge of all stops and amount of fuel they require

As in,

Let's say we were at a stop which can provide 2 unit fuel and we have 4 units of fuel, and two other stops are at distance 2 unit each consecutively, but next one provides 100 units fuel(which can cover whole travel) and one after that makes me stop.

So what should be the local optimal solution approach here, because I am unable to find any without taking the whole scenario into account?

  • Vote: I like it
  • +4
  • Vote: I do not like it