|
In the usual game of 20 questions, one player tries to
determine a hidden object by asking a series of "yes or no"
questions. A number of real life search problems have this general
form. However, in applications one is usually limited to a
predetermined set of questions, and one is not
required to determine the hidden object precisely, but rather only to
determine the object up to some sort of equivalence.
For example: Suppose one has a communications network, and
a storm (or a terrorist attack, or...) knocks out some of the arcs in
the
network. For each arc of the network, one may test "Is this arc still
working?" (This is the predetermined list of allowable questions.)
The goal may not be to determine the surviving network precisely,
but instead to determine the answers to a small list of questions
of the form "Is the network still connected?" "Is there still a direct
connection between Point A and the Point B?", etc.
In the problems we examine, we will assume that one can complete
the task if one is permitted to ask all of the allowable questions.
The question we will examine is - Is it possible to do better? That
is, can one complete the task without asking all of the allowable
questions?
Our approach is to restate the problem in a more topological form.
We will then define a new homology theory that captures the difficulty
of solving this problem. The link between the homology theory and the
original search problem is provided by a slight generalization of
"Discrete Morse Theory."
|