Definition of traveling salesman problem in English:

traveling salesman problem


  • A mathematical problem in which one tries to find the shortest route that passes through each of a set of points once and only once.

    • ‘What is the expected path length L of the optimum travelling salesman problem tour in Euclidean norm?’
    • ‘A classic example is the travelling salesman problem, which entails working out the shortest route connecting a large number of points in space so that each is visited just once.’
    • ‘Furthermore the travelling salesman problem can be solved in linear time on a weighted 3-connected Halin graph.’
    • ‘These ‘ants’ are good for solving a classic algorithm problem, the so-called ‘travelling salesman problem.’
    • ‘The travelling salesman problem is quite simple: a travelling salesman has to visit customers in several towns, exactly one customer in each town.’
    • ‘In the travelling salesman problem, you have to find the shortest round trip visiting every town exactly once.’
    • ‘The travelling salesman problem is of fundamental interest to mathematicians and physicists, and has a number of practical applications, such as computer design.’
    • ‘Thus, you can, for example, set up a ring topology which can be used to optimize the classical travelling salesman problem.’
    • ‘The travelling salesman problem belongs to the large class of nondeterministic polynomial time complete problems.’
    • ‘Instead of starting with random collections of answers, such as the various routes in the travelling salesman problem, GP begins with random collections of mathematical operations and inputs: add, x, sine, multiply, y, and so on.’