An interesting problem
matt.lawrence at virgin.net
Thu Jan 4 09:59:00 GMT 2007
David Landgren wrote:
> 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
> 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
> coalesce them.
That's a much better description of the solution I was groping for earlier.
More information about the london.pm