today'sclass.ppt

Today’s class
Interleaving backtracking and consistency checking
Variable-ordering heuristics
Value-ordering heuristics
Intelligent backtracking
Marie desJardins
1
Advanced Constraint Techniques
Kumar, “Algorithms for constraint satisfaction problems: A survey”
Barták, “Constraint programming: In pursuit of the holy grail”
2
Review
Represent a problem as a set of variables and constraints among those variables
For binary constraints, result is a constraint graph G = (V, C) with N variables and M constraints
Use search and/or constraint propagation to solve the work
Improve efficiency of solving by
Interleaving search and constraint propagation
Variable ordering
Value ordering
Intelligent backtracking
3
A famous example:Labelling line drawings
Waltz labelling algorithm – one of the earliest CSP applications
Convex interior lines are labelled as +
Concave interior lines are labeled as –
Boundary lines are labeled as
There are 208 labellings (most of which are impossible)
Here are the 18 legal labellings:
4
Labelling line drawings II
Here are some illegal labelings:
+
+
-
-
-
5
Labelline line drawings (cont.)
Waltz labelling algorithm: Propagate constraints repeatedly until a solution is found
A solution for one labelling problem
A labelling problem with no solution
6
Ordered constraint graphs
Select a variable ordering, V1, …, Vn
Width of a node in this OCG is the number of arcs leading to earlier variables:
w(Vi) = Count ( (Vi, Vk) | k < i)
Width of the OCG is the maximum width of any node:
w(G) = Max (w (Vi)), 1 <= i <= N
Width of an unordered CG is the minimum width of all orderings of that graph (“best you can do”)
7
Tree-structured constraint graph
An OCG with width 1 is a constraint tree rooted at V1
That is, in the ordering V1, …, Vn, every node has zero or one parents
If this constraint tree is also node- and arc-consistent (., strongly 2-consistent), then it can be solved without backtracking
More generally, if the ordered gr