Local Search On A Cycle Cutset
Local search 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.
For any assignment of the variables of the cutset, the remaining problem has a forest as primal graph. As a result, it can be solved efficiently. In order to guide local search, an algorithm detecting the minimal number of constraints that can be violated is used in place of a satisfiability algorithm on the for forest part of the problem.
This minimal number is found by determining the cost of each variable assignment. This cost is the minimal number of constraints violated by an assignment of the variables in the subtree rooted at the variable, when the variable takes the given value. This cost can be calculated as follows. If denotes the cost of the assignment and are the children of, the following formula holds. In this formula, is the 0 or 1 depending on whether the assignment violates the constraint between and .
The cost for variables in the cutset is zero, and these variables are assumed to be allowed to take only their given value. With these assumptions, the above formula allows computing the cost of all variable evaluations by iteratively proceeding bottom-up from the leaves to the root(s) of the forest.
The cost of variable evaluations can be used by local search for computing the cost of a solution. The cost of values of the roots of the forest is indeed the minimal number of violated constraints in the forest for these given values. These costs can therefore used to evaluate the cost of the assignment to the cutset variables and to estimate the cost of similar assignments on the cutset variables.
Read more about this topic: Local Search (constraint Satisfaction)
Famous quotes containing the words local, search and/or cycle:
“The local is a shabby thing. Theres nothing worse than bringing us back down to our own little corner, our own territory, the radiant promiscuity of the face to face. A culture which has taken the risk of the universal, must perish by the universal.”
—Jean Baudrillard (b. 1929)
“Let the maiden, with erect soul, walk serenely on her way, accept the hint of each new experience, search in turn all the objects that solicit her eye, that she may learn the power and charm of her new-born being, which is the kindling of a new dawn in the recesses of space.”
—Ralph Waldo Emerson (18031882)
“Only mediocrities progress. An artist revolves in a cycle of masterpieces, the first of which is no less perfect than the last.”
—Oscar Wilde (18541900)