Linear search problem

Last updated

In computational complexity theory, the linear search problem is an optimal search problem introduced by Richard E. Bellman [1] and independently considered by Anatole Beck. [2] [3] [4]

Contents

The problem

"An immobile hider is located on the real line according to a known probability distribution. A searcher, whose maximal velocity is one, starts from the origin and wishes to discover the hider in minimal expected time. It is assumed that the searcher can change the direction of his motion without any loss of time. It is also assumed that the searcher cannot see the hider until he actually reaches the point at which the hider is located and the time elapsed until this moment is the duration of the game."

The problem is to find the hider in the shortest time possible. Generally, since the hider could be on either side of the searcher and an arbitrary distance away, the searcher has to oscillate back and forth, i.e., the searcher has to go a distance x1 in one direction, return to the origin and go distance x2 in the other direction, etc., (the length of the n-th step being denoted by xn). (However, an optimal solution need not have a first step and could start with an infinite number of small 'oscillations'.) This problem is usually called the linear search problem and a search plan is called a trajectory. It has attracted much research, some of it quite recent.[ when? ]

The linear search problem for a general probability distribution is unsolved. [5] However, there exists a dynamic programming algorithm that produces a solution for any discrete distribution [6] and also an approximate solution, for any probability distribution, with any desired accuracy. [7]

The linear search problem was solved by Anatole Beck and Donald J. Newman (1970) as a two-person zero-sum game. Their minimax trajectory is to double the distance on each step and the optimal strategy is a mixture of trajectories that increase the distance by some fixed constant. [8] This solution gives search strategies that are not sensitive to assumptions concerning the distribution of the target. Thus, it also presents an upper bound for a worst-case scenario. This solution was obtained in the framework of an online algorithm by Shmuel Gal, who also generalized this result to a set of concurrent rays. [9] The best online competitive ratio for the search on the line is 9 but it can be reduced to 4.6 by using a randomized strategy. Demaine et al. gave an online solution with a turn cost. [10]

These results were rediscovered in the 1990s by computer scientists as the cow path problem.

See also

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.

Reinforcement learning (RL) is an interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent ought to take actions in a dynamic environment in order to maximize the cumulative reward. Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning.

<span class="mw-page-title-main">Simulated annealing</span> Probabilistic optimization technique and metaheuristic

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent or branch and bound.

The rendezvous dilemma is a logical dilemma, typically formulated in this way:

The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces that do not occur in low-dimensional settings such as the three-dimensional physical space of everyday experience. The expression was coined by Richard E. Bellman when considering problems in dynamic programming. The curse generally refers to issues that arise when the number of datapoints is small relative to the intrinsic dimension of the data.

In mathematics, a Markov decision process (MDP) is a discrete-time stochastic control process. It provides a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker. MDPs are useful for studying optimization problems solved via dynamic programming. MDPs were known at least as early as the 1950s; a core body of research on Markov decision processes resulted from Ronald Howard's 1960 book, Dynamic Programming and Markov Processes. They are used in many disciplines, including robotics, automatic control, economics and manufacturing. The name of MDPs comes from the Russian mathematician Andrey Markov as they are an extension of Markov chains.

<span class="mw-page-title-main">Linear programming relaxation</span>

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

A princess and monster game is a pursuit–evasion game played by two players in a region.

<span class="mw-page-title-main">Smoothed analysis</span>

In theoretical computer science, smoothed analysis is a way of measuring the complexity of an algorithm. Since its introduction in 2001, smoothed analysis has been used as a basis for considerable research, for problems ranging from mathematical programming, numerical analysis, machine learning, and data mining. It can give a more realistic analysis of the practical performance of the algorithm compared to analysis that uses worst-case or average-case scenarios.

A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. The game is zero sum with the payoff being the time spent in searching. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" and has been developed further by Shmuel Gal and Steve Alpern. The princess and monster game deals with a moving target.

<span class="mw-page-title-main">Shmuel Gal</span>

Shmuel Gal is a mathematician and professor of statistics at the University of Haifa in Israel.

Steve Alpern is a professor of Operational Research at the University of Warwick, where he recently moved after working for many years at the London School of Economics. His early work was mainly in the area of dynamical systems and ergodic theory, but his more recent research has been concentrated in the fields of search games and rendezvous. He informally introduced the rendezvous problem as early as 1976. His collaborators include Shmuel Gal, Vic Baston and Robbert Fokkink.

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

<span class="mw-page-title-main">Affine scaling</span> Algorithm for solving linear programming problems

In mathematical optimization, affine scaling is an algorithm for solving linear programming problems. Specifically, it is an interior point method, discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s.

Probabilistic numerics is an active field of study at the intersection of applied mathematics, statistics, and machine learning centering on the concept of uncertainty in computation. In probabilistic numerics, tasks in numerical analysis such as finding numerical solutions for integration, linear algebra, optimization and simulation and differential equations are seen as problems of statistical, probabilistic, or Bayesian inference.

References

  1. ↑ Bellman, Richard (July 1963), "Problem 63-9, An Optimal Search", SIAM Review, 5 (3): 274, JSTOR   2027629
  2. ↑ Beck, Anatole (December 1964), "On the linear search Problem", Israel Journal of Mathematics , 2: 221–228, doi: 10.1007/BF02759737
  3. ↑ Beck, Anatole (June 1965), "More on the linear search problem", Israel Journal of Mathematics , 3: 61–70, doi: 10.1007/BF02760028
  4. ↑ Beck, Anatole; Beck, Micah (December 1986), "The linear search problem rides again", Israel Journal of Mathematics , 53: 365–372, doi: 10.1007/BF02786568
  5. ↑ Alpern, Steve; Gal, Shmuel (2003), "Chapter 8. Search on the Infinite Line", The Theory of Search Games and Rendezvous, Part 2, International Series in Operations Research & Management Science, vol. 55, pp. 123–144, doi: 10.1007/0-306-48212-6_8 . On p. 124, Alpern and Gal write "no algorithm for solving the problem for a general probability distribution function has been found during about 37 years since the LSP was first presented."
  6. ↑ Bruss, F. Thomas; Robertson, James B. (December 1988), "A survey of the linear-search problem" (PDF), The Mathematical Scientist , 13: 75–89[ dead link ]
  7. ↑ Alpern, Steve; Gal, Shmuel (2003), "Section 8.7. A Dynamic Programming Algorithm for the LSP", The Theory of Search Games and Rendezvous, Part 2, International Series in Operations Research & Management Science, vol. 55, pp. 139–144, doi: 10.1007/0-306-48212-6_8
  8. ↑ Beck, Anatole; Newman, Donald J. (December 1970), "Yet More on the linear search problem", Israel Journal of Mathematics , 8: 419–429, doi: 10.1007/BF02798690
  9. ↑ Gal, Shmuel (1980), Search games, Academic Press
  10. ↑ Demaine, Erik D.; Fekete, Sandor; Gal, Shmuel (September 2006), "Online searching with turn cost", Theoretical Computer Science, 361 (2–3): 342–355, arXiv: cs/0406045 , doi: 10.1016/j.tcs.2006.05.018
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.