Re: Problem on an nxn grid
- From: Chip Eastham <hardmath@xxxxxxxxx>
- Date: 11 May 2007 08:47:00 -0700
On May 10, 11:22 pm, Jonathan Berry <jbe...@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!
TIA.
--
Jonathan Berry
It's an interesting problem, so I admit it's a petty
observation to point out that your solution of the
example problem is incorrect. It is customary
to provide the row coordinate first and column
coordinate second, but for consistency I'll try
to use your notation.
You say the grid entries are numbered from the
top and left, so presumably your (5,1) entry
is claimed to be 1 based on the 5th column,
1st row being 1. Likewise the claim of (2,6)
entry being 2 appears to correspond to 2nd
column and 6th row. But neither (4,3) entry
interpreted as 4th column, 3rd row nor vice
versa contains an additional 1 (though a 2
appears in the 4th column and 3rd row).
Perhaps you had these entries in mind
which give a minimal sum of 4:
1st col, 3rd row = 1
2nd col, 4th row = 2
5th col, 6th row = 1
The minimal solution is not unique, for example:
1st col, 3rd row = 1
2nd col, 6th row = 2
4th col, 5th row = 1
A slightly more useful observation: Without
loss of generality, you may symmetrize the
grid by replacing A(i,j) by the least of A(i,j)
and A(j,i) for all distinct i,j. This follows
from the observation that in any feasible
choice of n/2 entries, replacing A(i,j) by
A(j,i) is again feasible (no duplicated
coordinates).
It appears that branch and bound methods
for these problems will be effective. If you
have a "real world" size problem you'd like
me to tackle, email me and I'll try a quick
Prolog program on it.
regards, chip
.
- Follow-Ups:
- Re: Problem on an nxn grid
- From: Jonathan Berry
- Re: Problem on an nxn grid
- References:
- Problem on an nxn grid
- From: Jonathan Berry
- Problem on an nxn grid
- Prev by Date: Re: Cantor Confusion
- Next by Date: Re: Cantor Confusion
- Previous by thread: Re: Problem on an nxn grid
- Next by thread: Re: Problem on an nxn grid
- Index(es):
Relevant Pages
|
