When presented with a spatial configuration of food sources, the amoeboid Physarum polycephalum adapts its morphology to create an efficient path between the food sources which can also be viewed as an approximate solution to TSP. Benchmarks For benchmarking of TSP algorithms, TSPLIB is a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual printed circuits. Popular culture Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the U.S. government to solve the most elusive problem in computer-science history: P vs. NP. Solutions to the problem are used by mathematician Bob Bosche in a subgenre called TSP art. See also Canadian traveller problem Exact algorithm Route inspection problem (also known as "Chinese postman problem") Set TSP problem Seven Bridges of Königsberg Steiner travelling salesman problem Subway Challenge Tube Challenge Vehicle routing problem Graph exploration Mixed Chinese postman problem Arc routing Snow plow routing problem Notes References . . . . . . . . . . . . . . . . . . . Further reading External links at University of Waterloo TSPLIB at the University of Heidelberg Traveling Salesman Problem by Jon McLoone at the Wolfram Demonstrations Project TSP visualization tool NP-complete problems NP-hard problems Combinatorial optimization Graph algorithms Computational problems in graph theory Hamiltonian paths and cycles