World's most popular travel blog for travel bloggers.

[Solved]: Distribute numbers 1,N on a grid as evenly as possible

, , No Comments
Problem Detail: 

I'm working on a complex engineering problem that I've essentially reduced to this problem:

I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map each number to each cell so that the distribution (in a geometric sense) is as flat as possible. I'm still working on the definition of flat, but so far

  1. The average of the numbers of a cell and its nearest neighbours must be as close to $N/2$ as possible, for every cell.

  2. The average of the distance between a cell and each neighbour must be as large as possible.

If a cell has a number $n$ and its neighbour $m$ the distance between these neighbours is $min(|n-m|,N-|n-m|)$. It's essentially cyclical.

If $.$ represents a small number and # a large number I'm looking chessboard-like configurations like

.#.#.#.# #.#.#.#. .#.#.#.# 

I need to find the best configuration (or a very good one) without using brute force.

Can you point me to some good algorithms that may be useful for this problem? I could only get above-average results on my own.

In my problem $N\approx~500$ and there is no runtime constraint.

Asked By : Fequi

Answered By : ebracho

Simulated Annealing might work well for this problem.

The idea is to introduce a "temperature" component to your heuristic function to avoid getting stuck at local optima. Temperature corresponds to how willing the heuristic function is to accept an inferior arrangement. With simulated annealing, temperature starts off high and decreases until an optimal solution is found.

Here is solution to the Travelling Salesman Problem using simulated annealing

You can tinker with the starting temperature and its rate of change to try and find an optimal arrangement.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51631

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback