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:
“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)
“At any age we must cherish illusions, consolatory or merely pleasant; in youth, they are omnipresent; in old age we must search for them, or even invent them. But with all that, boredom is their natural and inevitable accompaniment.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“Only mediocrities progress. An artist revolves in a cycle of masterpieces, the first of which is no less perfect than the last.”
—Oscar Wilde (1854–1900)