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?

Acetyl

Are you looking for the optimal solution? Or can do for heuristics? Seems like Gentic Algorithms and/or Hill Climbing can bring a decent result quickly\ – Marseillaise

@fordprefect For the problem to make any sense, a needs to be less than 4b, since 4b is the maximum cost you can avoid paying by changing a cell. Edit: Whoops, ninja'd. Oh well, leaving this here. – Cabbageworm

@Jack Newton could you provide any image of binary matrix. How could matrix consists of 4 neighbors instead of 8? – Emergency

I think he's referring to the top, left, right, and bottom neighbors. – Anemology

@EAGER_STUDENT That just comes from defining neighborhood to be 4-connected rather than 8-connected. I.e. the neighbors are the cells up, down and to the sides, and not along diagonals. See this. (It talks about pixels, but the same concept applies.) – Cabbageworm

@ImreKerr How is the time-complexity calculated as ` O(2 ^ (n * n))` – Emergency

@Marseillaise yes I am looking for optimal solution – Acetyl

@EAGER_STUDENT we have n * n cells and each cell can be changed or not so for each cell we have 2 possible ways so we can find all 2 ^ (n * n) ways of changing the matrix and compute the cost of each of them. – Acetyl

How good are you on algorithms? It sounds to me like this could apply for a dynamic programming solution, but that would require certain expertise and/or reading. – Eusebiaeusebio

@Eusebiaeusebio actually I used dp and reached an algorithm O(2 ^(2n)) but it is not still eifficient – Acetyl

@Jack Newton Could you please do a rough explanationof how you designed your dp matrix? :) – Eusebiaeusebio

Are your costs $a and $b really variable, or are they fixed? If they are fixed, then knowing the values could result in drastically simpler solutions. For example, if $a >> $b, then the solution is to not change any cells. If $a << $b, then the solution is to change all cells to the same value. For some values of $a and $b, you could just loop over the matrix again and again, and change each cell where the "neighbor cost" of that cell is greater than the "change cost", and the total cost will eventually reach a global minimum. For other values of $a and $b, this method might not work. – Hypogeal

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.

Katlynkatmai

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

Eusebiaeusebio