Spelunking is a recreational sport in which "spelunkers" explore systems of caves, either on land or underwater. This problem deals with the idea of finding a spelunker who has become lost in a system of caves. The general idea is that the spelunker is lost in a cave system that has been mapped out on previous expeditions, so that when a search party is sent in, they know all the corridors and paths that they can take within the system.
There are many different ways to explore this problem and there are many different applications of the theories that are used to solve such a problem. The theories explored can be used to help find people who have become lost in cave systems but these theories can also be applied to anything that can be modeled into a graph. For example, a map of Regina can be modeled as a graph then systematically searched to try and find something within it. Following this logic, we can then map out all sorts of other networks (software and internet networks included) and search these for anything as well. This is useful in that we can search networks for intruders including hackers and other internet-based thieves.
Goals:
- To find a spelunker who is lost in a cave system under a variety of different constraints.
- To find an intruder in a cave or software system.
A useful paper for the investigation: Time Constrained Graph Searching (2008) - B. Alspach, D. Dyer, D. Hanson, and B. Yang [Warning: external links open in a new window]
