[ library(gfd) | Reference Manual | Alphabetic Index ]

try_value(?Var, ++Method)

Two-way and multi-way choice predicate
Var
a domain variable or an integer
Method
an atom denoting the value choice method

Description

This search predicate makes a choice on the domain of the variable. This choice can be a binary choice, or an indomain style multi-way choice which branches on different values in the domain of the variable.

The binary choice methods create two search alternatives, which reduce the variable domain in complementary ways. The details are determined by the Method.

The first group of binary methods tries to set the variable to a particular value, and in the alternative excludes this value from the domain, logically:

	( Var = Value ; Var #\= Value )
min
try the minimum value in the domain
max
try the maximum value in the domain
median
try the median value in the domain
The next binary group only halves the domain in each alternative (where the split value is the arithmetic mean of the lower and upper domain bound, rounded down):
	( Var #=< Split ; Var #> Split )
split
try first the lower domain half, then the upper
reverse_split
try first the upper domain half, then the lower
The indomain style group chooses an initial value from the variable's domain of according to the given method, and on backtracking select other values in the domain.
indomain_min
Values are tried in increasing order.
indomain_max
Values are tried in decreasing order.
indomain_median
Values are tried starting from the median value of the domain, then alternately the next larger and smaller values in the domain.
indomain_middle
Values are tried starting from the middle of the range (which does not need to be in domain), then alternately the next larger and smaller values in the domain.
indomain_from(+Val)
Values are tried starting from Val (which does not need to be in domain), then alternately the next larger and smaller values in the domain.

As opposed to the value choice predicates indomain/1 and indomain/2, the binary choice methods of try_value/2 does not necessarily instantiate the variable. If used in a tree search, this means that the variable must remain available to the variable selection, as it may be selected repeatedly at different depth of the search tree.

The indomain style methods do instantiate the variable. If used in a tree search, try_value represents a n-ary choice for all the values of a variable. In this case, the maximum depth of the search-tree is the number of problem variables.

This predicate should be more efficient than using generic value choice predicates or explicitly writing code to do the choice. The exclusion of values before a new choice is done by specialised low-level primitives that are more efficient than user-level constraints. This efficiency is particularly important because they make recomputation more efficient. For the binary choice methods, the exclusion of values are performed in every recomputation of the choice; and for the indomain style methods, the old values are excluded from the variable's domain to allow the next value to be chosen. On recomputation, the variable is directly set to the chosen value. This reduces the amount of recomputation, but any reduction in the search space resulting from propagating the exclusion of old values may also be lost.

try_value/2 is best used in combination with select_var/5. Both can be used to parameterise the generic gfd_search:search/6 procedure.

Modes and Determinism

Examples

    % Used with generic search/6
    gfd_search:search(Xs,0,select_var(first_fail),try_value(min),complete,[]).


    % Simple labelling implemented using select_var/5 and try_value/2
    labelling(Vars, Select, Choice) :-
        (select_var(V, Vars, Rest, 0, Select) ->
            try_value(V, Choice),
            labelling(Rest, Select, Choice)
        ;
            true
        ).