Re: Problem on an nxn grid

On May 11, 8:47 am, Chip Eastham <hardm...@xxxxxxxxx> wrote:
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

Thank you, Chip, for so gently pointing out the drawbacks in
my analysis of the example. I saw 2 at (4,3), but typed
1. Then I overlooked that there were two "other" solutions.
Kind of like a chess player giving away the queen, then both
rooks, in the same game. Or to warp another saw, "Make
up an example on the fly, then ... live with it".

I am not sure that your observation about symmetrizing
the grid is helpful to me. In the application that I have in mind
(which is the pairing of chess tournaments!), the important
part is the coordinates (and ij is importantly different from ji), not
in the value of the cells nor in the value of the sum, except that it
be minimized.

It is slightly concerning that there may be more than one solution,
but if larger numbers are used, then that becomes less likely.

Thank you, but I'll hold off on your offer of writing a Prolog program
for now. I'm trying to get everything under one "roof",
in PowerBASIC. But I may be out of my depth here. So
"for now" may be very short.

I only partly understood the algorithm described by Ali (Asinop). I'm
OK until:

"- Then form a graph with n nodes representing coordinates. Place
edges between nodes i and j (i<j) with weight a'_{ij}.
- Do maximum weighted matching on this graph."

I'd need to learn what graph, node, weight, and (maximum) weighted
matching are. And then translate that into plodding computer code.

Ironically, I do hold a Math bachelor's from the same institution
where Robert Israel teaches. You might call it a "No-More Analysis-My-
Head-Hurts" degree. Likely to his credit, my degree was granted while
he was still at Princeton.

--
Jonathan Berry

.

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)
  • 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)
  • 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, ...
    (sci.math)
  • Re: Sum column in GridView
    ... In the dotnet newsgroup we don't like it if somebody is asking almost the ... same question in diffferent threads in almost less than an hour. ... I'm using this function to sum the values of a column in a grid view and ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: iwidgets::tabnotebook & stuffing
    ... grid .nb -sticky news ... the centering effect you see is mentioned in this sentence: ... In your case you have the default weight of zero for both the row and column. ... the slave is centered within the master. ...
    (comp.lang.tcl)