- Applied mathematics
- >
- Theoretical computer science
- >
- Algorithms
- >
- Search algorithms

- Fields of mathematics
- >
- Applied mathematics
- >
- Algorithms
- >
- Search algorithms

- Fields of mathematics
- >
- Mathematical logic
- >
- Algorithms
- >
- Search algorithms

- Philosophy of mathematics
- >
- Mathematical logic
- >
- Algorithms
- >
- Search algorithms

Golden-section search

The golden-section search is a technique for finding an extremum (minimum or maximum) of a function inside a specified interval. For a strictly unimodal function with an extremum inside the interval,

Best node search

Best node search (BNS), originally known as fuzzified game tree search, is a minimax search algorithm, developed in 2011. The idea is that the knowledge that one subtree is relatively better than some

Finger search

In computer science, a finger search on a data structure is an extension of any search operation that structure supports, where a reference (finger) to an element in the data structure is given along

Dancing Links

In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithm

Minimax

Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst

Phrase search

In computer science, phrase searching allows users to retrieve content from information systems (such as documents from file storage systems, records from databases, and web pages on the internet) tha

Double hashing

Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collisio

Quadratic probing

Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive

Combinatorial search

In computer science and artificial intelligence, combinatorial search studies search algorithms for solving instances of problems that are believed to be hard in general, by efficiently exploring the

Backjumping

In backtracking algorithms, backjumping is a technique that reduces search space, therefore increasing efficiency. While backtracking always goes up one level in the search tree when all values for a

Dichotomic search

In computer science, a dichotomic search is a search algorithm that operates by selecting between two distinct alternatives (dichotomies) at each step. It is a specific type of divide and conquer algo

Ternary search tree

In computer science, a ternary search tree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather

SSS*

SSS* is a search algorithm, introduced by George Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm. SSS* is

Hash function

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashe

Look-ahead (backtracking)

In backtracking algorithms, look ahead is the generic term for a subprocedure that attempts to foresee the effects of choosing a branching variable to evaluate one of its values. The two main aims of

State space search

State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the inte

Parallel metaheuristic

Parallel metaheuristic is a class of techniques that are capable of reducing both the numerical effort and the run time of a metaheuristic. To this end, concepts and technologies from the field of par

Late move reductions

In computer chess, and in other games that computers play, late move reductions is a non-game-specific enhancement to the alpha–beta algorithm and its variants which attempts to examine a game search

Similarity search

Similarity search is the most general term used for a range of mechanisms which share the principle of searching (typically, very large) spaces of objects where the only available comparator is the si

Inversion list

In computer science, an inversion list is a data structure that describes a set of non-overlapping numeric ranges, stored in increasing order. The set is stored in an array. Every other element is the

Johnson's algorithm

Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-wei

Index mapping

Index mapping (or direct addressing, or a trivial hash function) in computer science describes using an array, in which each position corresponds to a key in the universe of possible values.The techni

MaMF

MaMF, or Mammalian Motif Finder, is an algorithm for identifying motifs to which transcription factors bind. The algorithm takes as input a set of promoter sequences, and a motif width(w), and as outp

Nearest neighbor search

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically

Rapidly exploring dense trees

Rapidly exploring dense trees is a family of planning algorithms that includes the rapidly exploring random tree.

Difference-map algorithm

The difference-map algorithm is a search algorithm for general constraint satisfaction problems. It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projection

Contraction hierarchies

In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to

Linear search

In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has

Beam stack search

Beam stack search is a search algorithm that combines chronological backtracking (that is, depth-first search) with beam search and is similar to depth-first beam search. Both search algorithms are an

Mobilegeddon

Mobilegeddon is a name for Google's search engine algorithm update of April 21, 2015. The term was coined by Chuck Price in a post written for Search Engine Watch on March 9, 2015. The term was then a

Finger search tree

In computer science, finger search trees are a type of binary search tree that keeps pointers to interior nodes, called fingers. The fingers speed up searches, insertions, and deletions for elements c

Jump point search

In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating

Rainbow table

A rainbow table is an efficient way to store data that has been computed in advance to facilitate cracking passwords. To protect stored passwords from compromise in case of a data breach, organization

Hill climbing

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a prob

Linear-quadratic regulator rapidly-exploring random tree

Linear-quadratic regulator rapidly-exploring random tree (LQR-RRT) is a sampling based algorithm for kinodynamic planning. A solver is producing random actions which are forming a funnel in the state

