# --- Copyright University of Sussex 1993. All rights reserved. ----------
# File:             $poplocal/local/plog/teach/search
# Purpose:          Example program from lecture
# Author:           Sharon Wood, Nov 24 1993 (see revisions)
# Documentation:
# Related Files:    TEACH CROSSRIVER

TEACH SEARCH                                                Sharon Wood
                                                            November 1993


This teachfile contains the programs provided as examples in the Introduction
to Logic Programming lecture: Search Techniques II.

Below, the depth-first route finding predicate route/4 is incrementally
modified into a new predicate, breadth/3, which carries out breadth-first
search.

/*route/4 depth first search version

NB link/2 must be defined for your problem domain, for example, as suggested
in TEACH CROSSRIVER.*/

route(S,Finish,_,[Finish]):-
    link(S,Finish).

route(S,Finish,History, [S1|SolutionPath]),
    link(S,S1),                                 ;;;generate
    not(member(S1,History)),                    ;;;test
    route(S1,Finish,[S1|History],SolutionPath).


/*First step: moving membership of History list test to link and changing
link/2 name to generate_daughters/2.

NB For this definition to work, History, must be passed as an extra argument
to generate_daughters/2.  However, this is not necessary in the final
version.*/

route(S,Finish,_,[Finish]):-
    generate_daughters(S,Finish).

route(S,Finish,History, [S1|Solution]),
    generate_daughters(S,S1 <History>),                   ;;;generate
    route(S1,Finish,[S1|History],Solution).               ;;;test

generate_daughters(S,S1 <History>):-
    link(S,S1),                                 ;;;generate
    not(member(S1,History)),                    ;;;test

/*Second step: altering generate_daughters to generate all daughters in a
breadth-first manner, instead of just one next daughter.*/

generate_daughters([Node|Path], NewPaths):-
    setof([Daughter,Node|Path],
          (link(Node,Daughter), not(member(Daughter,[Node|Path]))),
          NewPaths),
          !.

generate_daughters(_,[]).   ;;;clause which allows predicate to succeed where
                            ;;;there are no daughters and setof/3 fails.
                            ;;;NB this was never a problem for depth-first
                            ;;;version because failure automatically triggered
                            ;;;backtracking to last choice point in a depth-
                            ;;;first manner.

/*Third step in which we modify main clause of breadth first search to:

    - call generate_daughters/2 to generate a set of daughter nodes
    - attach these to the end of the agenda in order to conduct breadth-first
        search
    - treat a state as a node plus 'path to node'.  This means each state
        space node carries with it its own pathway/history thus eliminating
        the need for a separate history argument.
*/

breadth([ NodePath | Agenda ], Finish, Solution):-
    generate_daughters(NodePath,NewPaths),
    append(Agenda,NewPaths, NewAgenda),
    breadth(NewAgenda, Finish, Solution).

/*Fourth step in which we modify test for having reached the goal.  No longer
the last step in the search, but instead a test that the goal is not the first
state on the agenda.

Notice also that the path to the finish is passed back (in reverse) untouched.
This is because the solution was not found going into the recursion and
therefore cannot be constructed coming out of the recursion.*/

breadth([ [Finish|Path] | Agenda ], Finish, Solution):-
    qrev([Finish|Path], Solution).

/*A fifth step might introduce an evaluation function and its use in ordering
the agenda.*/

# --- Revision History ---------------------------------------------------
# --- Sharon Wood, Nov 24 1993