Information Technology Reference
In-Depth Information
by Isaacs that the searcher can find a non-wasteful trajectory is not made, so the
searcher strategy given in [
14
] is not always available and the value of the game
may be greater than
2. The searcher is also restricted to picking a path which
starts from
O
, so it may not be possible for him to implement the 'reverse' of a path.
For instance, if
Q
is a single unit length arc with the root
O
at one end and a point
A
at the other, the value of this game is clearly 1
μ
/
2. The hider simply uses the
pure strategy of hiding at
A
and the searcher picks the path from
O
to
A
.
However, adapting the searcher strategy given in [
14
], Gal gives an upper bound
for the value. The searcher may not be able to find a non-wasteful, reversible path in
Q
, but he will always have some minimal time tour
S
of
Q
starting and ending at
O
of
length ¯
>
μ
/
. He can then use the mixed strategy where he picks
S
with probability
1/2 and the reverse of
S
with probability 1/2, ensuring that he finds every point in
Q
in expected time no more than ¯
μ
≥
μ
2. The searcher's minimal tour
S
is later called
a Chinese Postman Tour (CPT) in [
12
], and the randomized strategy given here is
called the Random Chinese Postman Tour (RCPT). The RCPT gives an upper bound
for the value
V
, and combining this with the lower bound we have
μ
/
μ
/
2
≤
V
≤
μ
/
¯
2
(2.1)
Gal examines when these two bounds are tight. Suppose
Q
is Eulerian, so that
it has a continuous closed path that visits each point of
Q
exactly once. Then the
searcher's CPT is one such Eulerian path starting at
O
. Since the length
¯
μ
of this
¯
tour is
2. The uniform
strategy u is optimal for the hider. It is easy to see that Eulerian networks are the
only networks for which
¯
μ
, the bounds in (
2.1
) are tight and we have
V
=
μ
/
2
=
μ
/
.
We can also consider the game played on a tree, that is a network without any
cycles. In a sense, a tree is the opposite of an Eulerian network since the CPT of
a tree has the maximum possible length,
¯
μ
=
μ
μ
=
, as all arcs must be traversed in
both directions. The inequalities (
2.1
) therefore become
2
μ
μ
/
≤
≤
μ
. Clearly the
uniform hider strategy
u
is not optimal for the hider, since every point
H
of
Q
is
dominated in strategies by a leaf node (a node of degree 1). Hence an optimal hider
strategy must be some distribution on the leaf nodes. In [
10
] Gal defines a hider
distribution later called the Equal Branch Density (EBD) distribution in [
12
], and
shows that it is optimal for the hider, guaranteeing him an expected search time of
no less than
2
V
μ
=
μ
/
¯
2, which is the value of the game. The RCPT is optimal for the
searcher.
The EBD distribution can be defined in terms of a concept called
search density
,
which extends to general search spaces
Q
that may not be networks. For a connected
subset
A
of
Q
and a hider hidden on
Q
according to a fixed distribution, the search
density
is defined as the time taken for the searcher to tour
A
divided by the
probability the hider is in
A
. Consider a tree
Q
and a node
x
of
Q
that has degree at
least 3. We call
x
a branch node. The arcs touching
x
consist of one arc on the path
from
x
to
O
and some other arcs. For each of these other arcs
a
, we define a branch
at
x
which consists of
a
together with all arcs whose unique path to
O
intersects
with
a
. The EBD distribution is the unique hider distribution on the leaf nodes of
Q
that ensures that at every branch node of
Q
, all branches have equal search density.
ρ
(
A
)
Search WWH ::
Custom Search