Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Online Projects » pow-teach

Topic: math club ski trip problem on MidPOW
Replies: 2   Last Post: Jan 30, 2001 11:30 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Mary O'Keeffe

Posts: 59
Registered: 12/3/04
math club ski trip problem on MidPOW
Posted: Jan 22, 2001 10:49 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Both of the sample solutions posted so far for the Math Club Ski Trip
problem apparently rely on the greedy algorithm (also known as the
"nearest neighbor" algorithm.)

Andrei Lazanu's posted sample solution helpfully points in the
direction of an old Discrete Math problem at

http://forum.swarthmore.edu/dmpow/solutions/solution.ehtml?puzzle=58

I'd definitely recommend that MidPOW teachers and students visit that
December 18 Discrete Math POW, because it mentions that neither the
"nearest neighbor" algorithm nor the "cheapest link" algorithm is
guaranteed to yield the optimal solution, only a "nearly optimal
solution."

However, one of my students did an exhaustive analysis using a
computer spreadsheet and she confirmed that in the Ski Club trip, the
nearest neighbor algorithm does in fact yield the optimum in this
particular case. (There are 120 possible solutions to consider in an
exhaustive examination, but symmetry cuts them down to 60.)

As far as I can tell, however, there was no a priori reason to expect
the nearest neighbor algorithm to work perfectly in this particular
case? (Does anyone know a sufficient condition to guarantee that the
nearest neighbor algorithm will yield a true optimum?)

It seems to me that that teachers using this MidPOW should point out
to their students that the greedy algorithm/nearest-neighbor algorithm
is not always guaranteed to yield the optimal solution, even though it
happens to do so in this case. It's also worth pointing out that an
exhaustive examination of all possible cases quickly becomes
impractical, even with high-speed supercomputers.

I really liked this problem, by the way, and I especially liked the
way Andrei's solution cross-referenced to the Discrete Math POW for
December 18.

Cheers,
Mary





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.