Re: [eclipse-users] Counting Backtracks

kot23 wrote:
> Hello all, 
>
> I have a question concerning the total number of backtracks during branch and bound search.
>
> I use the search/6 predicate with the option [backtrack(B)] to count the number of backtracks, which is printed to the screen, like this (M is a matrix):
>
> search_mods(M) :-
>     term_variables(M, Vars),
>     search(Vars,
>             0,
>             first_fail,
>             indomain_max,
>             dbs(4,bbs(300)),
>             [backtrack(B)]),
>     writeln('    ':backtracks:B).
>
> I then use the bb_min/3 predicate to minimize the cost like this (the COST variable is already set up, elsewhere):
>
> bb_min( search_mods(M),
>             COST,
>             bb_options{from:240}).
>
> The output I have is like this:
>
>      : backtracks : 0
> Found a solution with cost 335
>      : backtracks : 901
> Found a solution with cost 285
>      : backtracks : 904
> Found a solution with cost 270
>      : backtracks : 915
> Found a solution with cost 255
> Found no solution with cost 240.0 .. 240.0
>
> So, my question is, what is the real number of backtracks, for finding the last solution in the case above? Is it "915" backtracks or the sum of each intermediate solution, ie: 0+901+904+914=2719 backtracks?
>
> Thanks,
> Christoforidis Nikos
>
>   
As stated in the documentation, the backtracks reported is the number of 
backtracking steps used in the search routine, i.e. 915 is the total 
number of backtracks performed by the search to find the last (optimal) 
solution. It does not include the backtracks performed in the search 
after this, that finds no better solution and thus prove the solution is 
optimal, however.

You can also look at the source for the search/6 predicate to verify 
this. This code is found in generic_search.ecl, and the code looks like:

% search/6
% most predicates have a Module argument at the end, in order to pass the
% caller module name to the meta-call predicates
%
:-tool(search/6,search_body/7).
search_body(Vars,Arg,Select,Choice,Method,Option,Module):-
    ....
    !,
    reset_backtrack_count(Option),
    .....
    block(search1(....),nodes,search_nodes_failed),
    ....
    get_backtrack_count(Option).
search_body(Vars,Arg,Select,Choice,Method,Option,Module):-
    error(5, search(Vars,Arg,Select,Choice,Method,Option), Module).

I have left out some of the code that are not relevant here, but you 
should be able to see that the search is performed by the search1 
predicate inside the block/3, and that get_backtrack_count/1 is used to 
get the backtrack count whenever search1 succeeds, i.e. when it finds a 
solution. The reset_backtrack_count/1 is used to reset the count (to 
zero), and is only performed before the start of the search, i.e. before 
the call to search/1.

Cheers,

Kish