Search Algorithm
Jump to navigation
Jump to search
A Search Algorithm is an algorithm that can solve a search task.
- Context:
- It can range from being an Exhaustive Search Algorithm to being an Approximate Search Algorithm.
- It can be a Ranking Search Algorithm.
- Example(s):
- a String Searching Algorithm(String Matching Algorithm).
- a Tuple Searching Algorithm(Tuple Matching Algorithm).
- a Graph Searching Algorithm(Graph Matching Algorithm), such as a: Lattice Searching Algorithm.
- an Ontology-based Search Algorithm, if an Ontology is available.
- …
- Counter-Example(s):
- See: No Free Lunch Theorem.
References
2011
- (Wikipedia, 2011) ⇒ http://en.wikipedia.org/wiki/Search_algorithm
- 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.
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.
- 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.
2009
- (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
- In computing, there are circumstances in which the outputs of all procedures solving a particular type of problem are statistically identical. A colorful way of describing such a circumstance, introduced by David H. Wolpert and William G. Macready in connection with the problems of search[1] and optimization,[2] is to say that there is no free lunch. Wolpert had previously derived no free lunch theorems for machine learning (statistical inference). [3] Before Wolpert's article was published, Cullen Schaffer had summarized a preprint version of this work of Wolpert's, but used different terminology. [4]
- In the "no free lunch" metaphor, each "restaurant" (problem-solving procedure) has a "menu" associating each "lunch plate" (problem) with a "price" (the performance of the procedure in solving the problem). The menus of restaurants are identical except in one regard — the prices are shuffled from one restaurant to the next. For an omnivore who is as likely to order each plate as any other, the average cost of lunch does not depend on the choice of restaurant. But a vegan who goes to lunch regularly with a carnivore who seeks economy pays a high average cost for lunch. To methodically reduce the average cost, one must use advance knowledge of a) what one will order and b) what the order will cost at various restaurants. That is, improvement of performance in problem-solving hinges on using prior information to match procedures to problems. [2][4]
- In formal terms, there is no free lunch when the probability distribution on problem instances is such that all problem solvers have identically distributed results. In the case of search, a problem instance is an objective function, and a result is a sequence of values obtained in evaluation of candidate solutions in the domain of the function. For typical interpretations of results, search is an optimization process. There is no free lunch in search if and only if the distribution on objective functions is invariant under permutation of the space of candidate solutions. [5][6][7] This condition does not hold precisely in practice,[6] but an "(almost) no free lunch" theorem suggests that it holds approximately. [8]