University:
Winston-Salem Forsyth County Schools
Course:
AP Calculus AB
Academic year:

2014
Views:

174

Pages:

2
Author:

Skyla Potter

The Traveling Salesman Problem The Traveling Salesman Problem A really good algorithm for solving TSP’s in general would have to be both efficient (like the nearest-neighbor) and optimal (like the brute-force). Unfortunately, nobody knows of such an algorithm. 6.6 Approximate Algorithm We will use the term approximate algorithm to describe any algorithm that produces solutions that are, most of the time, reasonably close to the optimal solution. 49 48 The Traveling Salesman Problem The Traveling Salesman Problem Algorithm 3: The Repetitive Nearest-Neighbor Algorithm Let X be any vertex. Find the nearestneighbor circuit using X as the starting vertex and calculate the total cost of the circuit. 6.7 The Repetitive Nearest-Neighbor Algorithm 51 50 The Traveling Salesman Problem The Traveling Salesman Problem Algorithm 3: The Repetitive Nearest-Neighbor Algorithm Algorithm 3: The Repetitive Nearest-Neighbor Algorithm We compute the nearestneighbor circuit with A as the starting vertex, and we got A, C, E, D, B, A with a total cost of $773. 52 Repeat the process with each of the other vertices of the graph as the starting vertex. 53 The Traveling Salesman Problem The Traveling Salesman Problem Algorithm 3: The Repetitive Nearest-Neighbor Algorithm Algorithm 3: The Repetitive Nearest-Neighbor Algorithm If we use B as the starting vertex, the nearest-neighbor circuit takes us from B to C, then to A, E, D, and back to B, with a total cost of $722. 54 Remember we must start and end the trip at A– this very same circuit would take the form A, E, D, B, C, A. 55 The Traveling Salesman Problem The Traveling Salesman Problem Algorithm 3: The Repetitive Nearest-Neighbor Algorithm Algorithm 3: The Repetitive Nearest-Neighbor Algorithm The process is once again repeated using C, D, and E as the starting vertices with respective costs of $722, $722, and $741. 56 Of the nearest-neighbor circuits obtained, keep the best one. If there is a designated starting vertex, rewrite the circuit using that vertex as the reference point. 57