|
L{{'}}'''answer set programming''' ('''ASP''') è una forma di [[programmazione logica]] di tipo [[Programmazione dichiarativa|dichiarativo]] utilizzato per [[Algoritmo di ricerca|problemi di ricerca]] complessi (in primis [[NP-difficile|NP-difficili]]), basata sulla [[semantica del modello stabile]] (o ''answer set'').<ref name="pitoni">{{cita pubblicazione|autore=Valentina Pitoni|titolo=Answer Set Programming|url=http://costantini.di.univaq.it/CorsoAI/Answer%20Set%20Programming.pdf|formato=pdf|editore=[[Università degli Studi dell'Aquila]]|accesso=4 aprile 2016|urlarchivio=https://web.archive.org/web/20161104023636/http://costantini.di.univaq.it/CorsoAI/Answer%20Set%20Programming.pdf|dataarchivio=4 novembre 2016|urlmorto=sì}}</ref> In ASP i problemi di ricerca sono ridotti al calcolo di modelli stabili; per generare tali modelli vengono utilizzati programmi appositi noti come ''answer set solvers''. Il linguaggio tipico di questo modello di programmazione è l{{'}}''Answer Set Programming in Logic'' ([[#AnsProlog|AnsProlog]]), sottoinsieme del [[Prolog]], ed è impiegato in particolare per risolvere problemi di pianificazione (''planning'') e [[rappresentazione della conoscenza]].<ref name="pitoni"/>
== Storia ==
Il metodo di planning proposto nel 1993 da Dimopoulos, Nebel e Köhler<ref>{{cita libro|lingua=en|nome1=Y. |cognome1=Dimopoulos |wkautore2=Bernhard Nebel |nome2=B. |cognome2=Nebel |nome3=J. |cognome3=Köhler |capitolo=Encoding planning problems in non-monotonic logic programs |pp=273–285273-285 |curatore-nome1=Sam |curatore1=Steel |curatore-nome2=Rachid |curatore2=Alami |titolo=Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings |url=http://books.google.com/books?id=QSBoQgAACAAJ |anno=1997 |editore=Springer |isbn=978-3-540-63912-1 |volume=1348 |trasmissione=Lecture notes in computer science: Lecture notes in artificial intelligence}} [ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/dimopoulos-etal-ecp97.ps.gz as Postscript]</ref>, basato sulla stretta relazione tra le pianificazioni e i modelli stabili,<ref>{{cita libro|lingua=en|nome1=V.S. |cognome1=Subrahmanian |nome2=C. |cognome2=Zaniolo |capitolo=Relating stable models and AI planning domains |curatore=Leon Sterling |titolo=Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming |url_capitolourlcapitolo=http://books.google.com/books?id=vpGEyZWP1dYC&pg=PA233 |anno=1995 |editore=MIT Press |isbn=978-0-262-69177-2 |pp=233–247233-247}} [http://www.cs.ucla.edu/%7Ezaniolo/papers/iclp95.ps as Postscript]</ref> costituì uno dei primi esempi di ''answer set'' programming. L'utilizzo di ''[[answer set]]'' per risolvere problemi di ricerca fu proposto come nuovo paradigma da Marek e Truszczyński, la cui teoria apparve inizialmente nel 1999 su due differenti pubblicazioni.<ref>{{cita libro|lingua=en|nome1=V. |cognome1=Marek |nome2=M. |cognome2=Truszczyński |capitolo=Stable models and an alternative logic programming paradigm |curatore=Krzysztof R. Apt |titolo=The Logic programming paradigm: a 25-year perspective |url=http://books.google.com/books?id=GIhQAAAAMAAJ |anno=1999 |editore=Springer |isbn=978-3-540-65463-6 |url_capitolourlcapitolo=http://xxx.lanl.gov/pdf/cs/9809032 |formato=PDF |pp=169–181169-181 |cid={{harvid|Apt|, 1999}}}}</ref><ref>{{cita pubblicazione|lingua=en|nome=I. |cognome=Niemelä |titolo=Logic programs with stable model semantics as a constraint programming paradigm |rivista=Annals of Mathematics and Artificial Intelligence |volume=25 |pp=241–273241-273 |anno=1999 |doi=10.1023/A:1018930122475 |url=http://users.ics.aalto.fi/ini/papers/lp-csp-long.ps.gz}} ([[PostScript]])</ref>
L'espressione "''answer set''" come sinonimo di "''stable model''" fu proposta da Lifschitz.<ref>{{Cita pubblicazione|lingua=en|nome=V. |cognome=Lifschitz |titolo=Action Languages, Answer Sets, and Planning |anno=1999}} In {{harvnb|Apt|1999|pp=357–374}}</ref>
== AnsProlog ==
{p,q,r}.
</syntaxhighlight>
afferma: scegli arbitrariamente quali fra gli [[Atomo (logica)|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>
== 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:
<syntaxhighlight lang="bash">
% lparse <filename> | smodels
== Applicazioni ==
Come già detto, lL'answer set programming, oltre ad avere riscontro nella rappresentazione della conoscenza, può essere anche utilizzato per risolvere problemi [[Teoria della complessità computazionale|computazionalmente]] difficili, come il problema della [[colorazione dei grafi]], del [[cammino hamiltoniano]] o di [[soddisfacibilità booleana]].<ref>{{cita web|url=https://www.cs.sfu.ca/CourseCentral/411/jim/ASP2.Modelling.pdf|titolo=Modelling Problems in ASP|editore=Simon Fraser University|formato=PDF|sito=cs.sfu.ca|lingua=en|urlarchivio=https://web.archive.org/web/20160404175606/https://www.cs.sfu.ca/CourseCentral/411/jim/ASP2.Modelling.pdf|dataarchivio=4 aprile 2016|urlmorto=no|accesso=4 aprile 2016}}</ref>
=== Colorabilità ===
In Prolog il problema può essere modellato come segue:
<syntaxhighlight lang="prolog">
dentro(X,Y) | fuori(X,Y) :- arco(X,Y). % ogni arco può essere dentro o fuori ildal percorso.
:-dentro(X,Y), dentro (X,Y1), Y<>Y1. % partendo da un vertice non si può giungere a due vertici distinti.
:-dentro(X,Y), dentro (X1,Y), X<>X1. % partendo da due vertici distinti non si può giungere allo stesso vertice.
| 