Timeline for Travelling salesman using brute-force and heuristics
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2019 at 18:12 | history | protected | Jamal | ||
| Dec 6, 2018 at 18:49 | comment | added | Apostolos | I see. I got a little dizzy but it's OK ... :)) | |
| Dec 5, 2018 at 17:38 | comment | added | Caridorc | @Apostolos to get an approximate idea consider that 20 factorial is 2.432902e+18 while 20^2 = 400. So while the brute-force algoritm that take time proportional to N! is only viable up to 12 (12! = 479001600 ~ half a billion) or something cities, because the factorial skyrockets like crazy, the optimized one that runs in time proportional to N^2 can handle up to 10000 (10000^2 = 10^8 long but feasible). So it can handle tremendously more cities while only making the route ~25% longer according to wikipedia | |
| Dec 5, 2018 at 17:20 | comment | added | Apostolos | Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :) | |
| Dec 5, 2018 at 14:36 | comment | added | Caridorc | @Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter | |
| Dec 4, 2018 at 23:08 | comment | added | Apostolos | Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it? | |
| Mar 14, 2018 at 17:33 | answer | added | Manuel Martinez | timeline score: 3 | |
| May 13, 2017 at 0:30 | comment | added | Akavall | optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman | |
| Mar 13, 2015 at 18:40 | vote | accept | Caridorc | ||
| Feb 19, 2015 at 0:30 | history | edited | nhgrif | [Edit removed during grace period] | |
| Feb 18, 2015 at 23:08 | comment | added | jonrsharpe | The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True. | |
| Feb 18, 2015 at 22:55 | answer | added | ferada | timeline score: 9 | |
| Feb 18, 2015 at 22:04 | history | edited | Jamal | CC BY-SA 3.0 | edited title |
| Feb 18, 2015 at 21:47 | history | asked | Caridorc | CC BY-SA 3.0 |