A network problem that can be formulated as a combinatorial optimization problem. A salesman has to visit a number of interconnected destinations. The problem is to determine the route that minimizes the total distance travelled.
Travelling salesman problem. The route illustrated would be appropriate for a travelling salesman in East Anglia, England.
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 travelling 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).