Search algorithm: Difference between revisions

Revision as of 01:34, 30 June 2017

Revision as of 01:35, 30 June 2017

Line 15:

===For virtual search spaces===

Algorithms for searching virtual spaces are used in the constraint satisfaction problem, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical [[equation]]s and [[inequation]]s / equalities. They are also used when the goal is to find a variable assignment that will [[discrete optimization|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 [[heuristic function|heuristic]]s that try to exploit partial knowledge about the structure of thethis space, such as linear relaxation, constraint generation, and [[Local consistency|constraint propagation]].

An important subclass are the [[Local search (optimization)|local search]] methods, that view the elements of the search space as the [[vertex (graph theory)|vertices]] of a graph, with edges defined by a set of heuristics applicable to the case; and scan the space by moving from item to item along the edges, for example according to the [[gradient descent|steepest descent]] or [[best-first search|best-first]] criterion, or in a [[Stochastic optimization|stochastic search]]. This category includes a great variety of general [[metaheuristic]] methods, such as [[simulated annealing]], [[tabu search]], A-teams, and [[genetic programming]], that combine arbitrary heuristics in specific ways.