Local Search (constraint Satisfaction)
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 violated by the assignment. This amount is called the cost of the assignment. The aim of local search is that of finding an assignment of minimal cost, 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 decrease (or at least, non-increase) its cost. The main problem of these algorithms is the possible presence of plateaus, which are regions of the space of assignments where no local move decreases cost. The second class of local search algorithm have been invented to solve this problem. They escape these plateaus by doing random moves, and are called randomized local search algorithms.
Read more about Local Search (constraint Satisfaction): Random Walk, Local Search On A Cycle Cutset
Famous quotes containing the words local and/or search:
“Hey, you dress up our town very nicely. You don’t look out the Chamber of Commerce is going to list you in their publicity with the local attractions.”
—Robert M. Fresco, and Jack Arnold. Dr. Matt Hastings (John Agar)
“His life itself passes deeper in nature than the studies of the naturalist penetrate; himself a subject for the naturalist. The latter raises the moss and bark gently with his knife in search of insects; the former lays open logs to their core with his axe, and moss and bark fly far and wide. He gets his living by barking trees. Such a man has some right to fish, and I love to see nature carried out in him.”
—Henry David Thoreau (1817–1862)