SECTION 13B HIGHLIGHTS
Assignment: Read about the Traveling Salesman Problem in Section 13B
of the text. Do pp. 727-730
RQ(2), BSC(9-13,20-23), WP(28).
Web Project #28 Link: The following link is a nice place to play with the
Traveling Salesman Problem.
TRAVELING
SALESMAN EXPERIMENTS
Vocabulary: Traveling Salesman Problem, Hamiltonian Circuit, Factorial, cycle, complete network, Brute Force Method, Nearest Neighbor Method.
Notes:
In this section you are introduced to a famous mathematical
problem known as the Traveling Salesman Problem. This is a problem that
is currently being attacked by mathematicians around the world. The
basic idea of the Traveling Salesman Problem is that a salesman wishes to visit
all of the cities in a sales trip and return home with a minimum amount of
travel. This problem is manageable if the number of cities is small, but
if the salesman is required to travel to as few as 30 cities it will be
nearly impossible to check all of the possible routes.
In the vocabulary of network analysis, the route taken by the traveling salesman is a Hamiltonian Circuit. A Hamiltonian Circuit is defined to be a circuit that passes through each vertex of a network exactly once and returns to the starting vertex. Unfortunately, except for a few cases, there is no known rule for efficiently determining if a network contains a Hamiltonian Circuit. Two networks that always contain Hamiltonian Circuits are cycles and complete networks.
The number of Hamiltonian Circuits in a complete network of order n is (n-1)!/2
To solve the Traveling Salesman problem you are required to find the shortest Hamiltonian Circuit in a network. One way to do this is to check them all. This process is known as the Brute Force Method. The Brute Force Method is a process goes from tedious to impossible as the number of vertices increases. You can get a reasonable (not necessarily the best) solution using the Nearest Neighbor Method. To use this method, begin at any vertex and move to the nearest vertex and continue this process until you get to the circuit is complete.
Skills to be mastered:
1. Determine the number of Hamiltonian Circuits in a complete network.
2. Apply the Brute Force Method to find the minimum cost circuit in
a network.
3. Apply the Nearest Neighbor Method to find a minimum cost circuit in a
network.
Traveling Salesman Activity
ACTIVITY