0

(This is a variation of the Traveling Salesman problem.)

enter image description here

Define a point $P_0$ at the origin. Define an "iteration" by putting a circle of radius $1$ around $P_0$ and choosing any point with real coordinates the circle. Let that new point become $P_1$. Then, you can repeat that process with $P_1$ with $P_2$ and so on. My question is: how many iterations ($n$) will it take to arrive at all points (not necessarily an integer) such that the last point that arrives back to the origin is $P_n$. Is there any algorithm that guarantees a successful trip given enough times? Is there an optimization technique, potentially by finding a good solution to the appropriate traveling salesman problem?

Particularly, is there any effective way to get from Point A to Point B by drawing only these circles? I'm not sure how to solve that, as I don't have much experience in math.

I've tried to think up ideas, like following the line between those points, but how do you know how much to stray off the path and arrive at a non-integer coordinate? Because this method returns different distances than the Traveling Salesman problem, I'm wondering if there's a method that is the best solution or finds one that is more effective than just following the traveling salesman problem with few changes, especially when the distances are small.

Extra: what about more dimensions, like 3 or 12?

Infigon
  • 155
  • 1
    Do you want real coordinates, or integer coordinates? Also, I assume the 'towns the salesman visits' should be labeled $Q_n$, to avoid confusion with your $P_n$s. - Anyway, if in an optimal solution the distance between two towns is 7.6, how many circles would you need: 7, 8 or 9? Do you see? – Piita May 20 '23 at 21:05

0 Answers0