Information Technology Reference
In-Depth Information
For any positive sequence
X
=
{
x
i
}
i
+
M
−
1
x
j
i
+
M
−
1
g
j
g
i
g
M
g
M
M
∑
∑
inf
X
sup
i
=
min
g
=
min
g
1
=
M
−
1
x
i
−
(
M
−
1
)
>
1
>
1
M
M
−
with the minimizing generator of the geometric sequence being
.
This minimax
1
M
M
trajectory achieves the competitive ratio 1
+
2
∼
1
+
2
eM
5
.
4
M
for large
M
−
1
(
M
−
1
)
M
.
Similarly to the linear search problem, the (expected) competitive ratio can be
reduced to 3
09
M
by using mixed search strategies based on geometric trajecto-
ries. In contrast to the pure strategy case, however, the optimality proof applies
only to strategies that use periodic and monotone trajectories. (See [
24
,
33
,
34
]and
[
41
].) López-Ortiz and Schuierer have solved several extensions of the star search
for bounded distance, [
37
], and for search by several agents who move in paral-
lel, [
38
].
.
1.4 Online Searching in the Plane
1.4.1 An Open Problem Recently Solved
An immobile hider is located at an unknown point
H
in the plane. The searcher
chooses a trajectory, starting from
O
and discovers the hider at the moment when
H
is covered by the area swept by the radius vector
R
of his trajectory. It is natu-
ral to use
periodic and monotonic
trajectories
R
,
of the radius
vector always strictly increasing, and the trajectory does not intersect itself. Under
this assumption, as we mentioned before, there exists a minimax search trajectory
within the family of exponenti
al spirals
, i.e.,
(
θ
)
with the angle
θ
e
b
θ
,
|
R
|
=
where
b
>
0 is a constant.
The competitive ratio is
e
2π
b
1
b
2
with minimal value about 17
+
1
/
.
3, attained at
b
16 (see Gal [
24
]). Since then it has been an open problem whether the given
strategy is optimal in general without the periodic and monotonic assumption. A re-
cent work of Langetepe [
36
] has solved this 30 years old open problem and showed
that the above described spiral search is indeed the overall optimal trajectory.
0
.
1.4.2 'Swimming in a fog' Problem
The following problem has been proposed by Bellman [
9
]. A person has been ship-
wrecked in a fog and wishes to minimize the maximum time required to reach the
shore. The shape of the shore is known and some information is given about its
distance. If the shore is a straight line with a known distance
D
then the minimax
trajectory is given by Isbell [
31
] as follows: Imagine a clock face and a circle of
Search WWH ::
Custom Search