Programare set de răspunsuri

Programarea setului de răspunsuri ( ASP ) este o formă de programare logică declarativă utilizată pentru probleme complexe de căutare (în primul rând NP-dificilă ), bazată pe semantica modelului stabil (sau set de răspunsuri ). ^[1] În ASP problemele de cercetare sunt reduse la calculul modelelor stabile; pentru a genera aceste modele sunt utilizate programe speciale cunoscute sub numele de solutori de seturi de răspunsuri . Limbajul tipic al acestui model de programare este Answer Set Programming in Logic ( AnsProlog ), un subset de Prolog și este utilizat în special pentru rezolvarea problemelor de planificare și reprezentare a cunoștințelor . ^[1]

Istorie

Metoda de planificare propusă în 1993 de Dimopoulos, Nebel și Köhler ^[2] , bazată pe relația strânsă dintre planificare și modele stabile, ^{[3] a} constituit unul dintre primele exemple de programare a setului de răspunsuri . Utilizarea seturilor de răspunsuri pentru rezolvarea problemelor de cercetare a fost propusă ca o nouă paradigmă de Marek și Truszczyński, a căror teorie a apărut pentru prima dată în 1999 în două publicații diferite. ^[4] ^[5] Expresia „ set de răspunsuri ” ca sinonim pentru „ model stabil ” a fost propusă de Lifschitz. ^[6]

AnsProlog

Lparse este numele programului care a fost creat inițial pentru soluția de răspunsuri smodels . Limbajul acceptat de Lparse este AnsProlog. Un program din AnsProlog constă din reguli scrise sub forma:

 < cap > : - < corp > .

Simbolul :- ("dacă") este omis dacă <body> este gol; asemenea reguli, ca și în Prolog , se numesc fapte .

Un alt tip de construcție este alegerea . De exemplu, regula:

 { p , q , r }.

afirmă: alegeți în mod arbitrar care dintre atomi $p, q, r$ ${\ displaystyle p, q, r}$ $p, q, r$ include în modelul stabil. Un program care conține doar această regulă are 8 modele stabile, subseturi de $\{p,q,r\}$ ${\ displaystyle \ {p, q, r \}}$ ${\ displaystyle \ {p, q, r \}}$ . Semnificația acestei reguli în semantica modelului stabil este reprezentată de formula propozițională :

(p\lor \neg p)\land (q\lor \neg q)\land (r\lor \neg r).

{\ displaystyle (p \ lor \ neg p) \ land (q \ lor \ neg q) \ land (r \ lor \ neg r).}

{\ displaystyle (p \ lor \ neg p) \ land (q \ lor \ neg q) \ land (r \ lor \ neg r).}

De asemenea, este posibil să se impună constrângeri regulilor de selecție, cum ar fi:

 1 { p , q , r } 2.

O astfel de regulă afirmă: alege cel puțin unul dintre atomi $p, q, r$ ${\ displaystyle p, q, r}$ $p, q, r$ , dar nu mai mult de două. Sensul în logica propozițională este dat de următoarea formulă:

(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).

{\ displaystyle (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).}

{\ displaystyle (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).}

Constrângerile de cardinalitate pot fi utilizate și în corpul regulii, de exemplu:

 : - 2 { p , q , r }.

Această constrângere forțează programul să elimine modelele stabile care conțin cel puțin doi atomi aparținând setului $\{p,q,r\}$ ${\ displaystyle \ {p, q, r \}}$ ${\ displaystyle \ {p, q, r \}}$ . Sensul în logica propozițională este dat de următoarea formulă:

\neg ((p\land q)\lor (p\land r)\lor (q\land r)).

{\ displaystyle \ neg ((p \ land q) \ lor (p \ land r) \ lor (q \ land r)).}

{\ displaystyle \ neg ((p \ land q) \ lor (p \ land r) \ lor (q \ land r)).}

Variabilele (cu majuscule, ca în Prolog) sunt utilizate pentru a abrevia colecții de reguli care urmează același model sau pentru a abrevia colecții de atomi în cadrul aceleiași reguli. De exemplu, programul:

 p ( a ). p ( b ). p ( c ).
q ( X ) : - p ( X ), X ! = a .

are aceeași semnificație ca:

 p ( a ). p ( b ). p ( c ).
q ( b ). q ( c ).

Programul:

 p ( a ). p ( b ). p ( c ). p ( d ). p ( e ).
{ q ( X ): - p ( X )} 2.

este o prescurtare pentru:

 p ( a ). p ( b ). p ( c ). p ( d ). p ( e ).
{ q ( a ), q ( b ), q ( c ), q ( d ), q ( e )} 2.

Un interval este exprimat sub forma:

 ( început .. sfârșit )

unde start și end sunt expresii aritmetice cu o valoare constantă. Un interval este o abreviere notationala pentru definirea domeniilor numerice. De exemplu, faptul:

 a ( 1..3 ).

