For these sizes, it looks like it will be very difficult to even get closer. Anyway, here are a couple of ideas.
When a cell needs to change from 0 to 1, I will write + , when I need to change in a different direction, I will write - , and when it needs to stay as it is, I’ll write either 0 or 1 (that is, whatever it is At the moment). So, for example, the instance of the problem in the OP question looks like
- - - 1 - - 1 + - 1 + + 1 + + +
Consider a lighter monotonous version of a problem in which we never change a cell twice.
- Usually many more moves are required, but gives a useful starting point and upper bound.
- In this version of the problem, it does not matter in which order we execute the moves.
- Simple options may be more effective as heuristics, for example. performing a small number of initial 0-> 1 moves, in which each cell
+ changes by 1, and possibly other cells also change, and then the series 1-> 0 moves to change / fix all other cells.
Safe change of problem
[EDIT 11/12/2014: The third rule is fixed below. Unfortunately, it can be used much less frequently.]
The following tricks never lead to the fact that the solution becomes suboptimal and can simplify the problem:
- Delete any rows or columns that do not contain
+ -cell or - -cell: no move will ever use them. - If there are identical rows or columns, collapse them: no matter what you do with this single collapsed row or column, you can make all rows or columns separately.
- If there is any row with only one
+ -cell and without 1-cells , you can immediately fix all + -cells in the entire column containing it with one 0 → 1, since in the monotone task it was not possible to fix this cell in the same 0-> 1 motion as any + -cable in another column. Similarly, rows and columns are swapped with one cell - and 0-cells.
Applying these rules several times can lead to further simplification.
Very simple heuristic
You can correct the entire row or column + or - -cells in one move. Therefore, you can always solve the problem with 2 * min moves (width, height) (there are 2 there, because we may need both 0-> 1 and 1-> 0 movements). A slightly better approach is to greedily find a row or column with most cells that need correction, and fix it in one move, freely switching between rows and columns.
Best possible movement
Suppose we have two + elements (i, j) and (k, l), where i <= k and j <= l. They can be changed in the same 0-> 1 motion exactly when both of their “opposite angles” (i, l) and (k, j) are either + or 1. Also note that if one or both of (i, j) and (k, l) are equal to 1 (instead of + ), they can still be included in the same move, although this move will not have an effect for one or both of them. So, if we construct a graph G in which we have a vertex for each cell and an edge between two vertices (i, j) and (k, l) whenever (i, j), (k, l), ( i, l) and (k, j) either either + or 1, a clique in this graph corresponds to a set of cells that can all be changed to (or to the left by) 1 in one move 0-> 1. To find the best possible a move - that is, a movement that changes the most possible 0s to 1s - we don’t really want the maximum size click on the chart; what we really want is the click that contains the largest number of + -cell vertices. We can formulate an ILP that will find this using the 0/1 x_i_j variable to represent whether the vertex (i, j) is in a click:
Maximise the sum over all variables x_i_j such that (i, j) is a `+`-cell Subject to x_i_j + x_k_l <= 1 for all i, j, k, l st there is no edge (i, j)-(k, l) x_i_j in {0, 1} for all i, j
Constraints prevent the inclusion of any pair of vertices from both if there is no edge between them, and the objective function tries to find the largest possible subset of + -cell vertices that satisfies them.
Of course, the same procedure works to find 1-> 0 moves.
(You’ll already have problems just building a graph of this size: with N and M about 1000, there are about a million vertices and up to a million million edges. And finding the maximum click is an NP-difficult problem, so it slows down even for graphs with hundreds of edges. ..)
Least possible moves
A similar approach can tell us about the smallest number of 0-> 1 (or 1-> 0) moves needed and at the same time give us a representative cell from each movement. This time we are looking for the largest independent set in the same column G:
Maximise the sum over all variables x_i_j such that (i, j) is a `+`-cell Subject to x_i_j + x_k_l <= 1 for all i, j, k, l st there is an edge (i, j)-(k, l) x_i_j in {0, 1} for all i, j
All that changed in the problem was that “without edge” changed to “edge”. Now it finds (maybe more than one) a set of maximum sizes of + -element vertices that do not share a border. No pair of such cells can be changed by the same 0-> 1 movement (without changing the 0-cell or - -cell to 1, which we prohibit in the monotonous version of the problem, because then it will be needed which will be changed a second time), therefore, however, many vertices are returned, at least many separate 0-> 1 moves are required. And since we requested the maximum independent set, no more movements are required (if more moves are required, there will be a large independent set having many vertices in it).