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/nearestneighbor 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 highspeed supercomputers.
I really liked this problem, by the way, and I especially liked the way Andrei's solution crossreferenced to the Discrete Math POW for December 18.
Cheers, Mary



