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:
“Civility, which is a disposition to accommodate and oblige others, is essentially the same in every country; but good breeding, as it is called, which is the manner of exerting that disposition, is different in almost every country, and merely local; and every man of sense imitates and conforms to that local good breeding of the place which he is at.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“When you start with a portrait and search for a pure form, a clear volume, through successive eliminations, you arrive inevitably at the egg. Likewise, starting with the egg and following the same process in reverse, one finishes with the portrait.”
—Pablo Picasso (1881–1973)