0

私は dlv に次の事実を持っています。know (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, _).

これにより、事実からすべての人が得られます。私は述語popular(X)を見つけようとしています。それは人気のある人に与えるでしょう。すべての人が X を知っている場合、X は人気があると定義されます。上記の事実のリストに対する答えは、アリスとピーターです。以下のように定義しました。

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

Xは人であり、誰もがXを知っている場合に人気があります。しかし、実行すると結果としてすべての人が得られます。どこで間違いを犯していますか?

4

2 に答える 2

1

As per the comment string on the original post, you have defined popular to be "a person that is known by someone". Since - in your knowledge base - everyone is known by someone, everyone is popular.

Assuming "a popular person is one whom everyone knows but the popular person knows only other popular persons"; if we want to know if X is popular:

  • We either need to count all the people that know X and then compare that to the number of people;
  • Or we need to verify that it is never the case that someone doesn't know X.

I'll focus on the second way to do this, using forall. Take sometime and run some tests on your own to understand how that works. Here's an example of what you might do:

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

If you run this, you get Alice and Peter as answers.

But if we include the other condition:

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

That last line says X needs to know people that are popular exclusively... and now, if you run this, you're most likely going to get a 'out of local stack' - it's a bottomless recursive definition.

You always need to check if someone is popular to know if someone is popular to know if someone is popular... Try to think about the problem and why that is. Is there a way to check if someone is popular without needing to check if someone else is popular? What if someone 'knows' themselves? What if two people know each other? This might take a slightly more complex approach to solve.


By the way, notice that your definition of person returns multiple people - everyone is a person for every person they know. Besides making every check take a lot longer (since there are more 'people' to check), this might be a problem if you decide to go with the firs approach (the counting one).

Wouldn't it make sense to define explicitly who are the people and then define 'knowing' as a relation between people?

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

knows('Alice','Bob').
于 2014-11-12T14:59:31.250 に答える
0

ラーカーのコメントで述べたように(私が少し変更して強調します)、結果としてすべての人を取得する理由は次のとおりです。

人を次のように定義しました: Xが誰かを知っている場合、X は人ですXが人であり、誰かがXを知っている場合、 Xは人気があります。

Xが人であり、誰もがXを知っている場合、 Xは人気があります。

以下は、clingo 4 の ASP ソリューションです。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.
于 2015-06-09T14:13:34.393 に答える