Local search (constraint satisfaction)
 | This article is actively undergoing a major edit for a little while. To help avoid edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 11:40, 21 February 2006 (UTC) (19 years ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions. |
In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name local search.
All local search algorithms use a function that evaluates the quality of assignment, for example the number of constraints satisfied by the assignment. The aim of local search is that of finding an assignment with the best possible quality, which is a solution if any exists.
Two classes of local search algorithms exist. The first one is that of greedy or non-randomized algorithms. These algorithms proceed by changing the current assignment by always trying to improve (or at least, non-decrease) its quality. The main problem of these algorithms is the possible presence of plateaus, which are regions of the space of assignments where no local move increases quality. The second class is that of randomized algorithms, the randomized ones, escape these plateaus by doing random moves.
Greedy algorithms
Hill climbing
The most basic form of local search is based on always trying to improve the quality of the solution. This method is called hill climbing proceed as follows: first, a random assignment is chosen; then, a value is changed in such as to maximally improve the quality of the resulting assignment. If no solution has been found after a given number of changes, a new random assignment is selected. Hill climbing algorithms can only escape a plateau by doing changes that do not change the quality of the assignment. As a result, they can be stuck in a plateau where the quality of assignment has a local maxima.
GSAT (greedy sat) was the first local search algorithm for satisfiability, and is a form of hill climbing.