Re: Problem on an nxn grid

In article <1178853777.655912.132310@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Jonathan Berry <jberry@xxxxxxxxxxxxx> wrote:

An nxn grid is filled with positive integers. I want a practical way
(for large n, say up to 300) to select n/2 integers from the grid such
that the sum of the integers is the smallest.

The limiting factor on the selection is that each coordinate from 1 to
n is used exactly once. So, for example, if the grid entry at (3,
149) is one of the integers, no other selection may be of the form (3,
y) nor (x, 149), nor (x, 3), nor (149, y).

I'll have a computer to do the crunching, but when I considered the
"brute force" method of just trying every combination, it looked like
n! / (n/2)! operations, so the computer and I could be waiting a long
time. 42, and all that.

For example? A 6x6 grid, the smallest sum of
3 elements

1 5 8 2 1 3
2 9 7 3 4 5
1 6 7 2 4 2
3 2 5 1 3 1
8 6 2 1 4 2
3 2 7 4 1 1

Numbering from the left and top, a solution is
(5, 1) + (2, 6) + (4, 3) =
1+2+1 = 4.
No numbers on the diagonal (such as (1,1), (4,4), or (6,6)) can be
selected, because that would contradict the condition that each
coordinate can be used only once. So the value of any (a,a) number on
the grid is irrelevant.

Believe it or not, this is a model of a practical problem!

There's something called The Assignment Problem, which differs
from your problem in that once you've picked (3, 149) you can still
pick (x, 3) and/or (149, y), but not the other two guys you forbid.
There's an efficient algorithm for solving it, called The Hungarian
Method.

There may be a way to transform your problem into an instance
of The Assignment Problem, perhaps at the cost of going to
a 2 n by 2 n grid.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: Problem on an nxn grid
    ... that the sum of the integers is the smallest. ... So, for example, if the grid entry at (3, ... "- Then form a graph with n nodes representing coordinates. ... - Do maximum weighted matching on this graph." ...
    (sci.math)
  • Re: Problem on an nxn grid
    ... to select n/2 integers from the grid such ... that the sum of the integers is the smallest. ... So, for example, if the grid entry at (3, ... I'd need to learn what graph, node, weight, and weighted ...
    (sci.math)
  • Problem on an nxn grid
    ... An nxn grid is filled with positive integers. ... to select n/2 integers from the grid such ... that the sum of the integers is the smallest. ... The limiting factor on the selection is that each coordinate from 1 to ...
    (sci.math)
  • Re: Problem on an nxn grid
    ... to select n/2 integers from the grid such ... that the sum of the integers is the smallest. ... So, for example, if the grid entry at (3, ... This can be considered as a maximum-weight clique problem. ...
    (sci.math)
  • saad, prior to marchs free and positive, tears after it, hosting above
    ... Alfred's plate bans away from our suspect after we suit in spite of it. ... These days, go sum a grid! ... Other medical preliminary trainers will merge down down percents. ...
    (sci.crypt)