Sry I misunderstood your comment. I don't "feel" the greedy solution which you gave will work in all the cases. Will update the thread when I next sleep over it.
Programmers should realize their critical importance and responsibility in a world gone digital. They are in many ways similar to the priests and monks of Europe's Dark Ages; they are the only ones with the training and insight to read and interpret the "scripture" of this age. On Mon, Jan 17, 2011 at 9:39 AM, SVIX <[email protected]>wrote: > @avi... i didn't quite fully understand the intent of the comment... u > had initially said greedy would make wrong choices 3->5->4 and hence > give wrong minimum number of jumps while DP would give 3->4... hence i > responded saying that if we go greedy on a different function, greedy > will yield the right result as well... and in a shorter time > > On Jan 16, 12:28 pm, Avi Dullu <[email protected]> wrote: > > @svix that is precisely the reason why i gave my greedy approach first > and > > then the pseudo code and then the example, also I mentioned that greedy > can > > be be of different *locally optimal policies* so they *may* have a higher > > running time than the corresponding DP solution. > > > > regarding "your algorithm should be greedy on" .. it depends solely on me > as > > to what I want to be greedy upon, given that I can provide a proof that > the > > approach will always work. Like in interval scheduling problem there are > > numerous different greedy scheduling policies, but just one can be proved > to > > work for all the cases. > > > > Programmers should realize their critical importance and responsibility > in a > > world gone digital. They are in many ways similar to the priests and > monks > > of Europe's Dark Ages; they are the only ones with the training and > insight > > to read and interpret the "scripture" of this age. > > > > On Mon, Jan 17, 2011 at 1:52 AM, SVIX <[email protected] > >wrote: > > > > > > > > > > > > > > > > > @avi > > > > > regarding ur statement... > > > > > " > > > 3, 5, 3, 4, 1, 3, 4, 5 > > > > > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps) > > > whereas DP would take 3, 4 ( 2 steps) > > > " > > > > > it depends on what you are greedy about... as i had mentioned earlier, > > > your algorithm should be greedy on how far the value you choose will > > > let you jump and not just on the size of the value... i.e, get the > > > local maximum for (currentIndex + array[currentIndex]) > > > > > that is, > > > > > input: 3, 5, 3, 4, 1, 3, 4, 5 > > > index 0 1 2 3 4 5 6 7 > > > > > when index = 0, u can choose items at index 1, 2 and 3... go greedy on > > > f(index) = index + array[index] > > > > > so f(1) = 1 + 5 = 6 > > > f(2) = 2 + 3 = 5 > > > f(3) = 3 + 4 = 7 > > > > > plainly, if u define ur greedy criteria right, u go for index 3... > > > > > On Jan 15, 11:15 pm, Avi Dullu <[email protected]> wrote: > > > > The greedy will always chose the maximum, so iff a 0 is chosen, that > > > implies > > > > one cannot reach the end of the array. > > > > > > Programmers should realize their critical importance and > responsibility > > > in a > > > > world gone digital. They are in many ways similar to the priests and > > > monks > > > > of Europe's Dark Ages; they are the only ones with the training and > > > insight > > > > to read and interpret the "scripture" of this age. > > > > > > On Sun, Jan 16, 2011 at 12:16 PM, SVIX < > [email protected] > > > >wrote: > > > > > > > thinkin abt this again, there may be a slight problem with > > > > > straightforward greedy... > > > > > note that reaching 0 doesn't let u move forward... > > > > > > > On Jan 15, 12:54 pm, Avi Dullu <[email protected]> wrote: > > > > > > @jammy Thanx for the elongated description :) > > > > > > > > Yes, I feel I probably gave a DP solution wrongly to the Greedy > > > approach. > > > > > > But just to clarify, Greedy does not solve any subproblems, it > just > > > makes > > > > > a > > > > > > locally optimal choice and proceedes towards a global optimal > > > strategy. > > > > > And > > > > > > your point that greedy usually takes lesser time than DP also > stands > > > > > > correct, but there are a lot of exceptions wherein the choice of > > > local > > > > > > optimal strategy may be of very high order, and thus perform > worse > > > than > > > > > DP. > > > > > > > > Just to rest (and clarify) my argument, the following is the > greedy > > > > > approach > > > > > > I feel, *will* fail: > > > > > > > > for i = 1; i < n; i++ > > > > > > next_jump_will_be_from_index = index of max(input[ i ... i + > > > input[i] > > > > > ]) > > > > > > > > i.e. after each jump, greedy strategy is to choose the next > jumping > > > point > > > > > as > > > > > > the one which has maximum value > > > > > > > > 3, 5, 3, 4, 1, 3, 4, 5 > > > > > > > > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps) > > > > > > whereas DP would take 3, 4 ( 2 steps) > > > > > > > > and if you notice, the implementation of this greedy (without > using > > > fancy > > > > > > RMQ/segment trees) would still be O(n^2) or O(nlogn) (using > > > RMQ/segment > > > > > > trees) > > > > > > > > Programmers should realize their critical importance and > > > responsibility > > > > > in a > > > > > > world gone digital. They are in many ways similar to the priests > and > > > > > monks > > > > > > of Europe's Dark Ages; they are the only ones with the training > and > > > > > insight > > > > > > to read and interpret the "scripture" of this age. > > > > > > > > On Sun, Jan 16, 2011 at 1:39 AM, Jammy <[email protected]> > > > wrote: > > > > > > > @svix, I think pacific means takes i+v, But it still won't give > the > > > > > > > global optimal > > > > > > > > > @Avi, I am not an expert on greedy algorithm and some problems > may > > > be > > > > > > > solved by using greedy. But as far as I understand, the > difference > > > > > > > between DP and Greedy is DP makes use of the solution of the > > > > > > > subproblems while greedy doesn't. DP solves current problem by > > > solving > > > > > > > subproblems first and then making the choice. Greedy solves > current > > > > > > > problem by making a choice and solving subproblems. (see > > > CLRS).That's > > > > > > > why greedy gives me this idea that it usually takes less time > then > > > > > > > DP. > > > > > > > > > In your latest post, it appears to me you are using DP instead > > > greedy > > > > > > > because your solution to current problem is built upon the > solution > > > of > > > > > > > subproblems. > > > > > > > > > Please give me your input. > > > > > > > > > On Jan 15, 12:59 pm, SVIX <[email protected]> > wrote: > > > > > > > > actually, there is a way t do this in greedy... instead of > taking > > > the > > > > > > > > local maximum value v for an index i, take the local maximum > f(v) > > > = i > > > > > > > > + v... this will get you the right answer...more efficient > than > > > DP? > > > > > > > > that i'm not sure... but average case will be close to > linear.... > > > > > > > > > > On Jan 14, 9:29 pm, SVIX <[email protected]> > > > wrote: > > > > > > > > > > > @pacific.. > > > > > > > > > the approach needs a little bit of tuning... > > > > > > > > > > > for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur > > > approach, u > > > > > > > > > will pick 9, 8, 7, 6 etc... > > > > > > > > > > > minimum jumps in reality is from 9 to 1 to 2. > > > > > > > > > > > On Jan 14, 8:19 pm, pacific pacific <[email protected] > > > > > wrote: > > > > > > > > > > > > At each location if the value is k , > > > > > > > > > > find the largest value in the next k elements and jump > there. > > > > > > > > > > > > This greedy approach works in 0(n^2) and i believe it > works. > > > If > > > > > not > > > > > > > can > > > > > > > > > > someone give me a counter example ? > > > > > > > > > > > > On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu < > > > [email protected]> > > > > > > > wrote: > > > > > > > > > > > @jammy Even I felt the same, but the greedy 'algo' u > > > suggest is > > > > > > > actually > > > > > > > > > > > IMHO not a greedy approach. You just take each arr[i] > and > > > jump > > > > > > > *without > > > > > > > > > > > deciding a locally optimal policy* . SO, if u were to > *see* > > > > > arr[i] > > > > > > > and > > > > > > > > > > > *decide* on the optimal policy I feel one would follow > d > > > same > > > > > steps > > > > > > > as in a > > > > > > > > > > > DP solution. Its only just that the implementation > would be > > > > > O(n^2). > > > > > > > Just to > > > > > > > > > > > add, this is the greedy approach I feel: > > > > > > > > > > > > > greedy_min_steps[n] > > > > > > > > > > > for i = 0; i < n; i++: > > > > > > > > > > > for (j = 0; j < input[i]; j++) > > > > > > > > > > > greedy_min_steps[ i + j ] = min(greedy_min_step[ i > + j > > > ], > > > > > > > > > > > greedy_min_steps[ i ] + 1) > > > > > > > > > > > > > this is the greedy approach I build and I see this > being > > > > > exactly > > > > > > > similar to > > > > > > > > > > > my DP approach. There are instances of greedy approach > > > based > > > > > > > algorithms > > > > > > > > > > > which have *optimized* DP counter parts. I feel this > > > problem is > > > > > one > > > > > > > of them. > > > > > > > > > > > More ideas ? > > > > > > > > > > > > > Programmers should realize their critical importance > and > > > > > > > responsibility in > > > > > > > > > > > a world gone digital. They are in many ways similar to > the > > > > > priests > > > > > > > and monks > > > > > > > > > > > of Europe's Dark Ages; they are the only ones with the > > > training > > > > > and > > > > > > > insight > > > > > > > > > > > to read and interpret the "scripture" of this age. > > > > > > > > > > > > > On Sat, Jan 15, 2011 at 2:14 AM, Jammy < > > > [email protected]> > > > > > > > wrote: > > > > > > > > > > > > >> @Avi Greedy approach doesn't work since you can't > ensure > > > the > > > > > > > choice is > > > > > > > > > > >> locally optimum. Consider 3,9,2,1,8,3. Using greedy > alg. > > > > > would > > > > > > > give > > > > > > > > > > >> you 3,1,8,3 while otherwise DP would give you 3,9,3. > > > > > > > > > > > > >> On Jan 14, 6:11 am, Avi Dullu <[email protected]> > > > wrote: > > > > > > > > > > >> > I guess u got confused with the comment I wrote, I > have > > > > > added 2 > > > > > > > print > > > > > > > > > > >> > statements and now I guess it should be clear to you > as > > > to > > > > > why > > > > > > > the code > > > > > > > > > > >> is > > > > > > > > > > >> > O(n). The comment means that each element of the > > > > > min_steps_dp > > > > > > > will be > > > > > > > > > > >> > ACCESSED only ONCE over the execution of the entire > > > program. > > > > > > > Hence the > > > > > > > > > > >> outer > > > > > > > > > > >> > loop still remains O(n). The next_vacat variable if > u > > > notice > > > > > is > > > > > > > always > > > > > > > > > > >> > incremental, never reset to a previous value. > > > > > > > > > > > > >> > #include<stdio.h> > > > > > > > > > > >> > #include<stdlib.h> > > > > > > > > > > > > >> > #define MAX 0x7fffffff > > > > > > > > > > > > >> > inline int min(int a, int b) { > > > > > > > > > > >> > return a >= b ? b : a; > > > > > > > > > > > > >> > } > > > > > > > > > > > > >> > int find_min_steps(int const * const input, const > int n) > > > { > > > > > > > > > > >> > int min_steps_dp[n], i, temp, next_vacant; > > > > > > > > > > >> > for (i = 0; i < n; min_steps_dp[i++] = MAX); > > > > > > > > > > > > >> > min_steps_dp[0] = 0; > > > > > > > > > > >> > next_vacant = 1; // Is the index in the array > whose > > > > > min_steps > > > > > > > needs to > > > > > > > > > > >> be > > > > > > > > > > >> > updated > > > > > > > > > > >> > // in the next iteration. > > > > > > > > > > >> > for (i = 0; i < n && min_steps_dp[n - 1] == MAX; > > > > ... > > > > read more ยป > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
