Deep Search with Prolog - how to limit depth?

Question

Deep Search with Prolog - how to limit depth?

Navigation

#1 by (0 votes)

1

I'm implementing an in-depth search on graphs 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 dfs , History 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) SWI-Prolog runs and does not end. So, I believe I need to narrow the depth of the search ... how can I do that?

algoritmo busca grafo prolog dfs

asked by anonymous 25.10.2018 / 21:02

1 answer

Create DropDownList with ViewBag Use 2 models in a View, but separate them in the form submission

score 0 · Answer 1

Actually, using History and verifying that the node already does or does not belong to History , you are already limiting the search and avoiding repeated nodes. It is not necessary to artificially limit the depth (type search to an arbitrary depth X).

Your problem is that you use both edge facts to represent your graph and a edge rule that visits the inverse path. And it is this rule that goes into 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, do this visit in two directions in the sucessor relation:

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 verifying that 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).