The Traveling Salesman Problem.

[NickKemaev]

 

Gentlemen, please don't take this as impudence, but could you tell me how to make sure that the paths don't cross?

[terryhendicott · Accepted solution]

Hi,

QED

Cheers

Terry

[NickKemaev]

Thanks terryhendicott, I wanted to return to the starting point, is this also possible without crossing?

[terryhendicott]

Hi,

Yes it is possible with the following algorithm.

Find convex hull of points

Select lowest point on convex hull as starting point

Seperate out clockwise part of convex hull from highest point to lowest point

of remainder of points including anticlockwise convex hull sort into y order

join lines from lowest to highest "y" then come clockwise down the convex hull to the starting point.

This would mean the convex hull of a series of points needs to be implimented.  

Such an impimentation would take time I don't have.

Cheers

Terry

[Werner_E]

Hmmm, I guess you may run into some kind of "crossing" if two or more points have the same y-coordinate, right?

And as far as I see there is no attempt to find a way of minimum length.

[Werner_E]

Just for the sake of completeness and fairness, perhaps the original source of the posted sheet should be given

Travelling Salesman Problem - Valery Ochkov

(This is just the first thread I found - Valery had posted the sheet in slight variations on several occasions.)

As for the crossing paths (which clearly shows that Valery's algorithm is not finding the minimal path) you may create a program which finds all offending crossing segments and apply the substitution as shown in Fig. 6.26 here: https://web.mit.edu/urban_or_book/www/book/chapter6/6.4.7.html

Quite some work to do, as you would have to compare all combinations of two segments and check for crossing and as usual the most work would have to be done to cover the special cases (like two segments cross in one of the four involved points or the four points being collinear, etc.). Furthermore care must be taken choose the correct one of the two possible substitutions for each pair of crossing segments (as otherwise the continuous path would be split in two). Moreover 'uncrossing' a pair of crossing line segments may result in created new pairs of crossings segments, so I guess its not the easiest way to work starting from a path already created by an algorithm like Valery's.

[NickKemaev]

Thank you, Werner_E, I certainly saw Valery Ochkov's solution to this problem, actually this is his solution, he asked there whether it was possible to do this without crossing the lines, but there was no answer from him or anyone else, that's actually what I wanted to know. Thanks again for participating.

 

[NickKemaev]

Here is a genetic algorithm for 30 points, although this is also a random option, and I would like it to be constant without line intersections.