For video footage from past you can visit the individual event pages, or go to our YouTube Channel

To filter by event category, click on the event category link in the table below or use the menu on the right.

List of Past Events

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