1Directional consistencyChapter 4ICS-275Fall 2010Fall 2010 ICS 275 - Constraint NetworksFall 20102Tractable classesFall 2010ICS 275 - Constraint Networks3Backtrack-free search: orWhat level of consistency will guarantee global-consistencyBacktrack free and queries:Consistency,All solutionsCountingoptimizationFall 2010ICS 275 - Constraint Networks4Directional arc-consistency:another restriction on propagationD4={white,blue,black}D3={red,white,blue}D2={green,white,black}D1={red,white,black}X1=x2, x1=x3,x3=x4Fall 2010ICS 275 - Constraint Networks5Directional arc-consistency:another restriction on propagation D4={white,blue,black} D3={red,white,blue} D2={green,white,black} D1={red,white,black} X1=x2, x1=x3,  x3=x4After DAC:  D1= {white}, D2={green,white,black}, D3={white,blue}, D4={white,blue,black}Fall 2010ICS 275 - Constraint Networks6Algorithm for directional arc-consistency (DAC))(2ekO Complexity:Fall 2010ICS 275 - Constraint Networks7Directional arc-consistency may not be enough Directional path-consistencyFall 2010ICS 275 - Constraint Networks8Algorithm directional path consistency (DPC)Fall 2010ICS 275 - Constraint Networks9Example of DPCEDACB}2,1{}2,1{}2,1{}2,1{}3,2,1{Fall 2010ICS 275 - Constraint Networks10Directional i-consistencyFall 2010ICS 275 - Constraint Networks11Algorithm directional i-consistencyFall 2010ICS 275 - Constraint Networks12The induced-widthDPC recursively connects parents in the ordered graph, yielding: Width along ordering d, w(d):• max # of previous parents Induced width w*(d):• The width in the ordered induced graph Induced-width w*:• Smallest induced-width over all orderings Finding w*• NP-complete (Arnborg, 1985) but greedy heuristics (min-fill).EDACBFall 2010ICS 275 - Constraint Networks13Induced-widthFall 2010ICS 275 - Constraint Networks14Induced-width and DPC The induced graph of (G,d) is denoted (G*,d) The induced graph (G*,d) contains the graph generated by DPC along d, and the graph generated by directional i-consistency along d.Fall 2010ICS 275 - Constraint Networks15Refined complexity using induced-width Consequently we wish to have ordering with minimal induced-width Induced-width is equal to tree-width to be defined later. Finding min induced-width ordering is NP-completeFall 2010ICS 275 - Constraint Networks16Greedy algorithms for induced-width• Min-width ordering• Max-cardinality ordering• Min-fill ordering• Chordal graphsFall 2010ICS 275 - Constraint Networks17Min-width orderingFall 2010ICS 275 - Constraint Networks18Min-induced-widthFall 2010ICS 275 - Constraint Networks19Min-fill algorithm Prefers a node who adds the least number of fill-in arcs. Empirically, fill-in is the best among the greedy algorithms (MW,MIW,MF,MC)Fall 2010ICS 275 - Constraint Networks20Cordal graphs and max-cardinality ordering A graph is cordal if every cycle of length at least 4 has a chord Finding w* over chordal graph is easy using the max-cardinality ordering If G* is an induced graph it is chordal K-trees are special chordal graphs. Finding the max-clique in chordal graphs is easy (just enumerate all cliques in a max-cardinality orderingFall 2010ICS 275 - Constraint Networks21ExampleWe see again that G in Figure 4.1(a) is not chordal since the parents of A are not connected in the max-cardinality ordering in Figure 4.1(d). If we connect B and C, the resulting induced graph is chordal.Fall 2010ICS 275 - Constraint Networks22Max-cardinality orderingFigure 4.5 The max-cardinality (MC) ordering procedure.Fall 2010ICS 275 - Constraint Networks23Width vs local consistency:solving treesFall 2010ICS 275 - Constraint Networks24Tree-solving)(:2nkOcomplexityFall 2010ICS 275 - Constraint Networks25Width-2 and DPCFall 2010ICS 275 - Constraint Networks26Width vs directional consistency(Freuder 82)Fall 2010ICS 275 - Constraint Networks27Width vs i-consistency DAC and width-1 DPC and width-2 DIC_i and with-(i-1)  backtrack-free representation If a problem has width 2, will DPC make it backtrack-free? Adaptive-consistency: applies i-consistency when i is adapted to the number of parentsFall 2010ICS 275 - Constraint Networks28Adaptive-consistencyFall 2010ICS 275 - Constraint Networks29Bucket E: E D, E  CBucket D: D ABucket C: C BBucket B: B  ABucket A:A C widthinduced -**w ))exp(w O(n :Complexitycontradiction=D = CB = ABucket EliminationAdaptive Consistency (Dechter & Pearl, 1987)=Fall 2010ICS 275 - Constraint Networks30 dordering along widthinduced -(d) , **w(d)))exp(w O(n :space and Time EDACB}2,1{}2,1{}2,1{}2,1{}3,2,1{:)(AB :)(BC :)(AD :)(BE C,E D,E :)(ABucketBBucketCBucketDBucketEBucketAEDCB:)(EB :)(EC , BC :)(ED :)(BA D,A :)(EBucketBBucketCBucketDBucketABucketEADCB|| RDBE ,|| RE|| RDB|| RDCB|| RACB|| RABRARCBEBucket EliminationAdaptive Consistency (Dechter & Pearl, 1987)Fall 2010ICS 275 - Constraint Networks31The Idea of Elimination project and join E variableEliminate ECDBCEBEDDBCRRRR3value assignmentDBCRDBCeliminating EFall 2010ICS 275 - Constraint Networks32Variable Elimination Eliminate variablesone by one:“constraintpropagation”Solution generation after elimination is backtrack-free3Fall 2010ICS 275 - Constraint Networks33Adaptive-consistency, bucket-eliminationFall 2010ICS 275 - Constraint Networks34Properties of bucket-elimination(adaptive consistency) Adaptive consistency generates a constraint network that is backtrack-free (can be solved without dead-ends). The time and space complexity of adaptive consistency along ordering d is respectively, or O(r k^(w*+1)) when r is the number of constraints. Therefore, problems having bounded induced width are tractable (solved in polynomial time) Special cases: trees ( w*=1 ), series-parallel networks(w*=2 ), and in general k-trees ( w*=k ). 1*w1*w(k ) O (n),(2 k) O (n 1*wFall 2010ICS 275 - Constraint Networks35Back to Induced width Finding minimum-w* ordering is NP-complete (Arnborg, 1985) Greedy ordering heuristics: min-width, min-degree, max-cardinality (Bertele and Briochi, 1972; Freuder 1982), Min-fill.Fall 2010ICS 275 - Constraint Networks36Solving Trees (Mackworth and Freuder, 1985)Adaptive consistency is linear for trees andequivalent to enforcing directional