Breadth-First in Prolog

prolog breadth-first-search logic-programming
Ricardo picture Ricardo · Apr 20, 2009 · Viewed 10.1k times · Source

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

starblue picture starblue · Apr 21, 2009

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.

Related questions

Solve Cannibals/Missionaries using breadth-first search (BFS) in Prolog?

I am working on solving the classic Missionaries(M) and Cannibals(C) problem, the start state is 3 M and 3 C on the left bank and the goal state is 3M, 3C on the right bank. I have complete the basic …

Read More
'if' in prolog?

Is there a way to do an if in prolog, e.g. if a variable is 0, then to do some actions (write text to the terminal). An else isn't even needed, but I can't find any documentation of if.

Read More
Prolog "or" operator, query

I'm working on some prolog that I'm new to. I'm looking for an "or" operator registered(X, Y), Y=ct101, Y=ct102, Y=ct103. Here's my query. What I want to write is code that will: "return X, given that …

Read More