Minimize Manhattan distance travel algorithm

Question

I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has.

Say I have a matrix like:

$$ \begin{array}{|r|r|r|} \hline \hphantom{-}1 & -1 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array} $$

I know that the sum of each element of the matrix is zero.

And an operation $f$ which sums two elements of the matrix together and replaces both of them with this sum. In our example $f( a_{1,1} a_{1,2} )$ (where $a_{r,c}$ is the element of the matrix at row $r$ and column $c$) would lead to

$$ \begin{array}{|r|r|r|} \hline \hphantom{-}0 & \hphantom{-}0 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array} $$

The cost of this operation is the Manhattan distance between the two points, in this case $1$.

Now, I want to find the moves that:

• make each element of the matrix go to $0$
• minimize the total cost

Is there an algorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!

Answer 1

You could always try the A* algorithm. It might not be optimal but it is something you could try, and depending on how big the matrix is it might be good enough. You'll need to design an appropriate heuristic (e.g., maybe the number of elements that are non-zero, divided by two?).