Comment encoder cela dans la programmation des ensembles de réponses?

Question

Je suis un novice total pour répondre à la programmation de set, et j'ai du mal avec une question assez simple. Le programme doit être écrit en clingo.

Voici donc la question:

Un cadre d'argumentation abstraite est constitué d'un ensemble A d'arguments et d'une relation d'attaque R ⊆ AXA entre eux. Pour deux arguments a1 et a2 quelconques, si (a1, a2) ∈ R alors on dit que a1 attaque a2: si on admet l'argument a1 alors il jette un doute sur l'argument a2. Formellement, un sous-ensemble d'arguments E ⊆ A est stable si les deux conditions suivantes sont remplies:

1. aucun argument dans E n'attaque un autre argument d'E.
2. tout argument en dehors de E est attaqué par un argument de E.

Écrivez un programme ASP qui identifie des sous-ensembles stables d'arguments dans une instance donnée via des ensembles de réponses. L'instance sera fournie via deux prédicats argument / 1 et attaque / 2 correspondant respectivement à A et R.

Voici un exemple:

argument (a).    
argument (b).    
argument (c).    
argument (d).    
attack (a,b).    
attack (b,c).    
attack (d,c).

Sortie valide:

choose (a) choose (d)

C'est ce que j'ai essayé, ce qui est évidemment faux:

choose(X)  :- argument(X), attack(X,Y).

Je ne sais pas du tout comment aborder cela.

Veuillez aider.

Answer 1

Une approche simple de résolution en 3 étapes est la suivante:

1. décrire les faits (vérifier)
2. générer ce que vous voulez en conséquence, mais laissez le programme un choix
3. donner des règles dont les solutions ne s'appliquent pas

Alors commencez par 2:

générer des résultats possibles. Pensez-y en termes simples: pour chaque argument, je le choisis ou non.
La partie peut ou non peut être résolue avec un subsum {}.

{choose(X)} :- argument(X).

ou encore plus simple: je choisis un subsum parmi les arguments

{choose(X):argument(X)}. 

Vérifions les solutions avec Potassco et #show choose/1., mode de résonance enumerate all:

Answer: 1

Answer: 2
choose(b)
Answer: 3
choose(c).
..
Answer: 15
choose(a) choose(b) choose(c)
Answer: 16
choose(a) choose(b) choose(c) choose(d)
SATISFIABLE

Toutes les combinaisons sont trouvées. Il est temps de supprimer les mauvais éléments. Encore une fois: pensez-y en termes simples: il n'est pas possible que je choisisse deux arguments où l'un attaque l'autre. (Si la tête est laissée ouverte, cela se lit comme un faux.)

:- choose(X), attack(X,Y), choose(Y).

Maintenant, vérifiez à nouveau:

Answer: 1

Answer: 2
choose(a)
Answer: 3
choose(d)
Answer: 4
choose(a) choose(d)
Answer: 5
choose(c)
Answer: 6
choose(a) choose(c)
Answer: 7
choose(b)
Answer: 8
choose(b) choose(d)
SATISFIABLE

Nous devons maintenant nous assurer que chaque argument non choisi est attaqué par au moins un élément choisi:

1 {choose(Y):attack(Y,X)} :- argument(X), not choose(X).

Lit: Pour chaque argument X, qui n'est pas choisi, le nombre d'arguments choisis qui l'attaquent est au moins un.

Vérifions-le:

Answer: 1
choose(a) choose(d)
SATISFIABLE

Agréable.

Puisque les contraintes sont normalement formulées avec une tête vide, reformulons la dernière règle:

:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

Lit: Il n'y a aucun argument X, qui n'est pas choisi et a un maximum de 0 arguments choisis, qui attaquent X. Cela donne le même résultat.

Code complet:

argument (a;b;c;d).   
attack (a,b).    
attack (b,c).    
attack (d,c).

{choose(X):argument(X)}.
:- choose(X), attack(X,Y), choose(Y).
:- argument(X), not choose(X), {choose(Y):attack(Y,X)} 0.

#show choose/1.