RuCCS Colloquia

The Traveling Salesman Problem: Human Performance and a Computational Model

Dr. Zygmunt Pizlo

Tuesday, October 24, 2006, 01:00pm - 02:00pm

Purdue University, Department of Psychological Sciences, School of Electrical and Computer Engineering

Copy to My Calendar (iCal) Download as iCal file
 

Prior research on human problem solving concentrated on tasks whose search
spaces were fairly small.  Human performance in such tasks can be
adequately modeled by search algorithms implementing the concept of
production rules.  These models do not generalize, however, to
combinatorial problems, such as the Traveling Salesman (TSP), which are
known to be "computationally intractable".  Psychophysical experiments
show that human subjects produce approximate solutions to TSP in time that
is linearly related to the problem size, which implies that the amount of
search is minimal.  Despite the absence of search, human subjects produce
optimal or close to optimal solutions.  A computational model of the
underlying mental mechnisms will be presented.  The model begins with
producing a multiresolution representation of a TSP problem by means of
hierarchical clustering.  A TSP tour is then formed in a sequence of
successive approximations, in which a solution on a higher resolution
representation is controlled by a lower resolution representation.  The
computational complexity of the model is O(NlogN), and thus similar to
that of the mental mechanisms.

Dr. Zygmunt Pizlo


The RuCCS Colloquia Series is organized by Dr. Julien Musolino and Dr. Sara Pixley. The talks are held on Tuesdays in the Psychology Building, Room 101 on the Busch Campus from 1:00-2:30pm.

Note: If you would like to receive email announcements about the colloquium series, please contact the Business Office to have your name added to our announce lists at business_manager@ruccs.rutgers.edu.