1

Suppose you have an N x N matrix of element type T.

Let's say the eight neighbours of a given element E are the other cells in the 3x3 square with E at its center:

.......
.......
...XXX.
...XEX.
...XXX.
.......

X = neighbour

There is a commutative binary function f(a,b) on pairs of T that returns a float between 0.0 and 1.0. (f(a,b) = f(b,a) and f(a,a) = 0 for all a, b in T.)

We want to rearrange the elements of the matrix to minimize the total of f between neighbouring cells.

That is, we want to minimize totalf:

totalf = 0
for x in 1 to N
  for y in 1 to N
    for dx in -1 to +1
      for dy in -1 to +1
        totalf += f(M[x,y], M[x+dx,y+dy])

Any ideas? Is there a standard problem this is similar to?

Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
  • It is unlikely a generalist solution exists, besides brute-force. What other properties can be assumed? E.g., is T ordinal? Is function transitive? etc – Marat Jan 12 '22 at 21:48
  • Similar question: [Organizing felt tip pens: optimizing the arrangement of items in a 2D grid by similarity of adjacent items](https://stackoverflow.com/questions/63503229/organizing-felt-tip-pens-optimizing-the-arrangement-of-items-in-a-2d-grid-by-si); Research paper: [Exact solution of the 2-dimensional grid arrangement problem; Oswald, Reinelt, Wiesberg](https://www.sciencedirect.com/science/article/pii/S157252861200045X); – Stef Jan 13 '22 at 00:50
  • Unless you can find some interesting literature about the problem, a standard approach to such an optimization problem is local search. Start with a random position of the elements. Then, generate a random "small" permutation. If the permutation improves the position, then apply it. If it doesn't improve, then don't apply it. Do this repeatedly. To answer the question "would this small permutation improve the position?", note that you don't need to recalculate totalf from scratch! Just calculate the diff due to the swapped elements. – Stef Jan 13 '22 at 00:56
  • Once you've successfully implemented such a "local search" algorithm, read about [simulated annealing](https://en.wikipedia.org/wiki/Simulated_annealing), which is almost like local search, but better. Sorry, I don't have a better resource than wikipedia at hand. Then once you've read about simulated annealing, modify your local search algorithm to make it a simulated annealing algorithm. – Stef Jan 13 '22 at 00:58

0 Answers0