2015 | OriginalPaper | Buchkapitel
Group Search on the Line
verfasst von : Marek Chrobak, Leszek Gąsieniec, Thomas Gorry, Russell Martin
Erschienen in: SOFSEM 2015: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we consider the
group search problem
, or
evacu- ation problem
, in which
k
mobile entities (
${\cal M}{\cal E}$
s) located on the line perform search for a specific destination. The
${\cal M}{\cal E}$
s are initially placed at the same origin on the line
L
and the target is located at an unknown distance
d
, either to the left or to the right from the origin. All
${\cal M}{\cal E}$
s must
simultaneously
occupy the destination, and the goal is to minimize the time necessary for this to happen. The problem with
k
= 1 is known as the
cow-path
problem, and the time required for this problem is known to be 9
d
−
o
(
d
) in the worst case (when the cow moves at unit speed); it is also known that this is the case for
k
≥ 1 unit-speed
${\cal M}{\cal E}$
s. In this paper we present a clear argument for this claim by showing a rather counter-intuitive result. Namely, independent of the number of
${\cal M}{\cal E}$
s, group search cannot be performed faster than in time 9
d
−
o
(
d
). We also examine the case of
k
= 2
${\cal M}{\cal E}$
s with different speeds, showing a surprising result that the bound of 9
d
can be achieved when one
${\cal M}{\cal E}$
has unit speed, and the other
${\cal M}{\cal E}$
moves with speed at least 1/3.