Add one more city and the number of routes explodes
A salesman has to visit every city exactly once and return to the starting point. Which order is the shortest? Click the canvas to place cities, then work out an order yourself or compare it against the computer's answer.
Why is it hard? With n cities there are (n−1)!/2 possible visiting orders. Five cities is an easy 12, but ten cities is 180,000 and fifteen is over 40 billion! Checking every route for a guaranteed optimum is out of reach even for a computer, so in practice people mostly use methods that find a "pretty good" answer fast.
Cities 0Possible routes -Current route length -
Click the canvas to place at least three cities (dots). They are connected automatically in the order you place them.