Shortest distance problem in CC

The shortest distance problem in CC.

Hey guys, just created a quick program that creates 6 random points (numbering them 1-6, 1 being the start point and the rest 2-6, based on their number in the data table) and then draws a line from the start point to each point.

The challenge? Design an algorithm that calculates the shortest distance taken to go around to each point once. You don't have to finish at the start point, just get to each point once in the shortest distance possible.

This algorithm doesn't necessarily have to be scalable (only so many pixels..), but could probably be scaled up to about 20 points (lines would be an issue, however ignore that for now).





Best way I've found with this algorithm (so far) is that if you can tell the program to do a spiral of the points you will get the shortest distance about 9 times out of 10, at least. The way to do this would be to compare the X/Y of each object relative to the bounds of the points, then make your way in by calculating how many points are left on the outside (til there are none). Generally this is the fastest way in our heads but putting that in an algorithm will be slightly harder.

Not sure if you know about it, but you've designed the Travelling Salesman problem. It's a famous exercise in computer science.

apemanzilla, on 19 July 2017 - 06:36 AM said:

Not sure if you know about it, but you've designed the Travelling Salesman problem. It's a famous exercise in computer science.

Yeah, that's kind of what I was getting at on a smaller scale. It's a little less interesting in CC as there are only 51x19 pixels, but still, you could make some interesting algorithms with it.

Ported the program to Java (for increased pixels and workspace..) and came up with this, so far. All this does is calculates the nearest point from a given point and crosses the given point off the list, effectively resetting the starting point, until it finishes.

This is 1000 points (tested with 10 points, then shot it up to 1000 to see what would happen) and it worked quite well. You can see that there is almost a pattern there - and then it has the larger lines that go almost halfway across the screen at some points because of the lack of remaining points (can't see any neighbouring points so it looks further away until it finds one).