Re: How to solve a problem with an infinite loop [beginners question]

On Oct 6, 5:35 pm, philipp.str...@xxxxxxxxx wrote:
Hi everybody,

I have the following grammar

gleich(a,b).
gleich(b,c).

gleich(A,B) :-
A=B.

gleich(A,B) :-
gleich(B,A).

gleich(A,B) :-
gleich(A,X),gleich(X,B).

I want to ask prolog the following questions (which should all lead to
the answer true):

gleich(a,a).
gleich(a,b).
gleich(b,a).
gleich(a,c).
gleich(c,a).

gleich(a,c) and gleich(c,a) leads to an infinity loop how can I avoid
this?

best wishes

Philipp

Hi, Philipp:

It seems to be a case of finding the connected components
of an undirected graph, or equivalently the transitive
closure of a relation.

In this generality it is necessary to avoid backtracking
into previously reached nodes in order to avoid looping
problems. Thus we have to retain a memory of what prior
nodes are visited in a path.

It's a good idea to use separate predicates for the
"elementary" facts (edges of the graph) and for the
"derived" facts (rules pertaining to transitive closure).

One approach is to assert dynamic facts corresponding
to the reachable nodes. Another approach shown below
dispenses with the dynamic predicates. We assume that
at least the first argument is "input" (bound).

gleich(a,b).
gleich(b,c).

gleichClosure(A,B) :- gClosure([A],B).

gClosure([A|_],A).
gClosure([H|T],B) :-
(gleich(H,X);gleich(X,H)),
not(member(X,[H|T])),
gClosure([X,H|T],B).

member(H,[H|_]).
member(X,[_|T]) :- member(X,T).


regards, chip

.

Relevant Pages

  • Re: [Full-Disclosure] Re: Ciscos stolen code
    ... <big snip> ... > But, for realities sake, let's avoid hypothetical's and deal with the ...
    (Full-Disclosure)
  • Re: Wind energy extraction
    ... > The weight of the funnel and support structure would be much larger than ... I notice you avoid the facts that it would be more expensive and produce ...
    (sci.physics)
  • Re: Wind energy extraction
    ... > The weight of the funnel and support structure would be much larger than ... I notice you avoid the facts that it would be more expensive and produce ...
    (sci.energy)
  • Re: Choosing a Linux printer sucks.
    ... > The facts that Joe posted, which clearly show that the suggested printers ... The fact that Linux doesn't support 100% of every printer ... It's you that avoid using common sense. ...
    (alt.os.linux.suse)
  • Re: Choosing a Linux printer sucks.
    ... > The facts that Joe posted, which clearly show that the suggested printers ... The fact that Linux doesn't support 100% of every printer ... It's you that avoid using common sense. ...
    (alt.os.linux)