Пролог: устранение циклов из косвенной связи

У меня есть список пользовательских фактов, определенных как:

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

и так далее. Кроме того, у меня есть ряд фактов:

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

Я пытаюсь написать косвенное отношение (user1, user1), которое скажет мне, следует ли user1 косвенно за user2. Однако я не могу отказаться от циклических отношений.

Как и в данном примере, michael -> ana -> bob -> michael вызовет цикл.

Как лучше всего исключить эти циклы из результата косвенного (user1, user2)?


prolog transitive-closure
person na899    schedule 02.12.2014    source источник
comment
Почему вы ставите перед именами префикс @?   -  person false    schedule 03.12.2014
comment
@false, я пытаюсь создать твиттер с помощью пролога, и одно из правил, которые мне даны, заключается в том, что имя пользователя начинается с @.   -  person na899    schedule 03.12.2014
comment
Попробуй write_canonical(@abx). дает @(abx). То есть @ - это префикс-оператор (SWI). Если вы действительно хотите @ в именах, напишите '@name'   -  person false    schedule 03.12.2014
comment
Я бы попробовал. Спасибо @false. Я разместил здесь еще одну проблему stackoverflow.com/questions/27275378/list- обработка в прологе. Любая помощь или подсказка подойдут мне.   -  person na899    schedule 03.12.2014

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете создать правило, которое передает дополнительный список пользователей, которых вы «видели» на данный момент, и игнорирует подписки, исходящие от этих пользователей: follows(A, B, Seen).

Для этого определите «переходное правило следования», которое обертывает фактическое правило, например:

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

Теперь вы можете определить follows/3 правило следующим образом:

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]).

В базовом предложении говорится, что если есть факт о A, следующем за B, мы считаем предикат доказанным, если не видели B раньше.

В противном случае мы находим кого-то, кто подписан на A, проверяем, что мы еще не видели этого пользователя, проверяя not_member/2, и, наконец, смотрим, подписан ли этот пользователь на B, прямо или косвенно.

Наконец, вот как можно определить not_member:

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

Демо.

person Sergey Kalinichenko    schedule 02.12.2014
comment
Теперь у follows(A,B) есть только три решения. Вот почему (\=)/2 в not_member/2 - не лучшая идея. - person false; 03.12.2014
comment
Спасибо за помощь @dasblinkenlight. - person na899; 03.12.2014
comment
@ na899 Добро пожаловать! Взгляните на последнее изменение в ответ на последний комментарий на false (заменяющий =` with dif / 2`). - person Sergey Kalinichenko; 03.12.2014
comment
@false Еще раз спасибо, я забыл, насколько сложным может быть Prolog (последний раз я программировал на Prolog 20 лет назад). - person Sergey Kalinichenko; 03.12.2014

arrow_upward
1
arrow_downward 

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

См. определение closure/3.

person false    schedule 02.12.2014