# An amusing problem to solve

I was thinking about coding questions, and how you would write a coding question that tested peoples’ ability to explore algorithms in areas they weren’t likely to be that familiar with without necessarily being able to come up with optimal solutions.

I mulled over this a bit and came up with one which is entirely too evil to use. However I rather feel like I’m going to have to try to implement it anyway because it’s going to bug me. I figured I would inflict this on the rest of you, because misery loves company.

The problem is this:

You are given a non-negative symmetric $$n \times n$$ matrix $$A$$ with $$A_{ii} = 0$$, with real numbers represented as double precision. This is your potential matrix.

Find an assignment of coordinates $$x_1, \ldots, x_n \in [0, 1]$$ that has a low value for the energy function $$E = \sum\limits_{1 \leq i < j \leq n} \frac{A_{ij}}{|x_i – x_j|}$$. You are not required to minimize it, but if you can that would be lovely.

Some initial thoughts on how one might solve it:

1. Any optimal solution for a non-zero $$A$$ assigns at least one point to 0 and at least one point to 1.
2. For any given starting position there is a relatively straightforward gradient descent algorithm to find a local minimum
3. If $$A_{ij} > 0$$ for all $$i \neq j$$ then there are at least $$n!$$ local minima.
4. If you’ve placed $$k$$ items and you want to place a $$k + 1th$$, as long as it has a non-zero coordinate in $$A$$ with at least one of the items you’ve placed so far there is a unique place to put the k+1th item (though finding this is O(k)). This probably makes a greedy algorithm quite productive for smallish $$n$$.
5. If the graph with edges $$\{ \{i, j\} : A_{ij} \neq 0\}$$  is not connected you can run the problem separately on each component and merge the results, because they don’t affect each-other.
6. Some form of e.g. simulated annealing with the mutation operator being to swap pairs of elements then run a local optimisation would probably be quite productive.

As an additional comment: Trying to do combinatorial optimisation on permutations of indices is an exercise in frustration. Believe me, I know. This problem may prove more annoying than it’s worth.

This entry was posted in How do I computer?, Numbers are hard on by .