RE: Counting backtracks

Dear Karen,

Thank you very much for yours below. I will make the necessary acknowledgements
whenever I use the code in a public way.

with regards,

Farouk

Umaru Farouk Aminu
Department of Management Science,
Lancaster University,
Lancaster,
LA1 4YX,
UK.
Tel: +44 1524 383619 (Home)
      +44 1524 593865 (School)
      +44 1524 844885 (Fax)


-----Original Message-----
From: Karen Petrie [mailto:scomkep@zeus.hud.ac.uk]
Sent: 30 April 2003 19:51
To: eclipse-users@icparc.ic.ac.uk; f.aminu@lancaster.ac.uk
Subject: Re: [eclipse-users] Counting backtracks


Hi Farouk,

You wrote:
>I would like to count the number of backtracks done between successive 
>solutions until the 'last'. I would also like to know the number of 
>backtracks done between finding the optimum value and proving optimality. 
>Is there anyway I can do this in ECLiPSe?
>

Yes, there is a way to do it fairly easily if you are using the FD 
minimize predicate, as it rases the event handler 280 every time it 
outputs the optimal found to date. So all you need to do is set this even 
handler to also include a backtrack count. In my case I have only ever had 
it print out the value, but it should be fairly easy to output it to a 
file, if that was required.

Firstly, you need to write your own backtracking methods (this one 
actually comes from an example which Joachim Schimpf wrote, so all the 
credit goes to him):

:- local variable(backtracks), variable(deep_fail).

init_backtracks :-
        setval(backtracks,0).

get_backtracks(B) :-
        getval(backtracks,B).
        
count_backtracks :-
        setval(deep_fail,false).
count_backtracks :-
        getval(deep_fail,false),        % may fail
        setval(deep_fail,true),
        incval(backtracks),
        fail.
        
Then a search predicate which updates this count:

mylabeling(AllVars) :-
        ( foreach(Var, AllVars) do
            count_backtracks,
            indomain(Var)                       % select value
        ).
        
Then you need to redefine the event handler:

write_info(_Error, Predicate):-
	arg(1, Predicate, Minimum),
	printf("Found a solution with cost %d \n", [Minimum]),
	get_backtracks(B),
	printf("Backtracks to this point = %d \n \n", [B]).

%set event handler	
:- set_event_handler(280, write_info/2).	

Then all you do is call minimize on your labelling:

minimize(mylabeling(SearchVars), OptimalNumber)

I have attached an full example using 'The Peaceably Coexisting Armies of 
Queens' problem. Feel free to use any of the code, but I would appreciate 
an acknowledgment, if you use it in any public way.

One question I have though, is that I can not find an equivalent of the 
minimize predicate in the IC library, is it possible to do this with IC?

Karen