Results 1 to 2 of 2

Math Help - Tricky grid joining problem

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    1

    Tricky grid joining problem

    I have the following problem. Let's say I have a grid of values and that each point in this grid has two values associated with them. The numbers can be any positive number or 0. See figure 1. Now the challenge is to combine these grids so that each individual values has a sum of at least 3.
    That is, in the left upper corner: (1,4) can be combined with (6,1) to form (7,5), which is >3 for both values.

    - Combinations with closeby cells are preferred
    - But I they don't have to be connected

    Could anybody help me solve this problem? What kind of approach could I possibly use if I want to (possibly approximately) maximize the amount of cells (ie. each combination should yield cells that don't have values much larger than 3 for each value) and minimize the "area" over which each combination is spread out. I.e., close by combinations are prefered. I realze that there is a trade of between these two aims.

    If not a solution, could somebody point me in a direction on how to possibly solve this? Search-words, ideas, theories, similar porblems?

    Btw, my actual grid is huge, not anything like the toy example here.


    Code:
    +---+---+---+---+
    |1,4|5,5|1,1|4,5|
    +---+---+---+---+
    |6,1|0,0|2,2|2,2|
    +---+---+---+---+
    |5,4|5,5|1,1|0,0|
    +---+---+---+---+
    |0,1|5,5|6,7|2,5|
    +---+---+---+---+
    _one_ possible result:

    Code:
    +---+---+---+---+
    |   |5,5|  5,6  |
    +7,5+---+---+---+
    |       |  4,4  |
    +---+---+---+---+
    |   |5,5|    3,6|
    +5,5+---+---+   +
    |   |5,5|6,7|   |
    +---+---+---+---+
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2009
    Posts
    40
    Thanks
    5
    If you set up your Grid as a Graph data structure, you could modify Dijikstra's algorithm to solve this. You could actually implement a recursive algorithm, starting at a new Vertex after you have satisfied conditions for the Vertex you are starting at. The base cases would include grouping all vertices or attempting to group all vertices but being unable to do so.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Grid problem
    Posted in the Algebra Forum
    Replies: 7
    Last Post: May 10th 2011, 04:39 AM
  2. Problem with line intersection with grid.
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: February 22nd 2011, 07:15 PM
  3. Replies: 1
    Last Post: April 9th 2010, 05:09 PM
  4. nxn grid problem.
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: October 31st 2009, 08:00 AM

Search Tags


/mathhelpforum @mathhelpforum