Traveling Salesperson Problem: Software and Lab

The following are simple C++ implementations of various algorithms for solving small traveling salesperson problems exactly. All have a plain text-based interface. Only the source code is provided under the following links.

• tsp1.cpp carries out the basic brute-force TSP (traveling salesperson problem) algorithm to enumerate all the tours of the cities in order to find an optimal tour.
• tsp2.cpp uses the capability of backtracking to avoid recomputing the cost of a partial tour that has already been found. This reduces somewhat the number of additions used in finding the costs of the tours.
• tsp3.cpp also adds a simple branch and bound technique. Whenever a partial tour has a cost that is greater or equal to the lowest cost tour found thus far, the entire branch of the search tree that begins with this partial tour is eliminated.
• tspcombined.cpp carries out all three of the above TSP algorithms.
• Data files for use with the above programs.
• TSPLab.docx is a lab for students to time how long the above algorithms take to solve TSP problems with different numbers of cities, and to graph and analyze the results.

All of the above materials are made available under the following license: