 | This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Incomputer science, asearch algorithm is analgorithm designed to solve asearch problem. Search algorithms work to retrieve information stored within particulardata structure, or calculated in thesearch space of a problem domain, witheither discrete or continuous values.
Althoughsearch engines use search algorithms, they belong to the study ofinformation retrieval, not algorithmics.
The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data. Search algorithms can be made faster or more efficient by specially constructed database structures, such assearch trees,hash maps, anddatabase indexes.[1][2]
Search algorithms can be classified based on their mechanism of searching into three types of algorithms: linear, binary, and hashing.Linear search algorithms check every record for the one associated with a target key in a linear fashion.[3]Binary, or half-interval, searches repeatedly target the center of the search structure and divide the search space in half. Comparison search algorithms improve on linear searching by successively eliminating records based on comparisons of the keys until the target record is found, and can be applied on data structures with a defined order.[4] Digital search algorithms work based on the properties of digits in data structures by using numerical keys.[5] Finally,hashing directly maps keys to records based on ahash function.[6]
Algorithms are often evaluated by theircomputational complexity, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity ofO(logn), or logarithmic time. In simple terms, the maximum number of operations needed to find the search target is a logarithmic function of the size of the search space.
Specific applications of search algorithms include:
Algorithms for searching virtual spaces are used in theconstraint satisfaction problem, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematicalequations andinequations / equalities. They are also used when the goal is to find a variable assignment that willmaximize or minimize a certain function of those variables. Algorithms for these problems include the basicbrute-force search (also called "naïve" or "uninformed" search), and a variety ofheuristics that try to exploit partial knowledge about the structure of this space, such as linear relaxation, constraint generation, andconstraint propagation.
An important subclass are thelocal search methods, that view the elements of the search space as thevertices of a graph, with edges defined by a set of heuristics applicable to the case; and scan the space by moving from item to item along the edges, for example according to thesteepest descent orbest-first criterion, or in astochastic search. This category includes a great variety of generalmetaheuristic methods, such assimulated annealing,tabu search,A-teams,[7] andgenetic programming, that combine arbitrary heuristics in specific ways. The opposite of local search would be global search methods. This method is applicable when the search space is not limited and all aspects of the given network are available to the entity running the search algorithm.[8]
This class also includes varioustree search algorithms, that view the elements as vertices of atree, and traverse that tree in some special order. Examples of the latter include the exhaustive methods such asdepth-first search andbreadth-first search, as well as various heuristic-basedsearch tree pruning methods such asbacktracking andbranch and bound. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree-search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called "completeness".
Another important sub-class consists of algorithms for exploring thegame tree of multiple-player games, such aschess orbackgammon, whose nodes consist of all possible game situations that could result from the current situation. The goal in these problems is to find the move that provides the best chance of a win, taking into account all possible moves of the opponent(s). Similar problems occur when humans or machines have to make successive decisions whose outcomes are not entirely under one's control, such as inrobot guidance or inmarketing,financial, ormilitary strategy planning. This kind of problem —combinatorial search — has been extensively studied in the context ofartificial intelligence. Examples of algorithms for this class are theminimax algorithm,alpha–beta pruning, and theA* algorithm and its variants.
An important and extensively studied subclass are thegraph algorithms, in particulargraph traversal algorithms, for finding specific sub-structures in a given graph — such assubgraphs,paths, circuits, and so on. Examples includeDijkstra's algorithm,Kruskal's algorithm, thenearest neighbour algorithm, andPrim's algorithm.
Another important subclass of this category are thestring searching algorithms, that search for patterns within strings. Two famous examples are theBoyer–Moore andKnuth–Morris–Pratt algorithms, and several algorithms based on thesuffix tree data structure.
In 1953, AmericanstatisticianJack Kiefer devisedFibonacci search which can be used to find the maximum of a unimodal function and has many other applications in computer science.
There are also search methods designed forquantum computers, likeGrover's algorithm, that are theoretically faster than linear or brute-force search even without the help of data structures or heuristics. While the ideas and applications behind quantum computers are still entirely theoretical, studies have been conducted with algorithms like Grover's that accurately replicate the hypothetical physical versions of quantum computing systems.[9]
Categories:
