Search
Search encompasses a very general class of algorithms for exploring a
problem space in order to find a solution. Virtually every problem
can be solved using a search algorithm, although searching can be
relatively inefficient for tasks such as arithmetic. Search methods
can be divided into systematic and nonsystematic algorithms.
Systematic algorithms are guaranteed to find a solution to the problem
or prove that no solution exists, given sufficient resources (e.g.,
time and space). Examples of systematic search algorithms are brute
force methods like depth-first search and breadth-first search.
Nonsystematic search algorithms are not guaranteed to find a solution
and cannot be used to prove that no solution exists. Perhaps the best
example of a nonsystematic search algorithm is local search. Local
search starts from some initial problem state, and then generates a
set of problem states that comprise the neighborhood of the initial
state. The local search algorithm then chooses one of the states in
the set as the new problem state, and generates a new set of
neighbors. This cycle is repeated until some stopping condition is
met. Examples of local search include GSAT, tabu search, and
simulated annealing.
CIRL
CIRL members have investigated local search methods for constraint
satisfaction and satisfiability problems. Part of the ongoing
research at CIRL is to investigate ways to make local search more
systematic, and to understand the issues that make local search better
or worse than systematic methods. We are also working to extend
existing search method to deal with more expressive representation
formalisms, such as pseudo-Boolean
representations and the partially first-order language QPROP.
Parent areas:
Reasoning
Subareas:
Nonsystematic Search Methods
Systematic Search Methods
Back to the CIRL Overview Page.