Namespaces
Variants
Actions

Difference between revisions of "Search problem (linear)"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
 
Line 2: Line 2:
 
An optimality problem first formulated by R. Bellman [[#References|[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.
 
An optimality problem first formulated by R. Bellman [[#References|[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 [[#References|[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 [[#References|[a3]]] and subsequent papers in Israel J. Math.). Optimal search paths were constructed [[#References|[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 [[#References|[a5]]].
+
W. Franck [[#References|[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 [[#References|[a3]]] and subsequent papers in Israel J. Math.). Optimal search paths were constructed [[#References|[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 [[#References|[a5]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Bellman,  "Research problem No. 63–9"  ''SIAM Review'' , '''5'''  (1963)  pp. 274</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W. Franck,  "An optimal search problem"  ''SIAM Review'' , '''7'''  (1965)  pp. 503–512</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Beck,  "On the linear search problem"  ''Israel J. Math.'' , '''2'''  (1964)  pp. 221–228</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.J. Rousseeuw,  "Optimal search paths for random variables"  ''J. Comput. Appl. Math.'' , '''9'''  (1983)  pp. 279–286</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  F.T. Bruss,  J.B. Robertson,  "A survey of the linear search problem"  ''Math. Scientist'' , '''13'''  (1988)  pp. 75–89</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Bellman,  "Research problem No. 63–9"  ''SIAM Review'' , '''5'''  (1963)  pp. 274</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W. Franck,  "An optimal search problem"  ''SIAM Review'' , '''7'''  (1965)  pp. 503–512</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Beck,  "On the linear search problem"  ''Israel J. Math.'' , '''2'''  (1964)  pp. 221–228</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.J. Rousseeuw,  "Optimal search paths for random variables"  ''J. Comput. Appl. Math.'' , '''9'''  (1983)  pp. 279–286</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  F.T. Bruss,  J.B. Robertson,  "A survey of the linear search problem"  ''Math. Scientist'' , '''13'''  (1988)  pp. 75–89</TD></TR></table>

Latest revision as of 17:11, 30 December 2018

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