We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK


97% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > It looks easy! Heuristics for combinatorial opt...
View graph of relations

« Back

It looks easy! Heuristics for combinatorial optimization problems.

Research output: Contribution to journalJournal article


Associated organisational unit

<mark>Journal publication date</mark>2006
<mark>Journal</mark>The Quarterly Journal of Experimental Psychology
Number of pages0
Pages783 -800
<mark>Original language</mark>English


Human performance on instances of computationally intractable optimization problems, such as the travelling salesperson problem (TSP), can be excellent. We have proposed a boundary-following heuristic to account for this finding. We report three experiments with TSPs where the capacity to employ this heuristic was varied. In Experiment 1, participants free to use the heuristic produced solutions significantly closer to optimal than did those prevented from doing so. Experiments 2 and 3 together replicated this finding in larger problems and demonstrated that a potential confound had no effect. In all three experiments, performance was closely matched by a boundary-following model. The results implicate global rather than purely local processes. Humans may have access to simple, perceptually based, heuristics that are suited to some combinatorial optimization tasks.