Breadth-First in Prolog

Question

What is the general idea of using breadth-first over the default depth-first search scheme in Prolog?

Not taking infinite branches?

Is there any general way to use breadth-first in Prolog? I've been googling around and I didn't find too much useful info for a novice.

Answer 1

The advantage of breadth-first is that you will find all solutions. With depth-first you can become stuck in an infinite branch.

The disadvantage is that breadth-first uses a lot of memory, therefore it is not used generally for execution.

If you want to use it you'll need to implement it explicitly with some kind of queue.

Edit: If you want to have the advantages of breadth-first search without using much memory you can use iterative deepening. This is depth-first search with a depth-bound, which you increase successively. This causes some duplicate computation, but if your search space doesn't have long linear stretches without branching then this duplication is small.

Answer 2

There is something I got to know as "agenda search". While traversing the tree (of data, relations, rules, ...) you maintain an "agenda" (a list) of what to do next. When you enter a node you put its children on the agenda, and then continue with the first element of the agenda, which you pop. This way, if you put new items at the end of the agenda, you get breadth-first. If you put them in front of the agenda, you get depth-first.

It's easy to implement with Prolog.

EDIT: I might just as well give an implementation hint here. This is a very basic implementation of the agenda search algorithm.

agenda_search([N|T],Mode):-
    doWithNode(N),           % do whatever you do the searching for
    getNodeChildren(N,C),
    (Mode=bf ->              % bf or df (depth-first)
        append(T,C,A);
        append(C,T,A)),
    agenda_search(A,Mode).

It relies on external predicates doWithNode that stands for the action you want to perform with each node (e.g. compare node data to a search term, serialize node content, asf.). And getNodeChildren that will bind the list of children of the given node to C (I.e. this predicate actually knows the tree structure and how to find child nodes). Of course the doWithNode predicate might need additional parameters to do its job, which would also show up in the argument list of agenda_search.

You can invoke it like this:

agenda_search([RootNode], bf)   % for breadth-first search

and

agenda_search([RootNode], df)   % for depth-first search

I've also found a bit of explanation of the agenda search on this web page. The nice thing with agenda search is that you can easily switch between the two variants df and bf and play with the results. The algorithm is quite well-behaved memory-wise, as the agenda, the nodes still to explore, only captures a (more or less) small fraction of nodes in the tree at any one time (the so called fringe).

Answer 3

The code for agenda_search should work fine. For efficiency you may wish to consider using another datastructure; indeed, in breadth-first mode the entire list of nodes (T) will be traversed by append(T,C,A). You could for instance use the library(queues) module from SICStus. Breadth-First search would then look as follows (parametrised by predicates start/1, the successor predicate s/2 and the goal predicate goal/1). Note, I have also added loop checking.

bfs(Res) :- start(Start), empty_queue(EQ),
  queue_append(EQ,[e(Start,[])],Q1),
  bfs1(Q1,Res).

bfs1(Queue,Res) :- queue_cons(e(Next,Path),NQ,Queue),
   bfs2(Next,Path,NQ,Res).

bfs2(H,Path,_NQ,Res) :- goal(H), reverse([H|Path],Res).
bfs2(H,Path,NQ,Res) :-  
              findall(e(Succ,[H|Path]),
                      (s(H,Succ),\+ member(Succ,Path)),AllSuccs),
              queue_append(NQ,AllSuccs,NewQueue),
              bfs1(NewQueue,Res).

(You could also try and replace/complement the Path component by a better datastructure; e.g., AVL-trees.) An example problem to solve would be:

start(env(0,0)).
s(env(X,Y),env(X1,Y)) :- X1 is X+1.
s(env(X,Y),env(X,Y1)) :- Y1 is Y+1.
goal(env(3,3)).

You can also replace the queue by a priority queue, and compute the priority using a heuristic function. You then get A* search (which can emulate depth-first, breadth-first, best-first, ...). Bratko's book (Logic Programming for Artificial Intelligence) should be good source to read up this material.