Christofides’ Algorithm

https://www.wired.com/2013/01/traveling-salesman-problem/

In the past mathematicians would try and solve the traveling salesman problems for hours end . It might be easy to solve a traveling salesman problem with five stops but realistically the more stops the longer it will take. It makes more sense to create a system to have a computer solve this algorithm.   “A 49-city map in the 1950s, a 2,392-city map in the 1980s and a 85,900-city map in 2006 — no one has devised an algorithm that can efficiently solve everytraveling salesman problem. According to a landmark paper published in 1972, such a solution might not even be possible. Computer scientist Richard Karp, of the University of California at Berkeley.” The image below is the largest traveling salesman problem solved, was solved using this algorithm, 85, 900- city route was done in 2006 and is nearly impossible without the use of a computer solution. 

Leave a Reply