0
$\begingroup$

I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to reach the last element of the array in the minimum number of steps. At each step, I can move to any element with the same value, move forward one, or move backward one. The greedy criterion is to move furthest to the right as much as possible. For example, if we have array {1,2,3,4,1,5}, the algorithm will start at 1 move to 1 before the 5 then moves to 5 with number of steps of 2.

An an example of input instance that proves the given greedy algorithm wrong might be {1,2,1,3,2} where the given algorithm crosses the array in 3 steps whereas there is an optimal solution of moving from 1 to the second 2 right to last 2 in two steps. Now, what is a correct algorithm for solving this problem ?

$\endgroup$
1
$\begingroup$

The fact that you have several potential ways you can move in this problem should be an indicator of how to come up with a counterexample such that using the "greedy" strategy of simply going as far right as possible doesn't yield an optimal solution.

Consider the array, $A = \{1, 2, 1, 3, 2\}$

By the greedy strategy you would end up making the moves in this series:

$1 \xrightarrow{} 1 \xrightarrow{} 3 \xrightarrow{} 2$ $(3$ total moves$)$

However, the optimal strategy would be to make the moves:

$1 \xrightarrow{} 2 \xrightarrow{} 2$ $(2$ total moves$)$

Edit: I guess the question was edited as I was answering the question/after I answered it and we ended up with the same example..? Anyway here's another below:

Consider another counterexample (where backtracking produces a better solution):

$A = \{2, 1, 4, 6, 1, 5, 0, 10, 9, 8, 6\}$

The greedy strategy would yield the path: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xrightarrow{} 5 \xrightarrow{} 0 \xrightarrow{} 10 \xrightarrow{} 9 \xrightarrow{} 8 \xrightarrow{} 6$
$(8$ total moves$)$

Whereas the series of moves: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xleftarrow{} 6 \xrightarrow{} 6$ $(4$ total moves$)$

There's another series of moves resulting in a length $4$ path as well.

Since making the "locally optimal" decision for this problem at each step doesn't yield the optimal solution for the overall problem, this looks like a problem that could be solved using dynamic programming.

Look at it in a top-down fashion. What is the last move we'd want to make to get to the final element of the array, i.e., $a_n$. Recurse on that subproblem. Find a way to develop a solution using memoization (to avoid solving the same subproblem multiple times) or solve it iteratively, in a bottom-up manner. DP can be a bit difficult.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. How do you I come up with a correct algorithm without resorting to dynamic programming or memoization (I don't know what these are)? $\endgroup$ – user22295 Mar 20 at 4:41
  • $\begingroup$ No problem. I'm honestly not sure if this problem could be solved efficiently without dynamic programming. There are a lot of subproblems to consider at each step... I suppose you could come up with a recursive algorithm (that RR would be used to produce a DP algorithm though) for the problem and attempt to analyze the runtime to see if its feasible. $\endgroup$ – user114429 Mar 20 at 4:44
  • $\begingroup$ Is recursive algorithm different from greedy algorithm ? Can the greedy algorithm be recursive ? I am sorry if I am asking a lot of questions. I am terrible at this subject. I just want an alternative greedy algorithm that works. And you say "efficiently." Can it be solved in a non efficient way ? $\endgroup$ – user22295 Mar 20 at 4:49
  • $\begingroup$ That could work. Assuming we have array {1,2,1,3,2}, and given the constraints of movement, we could start at 2, move to 2, then end at 1 in two steps. $\endgroup$ – user22295 Mar 20 at 4:59
  • 1
    $\begingroup$ It's fine buddy. Thanks a lot for your help and time. $\endgroup$ – user22295 Mar 20 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy