Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Human performance on the traveling salesman problem

J N MacGregor1, T Ormerod

  • 1Loughborough University of Technology, England.

Perception & Psychophysics
|May 1, 1996
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Genetically engineered T cells expressing a HER2-specific chimeric receptor mediate antigen-specific tumor regression.

Cancer gene therapy·2008
Same author

When insight just won't come: the failure of visual cues in the nine-dot problem.

The Quarterly journal of experimental psychology. A, Human experimental psychology·2001
Same author

Information processing and insight: a process model of performance on the nine-dot and related problems.

Journal of experimental psychology. Learning, memory, and cognition·2001
Same author

Spatial and contextual factors in human performance on the travelling salesperson problem.

Perception·2001
Same author

Evaluating the importance of the convex hull in solving the Euclidean version of the traveling salesperson problem: reply to Lee and Vickers (2000).

Perception & psychophysics·2001
Same author

A model of human performance on the traveling salesperson problem.

Memory & cognition·2000

Human performance on the Traveling Salesman Problem (TSP) was studied. Results show TSP complexity depends on non-boundary points, and human solutions are remarkably effective, outperforming common algorithms.

Area of Science:

  • Cognitive Psychology
  • Computational Complexity
  • Operations Research

Background:

  • The Traveling Salesman Problem (TSP) is a complex combinatorial optimization problem.
  • Heuristics are commonly used to find approximate solutions for TSP.
  • Understanding human performance in solving TSP offers insights into problem-solving strategies.

Purpose of the Study:

  • To investigate human performance on the Traveling Salesman Problem (TSP).
  • To test the hypothesis that TSP complexity is determined by the number of non-boundary points.
  • To evaluate the quality of human-generated TSP solutions compared to known optimal solutions and heuristics.

Main Methods:

  • Two experiments were conducted using 10-point and 20-point TSP instances.

Related Experiment Videos

  • Subjects were tasked with finding the shortest path through a set of points, returning to the origin.
  • Solution quality was assessed by comparing them to best-known solutions, random solutions, and heuristic-generated solutions.

    • Main Results:

    • Both experiments supported the hypothesis that TSP complexity is a function of non-boundary points, not total points.
    • Human solutions were found to be close to the best-known solutions.
    • Subject solutions significantly outperformed three well-known heuristics and random solutions, falling beyond the 99.9th percentile.

    Conclusions:

    • The number of non-boundary points is a critical factor in TSP complexity.
    • Human subjects demonstrate a high level of performance in solving TSP, often surpassing algorithmic approaches.
    • The solution process for TSP appears to be perceptually based.