The Traveling Salesman Problem (TSP) is one of the more famous optimization problems in computer science. Its formulation is as follows: given a set of points (“cities”), what is shortest path that will visit each point once, returning to the first point after having done so? This can be easily compared to a salesman tasked with finding the shortest route between a number of cities, hence the moniker.
It is a relatively simple problem, but is classified under NP-hard, a category of problems which currently have no solution calculable in an efficient amount of time. This means that large TSPs must be solved using high performance computing, and beyond a certain number of points, they are not practically solvable at all. Despite this, an approximate solution may often be found using algorithms called heuristics; these yield solutions that can come very close to the optimal shortest path. There are many categories of TSP heuristics, all of which fall into the broad categories of “deterministic” and “probabilistic.” Deterministic algorithms, those with predictable behavior given any input, are better understood, and can consistently achieve approximate solutions within one percent of the optimal tour length; probabilistic algorithms show some potential, however, and yield competitive approximations in many circumstances.
Many probabilistic algorithms are based from natural, physical models; one heuristic, for example, approaches the distribution of cities as an ant colony might, while another uses models of the path taken by an amoeba toward a food source. The basis of the heuristic studied in this project is a model of physical process called annealing, a technique performed in metallurgy via rapid cooling of materials to enhance desired properties and reduce the prominence of defects. A classical algorithm simulating this process is compared with one empowered with quantum mechanics, introduced to simulate quantum tunneling to better solutions.
In this presentation, a leading deterministic TSP heuristic is quantitatively compared with two probabilistic algorithms: one classically modeling annealing and one empowered with quantum mechanics, introduced to simulate quantum tunneling to better solutions.
Simon Fink, ’17
Computer Sciencemovie Spider-Man: Homecoming 2017 trailer