Information Technology Reference
In-Depth Information
3.7 Local Revision Search
At present, most algorithms are constructive methods based on the tree search.
But another method to solve combination problem draws people's attention for its
surprising experimental results recently, that is so-called , “local revision”(Gu,
1992). Firstly, this method produces a global but may not inconsistent variable
assignment, and then modifies some variable value according to the contradiction
appeared in order to reduce the assignments that violates constraints, and repeats
the process again until achieving a consistent assignment. This method follows a
simple rule: Find a variable which causes the contradiction, then select a new
assignment to it, such that assignments can reduce contradictions to the least. The
basic idea of this method is as follows.
Given a set of variable, a set of binary constraint, and an assignment of each
variable. If two variable values violate a constraint, then the two variables are
contradictory.
The Process is to select a contradictory variable, and assign a new value to it
in order to reduce contradictions to the least.
Local revision search is very effective, and the main reason is that, more
information are provided by variable assignments, thus the next transforming
state will reduce the contradictions tremendously.
Local revision search has shortcomings as well. First, the strategy is
incomplete. When the solution of problem does not exist, the search may not
stop. When the density of solution is low, the search efficiency is very low too.
We compared revision search and tree search on graph coloring problem, the
results show that when there are less edges in graph, revision search is better and
otherwise, tree search has higher efficiency. If the problem has no solution,
however, revision search will not stop.
At present, a new research direction of constraint search is studying the
difficulty distribution of CSP. Although CSP is generally a NP problem, a large
amount of CSPs can be solved during the tolerated time. The real intractable
problems account for a small number.
3.8 Graph-based Backjumping
Graph-based backjumping is a kind dependency-directed method, in which
dependency information comes from graph structure of constraint network. A
constraint graph consists of vertex that denotes variable and edge that denotes