Sudoku solving algorithms

A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may conta

Dynamic perfect hashing

In computer science, dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure.While more memory-intensive than its hash table counterparts, this techn

Search tree

In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater t

Spiral hashing

Spiral hashing, also known as Spiral Storage is an extensible hashing algorithm. As in all hashing schemes, spiral hashing stores records in a varying number of buckets, using a record key for address

Binary search algorithm

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binar

Incremental heuristic search

Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incomple

Fractional cascading

In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence

Hopscotch hashing

Hopscotch hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table using open addressing. It is also well suited for implementing a concurrent h

Lexicographic breadth-first search

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produ

Maximum inner-product search

Maximum inner-product search (MIPS) is a search problem, with a corresponding class of search algorithms which attempt to maximise the inner product between a query and the data items to be retrieved.

Interpolation search

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957.

Uniform binary search

Uniform binary search is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth's The Art of Computer Programming. It uses a lookup table to update a single

Query expansion

Query expansion (QE) is the process of reformulating a given query to improve retrieval performance in information retrieval operations, particularly in the context of query understanding.In the conte

Spreading activation

Spreading activation is a method for searching associative networks, biological and artificial neural networks, or semantic networks. The search process is initiated by labeling a set of source nodes

Linear probing

Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a g

K-nearest neighbors algorithm

In statistics, the k-nearest neighbors algorithm (k-NN) is a non-parametric supervised learning method first developed by Evelyn Fix and Joseph Hodges in 1951, and later expanded by Thomas Cover. It i

Thought vector

Thought vector is a term popularized by Geoffrey Hinton, the prominent deep-learning researcher now at Google, which uses vectors based on natural language to improve its search results.

Bayesian search theory

Bayesian search theory is the application of Bayesian statistics to the search for lost objects. It has been used several times to find lost sea vessels, for example USS Scorpion, and has played a key

Iterative deepening depth-first search

In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of de

Best-first search

Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estim

Anytime A*

In computer science, anytime A* is a family of variants of the A* search algorithm. Like other anytime algorithms, it has a flexible time cost, can return a valid solution to a pathfinding or graph tr

Alpha–beta pruning

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly

God's algorithm

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any a

Any-angle path planning

Any-angle path planning algorithms are a subset of pathfinding algorithms that search for a path between two points in space and allow the turns in the path to have any angle. The result is a path tha

Fringe search

In computer science, fringe search is a graph search algorithm that finds the least-cost path from a given initial node to one goal node. In essence, fringe search is a middle ground between A* and th

Beam search

In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that r

Fibonacci search technique

In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.

UUHash

UUHash is a hash algorithm employed by clients on the FastTrack network. It is employed for its ability to hash very large files in a very short period of time, even on older computers. However, this

All nearest smaller values

In computer science, the all nearest smaller values problem is the following task: for each position in a sequence of numbers, search among the previous positions for the last position that contains a

Genetic algorithm

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA).

Amplitude amplification

Amplitude amplification is a technique in quantum computing which generalizes the idea behindthe Grover's search algorithm, and gives rise to a family ofquantum algorithms.It was discovered by Gilles

Rapidly-exploring random tree

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally

(1+ε)-approximate nearest neighbor search

(1+ε)-approximate nearest neighbor search is a special case of the nearest neighbor search problem. The solution to the (1+ε)-approximate nearest neighbor search is a point or multiple points within d

Multiplicative binary search

In computer science, multiplicative binary search is a variationof binary search that uses a specific permutation of keys in an array instead of the sorted order used by regular binarysearch.Multiplic

Range minimum query

In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in compu

B*

In computer science, B* (pronounced "B star") is a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals). Firs

Proof-number search

