This article does not cite any references or sources. (August 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. 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 heuristic functions to apply knowledge about the structure of the search space to try to reduce the amount of time spent searching. Image File history File links Question_book-3. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... Input3 is the term denoting either an entrance or changes which are inserted into a system and which activate/modify a process. ... In search algorithms, search space is the collection of possible solutions to a problem, and incorporates some notion of distance between candidate solutions; the correct solution will be near the optimal point in this hypothetical space, which may be envisioned as having a dimension for each variable. ... In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... A heuristic function or simply a heuristic is a function that ranks alternatives in various search algorithms at each branching step basing on an available information in order to make a decision which branch is to be followed during a search. ... In search algorithms, search space is the collection of possible solutions to a problem, and incorporates some notion of distance between candidate solutions; the correct solution will be near the optimal point in this hypothetical space, which may be envisioned as having a dimension for each variable. ...

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. Look up Implementation in Wiktionary, the free dictionary. ... In computer science, abstraction is a mechanism and practice to reduce and factor out details so that one can focus on a few concepts at a time. ... In search algorithms, search space is the collection of possible solutions to a problem, and incorporates some notion of distance between candidate solutions; the correct solution will be near the optimal point in this hypothetical space, which may be envisioned as having a dimension for each variable. ...

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 sorting algorithm) and also be random access. Interpolation search is better than binary search for large sorted lists with fairly even distributions, but has a worst-case running time of O(n). Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computer science, random access is the ability to access a random element of a group in equal time. ... Interpolation search parallels how humans search through a telephone book. ...

Grover's algorithm is a quantum algorithm that offers quadratic speedup over the classical linear search for unsorted lists. However, it requires a currently non-existent quantum computer on which to run. Grovers algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(logN) storage space (see big O notation). ... The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ...

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. In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ... An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ...

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 search

Tree search algorithms are the heart of searching techniques. These search trees of nodes, 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. Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... A node is a basic unit used to build data structures, such as linked lists and tree data structures. ... A node is a basic unit used to build data structures, such as linked lists and tree data structures. ... A binary tree, a simple type of branching linked data structure. ... In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ... 9, 14, 19, 67 and 76 are leaf nodes. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... Iterative deepening depth-first search or IDDFS is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches , the depth of the shallowest goal state. ... In Computer Science Depth-limited search is an algorithm to explore the Vertices of a Graph. ... Bidirectional search is a graph search algorithm that runs two simultaneous searches: one forward from the initial state, and one backward from the goal, and stopping when the two meet in the middle. ... In computer science, uniform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. ...

Graph search

Many of the problems in graph theory can be solved using Graph traversal 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. A drawing of a graph. ... Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. ... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. ... Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. ... Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ...

SQL search

Many of the problems in Tree search can be solved using SQL type searches. SQL typically works best on Structured data. It offers one advantage over hierarchical type search in that it allows access to the data in many different ways. In a Hierarchical search your path is forced by the branches of the tree (example name by alphabetical order) while with SQL you have the flexibility of accessing the data along multiple directions (name, address, income etc...). Tree search algorithms are specialized versions of graph search algorithms, which take the properties of trees into account. ... SQL (IPA: or ), commonly expanded as Structured Query Language, is a computer language designed for the retrieval and management of data in relational database management systems, database schema creation and modification, and database object access control management. ...

Tradeoff Based search

While SQL search offers great flexibility to search the data, it still operates like a computer does: by constraints. In SQL, constraints are used to eliminate the data, while tradeoff based search uses a more "human" metaphor. For example if you are searching for a car in a dataset, your SQL statement looks like: select car from dataset where price < $30,000, and Consumption > 30MPG, and Color = 'RED'. While a tradeoff type query would look like "I like the red car, but I will settle for the blue if it is $2,000 cheaper". SQL (IPA: or ), commonly expanded as Structured Query Language, is a computer language designed for the retrieval and management of data in relational database management systems, database schema creation and modification, and database object access control management. ...

Informed search

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. A heuristic function or simply a heuristic is a function that ranks alternatives in various search algorithms at each branching step basing on an available information in order to make a decision which branch is to be followed during a 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*. Like the uninformed algorithms, they can be extended to work for graphs as well. Best-first search is a search algorithm which optimizes breadth-first search by expanding the most promising node chosen according to some rule. ... The A* search algorithm (pronounced A star) is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ...

Adversarial search

In games such as chess, there is a game tree of all possible moves by both players and the resulting board configurations, and we can search this tree to find an effective playing strategy. This type of problem has the unique characteristic that we must account for any possible move our opponent might make. To account for this, game-playing computer programs, as well as other forms of artificial intelligence like machine planning, often use search algorithms like the minimax algorithm, search tree pruning, and alpha-beta pruning. This article is about the Western board game. ... In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. ... AI redirects here. ... Minimax is a method in decision theory for minimizing the expected maximum loss. ... Pruning is a term in mathematics and informatics which describes a method of enumeration, which allows to cut parts of a decision tree. ... Alpha-beta pruning is a search algorithm that reduces the number of nodes that need to be evaluated in the search tree by the minimax algorithm. ...

Constraint satisfaction

This is a type of search which solves constraint satisfaction problems 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. Common tricks or techniques involved in backtracking is Constraint propagation, which is a general form of Forward checking. Other local search algorithms, such as generic algorithm, which minimize the conflicts, also do a good job. Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. ... Combinatorial search is a branch of computer science that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. ... Backtracking is a type of algorithm that is a refinement of brute force search. ... Backtracking is a type of algorithm that is a refinement of brute force search. ...

Other types

• String searching algorithms search for patterns within strings; one popular data structure that makes this more efficient is the suffix tree
• Genetic algorithms use ideas from evolution as heuristics for reducing the search space
• Sorting algorithms necessary for executing certain search algorithms
• Simulated annealing is a probabilistic search algorithm
• Tabu search is a technique to avoid discrete searches getting stuck in local minima
• Federated search
• Minimax which can be highly optimized using alpha-beta pruning is an algorithm to search for good moves in zero-sum games
• Ternary search

String searching algorithms are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... Suffix tree for the string BANANA padded with $. The six paths from the root to a leaf (shown as boxes) correspond to the six suffixes A$, NA$, ANA$, NANA$, ANANA$ and BANANA$. The numbers in the boxes give the start position of the corresponding suffix. ... A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ... This article is about evolution in biology. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... For other uses, see Annealing. ... The word probability derives from the Latin probare (to prove, or to test). ... Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ... Federated Search is an emerging feature of automated, web based library and information retrieval systems. ... “Minmax” redirects here. ... Alpha-beta pruning is a search algorithm that reduces the number of nodes that need to be evaluated in the search tree by the minimax algorithm. ... Zero-sum describes a situation in which a participants gain (or loss) is exactly balanced by the losses (or gains) of the other participant(s). ... A ternary search algorithm is a computer science technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa. ...

See also

• Selection algorithm
• No free lunch in search and optimization
• Secretary problem is an online (ie sequentially presented) search problem with imperfect information, and a statistically optimal strategy.

In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list, called order statistics. ... Many computational problems are solved by searching for good solutions in a space of candidates. ... In statistics and decision theory, the secretary problem (also known as the marriage problem, the optimal stopping problem, the sultans dowry problem or the fussy suitor problem) is a puzzle involving being presented sequentially with a known number of items of varying quality. ...

External links

• Self-Guided Lesson on Uninformed Search Go to the Wikiversity and teach yourself to program an uninformed search solution.