как использовать forall X в программировании набора ответов (dlv) (пролог набора ответов)

У меня есть следующие факты в dlv: «знает (X, Y)» означает, что X знает Y.

knows(adam,  dan).
knows(adam,alice).
knows(adam,peter).
knows(adam,eva).
knows(dan,   adam).
knows(dan,alice).
knows(dan,peter).
knows(eva,   alice).
knows(eva,peter).
knows(alice, peter).
knows(peter, alice).

Я определил следующие предикаты,

person(X) :- knows(X, _).

Это даст все лица из фактов. Я пытаюсь найти популярный предикат (X). что даст популярный человек. Он определяется таким образом, что если все люди знают X, то X популярен. Ответ на приведенный выше список фактов - Алиса и Питер. Я определил это, как показано ниже,

popular(X):-person(X),knows(_,X).

X популярен, если это человек, и все знают X. Но в результате я получаю всех людей, когда запускаю его. Где я делаю ошибку?


answer-set-programming
person Darth Vader    schedule 11.11.2014    source источник
comment
Вы определили person как X — это человек, если X знает кого-то (не имеет значения, кого) . And you've defined popular`, поскольку ``X` популярен, если X — это человек (они кого-то знают), и если кто-то знает X. Поскольку каждый в вашей базе данных кого-то знает, и каждый в вашей базе данных кого-то знает, то по вашему определению все популярны.   -  person lurker    schedule 11.11.2014
comment
Я определил предикат человека, чтобы я мог получить все лица, а затем отфильтровать их. Как мне тогда подойти к этому?   -  person Darth Vader    schedule 11.11.2014
comment
Вам нужно переосмыслить свое определение popular. Если он дает вам неверный ответ (то есть, все люди), это означает, что ваше определение popular неверно. Подумайте, что значит быть popular логическим (попытайтесь выразить это на нормальном языке), а затем выразите это на Прологе.   -  person lurker    schedule 11.11.2014
comment
Что характерно для ASP в вашем вопросе? Кажется, это обычный вопрос Пролога.   -  person false    schedule 11.11.2014
comment
Популярный человек — это тот, кого все знают, но популярный человек знает только других популярных людей. Это то, что я пытаюсь решить здесь.   -  person NEO    schedule 11.11.2014
comment
@thefragmenter ты тот же человек, что и Дарт Вейдер? Если да, то правило, указанное в описании задачи, не соответствует определению, которое вы только что дали для популярного человека.   -  person lurker    schedule 12.11.2014
comment
Да, я пытаюсь определить предикат в соответствии с определением, которое я упомянул выше. Как мне поступить?   -  person NEO    schedule 12.11.2014

Ответы (2)


arrow_upward
1
arrow_downward

Согласно строке комментария к исходному сообщению, вы определили популярность как «человека, которого кто-то знает». Так как - в вашей базе знаний - все кем-то известны, все популярны.

Предполагая, что «популярный человек - это тот, кого все знают, но популярный человек знает только других популярных людей»; если мы хотим знать, популярен ли X:

  • Нам нужно либо подсчитать всех людей, которые знают X, а затем сравнить это с количеством людей;
  • Или нам нужно убедиться, что никогда не бывает так, чтобы кто-то не знал X.

Я сосредоточусь на втором способе сделать это, используя forall. Найдите время и проведите несколько тестов самостоятельно, чтобы понять, как это работает. Вот пример того, что вы можете сделать:

popular(X): - person(X),
              forall(  
                 (   person(Y), 
                     X \= Y
                 ),
                 knows(Y,X)
              ).

Если вы запустите это, вы получите Алису и Питера в качестве ответов.

Но если мы включим другое условие:

popular(X): - person(X),
              forall(  
                 (   person(Y), 
                     X \= Y
                 ),
                 knows(Y,X)
              ),
              forall(
                 knows(X,Z),
                 popular(Z)
              ).

В последней строке говорится, что X должен знать исключительно популярных людей... и теперь, если вы запустите это, вы, скорее всего, получите "выход из локального стека" - это бездонное рекурсивное определение.

Вам всегда нужно проверить, популярен ли кто-то, чтобы узнать, популярен ли кто-то, чтобы узнать, популярен ли кто-то... Попробуйте подумать о проблеме и о том, почему это так. Есть ли способ проверить, популярен ли кто-то, без необходимости проверять, популярен ли кто-то еще? Что, если кто-то «знает» себя? Что, если два человека знают друг друга? Это может потребовать немного более сложного подхода к решению.

Кстати, обратите внимание, что ваше определение человека возвращает несколько людей — каждый является человеком для каждого человека, которого они знают. Помимо того, что каждая проверка занимает намного больше времени (поскольку нужно проверить больше «людей»), это может быть проблемой, если вы решите использовать первый подход (подсчет).

Разве не имеет смысла явно определить, кто такие люди, а затем определить «знание» как отношения между людьми?

person('Alice').
person('Bob').

knows('Alice','Bob').
person vmg    schedule 12.11.2014
comment
Проблема с этим ответом в том, что он написан на Прологе, а не на ASP (программирование набора ответов). Путаница, вероятно, началась из-за того, что в названии вопроса используется Пролог набора ответов, а пролог был добавлен как тег. DLV, также упомянутый в названии, является решателем ASP. Задачи ASP кодируются на языке, который иногда называют AnsProlog или Программирование набора ответов в логике. - person vukk; 24.11.2014
comment
Ты прав. Этот вопрос должен быть помечен и предоставлен другой ответ - person vmg; 24.11.2014

arrow_upward
0
arrow_downward

Как сказано в комментарий люркера (с небольшими изменениями и акцентами, сделанными мной), причина, по которой в результате вы получаете всех людей, такова:

Вы определили человека следующим образом: X — это человек, если X кого-то знает. И вы определили популярность следующим образом: X популярен, если X — это человек и кто-то знает X.

Но вы хотели определить: X популярен, если X — человек и все знают X.

Ниже приведено решение ASP для clingo 4. DLV может иметь небольшие отличия в синтаксисе.

% Project
person(P) :- knows(P, _).

% Separate helper predicate knows2/2.
% Not needed if polluting knows/2 with knows(X, X) is OK.
knows2(O, P) :- knows(O, P).
knows2(P, P) :- person(P).

% Everybody knows a popular person.
% When there is a person O that doesn't know P, #false is active.
% I.e. all rule instantiations where some O doesn't know P are discarded.
popular(P) :- person(P), #false : person(O), not knows2(O, P).

% Popular person knows only other popular persons.
% Redundant at this point, since the above rule already results
%   in correct answer without further integrity constraints.
:- person(P), person(O), popular(P), not popular(O), knows(P, O).

#show popular/1.
person vukk    schedule 09.06.2015