Proof-number search (short: PN search) is a game tree search algorithm invented by Victor Allis, with applications mostly in , but also for sub-goals during games. Using a binary goal (e.g. first play

Universal hashing

In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical

Perfect hash function

In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective fun

Anytime algorithm

In computer science, an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends. The algorithm is expected to find better and better so

SMA*

SMA* or Simplified Memory Bounded A* is a shortest path algorithm based on the A* algorithm. The main advantage of SMA* is that it uses a bounded memory, while the A* algorithm might need exponential

D*

D* (pronounced "D star") is any one of the following three related incremental search algorithms:
* The original D*, by Anthony Stentz, is an informed incremental search algorithm.
* Focused D* is a

Variable neighborhood search

Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems.It explores dist

Backtracking

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandon

Dijkstra's algorithm

Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer sc

Grover's algorithm

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black

Breadth-first search

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior

Bidirectional search

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial

Locality-sensitive hashing

In computer science, locality-sensitive hashing (LSH) is an algorithmic technique that hashes similar input items into the same "buckets" with high probability. (The number of buckets is much smaller

Lifelong Planning A*

LPA* or Lifelong Planning A* is an incremental heuristic search algorithm based on A*. It was first described by Sven Koenig and Maxim Likhachev in 2001.

Null-move heuristic

In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm.

Cuckoo hashing

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of som

Disjoint-set data structure

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivale

Reverse-search algorithm

Reverse-search algorithms are a class of algorithms for generating all objects of a given size, from certain classes of combinatorial objects. In many cases, these methods allow the objects to be gene

Brute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enum

MTD(f)

MTD(f) is an alpha-beta game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a sho

Gestalt pattern matching

Gestalt pattern matching, also Ratcliff/Obershelp pattern recognition, is a string-matching algorithm for determining the similarity of two strings. It was developed in 1983 by John W. Ratcliff and an

Tabu search

Tabu search is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) se

Iterative deepening A*

Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph.

Exponential search

In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching so

Graphplan

Graphplan is an algorithm for automated planning developed by Avrim Blum and in 1995. Graphplan takes as input a planning problem expressed in STRIPS and produces, if one is possible, a sequence of op

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of

Stack search

Stack search (also known as Stack decoding algorithm) is a search algorithm similar to beam search. It can be used to explore tree-structured search spaces and is often employed in Natural language pr

K-independent hashing

In computer science, a family of hash functions is said to be k-independent, k-wise independent or k-universal if selecting a function at random from the family guarantees that the hash codes of any d

Knuth's Algorithm X

Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficie

Expectiminimax

The expectiminimax algorithm is a variation of the minimax algorithm, for use in artificial intelligence systems that play two-player zero-sum games, such as backgammon, in which the outcome depends o

Siamese method

The Siamese method, or De la Loubère method, is a simple method to construct any size of n-odd magic squares (i.e. number squares in which the sums of all rows, columns and diagonals are identical). T

Theta*

Theta* is an any-angle path planning algorithm that is based on the A* search algorithm. It can find near-optimal paths with run times comparable to those of A*.

Variation (game tree)

A variation can refer to a specific sequence of successive moves in a turn-based game, often used to specify a hypothetical future state of a game that is being played. Although the term is most commo

Geometric hashing

In computer science, geometric hashing is a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation, though extensions exist

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the

Linear hashing

Linear hashing (LH) is a dynamic data structure which implements a hash table and grows or shrinks one bucket at a time. It was invented by Witold Litwin in 1980. It has been analyzed by Baeza-Yates a

Rocchio algorithm

The Rocchio algorithm is based on a method of relevance feedback found in information retrieval systems which stemmed from the SMART Information Retrieval System developed between 1960 and 1964. Like

Jump search

In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items Lkm, where and m is the block size, until an item is found that

A* search algorithm

A* (pronounced "A-star") is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practic

NewsRx

NewsRx is a media and technology company focusing on digital media, printed media, news services, and knowledge discovery through its BUTTER platform. In 1995 the company was the world's largest produ

Best bin first

Best bin first is a search algorithm that is designed to efficiently find an approximate solution to the nearest neighbor search problem in very-high-dimensional spaces. The algorithm is based on a va

Search game

A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always

Ternary search

A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function. A ternary search determines either that the minimum or maximum cannot be in the

BitFunnel

BitFunnel is the search engine indexing algorithm and a set of components used in the Bing search engine, which were made open source in 2016. BitFunnel uses bit-sliced signatures instead of an invert

Extendible hashing

Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup. Because of the hierarchical nature of the system, re-hashing is an incremental operat

Search-based software engineering

Search-based software engineering (SBSE) applies metaheuristic search techniques such as genetic algorithms, simulated annealing and tabu search to software engineering problems. Many activities in so

Inverted index

In computer science, an inverted index (also referred to as a postings list, postings file, or inverted file) is a database index storing a mapping from content, such as words or numbers, to its locat

© 2023 Useful Links.