/*******************************************************************************
Chapter 13
Data
	f13_1_IDAstar_12_2.pl    f13_IDAstar_s7.pl
*******************************************************************************/
/*******************************************************************************
Figure 13.1  An iterative deepening A* search program.

idastar( Start, Solution):
    Perform IDA* search; Start is the start node, Solution is solution path

Problem: For Figure 12_2, defining f(t,N) 0 <= N <= 11 gives bestfirst path first
but gives it a second time (a third solution).  N >= 12 gives only the two paths
but in the reverse order of bestfirst.

The F values change as 6,7,8,10,9,10,12,11,12 then give the two paths.
The values differ from the book.
*******************************************************************************/

idastar( Start, Path)  :-
asserta(count(0,x)),           % Have expansion count 0 at node x
    retract( next_bound(_)), fail     % Clear next_bound
    ;
    asserta( next_bound( 0)),         % Initialise bound
    idastar0( Start, RP),
    reverse(RP,Path).

idastar0( Start, Sol)  :-
nl, write('***** New search *****'),
    retract( next_bound( Bound)),     % Current bound
    asserta( next_bound( 99999)),     % Initialise next bound
    f( Start, F),                     % f-value of start node
    df( [Start], F, Bound, Sol)       % Find solution; if not, change bound
    ;
    next_bound( NextBound),
    NextBound < 99999,                % Bound finite
write(' Try new bound '), write(NextBound), nl,
    idastar0( Start, Sol).            % Try with new bound

/*******************************************************************************
df( Path, F, Bound, Sol):
    Perform depth-first search within Bound
    Path is the path from start node so far (in reverse order)
    F is the f-value of the current node, i.e. the head of Path
*******************************************************************************/

df( [N | Ns], F, Bound, [N | Ns])  :-
    F =< Bound, 
    goal( N).                        % Succeed: solution found

df( [N | Ns], F, Bound, Sol)  :-
    F =< Bound, nl,
write('Expand ') , write(N) , write(' ') ,
write('F='), write(F), write(' B='), write(Bound), write(' '),
    update_count(N) ,                      % Node N within f-bound
    s( N, N1), \+ member( N1, Ns),   % Expand N
    f( N1, F1),
    df( [N1,N | Ns], F1, Bound, Sol).

df( [N | _], F, Bound, _)  :-
    F > Bound,                       % Beyond Bound
write(' Beyond bound at '),
    update_next_bound(F,N),           % Just update next bound
    fail.                            % and fail

/******************************************************************************/

update_next_bound( F,N)  :-
    next_bound( Bound),
update_count(N),

    Bound =< F, !                      % Do not change next bound
,write('Did not change bound '), write(Bound), nl
    ;
    retract( next_bound( _)), !,       % Lower next bound
write('New lower bound '), write(F), nl,
    asserta( next_bound( F)).

update_count(N) :-
    count(C,Nold) ,
( N = Nold
;
C1 is C+1 , asserta(count(C1,N)),
write('<') , write(C1) , write(' ') , write(N) , write('> ')

), !.