An interesting problem
david at landgren.net
Wed Jan 3 23:09:55 GMT 2007
Dirk Koopman did write:
> If the area required is fixed (or otherwise determinate), I would have
> thought that doing a pass through the grid looking for the indexes of
> the largest number(s) and then doing trial solutions putting that index
> in all the positions of the area should be close.
This doesn't work. A large (most positive) number may occur near a
couple negatives, thus reducing its value, whereas a small patch of
lowly positives elsewhere in the grid happen to have a larger overall sum.
I studied this algorithm at school, god, over twenty years ago. If no
values are negative, there is only one solution: the entire matrix.
When negative values are present, one of the best heuristic solutions is
to choose an arbitrary point and expand the region one row or column at
a time (left, right, top or bottom) and stop when any additional
increase in dimension results in a overall smaller sum.
As time permits, you then start over again somewhere else in the grid,
until you consider a sufficient amount of the search space has been
In the final step, you sort the regions by row or by column to see if
there are any adjoining regions with the same dimensionality and
More information about the london.pm