Chronicle Edward P, MacGregor James N, Ormerod Thomas C, Burr Alistair
Department of Psychology, University of Hawaii at Manoa, Honolulu, HI 96822, USA.
Q J Exp Psychol (Hove). 2006 Apr;59(4):783-800. doi: 10.1080/02724980543000033.
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.
人类在计算上难以处理的优化问题实例上，比如旅行商问题（TSP），表现可以非常出色。我们提出了一种边界跟踪启发式方法来解释这一发现。我们报告了三项针对旅行商问题的实验，在这些实验中运用这种启发式方法的能力有所不同。在实验1中，能够自由使用该启发式方法的参与者得出的解决方案比那些被阻止使用的参与者得出的解决方案明显更接近最优解。实验2和实验3共同在更大规模的问题中重复了这一发现，并表明一个潜在的混杂因素没有影响。在所有这三项实验中，边界跟踪模型与表现紧密匹配。结果表明涉及的是全局而非纯粹的局部过程。人类可能能够使用适合某些组合优化任务的基于感知的简单启发式方法。
