I made a simple website to simulate some common algorithms to solve the travelling salesperson problem and recorded there effectiveness as well as there efficiency. Using a brute force approach i was only able to simulate with an n of 8 before the website crashed. With a nearest neighbour, 2op and 2op approach I was able to get n of 40~ but that was more due to the limitations of creating the graph visualisation. I recorded the amount of operations the algorithm performed and unsurprisingly the brute force approach is a factorial time program. Nearest neighbour has a time complexity of O(n^2) because for each node in the graph it has to look at every edge to see what one is the smallest. 3op and 2op use nearest neighbour as a base that they improve and while experimentally they take longer the time the worst case time complexity is still O(n^2) because at most n searches have to be performed. My implementation could be optimised for example the brute force approach could be cone in half the time because half the graphs are just the reverse of the other half but this wouldn't affect the worst case complexity. The inputs were randomly generated using a seed that the user enters this helps keep consistent comparisons between runs.
-
Notifications
You must be signed in to change notification settings - Fork 0
Fish4203/TSP
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
About
No description, website, or topics provided.
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published