[Solved]: Correctness of the greedy algorithm

Problem Detail: 

I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of only 0's from it. A 1 in the sheet (represented by the matrix) indicates that we cannot cut the region out from the sheet. Given such a matrix, find the maximum number of blocks which can be extracted.

For instance, if the given matrix is:

There can be 2 blocks which can be extracted out of this.

My Solution:
I am using a greedy algorithm to solve the problem. I traverse from all the corners of the matrix (top-left, top-right, bottom-left, bottom-right) - one by one, extracting out the blocks on a first encountered first extracted basis. Finally I return the maximum of the 4 values that I get. From each corner, I traverse an entire row first (horizontally), only then I move up or down in the matrix.

The algorithm is as follows:

1) Starting from the top-left corner of the matrix (0,0), I iterate along all the columns in this row from left to right.   2) If a zero is encountered at a position (i,j), I check if this is a possible  contender to be the top-left corner of a 2x2 block consisting of all zeros - which would be the case when values at (i, j+1), (i+1, j) and (i+1, j+1) are all zeros.  3) If it is, I fill the 2x2 block {(i,j), {i,j+1), (i+1,j), (i+1,j+1)} with 1's, and a counter is incremented.  4) Steps 2 through 3 are repeated for all rows from the top to bottom.  5) I restore the original matrix in the problem, and start again from the top-right corner  of the matrix (0, N) - N being the number of columns in the matrix, and iterate along  all the columns in this row, from right to left.  6) If a zero is encountered at a position (i,j), I check if this is a possible contender  to be the top-right corner of a 2x2 block consisting of all zeros - which would be the  case when values at (i, j-1), (i+1, j) and (i+1, j-1) are all zeros.  7) If it is, I fill the 2x2 block {(i,j), {i,j-1), (i+1,j), (i+1,j-1)} with 1's, and a different counter is incremented.  8) Steps 6 through 7 are repeated for all rows from the top to bottom.  9) Likewise, the matrix is traversed two more times from bottom-left and bottom-right corners, checking for a '0', which can be a possible bottom-right or bottom-left corner for a 2x2 block consisting of all zeros. Each of these matrix traversals are performed on the original matrix given in the problem - i.e. changes made in top-left traversal are  discarded while traversing the matrix from top-right and so on.  10) The 4 traversals of the matrix give us 4 different counters, and the maximum of these 4 values is returned as the result. 

So far I have not been able to come with a test case which shows that the algorithm is incorrect. As I am not very good with proving correctness of algorithms, I need some help to figure out if this algorithm is correct.

Thanks!

Asked By : Abhigyan Mehra

Answered By : Yves Daoust

If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.

But there is an 8 blocks solution (on the right).

---

The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.

Repeating the search in different directions will not fix this, as it is possible to build symmetric patterns that result to the same behavior in all directions.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50265

 Ask a Question

 Download Related Notes/Documents