Almost a solution to the Traveling Salesman Problem

The Traveling Saleman Problem is this: There are some cities (or in this case points) that you have to go to. What is the shortest path that gets you to all of them?

My method of solving it:
I was watching a video by The Coding Train where he was making his solution to this problem. His approach was the brute-force-try-every-single-n!-possible-combinations approach. It worked, but it took a long time for higher numbers of points. It would have taken 16.8 hours just to find the best route.
I was thinking about the problem and this came to me:
pick a point, find the closest point, then find its closest point, etc. I tried this is my head it it quickly failed, but then I realized that those failures could be fixed if the starting point was changed.
So, this program
1: picks a point.
2: finds the closest point and its distance, finds the closest point to that point, etc.
3: Adds all the shortest distances.
4: repeats steps 2&3 for all the other points
5: compares the distance for each starting point
6: finds the shortest and displays it
However, it is sometimes wrong if the conditions are right.

To hide the gray lines:
Open the project in greenfoot, go to the Finder and open its code, then change showLines (near the top) to false

To hide the red path:
same thing but change showPath

To change the number of dots:
Open the code for the Background and change the value of n. (Note: the higher number, the more likely it is to be wrong.)

I tried to do it with buttons but greenfoot REALLY does not like this thing. Click act then try and drag something around and you'll see why.

1941 views / 21 in the last 7 days

Tags: simulation physics demo with-source math

Visit the web page for this scenario.