# Minimize Manhattan distance travel algorithm

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!

• What do you mean by "sums two elements"? Do you mean replacing the two elements with their sum? – Yuval Filmus Sep 27 '18 at 16:44
• What does (a1,1) mean? Do you mean the matrix element at (1,1)? What is a1? – D.W. Sep 27 '18 at 20:34
• @D.W. yes, with (a1,1) I meant the matrix element at (1,1). Sorry, I only write those on paper! – Frabetto Sep 28 '18 at 9:01
• @YuvalFilmus yes, replacing the two elements with their sum! – Frabetto Sep 28 '18 at 9:02
• I don't think replacing elements with their sum. Then [[0 1] [1 -2]] would not work. First move: [[0 2] [2 -2]]. Maybe just move one into another. Which satisfies your description. – rus9384 Sep 28 '18 at 22:58

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?).

• I cannot upvote as now, but let me thanks you here. – Frabetto Sep 28 '18 at 9:02
• @Frabetto You may not be able to upvote but you can accept the answer. – Solomonoff's Secret Jan 28 at 22:10