documents/search/search.tex

72 Every variable has a {\em domain} of values that it can take
82 \item If a variable is given a value (from its domain, of course),
83         we call this an {\em assignment}. If every problem variable is given
269 by variable and value selection strategies.
284 is to choose a particular value for a problem variable
288 For a boolean variable, this means setting the variable to 0 in one
295 Other forms of choices are possible. If X2 is a variable that can take
306 for a variable. It is also possible to make disjoint choices by
317 which means that the search tree nodes correspond to a variable
319 variable can take.
330 \caption{The effect of variable selection}
334 Figure \ref{figvarsel} shows how variable selection reshapes a search tree.
345 While with 2 variables there are only 2 variable selection strategies,
347 variables there are already $2^{2^{5}-1} = 2147483648$ different variable selection
351 are different, then the variable selection can change the number of internal
362 values from the domain of a variable in a particular order.
375 By combining variable and value selection, a large number of different
380 that can be obtained by variable and value selection (assuming domain size 2).
405 to backtrack search through variable and value selection.
406 We model the problem with one variable per queen, assuming that each queen
452 {\bf general-purpose variable-selection heuristic},
504 variable-selection strategies:
559 %sizes of all the (remaining) variable's domains:
583 It uses a non-logical counter variable (backtracks) and an additional
587 :- local variable(backtracks), variable(deep_fail).
606 \item Shallow backtracking (an attempt to instantiate a variable which
667 :- local variable(backtracks), variable(deep_fail).
826 value for each variable, respectively).  Each variable has a finite
849 must match the value, in case the variable is
902 The heuristic is stored with the variable as its tentative value.
905 variable is instantiated as a consequence of constraint propagation
911 Each variable in the list of variables {\em Vars}
921 constraint propagation instantiates the third variable to $2$,
1087         predicate, but it works on the variable's tentative values rather
1094 \item[Tentative values:] Every variable has, apart from its domain,
1148 \item Changing the tentative value of some variable, which in turn causes
1161 of the Profit variable (which is being constantly updated by tent\_is).
1188 The {\tt change_random} predicate changes a randomly selected variable with
1240 The move operator is implemented as follows. It chooses a random variable X
1259 value of the Profit-variable before and after the move is done.
1261 some variable, the tent\_is/2 primitive will automatically
1262 update the Profit variable.
1278 variable T, the inner loop does random moves until MaxIter steps have been
1401 where no value can be assigned to a variable without violating some
1409 new alternative values to one (generally the last assigned) variable. The
1419 a value to a variable, in which all the values in the remaining domain of the
1420 variable (i.e. values which causes no constraint violations with existing
1475 a variable are tried. The repair library was used to allow for tentative
1484 \item Setting the tentative value of a variable, either initially, or
1487 tentative values for remaining unlabelled variables as a variable is
1494 step tries out all the possible valid values for a variable, and picks the
1518 i.e. before any variable is labelled. The restart is then implemented by
1556 themselves have to be remembered, but which variable a particular value is
1558 non-logical variable feature of {\eclipse}, which allows copies of
1559 terms to be stored across backtracking. A non-logical variable is
1560 declared by a \verb'variable/1' declaration:
1563 :- local variable(varbindings).
1568 value of this variable can then be set via \verb'setval/2' and accessed
1570 which variable is associated with which value,  all the variables being
1598 The routine first picks an unlabelled variable to label next, and
1623 If a variable had been labelled in the previous search, the labelled value
1624 becomes the tentative value. Otherwise, the variable retains the original
1644 The algorithm described by Yokoo does not specify how the next variable is
1658 The next variable to be labelled is chosen from the set of variables whose
1660 (repair) constraints which are causing conflict, and any variable which are
1665 to select a variable (picking the one with the smallest domain and most
1666 constraints), and then this variable is checked to make sure that it is
1667 valid variable to be labelled, i.e.\ that it is one of the variables to be
1681 in that when only one variable specified in a nogood remains unlabelled,
1683 nogood, the constraint that this last variable cannot take on its nogood
1709 failure if this is the case. If a non-matching variable-value pair is
1710 encountered, the constraint disappears. If a variable is encountered,
1711 nogood/4 continues checking, and if the variable turns out to be the only
1713 If a second variable is encountered, the constraint re-suspends until