2
$\begingroup$

I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6x8 on which I am attempting to arrange 48 color swatches, such that the transition from each swatch to its neighbor is as smooth as possible.

I can compute perceptual color differences using LAB-space encoding, so it is simple to generate a matrix of color differences. If I were attempting to simply order these colors, it would essentially be the traveling salesman problem; and I could use some heuristic solutions to get a near optimal result.

However, arranging the colors into a grid introduces a new dimension. In the interest of symmetry, we can wrap the edges of the grid so that each swatch has exactly 4 neighbors.

I have a hunch that this problem reduces to the following graph problem: Given a fully connected weighted graph of 48 nodes, find a subset of this graph such that the resulting graph is fully connected, each node has exactly 4 edges, and the sum of edge weights is minimized.

Any ideas on existing algorithms that might be helpful in solving this problem? Approximate solutions and heuristic solutions are acceptable as I imagine this problem is in EXP.

$\endgroup$
7
  • 1
    $\begingroup$ The 4-connected graph problem is too unconstrained: Not every 4-connected graph corresponds to a wrapped-grid graph. E.g. make 2 wrapped-grid graphs, each on 3x8 vertices, then pick a "wrapping edge" in each one of them (say, $ab$ in the first and $cd$ in the second) and swap the endpoints (to make, e.g., $ac$ and $bd$) -- this new graph is still 4-connected but is not in general a wrapped-grid graph. $\endgroup$ – j_random_hacker Oct 26 '19 at 12:26
  • 1
    $\begingroup$ I would try local search using simple operations like swapping two randomly chosen positions and seeing whether the cost is now lower, and keeping the swap if so. Starting from a random arrangement, repeat this many times until you see no further improvements, then start from a new random arrangement. Do this a few times and pick the best overall. Other operations you could try include horizontally or vertically flipping random segments, and rotating random square segments. Easy to code and might get you some nice solutions :) $\endgroup$ – j_random_hacker Oct 26 '19 at 12:31
  • $\begingroup$ @j_random_hacker thanks, yeah, realized that in my sleep last night. I think you might be right on an iterative optimization solution; probably the best way to go... $\endgroup$ – Kevin Dolan Oct 26 '19 at 20:31
  • 2
    $\begingroup$ One approach worth trying is encoding this problem as an integer program and solving it with some integer programming solver like CPLEX, GLPK, SCIP or Gurobi. The solvers might be able to produce provably optimal solutions in practice even though the problem is theoretically very hard. $\endgroup$ – Laakeri Oct 27 '19 at 9:26
  • 1
    $\begingroup$ As a note on the theoretical hardness of this problem, a case with 1xN grid is equivalent to the traveling salesperson problem, so it is NP-hard. (I also believe that for any K, the KxN case is NP-hard). This problem also is clearly in NP. $\endgroup$ – Laakeri Oct 27 '19 at 9:30
2
$\begingroup$

You can solve the problem with any solver for the Quadratic Assignment Problem (QAP). In the traditional QAP, facilities are assigned to locations such that the cost of transporting necessary goods between any two facilities is minimal. QAP is NP-hard.

Here we assign the colors $C$ to the swatches $S$. The weight or flow $w : S \times S$ between the locations is $1$ if they are neighbors and zero otherwise – you may define neighborhood however you like. The distance $d : C \times C$ would be LAB-metric you already defined.

$\endgroup$
1
  • $\begingroup$ That's a very clever solution! It also opens the door to a lot of other alternative reformations. Love it! $\endgroup$ – Kevin Dolan Nov 8 '19 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.