traveling salesman problem

views updated

traveling salesman problem (TSP) A well-known graph-searching problem. In practical terms the problem can be thought of as that of a salesman who wishes to perform a circular tour of certain cities, calling at each city once only and traveling the minimum total distance possible. In more abstract terms, it is the problem of finding a minimum-weight Hamiltonian cycle in a weighted graph. The problem is known to be NP-complete (see P=NP question).