PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 16707362

It looks easy! Heuristics for combinatorial optimization problems.

Edward P Chronicle·James N MacGregor·Thomas C Ormerod·Alistair Burr
View original source ↗Export metadata ↓

Abstract

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.

Explore related subjects

AttentionDiscrimination LearningFemaleHumansMaleOrientationProblem SolvingPsychomotor PerformanceSpace PerceptionComparative StudyJournal Article

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Edward P Chronicle, James N MacGregor, Thomas C Ormerod, Alistair Burr. 2006. It looks easy! Heuristics for combinatorial optimization problems.. https://doi.org/10.1080/02724980543000033

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2007

A low glycaemic index breakfast cereal preferentially prevents children's cognitive performance from declining throughout the morning.

This study investigated whether the glycaemic index (GI) of breakfast cereal differentially affects children's attention and memory. Using a balanced cross-over design, on two consecutive mornings 64 children aged 6-11 years were given a high GI cereal and a low GI cereal in a counterbalanced order. They performed a series of computerised tests of attention and memory, once prior to breakfast and three times following breakfast at hourly intervals. The results indicate that children's performance declines throughout the morning and that this decline can be significantly reduced following the intake of a low GI cereal as compared with a high GI cereal on measures of accuracy of attention (M=-6.742 and -13.510, respectively, p<0.05) and secondary memory (M=-30.675 and -47.183, respectively, p<0.05).

Attention↗
PubMed2007

Inhibitory control test is a simple method to diagnose minimal hepatic encephalopathy and predict development of overt hepatic encephalopathy.

OBJECTIVES: To compare inhibitory control test (ICT), a simple/rapid test of attention, to a standard psychometric battery (SPT) to diagnose minimal hepatic encephalopathy (MHE) and predict development of overt hepatic encephalopathy (OHE) in cirrhotic patients. METHODS: Fifty nonalcoholic cirrhotics and 50 age/educational-status-matched controls were given ICT and SPT in the same sitting. Performance impaired beyond two standard deviations of controls was considered MHE in cirrhotics. ICT results (lure/target response and lures/person) were compared between controls and cirrhotics and within cirrhotics with/without MHE. Receiver-operating characteristic analysis was used to study ICT for MHE diagnosis. Twenty subjects were administered SPT and ICT twice to assess test-retest reliability. All cirrhotics were followed routinely for the development of OHE. RESULTS: Cirrhotics performed worse than controls on SPT and ICT. Using SPT, 39 cirrhotics had MHE. ICT was administered faster than SPT (15 vs 37 min). Cirrhotics with MHE had significantly higher lure (28%vs 3%) and lower target response (91%vs 96%) compared with those without MHE. Lure/person >5 had 90% sensitivity/specificity for MHE diagnosis. AUC for receiver-operating characteristic for lures alone was 95.8%. Lure and target responses were highly correlated (r= 0.9) between sessions showing high test-retest reliability. Five (10%) patients developed OHE on f/u of 26 +/- 10 months; all five had been diagnosed with MHE using ICT and SPT. None of the five patients with discordant results on SPT and ICT developed OHE. CONCLUSIONS: ICT has good sensitivity/specificity for MHE diagnosis, is reliable and is equivalent to SPT for predicting OHE development.

Attention↗