The Traveling Salesman Problem can best be described as planning a road trip throughout the country, where the driver (no doubt excited to undertake the 1000+ mile journey) needs to decide the route through various landmarks. The passengers wouldn't likely want to visit the same place twice, and they would probably want to find the shortest route through all the landmarks to make the most of their time.
Researchers have noted that the human mind, specifically the portion that deals with spatial reasoning, is good at finding optimal solutions to this type of problem in a reasonable amount of time (e.g. the amount of time it takes to plan a trip). Computers on the other hand, while able to find the optimal solution, would take an extraordinary amount of time to find it (factorial time). This is due to the fact that a computer program would attempt to test the total distance of every possible route in order to find the shortest route. It's crucial to note that this would hold true even with an arbitrarily small amount of places to visit.
Jason Brownlee decided to start an experiment testing just how well a person's spatial reasoning skills can be used to solve TSP problems. Disguised as a game, users would log into the application and attempt to find the shortest route going through all the points on a given graph. Anyone who finds a shorter route than the one already saved and posted earns points which are used to rank the user on a scoreboard.
I have open sourced the 'human tsp solver' web app and all collected data on github, have a look humanTSPsolver
ReplyDelete