So I've been looking for an explanation of a 2-opt improvement for the traveling salesman problem, and I get the jist of it, but I don't understand one thing.
I understand that IF two edges of a generated path cross each other, I can just switch two points and they will no longer cross. HOWEVER - I do not understand how I can determine whether or not two edges cross.
To make my question clear, this is what I've done so far: (I did it in java)
Point that represents a city, with an x and y coordinate.PointSet which has a set of Points contained in a List. PointSet called computeByNN() which arranges the PointSet in a fairly short manner through a Nearest Neighbor algorithm.So now I have a sorted PointSet (not optimal, but still short) and I want to do 2-opt on it. However, I don't know where to start. Should I check each and every line segment to see if they cross, and if they do, switch two points? I feel like that defeats the purpose of heuristics and it becomes a sort of brute force solution. Is there an efficient way to find if two segments of the tour cross?
I applogize if my question is not clear. I'll try to edit it to make it clearer if anyone needs me to.
If you like you can create a look-up table to detect crossed edges. For n = 1000, order 10^12 entries is obviously too extravagant. However you probably are most worried about the shorter edges? Suppose you aimed to include edges to about √n of the nearest neighbors for each node. Then you are only in the realm of megabytes of space and in any case O(n^2) preprocessing. From there it's a heuristic, so good luck!
Also will mention this can be done on the fly.