Re: [eclipse-clp-users] amount of shallow backtracking.

Hi Mauicio,

mauricio montecinos wrote:

> I would like to know if there is a predefined predicate that allow me get
> the amount of shallow backtracking.
> 
No.

> 
> 
> Shallow backtracking: An attempt to instantiate a variable causes immediate
> failure due to constraint propagation.
> 

This is the how shallow backtracking is described in the ECLiPSe 
tutorial, in a section on `counting backtracks'. Some code was also 
presented in that section to count backtrackings, without the shallow 
backtracking. I assume you have been reading this? Note that the 
description there is informal, and the above description of shallow 
bactracking should not be taken as a formal or complete description of 
`shallow backtracking'.

The type of `shallow backtracking' not counted by the code in the 
ECLiPSe tutorial are those `immediate failures due to constraint 
propagation' and for which another value for the same variable is then 
tried, e.g. if you are labelling a variable V, which has the domain 
[1,2,3], then if instantiating V to 1 fails immediately, the value of 1 
is then bactracked, and the value of 2 is tried, the backtracking here 
is shallow backtracking.

> 
> 
> I'm trying to count the shallow backtracking. The core of my program is
> based on codes of the form:
>

I am not sure if you really mean counting shallow bactracking only, or 
if you mean couting backtracking that takes into account shallow 
backtracking.

I can see that you may want to take shallow bactracking into account 
because you want to see how good your value selection (choose_val/2 in 
your code) is, but to really have an idea of this, you need to take into 
account the number of variables you have labelled, and to a lesser 
extent, the initial domain sizes of these variables. In short, a single 
number returned here will not be very informative.

The way the backtracks are counted in the tutorial does not give you any 
real idea of how good your value selection strategy is, but it does give 
useful information on your variable selection strategy (choose_var/3 in 
your code), because the count is in effect the number of variable 
selections that have to be backtracked.

> 
> 
> ( fromto(AllVars, Vars, Rest, [])
> 
>         do
> 
>         choose_var(Vars, Var, Rest),
> 
>         choose_val(Var,Val),
> 
>         Var = Val,
> 
>        ).
> 
> 
> 
> If choose_val is:
> 
> choose_val(Var,Val):-
> 
>      indomain(Var).
> 
> 
> 
> If I replace indomain(Var) for my_indomain:
> 
> my_indomain(Var,Val):-
> 
>     get_domain_as_list(Var,Domain),
> 
>     member(Val,Domain).
> 
> 
> 
> If I replace member(Val,Domain) for my_member :
> 
> my_member(X,[X|_]).
> 
> my_member(X,[_|Xs]):- my_member(X,Xs).
> 
> 
> 
> I think that by incorporating of the predicate count_shallowbt I get the
> amount of Shallow backtracking.
> 
> 
> 
> my_member(X,[X|_]).
> 
> my_member(X,[_|Xs]):- count_shallowbt, my_member(X,Xs).
> 
> 
> 
> Where:
> 
> count_shallowbt:-
> 
>    incval(shallowbt).
> 
> 

You are not counting shallow backtracking here. In fact, you are not 
really counting backtrackings at all. Instead, you are counting the 
number of new non-left branches that are started in the search-tree.

Your count is done during forward execution, and does not take into 
account if the following value selection succeeds or not. Since you are 
counting during forward execution, your count will miss the backtrack 
for the last domain value (although this is not a shallow backtrack).
It is however as good a measure of the `bushyness' of your search-tree 
as shallow backtracking would be [but you still need more than one 
number, as I stated previously]

> 
> Every time that a "deep batcktrack" happens, the count of "shallow
> backtracking" increases by one, for that reason, then I must be subtract the
> amount of "deep backtrack" to the amount of "shallow backtracking".
> 
> 
No. You are not counting backtrackings, and as you are counting during 
forward execution, each branch will be counted only once -- when you 
start it, and it does not matter if that branch fails immediately with 
shallow backtracking, or fails after a long while. It therefore does not 
make sense to do any subsctractions.

Perhaps you are thinking about subtraction because of the backtrack 
counting code presented in the tutorial:

count_backtracks :-
         setval(deep_fail,false).
count_backtracks :-
         getval(deep_fail,false),        % may fail
         setval(deep_fail,true),
         incval(backtracks),
         fail.

The difference from your code is that here the count is done during 
backtracking rather than forward execution -- more precisely, a 
choicepoint is created which increments the count when it is backtracked 
into, and then the backtracking is continued by failing. For this 
reason, it needs to be careful that a backtrack is only counted once 
(hence the `deep fail' check), because a single backtrack may backtrack 
pass the labelling of several variables, because these variables have no 
more alternative domains left (to be more precise, shallow failures may 
happen for some of these variables, but they will not be counted in this 
scheme). Simple subtraction cannot be done here either, because you 
don't know how many variables will be skipped until you get to one that 
does produce aternatives.

Cheers,

Kish


-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.