How to think of locally optimal solution in greedy?

Revision en2, by ay2306, 2018-07-02 06:56:03

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?

Tags greedy, unable to understand, approach

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ay2306 2018-07-02 13:41:16 1 Tiny change: 'e\n\nAs in\n\nLet's ' -> 'e\n\nAs in,\n\nLet's '
en3 English ay2306 2018-07-02 06:56:50 0 Tiny change: 'EXPEDI/). How in this que' -> 'EXPEDI/). In this que'
en2 English ay2306 2018-07-02 06:56:03 6 Tiny change: 'EXPEDI/). How in this que' -> 'EXPEDI/). In this que'
en1 English ay2306 2018-07-01 20:23:41 1263 Initial revision (published)