Answer set programming: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m fix corsivo |
m tag source deprecati, replaced: <source lang= → <syntaxhighlight lang= (18), </source> → </syntaxhighlight> (18) |
||
Riga 7:
== AnsProlog ==
[http://www.tcs.hut.fi/Software/smodels/lparse.ps Lparse] è il nome del programma che è stato creato in origine per l'answer set solver [http://www.tcs.hut.fi/Software/smodels/ smodels]. Il linguaggio che Lparse accetta è AnsProlog. Un programma in AnsProlog consiste di regole scritte nella forma:
<
<head> :- <body> .
</syntaxhighlight>
Il simbolo <code>:-</code> ("if") è omesso se <code><body></code> è vuoto; tali regole, come in [[Prolog]], vengono chiamati ''fatti''.
Un altro tipo di costrutto è la ''scelta''. Ad esempio, la regola:
<
{p,q,r}.
</syntaxhighlight>
afferma: scegli arbitrariamente quali fra gli atomi <math>p,q,r</math> includere nel modello stabile. Un programma contenente solo questa regola ha 8 modelli stabili, sottinsiemi di <math>\{p,q,r\}</math>. Il significato di questa regola nella semantica del modello stabile è rappresentato dalla formula [[Logica proposizionale|proposizionale]]:
:<math>(p\lor\neg p)\land(q\lor\neg q)\land(r\lor\neg r).</math>
È possibile, inoltre, imporre dei vincoli alle regole di scelta, come:
<
1{p,q,r}2.
</syntaxhighlight>
Tale regola afferma: scegli almeno uno degli atomi <math>p,q,r</math>, ma non più di due. Il significato in logica proposizionale è dato dalla seguente formula:
:<math>(p\lor\neg p)\land(q\lor\neg q)\land(r\lor\neg r) \land\,(p\lor q\lor r)\land\neg(p\land q\land r).</math>
I vincoli di cardinalità possono essere usati anche nel corpo della regola, ad esempio:
<
:- 2{p,q,r}.
</syntaxhighlight>
Questo vincolo impone al programma di eliminare i modelli stabili contenenti almeno due atomi appartenenti all'insieme <math>\{p,q,r\}</math>. Il significato in logica proposizionale è dato dalla seguente formula:
:<math>\neg((p\land q)\lor(p\land r)\lor(q\land r)).</math>
Le variabili(con iniziale maiuscola, come in Prolog) sono utilizzate per abbreviare collezioni di regole che seguono lo stesso schema, oppure per abbreviare collezioni di atomi all'interno della stessa regola. Ad esempio, il programma:
<
p(a). p(b). p(c).
q(X) :- p(X), X!=a.
</syntaxhighlight>
ha lo stesso significato di:
<
p(a). p(b). p(c).
q(b). q(c).
</syntaxhighlight>
Il programma:
<
p(a). p(b). p(c). p(d). p(e).
{q(X):-p(X)}2.
</syntaxhighlight>
è un'abbreviazione di:
<
p(a). p(b). p(c). p(d). p(e).
{q(a),q(b),q(c),q(d),q(e)}2.
</syntaxhighlight>
Un ''intervallo'' è espresso nella forma:
<
(start..end)
</syntaxhighlight>
dove <code>start</code> e <code>end</code> sono espressioni aritmetiche dal valore costante. Un intervallo è un'abbreviazione notazionale per definire domini numerici. Ad esempio, il fatto:
<
a(1..3).
</syntaxhighlight>
è un'abbreviazione di:
<
a(1). a(2). a(3).
</syntaxhighlight>
== Generazione di modelli stabili ==
Utilizzando il software Lparse<ref>{{cita web|url=http://www.tcs.hut.fi/Software/smodels/lparse.ps|titolo=Lparse|editore=[[Università Aalto|Aalto-yliopisto]] - Laboratory of Theoretical Computer Science|urlarchivio=https://web.archive.org/web/20160320044603/http://www.tcs.hut.fi/Software/smodels/lparse.ps|dataarchivio=20 marzo 2016|urlmorto=no|accesso=4 aprile 2016}} ([[PostScript]])</ref> per generare un modello stabile del programma memorizzato nel file dal titolo <code><filename></code> si utilizza il comando:
<
% lparse <filename> | smodels
</syntaxhighlight>
L'opzione <code>0</code> indica alla funzione <code>smodels</code> di trovare tutti i modelli stabili del programma.<br />Ad esempio, dato il seguente programma contenuto nel file "test":
<
1{p,q,r}2.
s :- not p.
</syntaxhighlight>
utilizzando il comando
<
% lparse test | smodels 0
</syntaxhighlight>
verrà prodotto l'output
<
Answer: 1
Stable Model: q p
Riga 98:
Answer: 6
Stable Model: r q s
</syntaxhighlight>
== Applicazioni ==
Riga 107:
Per fare ciò, basta un breve programma in AnsProlog:
<
c(1..n).
1 {color(X,I) : c(I)} 1 :- v(X).
:- color(X,I), color(Y,I), e(X,Y), c(I).
</syntaxhighlight>
Nella riga 1 vengono definiti <math>n</math> colori differenti. La regola presente in riga 2 si occupa di colorare i vertici, ovvero assegna un colore <math>i</math> ad ogni vertice <math>x</math>. Il vincolo nella riga 3 proibisce di assegnare lo stesso colore a due vertici <math>x</math> e <math>y</math> se sono connessi da un arco del grafo.
Definendo un grafo <math>G</math> nella maniera seguente:
<
v(1..100). % 1,...,100 sono vertici
e(1,55). % esiste un arco che connette 1 e 55
. . .
</syntaxhighlight>
ed eseguendo il comando smodels, con il valore numerico di <math>n</math> specificato a linea di comando, allora, se esiste una soluzione, verranno stampati in output degli atomi dalla forma <code>color(. , .)</code>, i quali indicano le assegnazioni colore-vertice da eseguire per ottenere la colorazione di cardinalità indicata.
Riga 126:
In Prolog il problema può essere modellato come segue:
<
dentro(X,Y) | fuori(X,Y) :- arco(X,Y). % ogni arco può essere dentro o fuori il percorso.
:-dentro(X,Y), dentro (X,Y1), Y<>Y1. % partendo da un vertice non si può giungere a due vertici distinti.
Riga 134:
raggiunto(X) :- partenza(X). % il punto di partenza è raggiunto per definizione.
raggiunto(X) :- raggiunto(Y), dentro(Y,X). % partendo da un vertice Y e arrivando ad un vertice X, quest'ultimo è raggiunto.
</syntaxhighlight>
== Note ==
| |||