This site requires JavaScript, please enable it in your browser!
Greenfoot back

Report as inappropriate.

TheGoldenProof
TheGoldenProof presents ...

2018/8/13

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.

367 views / 9 in the last 7 days

Tags: simulation physics demo with-source math

open in greenfoot
Your browser does not support the canvas tag.
A new version of this scenario was uploaded on 2018-08-13 22:02:11 UTC Added ALOT of documentation because I couldn't even figure out what my code did and I was the one who made it!
Super_HippoSuper_Hippo

2018/8/14

You distance method should be "return Math.hypot(x1-x2, y1-y2);". To test that your method doesn't work, execute this line: System.out.println(2^2); It prints 0 and that's not what you want to do. ^ is the XOR in Java, not the for powering a number. To calculate 2^2, you would need to use Math.pow(2, 2). The hypot method is a shortcut for Euclidian distances (= square-root of the sum of squared distances in each direction).
Super_HippoSuper_Hippo

2018/8/14

I just saw this image here https://i.gyazo.com/a5aeacfa6056d5a15af753f781274b06.png and noticed that something had to be wrong with the calculation of the shortest distance.
Super_HippoSuper_Hippo

2018/8/14

Oh, it is also not really needed that the calculation is done every act-cycle. You only need to execute it once (or once every time something changed).
1: I had no Idea about the XOR thing. I didn't think the distance values sounded right. Thank you for that. 2: Yeah I know its not really needed and its poor code on my part but I spent way longer and way more mental energy making this than i planned to so I just left it.
A new version of this scenario was uploaded on 2018-08-15 23:43:39 UTC Turns out my distance formula was completely wrong. The distance formula is fixed now thanks to Super_Hippo but the algorithm still doesn't work, and likely never will.
A new version of this scenario was uploaded on 2018-08-15 23:43:48 UTC Turns out my distance formula was completely wrong. The distance formula is fixed now thanks to Super_Hippo but the algorithm still doesn't work, and likely never will.

Want to leave a comment? You must first log in.

Who likes this?

No votes yet.