Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
math club ski trip problem on MidPOW
Posted:
Jan 22, 2001 10:49 PM
|
|
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
|
|
|
|
