Po stopách obchodního cestujícího – Cook William (2012)

Imagine you have a list of cities you need to visit, each once, and at the end of your journey, you want to get back home. How do you find the shortest route? This is the essence of the traveling salesman problem. It's very simple, and the solution surely is too - we just try all the routes and pick the shortest one. But there's a catch: even with 85 cities, there are more routes than there are atoms in the visible universe. That's probably unmanageable. Finding the shortest connection between many points is used in a variety of fields, from microchip manufacturing to planning the movement of the Hubble telescope, and by employing advanced search methods, tens of billions of dollars are saved annually. However, for mathematicians, perhaps the more important fact is that solving this problem would simultaneously overcome one of the seven greatest mathematical problems for the third millennium - P versus NP. In 2000, the Clay Mathematics Institute offered a reward of one million dollars for a solution to each of these problems, and this is also a reason (albeit a secondary one for altruistic mathematicians) why hundreds of the planet's best minds have been working on it for several decades. The theme of the book is presented at a high level of expertise - its author belongs to a select group of the most significant figures...