Content deleted Content added
fix reference formatting weirdness |
add examples of applications, to explain the usefulness of the algorithms |
||
Line 6:
}}
[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|upright=1.2|Visual representation of a [[hash table]], a [[data structure]] that allows for fast retrieval of information.]]
In [[computer science]], a '''search algorithm''' is any [[algorithm]] which solves the [[search problem]], namely, to retrieve information stored within some data structure, or calculated in the [[Feasible region|search space]] of a [[problem ___domain]]
* Problems in [[combinatorial optimization]], such as:
** The [[vehicle routing problem]], a form of [[shortest path problem]]
** The [[knapsack problem]]: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
** The [[nurse scheduling problem]]
* Problems in [[constraint satisfaction]], such as:
** The [[map coloring problem]]
** Filling in a [[sudoku]] or [[crossword puzzle]]
* In [[game theory]] and especially [[combinatorial game theory]], choosing the best move to make next (such as with the [[minmax]] algorithm)
* Finding a combination or password from the whole set of possibilities
* [[Factorization|Factoring]] an integer (an important problem in [[cryptography]])
* Optimizing an industrial process, such as a [[chemical reaction]], by changing the parameters of the process (like temperature, pressure, and pH)
* Retrieving a record from a [[database]]
* Finding the maximum or minimum value in a [[List (abstract data type)|list]] or [[Array data structure|array]]
* Checking to see if a given value is present in a set of values
[[Information retrieval]], such as [[web search]] is in some sense solving a search problem by finding which documents out of a large pool to display, and how to order them. But the problem of how to rank documents of relevance to human search queries is sufficiently specialized that this type of problem is generally studied separately from and solved and evaluated differently than the classic search problems above. Classic search algorithms are typically evaluated on how fast they can find a solution, and whether or not that solution is guaranteed to be optimal. Though information retrieval algorithms must be fast, the quality of ranking is more important, as is whether or not good results have been left out and bad results included.
The appropriate search algorithm often depends on the data structure being searched, and may also include prior knowledge about the data. Some database structures are specially constructed to make search algorithms faster or more efficient, such as a [[search tree]], [[hash map]], or a [[database index]]. {{Sfn|Beame|Fich|2002|p=39}}{{Sfn|Knuth|1998|loc=§6.5 ("Retrieval on Secondary Keys")}}
Search algorithms can be classified based on their mechanism of searching. [[Linear search]] algorithms check every record for the one associated with a target key in a linear fashion.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential Searching")}} [[Binary search algorithm|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.{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison of Keys")}} Digital search algorithms work based on the properties of digits in data structures that use numerical keys.{{Sfn|Knuth|1998|loc=§6.3 (Digital Searching)}} Finally, [[Hash table|hashing]] directly maps keys to records based on a [[hash function]].{{Sfn|Knuth|1998|loc=§6.4, (Hashing)}} Searches outside a linear search require that the data be sorted in some way.
==Classes==
| |||