- Click on the panel to place cites on the map (use the "Background" menu to select the background map).
- Drag a city if you want to move a city once you've placed it. Click once on a city and press the delete
key to remove it.
- To change the scale of the map (indicated in the top right corner of the window), select an edge by clicking
once on each endpoint and then pressing the Set Scale button (the third from the left on the top row). Enter
the length you want that edge to be, and all the other distances will rescale proportionately.
- Use the Clear button (the last button in the top row) to clear a circuit or erase an entire graph. When edges or a circuit
are highlighted, the clear button erases them, but leaves the underlying graph in place. When no edges are selected,
the Clear button erases the whole graph.
- The Greedy Algorithm:
Once you've placed some cities, click the Greedy algorith button (the fourth button from the left on the top row)
to find a Hamiltonian circuit using that algorithm. The total length of the circuit will show in the bottom row.
Advanced:
Click once on one city to highlight it, and then click once on another city. This will highlight
the edge joining them. Press the "+" button to force the Sorted Edges algorithm to include that edge
in your circuit. Often you can eyeball a graph and make some smart
guesses as to some of the edges that should be included in an efficient tour and then run the Sorted Edges algorithm
to fill in the rest of the details of the tour. A combination of your visual skills and the Sorted Edges algorithm
can produce much more efficient tours, and help the algorithm avoid inefficient choices.
- Nearest Neighbor Algorithm:
First, place some cities on the map. Next, click once on the city which you want to use as the starting point
for the nearest neighbor algorithm (the city, and all the edges leading out of it, will be highlit). Press the
Nearest Neighbor button (the fifth button from the left on the top row) and the edges in the circuit will
be displayed. The total length of the circuit will show in the bottom row.
Advanced:
Experiment with starting the Nearest Neighbor algorithm at different cities. Notice how the results you
get can vary depending on which city you start at. It's usually worth your time to run the algorithm once starting at
each city, and pick the shortest circuit you get. In fact the best thing to do with a large number
of cities is to run both Sorted Edges and Nearest Neighbor, and pick the shortest circuit.
- Brute Force Algorithm:
Place some cities on the map and then click the Brute Force algorithm button (the second button from the right on the top row). The calculator will find
the very shortest possible circuit, by examining all possible alternatives. Because the number of
paths that need to be searched can be huge, the method won't work for graphs with more than 8 or 9 cities.
Advanced:
Because the Brute Force algorithm always gives the very shortest possible circuit, you should try comparing the circuits you
get from the Brute Force method with the solutions the other algorithms give. Are the other algorithms always worse
than the Brute Force algorithm? Sometimes worse? How badly wrong?
|