@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; i++) > { > > > > > > > > >> > temp = i + input[i]; > > > > > > > > >> > if (temp >= n) { > > > > > > > > >> > min_steps_dp[n - 1] = min(min_steps_dp[n - 1], > > > > > min_steps_dp[i] + > > > > > > > > >> 1); > > > > > > > > >> > temp = n - 1; > > > > > > > > >> > } else { > > > > > > > > >> > printf("Updating min[%d] to %d \n", i + input[i], > > > > > min_steps_dp[i] > > > > > > > > >> + > > > > > > > > >> > 1); > > > > > > > > >> > min_steps_dp[temp] = min(min_steps_dp[temp], > > > > > min_steps_dp[i] + 1); > > > > > > > > >> > } > > > > > > > > >> > if (temp > next_vacant) { > > > > > > > > >> > printf("i: %d \n", i); > > > > > > > > >> > for (; next_vacant < temp; next_vacant++) { > > > > > > > > >> > printf("next_vacant: %d \n", next_vacant); > > > > > > > > >> > min_steps_dp[next_vacant] > > > > > > > > >> > = min(min_steps_dp[temp], > > > min_steps_dp[next_vacant]); > > > > > > > > >> > } > > > > > > > > >> > } > > > > > > > > >> > } > > > > > > > > >> > for (i=0;i<n;printf("%d > > > ",min_steps_dp[i++]));printf("\n"); > > > > > > > > >> > return min_steps_dp[n-1]; > > > > > > > > > > >> > } > > > > > > > > > > >> > int main() { > > > > > > > > >> > int n, *input, i; > > > > > > > > >> > scanf("%d",&n); > > > > > > > > >> > if ((input = (int *)malloc(n * sizeof(int))) == NULL) > { > > > > > > > > >> > return -1; > > > > > > > > >> > } > > > > > > > > >> > for (i = 0;i < n; scanf("%d",&input[i++])); > > > > > > > > >> > printf("Minimum steps: %d\n",find_min_steps(input, > n)); > > > > > > > > >> > return 0; > > > > > > > > > > >> > } > > > > > > > > > > >> > 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 Fri, Jan 14, 2011 at 1:49 PM, Decipher < > > > > > [email protected]> > > > > > > > > >> wrote: > > > > > > > > >> > > I don't think the inner loop is executing only once . > > > Kindly > > > > > check it > > > > > > > > >> for > > > > > > > > >> > > this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to > print > > > i in > > > > > inner > > > > > > > > >> loop > > > > > > > > >> > > you will find that for same values of i(Outer index) > inner > > > > > loop is > > > > > > > > >> called. > > > > > > > > >> > > Its an O(n2) solution . > > > > > > > > > > >> > > -- > > > > > > > > >> > > You received this message because you > > > > ... > > > > 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.
