| @dancastro: Yes, I realize that the solution you present here is more efficient than Knuth's "optimal" solution, but his is optimal for the model he considers. In his model (which, granted, is more of a toy question in graph theory than a serious question about geography), Montana is not adjacent to Utah; neither is Indiana adjacent to Tennessee, and you have to cover all of New England before passing through New York because you can't backtrack through New York to get anything you missed. Now, if you don't like those restrictions, you could change his graph by adding some more lines between states (add a line between Utah and Montana if you want), but you don't want to add *too* many more lines because you want the problem to be solvable. So you need to decide which lines to declare "impossible" for an optimal solution—for example, it's pretty certain that you won't want to go from Olympia to Tallahassee as one of the legs of your journey, so you don't include a line there. The trick is to include enough lines to give you all the options you might want to take, but not so many that the problem becomes too difficult to solve. The map Knuth uses is here: http://oi56.tinypic.com/2vi2rsg.jpg |
US States
Countries of Europe
Countries of Asia
