# Ida algorithm

## Description

An implementation of the IDA* algorithm.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: ida_algorithm.pl

## Listing

```% Figure 12.10:  An implementation of the IDA* algorithm.

:- op( 900, fy, not).

% not Goal): negation as failure;
%   Note: This is often available as a built-in predicate,
%   often written as prefix operator "\+", e.g. \+ likes(mary,snakes)

not Goal  :-
Goal, !, fail
;
true.

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

idastar( Start, Solution)  :-
retract( next_bound(_)), fail     % Clear next_bound
;
asserta( next_bound( 0)),         % Initialise bound
idastar0( Start, Solution).

idastar0( Start, Sol)  :-
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
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,                      % Node N within f-bound
s( N, N1), not member( N1, Ns),   % Expand N
f( N1, F1),
df( [N1,N | Ns], F1, Bound, Sol).

df( _, F, Bound, _)  :-
F > Bound,                       % Beyond Bound
update_next_bound( F),           % Just update next bound
fail.                            % and fail

update_next_bound( F)  :-
next_bound( Bound),
Bound =< F, !                      % Do not change next bound
;
retract( next_bound( Bound)), !,   % Lower next bound
asserta( next_bound( F)).``` 