Monday, September 9, 2013

Does 'traveling salesman' = 'connect the dots'?

The traveling salesman problem is a well-known problem: A salesman has to make X stops. Of all the routes he can take, which is the shortest one? Tom Vanderbilt has a fascinating article about this problem and its many cousins and great grandchildren: Unhappy Truckers and Other Algorithmic Problems.
Powell’s biggest revelation in considering the role of humans in algorithms, though, was that humans can do it better. “I would go down to Yellow, we were trying to solve these big deterministic problems. We weren’t even close. I would sit and look at the dispatch center and think, how are they doing it?” That’s when he noticed: They are not trying to solve the whole week’s schedule at once. They’re doing it in pieces. “We humans have funny ways of solving problems that no one’s been able to articulate,” he says. Operations research people just punt and call it a “heuristic approach.”

This innate human ability was at work in Santilli’s daughter’s class, too. The fifth graders got it about right. As James MacGregor and Thomas Ormerod note, “the task of the traveling salesman problem may happen to parallel what it is natural for the perceptual system to do in any case when presented with an array of dots.” Curiously, using this heuristic approach, they note, subjects in experiments were “exceptionally good at finding the optimum tours.” In other experiments, when subjects were shown images of optimal tours, they were thought to be more aesthetically pleasing than sub-optimal tours.
H/t Tyler Cowen.

No comments:

Post a Comment