linear search


triangle_rich
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. These mappings have highly unusual singularities, and the critical questions, such as existence of invariant manifolds cannot be addressed with available tools.

Consider, as an example, the (partially defined) mapping of the unit square \([0,1]×[0,1]\) into itself

\[h:\left(\begin{array}{c}s\\x\end{array}\right)\mapsto\left(\begin{array}{c}(1−x)^2\\s/(2−2x)\end{array}\right).\]

This mapping corresponds to the problem of optimal search of an item randomly located on \([0,1]\) with density \(2(1−x)\). We need to understand the properties of the mapping \(h\) near \((0,1)\), in particular the (unique?) invariant curve ending at this point.

,

No comments yet.

Leave a Reply