Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm

Question

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 ?

Answer 1

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.