Optimal non-Markovian composite search algorithms for spatially correlated targets

We study the eciency of a wide class of stochastic non-Markovian search strategies for spatially correlated target distributions. For an uninformed searcher that performs a non-composite random search, a ballistically moving search is optimal for destructible targets, even when the targets are correlated. For an informed searcher that can measure the time elapsed since the last target encounter and performs a composite search consisting of alternating extensive ballistic trajectories and intensive non-Markovian search trajectories, the eciency can be more than three times higher compared to a ballistic searcher. We optimize the memory function that describes the intensive non-Markovian search motion and nd a single-exponential memory function to be optimal. In our extended search model the intensive search mode is activated when the distance between two consecutively found targets in the extensive search mode is smaller than a threshold length called the memory distance d m . We nd that a nite value of d m quite generally leads to optimal search eciency for correlated target distributions.