6
$\begingroup$

I'm curious if somebody has already figured this out. Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling salesmen problem is known a priori, and such that we have a uniform distribution on the set of points? For example, I can think of an algorithm that will generate such a sequence by plotting a polygon, and the minimum distance would be the points going around the outside of the polygon, but the distribution on point-sets from this algorithm is highly biased.

So I would hope for an efficient algorithm that generates a set of points in $[0,1]^2$ (and its corresponding TSP solution), with equal probability to any set of points, i.e., each point has iid uniform distribution on $[0,1]^2$. You could interpret "efficient" as "polynomial time".

PS: I strongly suspect that no algorithm could exist because if so, I imagine the problem would be solvable, so in this case, is there a database somewhere with a large number of solutions for randomly generated sets of points?

$\endgroup$
12
  • 1
    $\begingroup$ But TSP is solvable, so yes, there is an algorithm: just generate sets of points, brute-force solves TSP on them and outputs the set and solution. I suspect you need to insert "efficient" or "in polynomial time" in a few places in your question. And, as you say, it looks like the solution for convex point sets is trivial so those could be output efficiently: why isn't that an answer? Are you looking for an algorithm that outputs all possible point sets and their solutions? Also note that the problem on random inputs might look very different: it's possible for a problem to be easy... $\endgroup$ Aug 3, 2018 at 13:36
  • 2
    $\begingroup$ with equal probability to any set of points in $\mathbb{R}^2$ This isn't defined. $\endgroup$ Aug 3, 2018 at 13:37
  • 3
    $\begingroup$ Also there are ways to generate (instance, solution) pairs efficiently even if it is likely hard to compute the solution from the instance. For example, if the problem is factorization, you can choose random factors and multiply them whereas there is no known efficient way to obtain the factors from the product. So I believe the intuition in your PS is flawed. $\endgroup$ Aug 3, 2018 at 13:38
  • 1
    $\begingroup$ So what you are asking for is a test generator for the TSP problem, an algorithm that produces problems with known solutions, so you can test whether a TSP solver does indeed find the shortest tour. I could imagine that such an algorithm can only efficiently find problems that are easy to solve. $\endgroup$
    – gnasher729
    Aug 3, 2018 at 23:59
  • 1
    $\begingroup$ Regarding your PS, sometimes we can "plant" a solution in such a way that someone who doesn't know the planted solution can't find it. This is the situation for the planted clique problem, in which we construct an instance with known maximum clique, but for appropriate parameters, this clique will be hard to find. $\endgroup$ Aug 26, 2018 at 16:08

2 Answers 2

1
$\begingroup$

For posterity and because I never received any answers in the end: my best guess is $\forall x_0 \in [0,1]^2$ was to pick any point $x_1 \in [0,1]^2$, then generate a second point $x_2$ such that the interior angle between the line between $x_0$ and $x_1$ is greater than 90$^{\circ}$ and less than 180$^{\circ}$. Now I can see two paths forward, one is to make a sort of quasi convex structure (obviously not every solution) by alternating whether the angles are interior or exterior and staying within the bounds. The solution is then $x_{0,...,n}$ for the minimum path.

The second possibility would be to put restrictions on the distance from the last point to the next point, (say halving each time) and again requiring the angle to be constrained, but perhaps this time we can loosen the constraint to greater than 90$^{\circ}$ and less than 270$^{\circ}$ and just require that we cannot cross a line we've already made. I can't guarantee this algorithm will always generate the correct solution, however I can guarantee that it won't generate all points in $[0,1]^2$, so the question remains unfortunately unanswered.

And for the PS in my original question: this might be a good place to get started for those looking.

$\endgroup$
1
$\begingroup$

Maybe you could find an algorithm that generates problems, and good, but not optimal solutions. So a TSP algorithm should find a solution that is as good or better than the optimal solution, and if it fails to do so, then it is not optimal.

To do this, you might start with n points and a purported optimal solution, then generate a point n+1 at random and spend some polynomial time to insert it into the solution for n points, which would tend to give a good solution. Then you use your TSP algorithm for the n+1 points. If it's worse than your good solution, then it's not optimal. If it's better than your good solution, maybe you can remove point n+1 and find a better solution to the n-point problem.

$\endgroup$
1
  • $\begingroup$ This is a very interesting idea to methodically create some sort of second best solution $\endgroup$ Nov 13, 2019 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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