Come codifico questo nella programmazione del set di risposte?

Question

Sono un principiante totale nel rispondere alla programmazione di set e sto lottando con una domanda piuttosto semplice. Il programma deve essere scritto in clingo.

Quindi ecco la domanda:

Una struttura di argomentazione astratta consiste in un insieme A di argomenti e una relazione di attacco R ⊆ AXA tra di loro. Per due argomenti qualsiasi a1 e a2, se (a1, a2) ∈ R allora diciamo che a1 attacca a2: se uno ammette l'argomento a1 allora pone dubbi sull'argomento a2. Formalmente, un sottoinsieme di argomenti E ⊆ A è stabile se valgono le seguenti due condizioni:

1. nessun argomento in E attacca qualsiasi altro argomento di E.
2. qualsiasi argomento al di fuori di E è attaccato da un argomento di E.

Scrivere un programma ASP che identifichi sottoinsiemi stabili di argomenti in una determinata istanza tramite insiemi di risposte. L'istanza verrà fornita tramite due predicati argomento / 1 e attacco / 2 corrispondenti rispettivamente ad A e R.

Ecco un esempio:

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

Uscita valida:

choose (a) choose (d)

Questo quello che ho provato, che ovviamente è sbagliato:

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

Non so affatto come affrontarlo.

Per favore aiuto.

Answer 1

Un semplice approccio alla risoluzione in 3 fasi è il seguente:

1. descrivere i fatti (controllare)
2. generare ciò che si desidera di conseguenza, ma lasciare al programma una scelta
3. dare regole le cui soluzioni non si applicano

Quindi inizia con 2:

generare possibili risultati. Pensalo in parole semplici: per ogni argomento lo scelgo o no.
La parte può o non può essere risolta con una somma parziale {}.

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

o anche più semplice: scelgo una somma parziale dagli argomenti

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

Controlliamo le soluzioni con Potassco e #show choose/1., in modalità risonanza 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

Vengono trovate tutte le combinazioni. È ora di rimuovere la roba sbagliata. Ancora: pensateci in parole semplici: non è possibile che scelga due argomenti in cui uno attacca l'altro. (Se la testa viene lasciata aperta, viene letto un Falso.)

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

Ora controlla di nuovo:

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

Ora dobbiamo assicurarci che ogni argomento non scelto sia attaccato da almeno un elemento scelto:

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

Legge: Per ogni argomento X, che non è scelto, il numero di argomenti scelti che lo attaccano, è almeno uno.

Controlliamo:

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

Bello.

Poiché i vincoli sono normalmente formulati a testa vuota, riformuliamo l'ultima regola:

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

Letture: non ci sono argomenti X, che non sono scelti e hanno un massimo di 0 argomenti scelti, che attaccano X. Fornisce lo stesso output.

Codice completo:

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.