Search algorithm

related topics
{math, number, function}
{theory, work, human}
{game, team, player}
{area, community, home}
{rate, high, increase}
{system, computer, user}
{woman, child, man}

In computer science, a search algorithm, broadly speaking, is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots of an equation with integer variables; or a combination of the two, such as the Hamiltonian circuits of a graph.

Contents

Classes of search algorithms

For explicitly stored databases

Algorithms for searching in explicitly stored databases include the simple linear search, and many other algorithms that use a variety of search data structures, such as binary search trees, heaps and hash tables, to speed up multiple queries over the same database.

There are also many algorithms designed specifically for retrieval in very large databases, such as bank account records, electronic documents, product catalogs, fingerprint and image databases, and so on.

For virtual search spaces

Algorithms for searching virtual spaces are used in constraint satisfaction problem, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical equations and inequations. They are also used when the goal is to find a variable assignment that will maximize or minimize a certain function of those variables. Algorithms for these problems include the basic brute-force search (also called "naïve" or "uninformed" search), and a variety of heuristics that try to exploit partial knowledge about structure of the space, such as linear relaxation, constraint generation, and constraint propagation.

Full article ▸

related documents
Constant of integration
Division algebra
Exact sequence
Separable space
Golomb coding
Mersenne prime
Probability space
Symmetric group
Banach fixed point theorem
Inverse limit
Euler's totient function
Analytic geometry
Linear equation
Kruskal's algorithm
Mersenne twister
Cardinality
Convex set
Tychonoff space
Local ring
Automated theorem proving
Controllability
Group representation
Separation axiom
Gamma function
Carmichael number
Topological group
Goodstein's theorem
Well-order
Diophantine set
Lebesgue measure