Traveling salesman problem The energy mule example is an instance of the well-known traveling salesman problem. It is not always possible to use brute force to solve the equations. Two algorithms found useful for large networks are:

(i) Nearest neighbor algorithm Begin at the starting node. Whenever at a node pick the next nearest unvisited node or neighbor. End at the starting node.

(ii) Cheapest link algorithm Step 1 Select an edge with the cheapest weight. Mark that edge.

Step 2 Select the next cheapest unmarked edge unless:

(I) The new edge completes a circuit,

(II) The new edge results in three marked edges emerging from a single node.

Step 3 Repeat Step 2 until the Hamilton circuit (closed loop through a graph that visits each node exactly once) is complete.

For Figure 10.4, find the cheapest route using (i) the nearest neighbor algorithm and (ii) the cheapest link algorithm. Comment on how well they do compared with an exhaustive search. Assume the starting point to be G.