este o prescurtare pentru:

 a ( 1 ). a ( 2 ). a ( 3 ).

Generarea de modele stabile

Utilizând software-ul Lparse ^[7] pentru a genera un model stabil al programului stocat în fișierul intitulat <filename> utilizați comanda:

 % lparse <filename> | smodele

Opțiunea 0 spune funcției smodels să găsească toate modelele stabile din program.
De exemplu, având în vedere următorul program din fișierul „test”:

 1 { p , q , r } 2.
s : - nu p .

folosind comanda

 % lparse test | smodels 0

rezultatul va fi produs

 Raspunsul 1
Model stabil: qp
Răspuns: 2
Model stabil: p 
Răspuns: 3
Model stabil: rp
Răspuns: 4
Model stabil: qs
Răspuns: 5
Model stabil: rs
Răspuns: 6
Model stabil: rqs

Aplicații

După cum sa menționat deja, programarea setului de răspunsuri, pe lângă faptul că are confirmare în reprezentarea cunoștințelor, poate fi folosită și pentru rezolvarea problemelor dificile din punct de vedere al calculului , cum ar fi problema colorării graficului , calea hamiltoniană sau satisfacția booleană . ^[8]

Colorabilitate

Acolo $n$ ${\ displaystyle n}$ $n$ -colorabilitatea unui grafic $G=\left\langle V,E\right\rangle$ ${\ displaystyle G = \ left \ langle V, E \ right \ rangle}$ ${\ displaystyle G = \ left \ langle V, E \ right \ rangle}$ este o funcție $color:V\to \{1,\dots ,n\}$ ${\ displaystyle color: V \ to \ {1, \ dots, n \}}$ ${\ displaystyle color: V \ to \ {1, \ dots, n \}}$ astfel încât $color(x)\neq color(y)$ ${\ displaystyle color (x) \ neq color (y)}$ ${\ displaystyle color (x) \ neq color (y)}$ pentru fiecare pereche de vârfuri adiacente $(x,y)\in E$ ${\ displaystyle (x, y) \ în E}$ ${\ displaystyle (x, y) \ în E}$ . Puteți utiliza ASP pentru a găsi unul $n$ ${\ displaystyle n}$ $n$ -colorarea unui grafic dat sau demonstrarea faptului că nu există.

Pentru a face acest lucru, este suficient un program scurt în AnsProlog:

 c ( 1 .. n ).                                           
1 { culoare ( X , I ) : c ( I )} 1 : - v ( X ).             
: - culoare ( X , I ), culoare ( Y , I ), e ( X , Y ), c ( I ).

În linia 1 sunt definite $n$ ${\ displaystyle n}$ $n$ Culori diferite. Regula din linia 2 se referă la colorarea vârfurilor, adică atribuie o culoare $the$ ${\ displaystyle i}$ $the$ la fiecare vârf $X$ ${\ displaystyle x}$ $X$ . Constrângerea din linia 3 interzice atribuirea aceleiași culori la două vârfuri $X$ ${\ displaystyle x}$ $X$ Și $y$ ${\ displaystyle y}$ $y$ dacă sunt conectate printr-un arc al graficului.

Prin definirea unui grafic $G.$ ${\ displaystyle G}$ $G.$ în felul următor:

 v ( 1..100 ). % 1, ..., 100 sunt vârfuri
și ( 1 , 55 ). % există un arc care leagă 1 și 55
. . .

și executarea comenzii smodels, cu valoarea numerică de $n$ ${\ displaystyle n}$ $n$ specificate pe linia de comandă, atunci, dacă există o soluție, vor fi imprimați în ieșire atomi cu color(. , .) formularului color(. , .) , care indică atribuțiile de culoare-vârf care trebuie efectuate pentru a obține colorarea cardinalității indicată.

Calea Hamiltoniană

Având în vedere un grafic direcționat $G=\left\langle V,E\right\rangle$ ${\ displaystyle G = \ left \ langle V, E \ right \ rangle}$ ${\ displaystyle G = \ left \ langle V, E \ right \ rangle}$ și un punct de plecare specific $v_{s}\in V$ ${\ displaystyle v_ {s} \ în V}$ ${\ displaystyle v_ {s} \ în V}$ , calea hamiltoniană de pe acest grafic este o cale care include toate vârfurile sale începând de la $v_{s}$ ${\ displaystyle v_ {s}}$ $v_ {s}$ .

În Prolog problema poate fi modelată după cum urmează:

 în interior ( X , Y ) | exterior ( X , Y ) : - arc ( X , Y ). % fiecare arc poate fi în sau în afara căii.
: - în interior ( X , Y ), în interior ( X , Y1 ), Y <> Y1 . % pornind de la un vârf nu este posibil să se atingă două vârfuri distincte.
: - în interior ( X , Y ), în interior ( X1 , Y ), X <> X1 . % pornind de la două vârfuri distincte nu este posibil să se atingă același vârf.
: - nod ( X ), nu a fost atins ( X ). % un vârf nu poate fi ratat.
: - în interior ( X , Y ), plecare ( Y ). % vârful de pornire nu poate fi atins de niciun alt vârf.
atins ( X ) : - plecare ( X ). % punctul de plecare este atins prin definiție.
atins ( X ) : - atins ( Y ), în interior ( Y , X ). % începând de la un vârf Y și ajungând la un vârf X, acesta este atins.

