The so-called "Traveling Salesman" problem is simply, "what is the shortest round trip through each of N cities, visiting each exactly once?" While it may sound trivial, this problem represents one of a broad class of problems called NP-complete problems, problems that arise in the design of communication networks, robotics, and elsewhere.
The applet below solves a fairly small problem with eight cities. It always starts with city number zero. There are seven ways to choose the next city; then, there are six ways to choose the next city, and five for the next, and so on. This continues, so there are 7*6*5*4*3*2*1 = 5040 ways to choose the round-trip route. The initial algorithm used below, the "Naíve algorithm," simply tries all of these routes in order. Actually, it only needs to try half that many because each of the 5040 permutations include only half that many unique routes, e.g., 0-1-2-3-4-5-6-7-0 is the same as 0-7-6-5-4-3-2-1-0 in reverse.
The applet shows the current path and its length, the best path and its length, a visual representation of both current and best paths, and at the bottom, a button for switching between the Naíve algorithm and the "Greedy algorithm." A pure greedy algorithm is deterministic, choosing as the next city in a path the one that is closest to the current city, provided it hasn't been visited yet. For example, given New York, Boston, Chicago, and Los Angeles and NY as the starting city, the pure greedy algorithm would always choose Boston next, Chicago, and finally Los Angeles. The non-deterministic greedy algorithm used below chooses cities at random, but with probabilities assigned based on distances, more for closer and less for more distant cities.
Try running the eight city case for a while and then change to the greedy algorithm. The solution to this case takes about 2.5 minutes to run through all the distinct routes. Reload and see how fast the greedy algorithm takes. The solution is <0-4-3-5-7-1-2-6-0>, length 1042.