Search algorithm: Difference between revisions

Revision as of 01:14, 17 March 2004

Revision as of 01:32, 17 March 2004

Line 1:

[[ja:検索]]

In [[computer science]], a '''search algorithm''', broadly speaking, is an [[algorithm]] that takes a problem as [[input]] and returns a solution to the problem. Most of the algorithms studied by computer scientists that solve problems are kinds of search algorithms. The set of all possible solutions to a problem is called the [[search space]]. [[Brute -force search]] or "naive" search algorithms use the simplest, most intuitive method of searching through the search space, whereas search algorithms that use [[heuristics]] apply knowledge about the structure of the search space to try to reduce the amount of time spent searching.

List search algorithms are perhaps the most basic kind of search algorithm. The goal is to find one element of a set by some key (perhaps containing other information related to the key). As this is a common problem in [[computer science]], the [[computational complexity]] of these algorithms has been well studied. The simplest such algorithm is [[linear search]]. It has [[big O notation|O]](n) running time, but can operate on a list containing the elements of the set. A more sophisticated list search algorithm is [[binary search]]. It runs in [[big O notation|O]](log(n)). This is significantly better than [[linear search]] for large lists of data, but it requires that the list be sorted before searching (see [[sort algorithm]]) and also be [[random access]]. [[Interpolation search]] is better than binary search for large sorted lists. However, the underlying data structure must allow such kind of searching. [[Hash table]]s are also used for search; they are the method of choice in most circumstances today. [[Grover's algorithm]] is a [[quantum computer|quantum algorithm]] that offers quadratic speedup over the classical linear search for unsorted lists.

[[Tree search algorithm]]s search nodes of [[tree (graph theory)|trees]],. andExamples manyinclude of the[[Depth-first problemssearch]], in[[Breadth-first search]], [[graphBest-first theorysearch]], areand solved[[A usingStar searchSearch algorithmsAlgorithm|A*]].

Many of the problems in [[graph theory]] are solved using search algorithms, such as [[Dijkstra's algorithm]], [[Kruskal's algorithm]], the [[nearest neighbour algorithm]], and [[Prim's algorithm]].

Game-playing computer programs and other forms of [[artificial intelligence]] like [[machine planning]] and often use search algorithms like the [[Minimax algorithm]], [[search tree pruning]], and [[alpha-beta pruning]].

[[String searching algorithm]]s search for patterns within [[string]]s.