 | Search algorithm: Encyclopedia II - Search algorithm - Uninformed search
Search algorithm - Uninformed search
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. The drawback is that most search spaces are extremely large, and an uninformed search (especially of a tree) will take a reasonable amount of time only for small examples. As such, to speed up the process, sometimes only an informed search will do.
Search algorithm - List search
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 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 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 algorithm that offers quadratic speedup over the classical linear search for unsorted lists.
Hash tables are also used for list search, requiring only constant time for search in the average case, but more space overhead and terrible O(n) worst-case search time. Another search based on specialized data structures uses self-balancing binary search trees and requires O(log n) time to search; these can be seen as extending the main ideas of binary search to allow fast insertion and removal. See associative array for more discussion of list search data structures.
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.
Search algorithm - Tree search
Tree search algorithms are the heart of searching techniques. These search nodes of trees, whether that tree is explicit or implicit (generated on the go). The basic principle is that a 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 search, Depth-limited search, Bidirectional search and Uniform-cost search.
Search algorithm - Graph search
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.
Other related archivesA*, Best-first search, Bidirectional search, Breadth-first search, Brute-force search, Depth-first search, Depth-limited search, Dijkstra's algorithm, Federated search, Genetic algorithms, Grover's algorithm, Hash tables, Interpolation search, Iterative-deepening search, Kruskal's algorithm, No-Free-Lunch theorems, O, Prim's algorithm, Search algorithms, Secretary problem, Simulated annealing, String searching algorithms, Tabu search, Tree search algorithms, Uniform-cost search, abstraction, algorithm, alpha-beta pruning, artificial intelligence, associative array, backtracking, binary search, chess, combinatorial search, computational complexity, computer science, constraint satisfaction problems, data structure, evolution, game tree, graph theory, heuristic, heuristics, implementation, input, leaf node, linear search, minimax algorithm, nearest neighbour algorithm, node, probabilistic, quantum algorithm, random access, search space, search spaces, self-balancing binary search trees, sort algorithm, strings, suffix tree, trees
 Adapted from the Wikipedia article "Uninformed search", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki |
