Citizendia
Your Ad Here

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. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation Input is the term denoting either an entrance or changes which are inserted into a System and which activate/modify a Process. 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. In Computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique A heuristic function or simply a Heuristic is a function that ranks alternatives in various Search algorithms at each branching step basing on

Contents

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. Implementation is the realization of an application or execution of a Plan, idea Model, Design, Specification, standard, Algorithm 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 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.

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. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources The simplest such algorithm is linear search, which simply examines each element of the list in order. In Computer science, linear search is a Search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular 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. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments A more sophisticated list search algorithm is binary search; it runs in O(log n) time. A binary search algorithm (or binary chop) is a technique for locating a particular value in a sorted list of values In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments 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. In Computer science, linear search is a Search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular 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 (sometimes called direct access) is the ability to access an arbitrary element of a sequence in equal time 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). Interpolation search is an Algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key

Grover's algorithm is a quantum algorithm that offers quadratic speedup over the classical linear search for unsorted lists. Grover's algorithm is a Quantum algorithm for searching an unsorted Database with N entries in O(N1/2 time and using A quantum computer is a device for Computation that makes direct use of distinctively Quantum mechanical Phenomena, such as superposition However, it requires a currently non-existent quantum computer on which to run.

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. In Computer science, a hash table, or a hash map, is a Data structure that associates keys with values. In Computational complexity theory, constant time, or O (1 time refers to the computation time of a problem when the time needed to solve that problem does not depend 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. In Computer science, a self-balancing binary search tree or height-balanced binary search tree is a Binary search tree that attempts to keep its height See associative array for more discussion of list search data structures. An associative array (also associative container, map, mapping, hash, dictionary, finite map, and in query-processing an

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. In Computer science, tree-traversal refers to the process of visiting each node in a Tree data structure, exactly once in a systematic way These search trees of nodes, whether that tree is explicit or implicit (generated on the go). In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path. A node is an abstract basic unit used to build linked Data structures such as trees, Linked lists and computer-based representations of graphs The basic principle is that a node is taken from a data structure, its successors examined and added to the data structure. A node is an abstract basic unit used to build linked Data structures such as trees, Linked lists and computer-based representations of graphs A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently 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). In Graph theory, breadth-first search ( BFS) is a Graph search algorithm that begins at the root node and explores all the neighboring nodes In Computer science, a leaf node or external node is a node of a Tree data structure that has zero Child nodes Often leaf nodes are Depth-first search ( DFS) is an Algorithm for traversing or searching a tree, Tree structure, or graph. Other examples of tree-searches include iterative-deepening search, depth-limited search, bidirectional search, and uniform-cost search. Iterative deepening depth-first search (IDDFS is a State space search strategy in which a Depth-limited search is run repeatedly increasing the depth limit with 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 In Computer science, uniform-cost search ( UCS) is a Tree search algorithm used for traversing or searching a Weighted tree, Tree

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. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner Dijkstra's algorithm, conceived by Dutch Computer scientist Edsger Dijkstra in 1959 is a Graph search algorithm that solves the single-source Shortest Kruskal's 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. Prim's algorithm is an algorithm in Graph theory that finds a Minimum spanning tree for a connected weighted graph These can be seen as extensions of the tree-search algorithms.

Informed search

In an informed search, a heuristic that is specific to the problem is used as a guide. A heuristic function or simply a Heuristic is a function that ranks alternatives in various Search algorithms at each branching step basing on 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*. Best-first search is a Search algorithm which explores a graph by expanding the most promising node chosen according to some rule In Computer science, A* (pronounced "A star" is a best-first, Graph search algorithm that finds the least-cost path from a given initial Like the uninformed algorithms, they can be extended to work for graphs as well.

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. Chess is a recreational and competitive Game played between two players. If you're looking for game tree as it's used in game theory (not combinatorial game theory please see Extensive form game. 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. Minimax (sometimes minmax) is a decision rule used in Decision theory, Game theory, Statistics and Philosophy for mini mizing 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 which seeks to reduce the number of nodes that are 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. Constraint satisfaction problems or CSP s are mathematical problems where one must find states or objects that satisfy a number of Constraints ' or criteria 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. Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of Feasible solutions is discrete or can be reduced Backtracking is a type of Algorithm that is a refinement of Brute force search. Common tricks or techniques involved in backtracking is Constraint propagation, which is a general form of Forward checking. Backtracking is a type of Algorithm that is a refinement of Brute force search. Other local search algorithms, such as generic algorithm, which minimize the conflicts, also do a good job.

Other types

See also

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic