Fast solutions to csps B ased on PROSSER, P Hybrid algorithms for the constraint satisfaction problem Computational Intelligence 9 (1993),268-299 Outline · Motivation Methods of advancing csp search Backmarking Forward Checking Hybrid algorithms · Conclusion
Fast Solutions to CSP’s Based on PROSSER, P. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9 (1993), 268--299 Outline • Motivation • Methods of advancing CSP search – Backmarking – Forward Checking • Hybrid algorithms • Conclusion
Problem to be solved Given a set of n variables where the ith variable 11) Why Binary CSPs Every higher order(multiple variables), finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introduced
Problem to be solved Given a set of n variables where the ith variable, 1i ) Why Binary CSP’s Every higher order (multiple variables) , finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introduced
What is the forward move and why change it? Forward move- the procedure that determines what actions to take(consistency checks, bookkeeping, etc)when the next variable is instantiated Goal: avoid unnecessary computation .Backmarking(BM)-remembers consistency checks it already erformed Forward Checking(FC)-doesn't expand nodes it knows arent feasible The 5 Base styles of search Go Backwards More BJ CBJ informed BM yards algorithms FC Generally Faste Different styles
What is the forward move and why change it? Forward move – the procedure that determines what actions to take (consistency checks, bookkeeping, etc) when the next variable is instantiated. Goal : avoid unnecessary computation •Backmarking (BM) – remembers consistency checks it already performed •Forward Checking (FC) – doesn’t expand nodes it knows aren’t feasible Go Backwards Go Forwards BT BM FC BJ CBJ More informed styles Different styles The 5 Base styles of search Hybrid Algorithms Generally Faster
Outline · Motivation Methods of advancing CSP search Backmarking Forward Checking ° Hybrid algorithms · Conclusion What does bm do? Objective: BM prevents redundant consistency checks when The current variable is known to fail with its current value because of some variable in the past still has the value that made the current variable fail The current variable is known to succeed with its current value in a check against a past value that still has the same value that made the current variable succeed Tradeoff: must spend time doing, and allot space for, bookkeeping
Outline • Motivation • Methods of advancing CSP search – Backmarking – Forward Checking • Hybrid algorithms • Conclusion What does BM do? • Objective : BM prevents redundant consistency checks when – The current variable is known to fail with its current value because of some variable in the past still has the value that made the current variable fail. – The current variable is known to succeed with its current value in a check against a past value that still has the same value that made the current variable succeed. • Tradeoff : must spend time doing, and allot space for, bookkeeping
What does bm do? Maximum checking level(mcl)array Size= number of variables x domain size mcli, k] holds the index of the deepest variable that v=k, kEDi, was checked against Minimum backup level(mbl)array Size= number of variablesx 1 mbl[i] the index of the shallowest past variable that has changed value since v[i] was the current variable What does bm do? mcli k]=mbll] means[=k passed consistency checking for all variables in the past of mbl1]. Vi] only needs to be checked for consistency with the new variables, those in the future of mbl[]
What does BM do? • Maximum checking level (mcl) array – Size = Number of variables x domain size – mcl[i,k] holds the index of the deepest variable that v[i] = k, k ∊ Di , was checked against • Minimum backup level (mbl) array – Size = Number of variables x 1 – mbl[i] the index of the shallowest past variable that has changed value since v[i] was the current variable What does BM do? • mcl[i,k] = mbl[i] means v[i] = k passed consistency checking for all variables in the past of mbl[i]. V[i] only needs to be checked for consistency with the new variables, those in the future of mbl[i]
I RGB 受 Backmarking example 000 40000 290Q 390 50 Suppose no element of the domain of the 5th variable is consistent with the first element of the domain of the first variable 上〓 Backmarking example domain 20 4◎0
Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 i mbl R G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Remaining domain Suppose no element of the domain of the 5th variable is consistent with the first element of the domain of the first variable Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 i mbl R G 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 Remaining domain
I RGB 受 Backmarking example 000 3000 2○0 4◎○ Skipping a step 上〓 Backmarking example domain 20
Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 i mbl R G 0 0 0 3 0 0 2 0 0 1 0 0 0 0 0 Remaining domain Skipping a step Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 0 0 3 0 0 2 0 0 1 0 0 0 0 0 Remaining domain X X
R B 受 Backmarking example G0000 000 2○0 4◎○ 夏 上〓 Backmarking example domain 20 5鱼Q
Backmarking example Variable # 1 2 3 4 5 0 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 1 0 3 0 0 2 0 0 1 0 0 0 0 0 Remaining domain X X X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 1 4 3 0 0 2 0 0 1 0 0 0 0 0 Remaining domain X X X X
R B 受 Backmarking example G0000 000 2○0 夏Q B Backmarking example 0003 domain 20 4Q○
Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 1 4 3 0 0 2 0 0 1 0 0 0 0 0 Remaining domain X X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 1 4 3 3 0 2 0 0 1 0 0 0 0 0 Remaining domain X
I RGB 受 Backmarking example 000 2○0 5夏QQ No consistency checks at level 5 will be performed until the value of the first variable is changed B Backmarking example 0003 domain 20 5鱼⑧ Eventually variable 4 also encounters dwo
Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 1 4 3 3 0 2 0 0 1 0 0 0 0 0 Remaining domain X No consistency checks at level 5 will be performed until the value of the first variable is changed X X Backmarking example Variable # 1 2 3 4 5 1 0 0 0 0 B 5 4 3 2 1 i mbl R G 1 1 4 3 3 0 2 0 0 1 0 0 0 0 0 Remaining domain X X Eventually variable 4 also encounters DWO X X X X