look-ahead

helps the choices in backtracking:

variable to evaluate
order of values for the variable

conflicting aims

when choosing the variable vs. the first value

variable: choose one that quickly proves inconsistency
value: that of a solution

why? next slides

choice of variable

the tree of recursive calls depends on the choice of the variables
not the same size!

extreme case: with a variable, immediate inconsistency
but, another is chosen

example: constraint y < x with D_y = {1,2,3}


choose variable `y`	choose another variable `z` then others before `y`

better choose y
inconsistency detected immediately

choose z: visit a tree

choice of variable

good = small subtrees

implicit assumption: no solutions in there

not intuitive…

find solution quickly vs. prove inconsistency quickly

finding solution is very quick, but …
only if correct path could be guessed each time

impossible to guarantee the correct choice at each node

one error ⇒ visit a tree

visiting a complete tree may be much larger than reaching the solution

visiting a subtree with no solution dominates the cost
⇒ optimize for that

number of possible values

rough estimation of the size of the subtree:


few possible values	many possible values

few values ⇒ few subtrees

not guaranteed: few large subtrees vs. many small subtrees
only an estimate!

estimate: better choose y

size of subtree

knowning the size of subtree would solve the problem
but, requires visiting them
(after done, no point into choosing another variable)

easy case?

The point of all this is to evaluate which variable x to choose before then testing all possible values for it. Actually visiting the subtrees amounts to actually performing all recursive calls with the assumption that x is chosen. At that point, there would be no point into testing another variable, since the subtree is already solved. Rather, the estimate of the size of the subtree should be as reliable as possible, but also quick, since it has to be done in every recursive call of the backtracking algorithm.

easy case

easy case: empty subtrees


few subtrees, none empty	may subtrees, but many of them empty

second is better
fewer non-empty subtrees

still a rough estimate

choice of the variable

best variable x:
minimal number of values x=a that are not immediately inconsistent

for each variable x:
- Dtemp_x=D_x
- for each a ∈ D_x
  - if the current evaluation plus x=a violates a constraint
    - remove a from Dtemp_x
select a variable x of minimal Dtemp_x

Look ahead

principle: simulate the effects of adding x=a to the current evaluation

remove values that immediately lead to ionconsistency

choose variable with few possible remaining values

difference look-ahead/backtracking

first do look-ahead (simulate x=a)
then do backtracking (add x=a)

same? repeated operations?

backtracking: do x=a only for the variable chosen in the recursive call
then perform the recursive call
look-ahead: test x=a for all x and a
done for choosing the variable x for the recursive calls
(then x=a only done for that variable)

in short: backtracking does x=a only for the chosen variable
look-ahead does it for all variables, and does it for choosing the variable

look-ahead as simulation

look-ahead simulates the first step of backtracking

evaluates the usefulness of the possible next steps

look ahead, recast

for each x=a, estimate the cost
size of subtree

how to estimate: check whether subtree is empty
constraint immediately violated with x=a

improve estimate?

forward checking

sometimes no solution has x=a
even if no constraint is violated

forward checking find some cases when it happens

simulates a simplification that can be done if x=a

forward checking algorithm

for variable x and value a ∈ D_x:

for each variable y in a constraint with x:
- remove from D_y all values not consistent with x=a
- if D_y=∅
  - x=a not possible

choice of variable, with forward checking

for each variable x:
- Dtemp_x=D_x
- for each a ∈ D_x
  - perform forward checking on x=a
  - if some domain ends up empty:
    - remove a from Dtemp_x
choose variable x with smallest Dtemp_x

all of this from a partial evaluation

look-ahead: generalization

instead of:

forward checking on x=a
check if some domain is empty

use:

simulate some effects of adding x=a
to the current partial evaluation
check if inconsistency is proved

example: instead of forward checking, use arc-consistency

forward checking and arc consistency

both remove elements from domains

both prove inconsistency when a domain is empty

they differ

forward checking vs. arc consistency

binary constraints

when checking x=a

forward checking: check arc consistency of un assigned variable with x
arc consistency: all pairs of variables

in both cases, with D'_x={a}

forward checking vs. arc consistency, graphically

with x=a

forward checking:
arc consistency:

red = constraints checked

full and partial look ahead

less costly than arc consistency

detect inconsistency more often than forward checking

full look ahead

force arc consistency once, only in one direction

for each constraint, check and force arc consistency

do not repeat, unlike arc consistency

partial look ahead

check consistency of a variable with the following

following = according to a given order

value order

variable chosen

second choice: which value to try first, second, etc.

general principle: choose the value most likely to be part of a solution

“most likely” = can never be sure without actually find a solution

value most likely to be in a solution

various methods

choose based on effects of the look ahead method used
(forward checking, arc consistency, ecc.)

look ahead done anyway ⇒ little additional cost

min-conflicts

choose value such that look ahead remove the fewest values from the domains

look ahead for each possible value
count how many values have been removed from all domains
first value is that removing less values, etc.

max-domain-size

do look ahead for each value

for each value, see which domain remains the smallest

first value is the one when this number is the largest

estimate number of solutions

do look ahead for each value

multiply the size of domains (what remains after look ahead)

this is a (largely optimistic) estimate of the number of solution

use this for ordering the values (larger is better)

randomization

two variables give the same estimate ⇒ choose randomly