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:
1 -1 0
0 0 1
0 1 -2
$$ \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$f$ which sums two elements of the matrix together and replaces both of them with this sum. In our example f( (a1,1) (a1,2) )$f( a_{1,1} a_{1,2} )$ (where wit (ar,x)$a_{r,c}$ is the element of the matrix at row r$r$ and column c$c$) would lead to
0 0 0
0 0 1
0 1 -2
$$ \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$1$.
Now, I want to find the moves that:
- make each element of the matrix go to 0$0$
- minimize the total cost
Is there an algorhitmalgorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!
