Tag Archives | linear search

linear search

Linear search problems deals with locating an object hidden on a half line (“long road”) by an absent-minded robot which gather everything it sees (see, e.g. here for more details). A program for the robot is a sequence $$0<x_1<x_2<\ldots$$ of excursions it takes until the object is found.

In the situation when the object is hidden at a random location with a known distribution function $$F$$, the problem of finding an optimal trajectory can be translated into understanding the dynamics of certain area preserving mappings.…