Modern Research on the Human Ability to Solve Problems that Have Large Search Spaces
Zygmunt Pizlo · Cambridge University Press eBooks · 2022
This chapter discusses the traveling salesman problem (TSP), which is the best-known problem with a large search space. TSPs with a moderate number of cities are solved very well by human subjects within a couple of minutes despite the fact that the number of possible tours can be equal to the number of seconds since the Big Bang. Randomly generated tours are much worse than the tours that humans produce. This means that human subjects must have an uncanny ability to navigate very intelligently through enormous spaces without considering too many, if any, alternatives. The absence of search in human problem solving is arguably the biggest difference between artificial intelligence, as it is designed today, and human intelligence, which is obviously the natural Intelligence. Human performance is described and compared to several heuristic algorithms such as the nearest neighbor, convex hull, and hierarchical pyramids. The chapter ends with a description of the performance of young children who solve TSP nearly as well as their parents.