Humans exceed capabilities of known AI algorithms on the Travelling Salesperson Problem?

Apparently so, says a friend, who notes,

The TSP is a pedagogical problem used to test new AI algorithms. It is used because it is in a class of problems where the complexity scales exponentially with problem size, making finding solutions using a computer very difficult.


Interestingly, human performance on the TSP scales linearly or near linearly with problem size. Either there is some shortcut humans are using, or they have some other capability not exhibited by AI algorithms.

Here’s more on the problem:

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

But bees can solve it.

What I would like to know is this: If the computer programmer became a travelling salesperson, would he solve an equivalent problem faster than the machine he is trying to use?

Abstract

Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence.
Received: 28 December 1998?/?Accepted: 20 January 2000

Children: Do babies know the difference between right and wrong?

Yes they do, according to Paul Bloom at Yale University. David Derbyshire reports:

Professor Paul Bloom, a psychologist at Yale University in Connecticut, whose department has studied morality in babies for years, said: 'A growing body of evidence suggests that humans do have a rudimentary moral sense from the very start of life.

'With the help of well designed experiments, you can see glimmers of moral thought, moral judgment and moral feeling even in the first year of life.

'Some sense of good and evil seems to be bred in the bones.'

What Dr. Bloom means to say, of course, is that morality is encoded in the genes and owes little or nothing to reason.

But other researchers are skeptical:

Dr Nadja Reissland, of Durham University, said babies started to learn the difference between good and bad from birth.

'Everything hinges on who decides what is normal,' she said. 'By saying pushing the ball up the hill is helpful, the researchers are making a moral judgement. The babies might just prefer to see things go up rather than down.

By “learn,” she means that the babies begin to apply concepts; Good vs.evil are not hardwired.

I think the most reasonable explanation of the experiments described is that babies prefer happy faces to sad or angry ones, etc., but good and evil are a bit more complex than that.