prolog - Prólogo: eliminación de ciclos de relación indirecta

transitive-closure

Question

Tengo una lista de hechos del usuario definida como:

user(@michael).
user(@ana).
user(@bob).
user(@george).
user(@john).

y así. Además, tengo un conjunto de hechos como:

follows(@michael,@ana).
follows(@ana,@bob).
follows(@bob,@michael).

Estoy tratando de escribir una relación indirecta (user1, user1) que me dirá si user1 indirectamente sigue a user2. Sin embargo, no puedo eliminar las relaciones cíclicas.

Como en el ejemplo dado, michael -> ana -> bob -> michael causará un ciclo.

¿Cuál es la mejor manera de eliminar estos ciclos del resultado de indirecto (usuario1, usuario2)?

Answer 1

Puede hacer una regla que pase una lista extra de usuarios que haya "visto" hasta el momento e ignorar los siguientes datos provenientes de estos usuarios: follows(A, B, Seen) .

Para hacerlo, defina una regla de "seguir transitivo" que ajuste la regla actual, como esta:

follows_tx(A, B) :- follows(A, B, []).

Ahora puede definir la regla follows/3 esta manera:

follows(A, B, Seen) :-
    not_member(B, Seen),
    follows(A, B).
follows(A, B, Seen) :-
    follows(A, X),
    not_member(X, Seen),
    follows(X, B, [A|Seen]).

La cláusula base dice que si hay un hecho sobre A sigue a B , consideramos el predicado probado mientras no hayamos visto a B anteriormente.

De lo contrario, encontramos a alguien que sigue a A , verifica que aún no hayamos visto a ese usuario marcando not_member/2 , y finalmente veamos si ese usuario sigue a B , directa o indirectamente.

Finalmente, aquí está cómo puedes definir not_member :

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

Manifestación.

Answer 2

indirect( A0,A) :-
   closure(follows, A0,A).

Busque una definición de closure/3 .