My Diversions

One disadvantage of the depth first search with iterative deepening is that it regenerates all the search paths from the start node every iteration. A true breadth first search, as described by Bratko on pages 250-252 doesn’t need to do that — it can start with a short search path (just the start node in fact) and then extend the current paths by one node each iteration. This trades space for time, as it needs to keep all the current candidate paths in memory.

The algorithm is applied to the same block domain as in our previous examples. Note that we use the Mercury trace goal to print the sets of paths as they are generated:

:- module stacks4.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is cc_multi.
:- implementation.
:- import_module list.
:- import_module solutions.

/*
 * In Mercury we can use types to represent the problem domain -- a situation
 * is a number of stacks of blocks.
 */
:- type block ---> a; b; c; d.
:- type stack == list(block).
:- type situation == list(stack).
:- type solution == list(situation).

:- pred s(situation, situation).
:- mode s(in,out) is nondet.

/*
 * list.delete uses a different order of arguments to the del predicate
 * used by bratko: delete(List, Element, Remainder)
 */
s(Stacks, [Stack1, [Top1 | Stack2] | OtherStacks]) :-
    delete(Stacks, [Top1 | Stack1], Stacks1),
    delete(Stacks1, Stack2, OtherStacks).

:- pred goal(situation::in) is semidet.
goal(Situation) :-
    member([a,b,c], Situation).

:- pred solve(situation::in, solution::out) is nondet.
solve(Start, Solution) :-
    breadthfirst([[Start]], Solution).

:- pred breadthfirst(list(solution)::in, solution::out) is nondet.
breadthfirst([[Node | Path] | _], [Node | Path]) :-
    goal(Node).
breadthfirst([Path | Paths], Solution) :-
    trace [io(!IO)] (io.write_list([Path | Paths], “—\n”, io.print, !IO),
        io.nl(!IO)),
    extend(Path, NewPaths),
    append(Paths, NewPaths, Paths1),
    breadthfirst(Paths1, Solution).

:- pred extend(solution::in,list(solution)::out) is nondet.
extend([Node | Path], NewPaths) :-
    solutions(
        pred(X::out) is nondet :- 
        (
            X = [NewNode, Node | Path],
            s(Node, NewNode),
            not member(NewNode, [Node | Path])
        ),
        NewPaths).

/*
 * Note that the solution returned by solve starts with the final goal node, so
 * we reverse it before printing it.
 */
main(!IO) :-
    if solve([[c,a,b],[],[]],S) then
        reverse(S,S1), print(S1,!IO)
    else
        print(”Failed\n”,!IO).