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.
Other articles related to "local":
... Localsearch usually works on all variables,improving a complete assignment to them ... However,local search can also be run on a subset of variables,using some other mechanism for the other variables ... A proposed algorithm works on a cycle cutset,which is a set of variables that,if removed from the problem,makes it acyclic ...
Famous quotes containing the words search and/or local:
“So often has my judgment deceived me in my life, that I always suspect it, right or wrong,at least I am seldom hot upon cold subjects. For all this, I reverence truth as much as any body; and ... if a man will but take me by the hand, and go quietly and search for it ... Ill go to the worlds end with him:MBut I hate disputes.”
—Laurence Sterne (17131768)
“Surely there must be some way to find a husband or, for that matter, merely an escort, without sacrificing ones privacy, self-respect, and interior decorating scheme. For example, men could be imported from the developing countries, many parts of which are suffering from a man excess, at least in relation to local food supply.”
—Barbara Ehrenreich (b. 1941)