Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Aug 01, 2024
12:26 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
12:26 AM

The Traveling Salesman Problem.

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

Solved! Go to Solution.

ACCEPTED SOLUTION

Accepted Solutions

Aug 01, 2024
04:08 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

7 REPLIES 7

Aug 01, 2024
04:08 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
04:21 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
04:21 AM

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

Aug 01, 2024
05:56 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
05:56 AM

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

Aug 01, 2024
08:22 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
08:22 AM

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.

Aug 01, 2024
08:23 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
08:23 AM

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.

Aug 01, 2024
09:47 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 01, 2024
09:47 AM

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.

Aug 06, 2024
06:04 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator

Aug 06, 2024
06:04 AM

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.