Notă

^ ^a ^b Valentina Pitoni, Answer Set Programming ( PDF ), Universitatea din L'Aquila . Adus la 4 aprilie 2016 (arhivat din original la 4 noiembrie 2016) .
^ (EN) Y. Dimopoulos, B. Nebel și J. Köhler, Codificarea problemelor de planificare în programele de logică non-monotonă în Sam Steel și Rachid Alami (eds), Progrese recente în planificarea AI: a 4-a Conferință europeană de planificare, ECP'97 , Toulouse, Franța, 24–26 septembrie 1997, Proceedings , Lecture notes in computer science: Lecture notes in artificial intelligence, vol. 1348, Springer, 1997, pp. 273-285, ISBN 978-3-540-63912-1 . ca Postscript
^ (EN) VS Subrahmanian și C. Zaniolo, Relating stable models and AI planning domains in Leon Sterling (ed), Logic Programming: Proceedings of the XII Congres International of Logic Programming, MIT Press, 1995, pp. 233–247, ISBN 978-0-262-69177-2 . ca Postscript
^ (EN) V. Marek și M. Truszczyński, Modele stabile și o paradigmă de programare logică alternativă , în Krzysztof R. Apt (eds), Paradigma de programare logică: o perspectivă de 25 de ani (PDF), Springer, 1999 pp. 169–181, ISBN 978-3-540-65463-6 .
^ (EN) I. Niemelä, Programe logice cu semantică model stabilă ca paradigmă de programare a constrângerii , în Annals of Mathematics and Artificial Intelligence, vol. 25, 1999, pp. 241-273, DOI : 10.1023 / A: 1018930122475 . ( PostScript )
^ (EN) V. Lifschitz, Action Languages, Answer Sets, and Planning, 1999. În Apt , pp. 357–374
^ Lparse ( ps ), pe tcs.hut.fi , Aalto-yliopisto - Laboratory of Theoretical Computer Science. Adus la 4 aprilie 2016 ( arhivat la 20 martie 2016) . ( PostScript )
^ (EN) Probleme de modelare în ASP (PDF) pe cs.sfu.ca, Universitatea Simon Fraser. Adus la 4 aprilie 2016 ( arhivat la 4 aprilie 2016) .

Elemente conexe

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[pitoni-1] Valentina Pitoni, Answer Set Programming ( PDF ), Universitatea din L'Aquila . Adus la 4 aprilie 2016 (arhivat din original la 4 noiembrie 2016) .

[2] (EN) Y. Dimopoulos, B. Nebel și J. Köhler, Codificarea problemelor de planificare în programele de logică non-monotonă în Sam Steel și Rachid Alami (eds), Progrese recente în planificarea AI: a 4-a Conferință europeană de planificare, ECP'97 , Toulouse, Franța, 24–26 septembrie 1997, Proceedings , Lecture notes in computer science: Lecture notes in artificial intelligence, vol. 1348, Springer, 1997, pp. 273-285, ISBN 978-3-540-63912-1 . ca Postscript

[3] (EN) VS Subrahmanian și C. Zaniolo, Relating stable models and AI planning domains in Leon Sterling (ed), Logic Programming: Proceedings of the XII Congres International of Logic Programming, MIT Press, 1995, pp. 233–247, ISBN 978-0-262-69177-2 . ca Postscript

[4] (EN) V. Marek și M. Truszczyński, Modele stabile și o paradigmă de programare logică alternativă , în Krzysztof R. Apt (eds), Paradigma de programare logică: o perspectivă de 25 de ani (PDF), Springer, 1999 pp. 169–181, ISBN 978-3-540-65463-6 .

[5] (EN) I. Niemelä, Programe logice cu semantică model stabilă ca paradigmă de programare a constrângerii , în Annals of Mathematics and Artificial Intelligence, vol. 25, 1999, pp. 241-273, DOI : 10.1023 / A: 1018930122475 . ( PostScript )

[6] (EN) V. Lifschitz, Action Languages, Answer Sets, and Planning, 1999. În Apt , pp. 357–374

[7] Lparse ( ps ), pe tcs.hut.fi , Aalto-yliopisto - Laboratory of Theoretical Computer Science. Adus la 4 aprilie 2016 ( arhivat la 20 martie 2016) . ( PostScript )

[8] (EN) Probleme de modelare în ASP (PDF) pe cs.sfu.ca, Universitatea Simon Fraser. Adus la 4 aprilie 2016 ( arhivat la 4 aprilie 2016) .

[1]

[2]

[3] a

[4]

[5]

[6]

[7]

[8]