Instructor: An industrial engineering master’s student working for
me says that this exercise is a classic in his major. IE people
specialize in scheduling. I asked him to explain it to you. This is
what he said about the exercise. NOTE: this explanation is for your
background only. It does NOT apply to this exercise.
The Traveling Salesperson Problem (TSP) is a deceptively simple
combinatorial problem. It can be stated very simply. A salesperson spends
Many TSP’s are symmetric — that is, for any two cities A and B, the distance
from A to B is the same as that from B to A. The same tour length will be
A salesperson has to visit “n” cities and return to his city of origin. Each city
You are a salesperson, and you must visit 20 cities spread across North
The answer is that there is no simple answer. Reasonable people will make a
reasonable choice and accept a reasonably short path.
However, there is only one way to 5nd the absolute shortest path, and that is
How many orderings are there? They can be counted this way:
For the first city to visit you have 20 choices.
For the second city to visit you have only 19 choices (because you can’t
orderings which equals
2,432,902,008,176,640,000 possible orderings. Wow!