Traveling Salesman Problem: an Interactive Gizmo

Traveling Salesman Problem

The Traveling Salesman Problem (TSP) consists in finding a Hamilton Circuit on a weighted graph with the least total weight. The problem is usually posted on nearly complete graphs.

The applet below lets you practice with three algorithms used for solving the TSP: the Brute-Force, Nearest-Neighbor and the Cheapest-Link algorithms. The instructions for using the applet are available on a separate page and can also be read under the first tab directly in the applet.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

(This applet was created to accompany Excursions in Modern Mathematics, Seventh Edition, by Peter Tannenbaum © Pearson Education. Reproduced with permission.)

The Brute-Force algorithm consists in simply listing all Hamiltonean circuits (if there are any) and choosing one (perhaps of many) with the least total weight. The Nearest-Neighbor algorithm forms a path, one vertex at a time, choosing a node joined to the previous one with an edge of the least possible weight. The Cheapest-Link algorithm picks edges almost randomly among those of the least weight, subject to two natural restrictions: there should not be three selected edges incident to the same node and no circuits should be formed until the very last step.

71546598