Computer Science 789 Online Algorithms
Hint 1 for the
Dungeon Searching Problem
You only need to prove that the value of the greedy path is at least
half the value of an arbitrary path. Do you see why?
If you ask, "how does the fact that the other path is optimal enter into
the proof?" the answer is that it doesn't.

Back to
Course Page
Back to
Assignment Page
Back to
Assignment 1