Search algorithm: Difference between revisions

Revision as of 20:54, 11 April 2005

Revision as of 22:14, 7 May 2005

Line 1:

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 "naïve"/uninformed search algorithms use the simplest, most intuitive method of searching through the search space, whereas informed search algorithms use [[heuristics (computer science)|heuristics]] to apply knowledge about the structure of the [[search space]] to try to reduce the amount of time spent searching.

== Uninformed Searchsearch ==

An uninformed search algorithm is one that does not take into account the specific nature of the problem. As such, they can be implemented in general, and then the same [[implementation]] can be used in a wide range of problems thanks to [[Abstraction (computer science)|abstraction]]. The drawback is that most [[search space]]s are extremely large, and an uninformed search (especially of a tree) will only take a reasonable amount of time for small examples. As such, to speed up the process, sometimes only an informed search will do.

=== List Searchsearch ===

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]], which simply examines each element of the list in order. It has expensive [[big O notation|O]](n) running time, where ''n'' is the number of items in the list, but can be used directly on any unprocessed list. A more sophisticated list search algorithm is [[binary search]]; it runs in [[big O notation|O]](log ''n'') time. 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 very large sorted lists with fairly even distributions. [[Grover's algorithm]] is a [[quantum computer|quantum algorithm]] that offers quadratic speedup over the classical linear search for unsorted lists.

Line 11:

Most list search algorithms, such as linear search, binary search, and self-balancing binary search trees, can be extended with little additional cost to find all values less than or greater than a given key, an operation called ''range search''. The glaring exception is hash tables, which cannot perform such a search efficiently.

=== Tree Searchsearch ===

[[Tree search algorithm]]s are the heart of searching techniques. These search nodes of [[tree (graph theory)|tree]]s, whether that tree is explicit or implicit (generated on the go). The basic principle is that a [[node (computer science)|node]] is taken from a [[data structure]], its successors examined and added to the data structure. By manipulating the data structure, the tree is explored in different orders for instance level by level ([[Breadth-first search]]) or reaching a [[leaf node]] first and backtracking ([[Depth-first search]]). Other examples of tree-searches include [[Iterative deepening depth-first search|Iterative-deepening search]], [[Depth-limited search]], [[Bidirectional search]] and [[Uniform-cost search]].

===Graph Searchsearch ===

Many of the problems in [[graph theory]] can be solved using search algorithms, such as [[Dijkstra's algorithm]], [[Kruskal's algorithm]], the [[nearest neighbour algorithm]], and [[Prim's algorithm]]. These can be seen as extensions of the tree-search algorithms.

== Informed Searchsearch ==

In an informed search, a [[heuristic]] that is specific to the problem is used as a guide. A good heuristic will make an informed search dramatically out-perform any uninformed search.

There are few prominent informed list-search algorithms. A possible member of that category is a hash table with a hashing function that is a heuristic based on the problem at hand. Most informed search algorithms explore trees. These include [[Best-first search]], and [[A Star Search Algorithm|A*]]. Like the uninformed algorithms, they can be extended to work for graphs as well.

== Adversarial Searchsearch ==

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

== Constraint Satisfactionsatisfaction ==

This is a type of search which solves [[constraint satisfaction problem]]s where, rather than looking for a path, the solution is simply a set of values assigned to a set of variables. Because the variables can be processed in any order, the usual tree search algorithms are too inefficient. Methods of solving constraint problems include [[combinatorial search]] and [[backtracking]], both of which take advantage of the freedom associated with constraint problems.

== Other Typestypes ==

[[String searching algorithm]]s search for patterns within [[string]]s; one popular data structure that makes this more efficient is the [[suffix tree]].

Line 35:

[[Simulated annealing]] is a [[probabilistic]] search algorithm.

== Related articles ==

[[No-Free-Lunch theorems]] relates to the generality of search algorithms and the need for ___domain knowledge.