I’ve been reading the book In Pursuit of the Traveling Salesman by William Cook lately. In Chapter 10, on “The Human Touch”, Cook mentions a paper, by James MacGregor and Thomas Ormerod, “Human performance on the traveling salesman problem”. One thing that this paper mentions is that humans reach solutions to the TSP by looking at global properties such as the convex hull — there’s a theorem that a tour must visit the vertices of the convex hull in order.
This reminds me of one of my favorite travelogues, Barry Stiefel’s fifty states in a week’s vacation, in which Stiefel visited all fifty states on a week’s vacation (doing the lower 48 by driving, and flying to Alaska and Hawaii) Stiefel writes, in regard to getting to Kentucky: Now things were going to get complicated. Until then, my route had been primarily one of following the inside perimeter of the states on the outside perimeter of the 48 states. When planning the route, I had stared at the map for over an hour before concluding that Kentucky was going to be the toughest state to get. I just couldn’t plan a route that efficiently went through it. So I had to do a several-hour out-and-back loop to get it.
It’s not obvious that Kentucky would be so hard. Kentucky borders Virginia and Ohio, both of which are on that outside perimeter, while a bunch of states further west don’t border any of the perimeter states. (By my eyeballing, those are Kansas, Nebraska, and Missouri.) Stiefel chose to approach Kentucky from the southeast, though, and southeastern Kentucky is not exactly crawling with highways. And as you might gather from the title of Stiefel’s page, he was in search of a shortest-time route, not a shortest-distance one.
God plays dice 
Reblogged this on nebusresearch and commented:
The ‘God Plays Dice’ blog here makes me aware of a really fascinating little project: in 1998, apparently, Barry Stiefel decided to use a week off work to see the United States. All of them. And by dint of driving with a ruthlessness I can hardly believe, he managed it, albeit with some states just barely peeked at from the road, with Kentucky surprisingly hard to get at. Stiefel also managed, in a 2003 road expedition, to visit 21 states in a single carefully chosen day. I’m impressed.
This all seems connected to the Travelling Salesman Problem, or generally the problem of how to find the beset way to do something when there are so many ways to do it there’s no hope of testing all the possible combinations, but when there aren’t an infinite continuum of ways so that you can’t use calculus techniques to find a solution. Problems like this tend to be interesting ones: you can usually see exactly why the problem might be interesting, and you can work out a couple easy little toy cases, and if you fiddle around with toys that are a little more realistic you see just how hard they are.
I’ve never driven in more than six United States states in a day, near as I can tell. I have driven across Pennsylvania, even though that means crossing the Appalachians, and as anyone from the East Coast knows deep down, the Appalachians are a fundamentally uncrossable geographic barrier and anyone claiming to have crossed it is surely mad.