Re: [eclipse-users] Counting Backtracks

On Sun, 02 Mar 2008 20:01:14 +0100, Kish Shen <kish_at_crosscoreop.com> wrote:

> 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.

I think a big source of confusion around this is caused by the extend  
n-queens example, which does all the recounting again itself, and thus  
gives wrong results:
http://eclipse.crosscoreop.com/examples/queens.ecl.txt

The correct all_queens\2 would be:
all_queens(Strategy, N) :-      % Find all solutions
     setval(solutions, 0),
     statistics(times, [T0|_]),
     (
         queens(N, Board),
         labeling(Strategy, Board, BT),
         setval(backtracks, BT),
%       writeln(Board),
%       put(0'.),
         incval(solutions),
         fail
     ;
         true
     ),
     get_backtracks(B),
     statistics(times, [T1|_]),
     T is T1-T0,
     getval(solutions, S),
     printf("\nFound %d solutions for %d queens in %w s with %d  
backtracks%n",
         [S,N,T,B]).

This can be verified with n=5 and the search tree from node(uDraw)


Greetings,
Tias

> Cheers,
>
> Kish
>
>
> _______________________________________________
> ECLiPSe-Users mailing list
> ECLiPSe-Users_at_crosscoreop.com
> http://www.crosscoreop.com/mailman/options/eclipse-users