Namespaces
Variants
Actions

Search problem (linear)

From Encyclopedia of Mathematics
Jump to: navigation, search

An optimality problem first formulated by R. Bellman [a1]. Suppose a particle is located on the real line, its unknown position being characterized by a symmetric probability distribution $F$. A searcher starts at the origin and can move in either direction with constant velocity until the target is found. The problem is to determine a path which minimizes the expected searching time.

W. Franck [a2] showed that there exist paths with finite expected searching time if and only if $\int|x|\,dF(x)<\infty$. Sufficient conditions for the existence of an optimal search path were established by A. Beck (in [a3] and subsequent papers in Israel J. Math.). Optimal search paths were constructed [a4] for the distributions of Gauss, Laplace and Student. A recent survey of the linear search problem, including generalizations and open questions, can be found in [a5].

References

[a1] R. Bellman, "Research problem No. 63–9" SIAM Review , 5 (1963) pp. 274
[a2] W. Franck, "An optimal search problem" SIAM Review , 7 (1965) pp. 503–512
[a3] A. Beck, "On the linear search problem" Israel J. Math. , 2 (1964) pp. 221–228
[a4] P.J. Rousseeuw, "Optimal search paths for random variables" J. Comput. Appl. Math. , 9 (1983) pp. 279–286
[a5] F.T. Bruss, J.B. Robertson, "A survey of the linear search problem" Math. Scientist , 13 (1988) pp. 75–89
How to Cite This Entry:
Search problem (linear). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Search_problem_(linear)&oldid=43611
This article was adapted from an original article by P.J. Rousseeuw (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article