Depth Search with Prolog - how to limit depth?

Question

I am implementing an in-depth graph search in Prolog, I already have the following:

%arestas:

edge(c4,b4).
edge(b4,b3).
edge(b3,a3).
edge(b3,c3).

%determina que o grafo é nao direcionado
edge(V1, V2) :- edge(V2, V1).

%busca em profundidade
dfsB(Node,Solution) :- dfsB3(Node, [], Solution).
dfsB3(Node, History, [Node|History]) :- goal(Node).

dfsB3(Node,History,Solution) :- sucessor(Node, Node1), not(member(Node1,History)), dfsB3(Node1,[Node|History],Solution).

sucessor(X,Y) :- edge(X,Y). %esta certo?

In the dfs, History is a list of the nodes that have already been visited. I’m in doubt if the sucessor(X,Y) is correctly implemented.

And when rotating a query dfs(c4,a3) (which was supposed to run because it has a path) SWI-Prolog is running and does not finish. So I believe I need to limit the depth of the search... how can I do that?

Answer 1

In fact, when using History and check whether the knot is already part of History, you are already limiting the search and avoiding repeated knots. There is no need to artificially limit depth (type search to arbitrary depth X).

Your problem is that you wear so many facts edge to represent your graph as a rule edge that visits the reverse way. And it’s this rule that goes into an infinite loop, because in it you don’t check the history to see if a node has been visited or not. It would be better not to have the rule:

edge(V1, V2) :- edge(V2, V1). % Causa loop infinito!

It is to make this visit in two directions in the relationship sucessor:

sucessor(X,Y) :- edge(X,Y). % sim, esta certo!
sucessor(X,Y) :- edge(Y,X). % faz a simetria aqui

That should be enough to solve your problem. But if you still want to know how to limit the search depth, I suggest putting an additional parameter Profundidade and check whether or not it is greater than zero before continuing the search:

dfsB(Node,Solution) :- dfsB3(Node, [], Solution, 5). % Máximo de 5 níveis de profundidade

dfsB3(_, _, _, 0) :- !, fail. % Falha imediatamente se o nível chegou a zero
dfsB3(Node, History, [Node|History], _) :- goal(Node).
dfsB3(Node,History,Solution,Profundidade) :- 
    sucessor(Node, Node1), 
    not(member(Node1,History)), 
    P1 is Profundidade - 1, % Diminui 1 na profundidade máxima de busca
    dfsB3(Node1,[Node|History],Solution,P1).