Search algorithm

The computer science designated search process or search algorithm an algorithm that searches in a search space for patterns or objects with specific properties. A distinction is simple and heuristic search algorithms. Simple search algorithms use intuitive methods of searching through the search space, while heuristic search algorithms include knowledge of the search space ( eg, data distribution) with, in order to reduce the search time required.

The solution of an algorithmic problem can be general ( the solution space ) can be understood as a search for the solution in a set of possible solutions. As a solution to the target state can be considered, but also the path to the destination or the order in action. If the search space finite, the search can with an appropriate search strategy always lead to a result. With infinite (solution ) amounts to search for certain criteria must be stopped ( after a certain time, for example ).

Repeated search in a finite set can be designed efficiently that through the data, an index structure is created ( eg in the form of a search tree ), which is sorted according to a certain criterion. Then have a search, not all entries will be considered (eg, one begins the search in a phone book in the letter with which the name begins ).

Simple search algorithms

Simple search algorithms neglect the special nature of the problem. Therefore, they can be implemented general and abstract, whereby the same implementation may be used for a wide range of problems. The disadvantage of simple search algorithms are the costs: The search space of search problems is generally very large, easy searching runs but only in small search spaces in a reasonable time from.

Search in lists

Algorithms for searching in lists are the simplest search algorithms in general. The objective of Search in lists is to find a particular element of a list, which is known the corresponding search key. Since this problem is encountered in computer science often are the algorithms used - as well as their complexity - very well studied.

The simplest search algorithm for lists is the linear search. In her one element after another is run through until an element with the searched key is encountered. The linear search has a running time of (n is the number of elements in the list ) and can be applied to both sorted and unsorted lists. A more advanced method is the binary search with a term of. For large lists, it is much more efficient than the linear search, however, presupposes that the list has been sorted before, and a random access to the elements is possible. The Interpolation, also called interval search is an improvement of the binary search, which requires an equal distribution of data. The running time is better than that of binary search only for very large amounts of data. Another search algorithm for lists of Grover 's algorithm, which depends on quantum computers for use and expires square faster than the classical linear search for unordered lists. For searching in lists and hashing can be used which has a constant time, but requires linear time on average in the worst case.

Search in trees

Searching in trees is the pinnacle among the search algorithms. You searched nodes of trees, regardless of whether the tree explicitly or implicitly ( during the search -generated) is. Here, the following principle is used: a node is taken out of a data structure. Its child nodes are investigated and optionally be added to the data structure. Depending on the selection of the data structure of the tree can be searched in various orders. The use of a queue then causes a breadth-first search, in which the tree is traversed level by level. When using a stack, however, is sought in each case up to a sheet and only then proceed to the next child node. This is referred to as depth-first search.

Search in graphs

Many problems in graph theory can be solved with the aid of search algorithms. Examples of these problems are the problem of the traveling salesman, shortest paths and minimum spanning trees. The corresponding algorithms are, for example, Dijkstra's algorithm, Kruskal's algorithm or Prims Algorithm which can be seen as extensions of the algorithms for searching in trees.

Heuristic ( Informed ) search algorithms

Strategies that can accelerate the discovery of solutions is called heuristics. Typical heuristics are rules of thumb, the orientation of examples and the simulation of the human problem solving process. Thus, the method can in uninformed (also called blind search ) and informed (use of heuristics ) can be distinguished. The study of different methods for heuristic search, development and implementation of new techniques and their application to various problem areas are expected normally to the algorithmic core of artificial intelligence. These include the automatic evidence that control of robots and, as typical representatives, especially games. This refers both to two-person games ( zero-sum games with perfect information ), such as chess, checkers, mill and one-person games such as sliding puzzles or Solitaire. The classical method to heuristic search, A *, IDA *, bidirectional search schemes, the minimax procedure, alpha-beta search.

Heuristic search algorithms are also used when an algorithm to solve the problem is too computationally intensive. In this case, a certain amount of error is accepted - that also accepts a non-optimal solution - if this computing time used may be significantly reduced. For example, can no longer be solved exactly in a realistic time already from a few dozen nodes Traveling Salesman Problems.

-Optimizing search

This type of search solves optimization problems, in which a number of variables with values ​​must be assigned. Since this can involve a large number of variables with a very large range of values, the search area is very large and conventional search methods fail.

Combinatorial search and backtracking are procedures that are used in the optimized search for the application, especially in discrete variables.

For analog search for maxima or minima of multidimensional functions, there are a number of numerical optimization methods, which are used depending on the particular initial conditions.

Another approach is based on the feedback provided by the user who has to assess the relevance of the results, see relevance feedback.

Other search methods

Search method for character strings in string after the occurrence of a key. Well-known representatives are the algorithm of Knuth - Morris - Pratt, Boyer -Moore 's algorithm as well as the Karp -Rabin algorithm. See also: string matching algorithm.

Evolutionary algorithms use ideas from the theory of evolution as heuristics to quickly get good results.

Simulated annealing ( simulated annealing ) is a value based on likelihood search algorithm.

Adversarial Search is used in the field of artificial intelligence.

Differences in performance of the search process

In the No -Free - Lunch theorems it was shown that - averaged over all mathematically be formulated problems - all search methods are equally good. A performance advantage of a search procedure on only one specific class of problems.