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

Question

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 function in my program and I need to implemet the search-strategy such as BFS and DFS.

Basically my code is learn from the Internet. So far I can successfuly run the program with DFS method, but I try to run with BFS it always return false. This is my very first SWI-Prolog program, I can not find where is the problem of my code.

Here is part of my code, hope you can help me find the problem of it

solve2 :-
   bfs([[[3,3,left]]],[0,0,right],[[3,3,left]],Solution),
   printSolution(Solution).

bfs([[[A,B,C]]],[A,B,C],_,[]).
bfs([[[A,B,C]|Visisted]|RestPaths],[D,E,F],Visisted,Moves) :-
   findall([[I,J,K],[A,B,C]|Visited]),
     (
       move([A,B,C],[I,J,K],Description),
       safe([I,J,K]),
       not(member([I,J,K],Visited)
     ),
     NewPaths
   ),
   append(RestPaths,NewPaths,CurrentPaths),
   bfs(CurrentPaths,[D,E,F],[[I,J,K]|Visisted],MoreMoves),
   Moves = [ [[A,B,C],[I,J,K],Description] | MoreMoves ].


move([A,B,left],[A1,B,right],'One missionary cross river') :-
   A > 0, A1 is A - 1.  
   % Go this state if left M > 0. New left M is M-1
.
.
.
.
.
safe([A,B,_]) :-
   (B =< A ; A = 0),
   A1 is 3-A, B1 is 3-B,
   (B1 =< A1; A1 =0).

I use findall to find all possible path before go to next level. Only the one pass the safe() will be consider as possible next state. The state will not use if it already exist. Since my program can run with DFS so I think there is nothing wrong with move() and safe() predicate. My BFS predicate is changing base on my DFS code, but its not work.

findall/3 has arity 3, but in you use just one argument in your code. You also use variables Visisted and Visited. Are they supposed to be the same? Try indenting your code to make it more readable, and add some comments. Otherwise it's hard to understand what you are trying to achieve with the findall/3 call and the following block. — twinterer

false false · Accepted Answer · 2012-03-30T15:58:01

There is a very simple way to turn a depth-first search program into a breadth-first one, provided the depth-first search is directly mapped to Prolog's search. This technique is called iterative deepening.

Simply add an additional argument to ensure that the search will only go N steps deep. So a dfs-version:

dfs(State) :-
   final(State).
dfs(State1) :-
   state_transition(State1, State2),
   dfs(State2).

Is transformed into a bfs by adding an argument for the depth. E.g. by using successor-arithmetics:

bfs(State, _) :-
   final(State).
bfs(State1, s(X)) :-
   state_transition(State1, State2),
   bfs(State2, X).

A goal bfs(State,s(s(s(0)))) will now find all derivations requiring 3 or less steps. You still can perform dfs! Simply use bfs(State,X).

To find all derivations use natural_number(X), bfs(State,X).

Often it is useful to use a list instead of the s(X)-number. This list might contain all intermediary states or the particular transitions performed.

You might hesitate to use this technique, because it seems to recompute a lot of intermediary states ("repeatedly expanded states"). After all, first it searches all paths with one step, then, at most two steps, then, at most three steps... However, if your problem is a search problem, the branching factor here hidden within state_transition/2 will mitigate that overhead. To see this, consider a branching factor of 2: We only will have an overhead of a factor of two! Often, there are easy ways to regain that factor of two: E.g., by speeding up state_transition/2 or final/1.

But the biggest advantage is that it does not consume a lot of space - in contrast to naive dfs.

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

6 Answers