% -*- Mode:Prolog -*-
/*

        TWO SEARCH METHODS:

        Prolog is often regarded as a great language for AI applications.  A common 
        issue in AI problems is to carry out searches.  Prolog with its backtracking 
        behaviour implements a depth first search strategy.  The problem with straight
        depth first search is that one can get stuck in cycles or simply get stuck on 
        an infinite search path which is probed before the actual solution path is 
        probed.

        There are two common search methods to avoid this:

             (a) Costed breadth first search
             (b) Iterative deepening of depth first search

        The purpose of these notes is to describe how the two techniques can be 
        implemented in Prolog.

        The basic problem we shall consider is finding the shortest path between two 
        nodes in an undirected graph with a "distance" associated with each arrow.
        The graph is specified by edges between nodes with attached 
        distances/cost/weights:
*/

%  The (assumed undirected) graph to be searched.
                                                 
edge(a,4,f).
edge(a,9,d).
edge(a,20,e).
edge(a,5,b).
edge(b,7,c).
edge(d,3,e).
edge(c,1,e).
edge(g,3,f).
edge(e,2,g).
edge(f,3,h).

%  For example we might want to determine the shortest path from a to e ...

/*
        (a)  COSTED BREADTH FIRST SEARCH:
        
        This search technique uses an agenda to hold all the "search probes" so far
	with the least cost probe first.  At each stage of the search the least 
        cost probe (which is first on the agenda) is expanded to get a set of 
        new probes which are added (in fact "pushed" in order) onto the  agenda.  
        This process is repeated until the goal state is first on the agenda ....  
        when this happens the least cost solution is found.

        Here is the code ...

*/


% The search predicate returns the path found in the second argument
% paired with the cost.  This calls the breadth first search ("bsearch")
% an agenda hold in a single item determined by the start state. The solution
% path must be reversed as it is collected in reverse order ...

bfsearch(Start,(Path,C),Goal):-
    bsearch(Start,Solution,Goal,[(Start,0,[])]),
    Solution = (P,C),
    reverse(P,Path).

% Breadth first search uses an agenda of search probes and their costs
%                  (ReachedNode,Cost,Path)
% The agenda is held with least cost search probe first.  This least
% cost item is developed and all its children search probes are pushed
% into the agenda. The search ends when the goal state is at the top
% of the agenda.
		   
bsearch(_,(Path,Cost),Y,[(Y,Cost,Path)|_]):- !.     % search ends!!
bsearch(Start,P,Y,[(X,Cost,Path)|Agenda]):-
     findall((C,Z), (edge(X,C,Z);edge(Z,C,X)), L),  % getting all the possible steps (undirected!)
     add_step(L,(X,Cost,Path),NextAgenda),          % creating agenda items for the next steps
     push(NextAgenda,Agenda,NewAgenda),             % pushing the next item onto the agenda
     bsearch(Start,P,Y,NewAgenda).                  % search continues ...

%  Create agenda items out of the single steps which are possible
add_step([],_,[]).
add_step([(C,Z)|Rest],(X,Cost,Path),[(Z,CNew,[(X,Z)|Path])|NewRest]):-
        CNew is C+Cost,
        add_step(Rest,(X,Cost,Path),NewRest).

% push(+,+,-) takes new agenda items and adds them to the agenda
% by repeatedly pushing each item, push_one(+,+,-), onto the agenda.

push([],A,A).
push([First|Rest],A,ANew):-
       push(Rest,A,ANext),
       push_one(First,ANext,ANew).

push_one(First,[],[First]).
push_one((X,Cost,Path),[(Z,C,P)|Rest],[(X,Cost,Path),(Z,C,P)|Rest]):-
        Cost =< C, !.
push_one((X,Cost,Path),[(Z,C,P)|Rest],[(Z,C,P)|NewRest]):-
         push_one((X,Cost,Path),Rest,NewRest).

%  Try running bfsearch(a,S,e) ...

/* 
        (b) ITERATIVE DEEPENING DEPTH FIRST SEARCH

         The idea with iterative deepening is to do a depth first search 
         but only to a limited depth. If the search fails at a given depth 
         then one simply increases the depth of search and try again.
         This may sound a bit crazy as one repeatedly redoes the search,
         however, it actually has some significant advantages. 
             (1) It does not require much storage (of order the depth to 
                 the solution) -- compare this to the above where an agenda 
                 carrying the current frontier must be held. 
             (2) Actually it is not that inefficient on an exponential 
                 search as if the time cost of a search probe to a given 
                 depth is: 
                               branch^depth
                 for a search to a particular depth then the cost of the 
                 search to depth N is:
                     \sum_{i=0}^N branch^i = branch (branch^N -1) / branch -1
                 for a small branching factor this almost branch^{N+1} but for 
                 a large branching factor this approaches branch^N 
                 (the cost of a single search probe).  This may seem 
                 counter-intuitive but it is because of how exponentials 
                 behave!!


          OK so here is the code:
*/

itsearch(Start,(Path,Cost),End):-
    isearch(0,Start,Path,End,Cost).

isearch(Bound,Start,P,End,Bound):-
    dfsearch(Bound,Start,P,End),!.    % finish if df search succeeds within bound
isearch(Bound,Start,P,End,Cost):-
    NextBound is Bound+1,             % otherwise increment the bound
    isearch(NextBound,Start,P,End,Cost).

dfsearch(_,End,[],End):- !.
dfsearch(Bound,Start,[(Start,Next)|Rest],End):-
    (edge(Start,Cost,Next);edge(Next,Cost,Start)), % undirected step
    Cost =< Bound,                                 %  bound the depth
    NewBound is Bound-Cost,           
    dfsearch(NewBound,Next,Rest,End).