| 释义 |
travelling salesman problem (TSP) (in graph theory) This is a situation similar to the minimum connector problem but the salesman wishes to return to the starting point (home) at the end, and so essentially the problem is to find a closed walk which visits every vertex and which minimizes the total distance travelled. In practice there can be unusual situations in which the most efficient route is to go A → B → A because to get to B from any other vertex, without going through A, is difficult. However, the problem is much easier to analyse if the assumption is made that every vertex is visited exactly once, and the problem reduces to finding the Hamiltonian cycle of minimum length. The travelling salesman problem is an NP problem with no known algorithm to solve it in polynomial time, but upper and lower limits are straightforward to find.
|