When1: 2001
Who: Scott Kirkpatrick [Kirkpatrick, Scott]
What: mathematician
Where: USA
works\ traveling-salesman problem [2001]
Detail: Salesmen want to travel shortest distance among cities, with no path duplication. What is the shortest path {traveling-salesman problem, Kirkpatrick} [2001]? Traveling-salesman problems are NP-complete. Number of possible paths is factorial of number of cities, divided by two, because trips can be in either direction. Tours are vertexes of N-dimensional polygons. Tours that differ by one city are near each other in N-dimensional space. Simulated annealing can find shorter paths but allow longer paths, to avoid local minima. Techniques can find good paths but not necessarily the best.
Mathematical Sciences>Mathematics>History>Computer Science
3-Mathematics-History-Computer Science
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0224