Finding minimum cost in a binary matrix

Question

Consider a n * n binary matrix. Each cell of this matrix has at most 4 neighbors (if it exists). We call two cells of this matrix incompatible if they are neighbors and their values are not equal. We pay $b for each incompatible pair. Also we can change the value of the cell with paying $a.

The question is to find the minimum cost for this matrix.

I already used backtracking and found an algorithm of O(2 ^ (n * n)). Can someone help me find a more efficient algorithm?

Answer 1

This idea is due to Greig, Porteous, and Seheult. Treat the matrix as a capacitated directed graph with vertices corresponding to matrix entries and arcs from each vertex to its four neighbors, each with capacity b. Introduce two more vertices, a source and a sink, and arcs of capacity a: from the source to each vertex with a corresponding 0 entry, and to the sink from each vertex with a corresponding 1 entry. Find a minimum cut; the entries with value 0 after changes are the vertices on the source side of the cut, and the entries with value 1 after changes are the vertices on the sink side of the cut.

The cost of this cut is exactly your objective. Of the capacity-a from-source arcs, the ones crossing the cut correspond to changes from 0 to 1. Of the capacity-a to-sink arcs, the ones crossing the cut correspond to changes from 1 to 0. Of the capacity-b arcs, the ones crossing the cut correspond to those instances where there is an arc from a 0 to a 1.

Answer 2

I would suggest you to reformulate your backtracking in order to use dynamic programming to trimm the backtracking tree. Here is the logic I propose to design it:

When deciding if you want or not to change a cell, it doesn't really matter how you assigned the previous cells, it only matters the accumulated cost, so you can keep track for each cell, and each possible accumulated cost, what was the minimum result already found. This way whenever you find the same configuration again, you will have the answer saved.

So your dp matrix would be something like:

dp[top_bound][n][n];

And before doing backtracking you should do:

if(dp[acc_cost][this_i][this_j] != -1)
    return dp[acc_cost][this_i][this_j];

// Perform your calculations
// ...

dp[acc_cost][this_i][this_j] = result;
return result;

Here I'm assuming -1 is an invalid value in the result, if not you just choose any invalid value and initialize your matrix to it. Since this matrix is of size n*n*top_bound, then a correctly implemented DP should solve the problem in O(n*n*top_bound).