Problem on an nxn grid
- From: Jonathan Berry <jberry@xxxxxxxxxxxxx>
- Date: 10 May 2007 20:22:57 -0700
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!
TIA.
--
Jonathan Berry
.
- Follow-Ups:
- Re: Problem on an nxn grid
- From: Chip Eastham
- Re: Problem on an nxn grid
- From: asinop
- Re: Problem on an nxn grid
- From: Robert Israel
- Re: Problem on an nxn grid
- From: Gerry Myerson
- Re: Problem on an nxn grid
- Prev by Date: Re: t'Hooft's Nobel Lecture & Lubos Motl
- Next by Date: Substitution Tiling With Heptagonal Symmetry
- Previous by thread: Re: Representation N=sum(i=1->m,aixi^2)
- Next by thread: Re: Problem on an nxn grid
- Index(es):
Relevant Pages
|
