Search for path is gprolog

user_14501649 0
Viewed 25

I'm trying to create a function in GProlog that I think is rather simple but I'm having issues writing it.

The idea is to assume a weighted directed graph is described by means of a predicate edge/3, such that edge(X,Y,C) is true is there is an edge from vertex X to vertex Y of cost C. For instance, to the right is a graph and its description using edge/3: edge(a, c,1). edge(a,d,3). edge(b,d,2). edge(c,e,5). edge(e, c,2). edge(e,f,2). edge(d,f,10).

The objective is to define a predicate cheaperPath/3, such that cheaperPath(X,Y,N) is true if there is a path from X to Y of total cost less than N. The predicate is supposed to be called with X, Y and N all instantiated, for example to the query cheaperPath(a,f,7) the anwer should be no.

Here is what I have done for now in Gprolog but the loop seems to be going on and on:

edge(a, c,1).
edge(a,d,3).
edge(b,d,2).
edge(c,e,5).
edge(e, c,2).
edge(e,f,2).
edge(d,f,10).


cheaperPath(X,Y,N):-edge(X,Y,N1),N1@=<N.
cheaperPath(X,Y,N):-edge(X,Z,N1),cheaperPath(Z,Y,M),M is (N-N1).

Any idea why??

prolog
1 Answers

You should reduce the bound when you take an edge, so:

cheaperPath(X, Y, N) :-
    edge(X,Y,N1),
    N1 @=< N.
cheaperPath(X,Y,N):-
    edge(X,Z,N1),
    M is N-N1,
    M > 0,
    cheaperPath(Z,Y,M).

Otherwise you implement this is in a generate-and-test manner where you first generate the entire path, and then you validate that it is indeed a shorter path.

user_675790
Related