Depth search with Prolog - how to limit depth?

Question

Depth search with Prolog - how to limit depth?

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?

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

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

3

prolog algoritmo grafo busca

Author: Leila, 2018-10-25

Source

1 answers

score 3 · Accepted Answer

In reality, by using History and checking whether or not the node is already part of History, you are already limiting the search and avoiding repeat nodes. It is not necessary to artificially limit the depth(type fetch up to an arbitrary depth X).

Your problem is that you use both facts edge to represent your graph and a Rule edge that visits the reverse path. And it is this rule that enters an infinite loop, because in it you do not check the history to see if a node has already been visited or not. It would be better not to have the rule:

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

And yes 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

This 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 checking 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).