Одговор сет програмирање

Одговор сет програмирање (ОКП) је облик декларативног програмирања оријентисано ка тешким (пре свега НП-тешко) претраживањем проблема. Она се заснива на стабилном моделу (одговор сет) семантичке логике програмирања. У ОКПу, проблеми претраге се своде на рачунарске стабилне моделе, а одговор комплет решење - програми за генерисање стабилних модела се користе за обављање претраге. Рачунарски процес запослен у дизајну који за многе одговоре поставља решење је унапређен у ДПЛЛ алгоритам и, у принципу, увек се завршава (за разлику од Пролог процене упита, што може довести до бесконачне петље).

У општем смислу, ОКП обухвата све апликације одговора комплета представљања знања и коришћење^[1]^[2] Пролог стила за процене упита за решавање проблема који се јављају у овим апликацијама.

Историја

Метод планирања предложен 1993. године Димопоулос, Небел и Кохлер^[3] је рани пример одговор сет програмирања. Њихов приступ се заснива на односу између планова и стабилних модела.^[4] Соининен и Ниемела^[5] примењује оно што је данас познато као одговор сет програма на проблем конфигурације производа. Употреба одговора постављених решења за претрагу је идентификован као нова парадигма програмирања од Марека и Трусзцзински у новинама које су се појавиле у 25-година перспективе на парадигму логике програмирања објављене 1999.^[6] године и у [Ниемела 1999].^[7] Заиста, нова терминологија "Одговор комплет" уместо "стабилан модел" је први предложио Лифсцхитз^[8] у новинама се појављују у истом обиму ретроспективно Марек-Трусзцзинсковом папиру.

Одговор сет програмирање језик АнсПролог

Ларсе је име програма који је првобитно настао као уземљење алата (фронт-енд) за одговор постављених решених смодела. Језик који Лпарсе прихвата се сада обично зове АнсПролог *,^[9] скраћено од одговора сет програмирања у логици.^[10] Сада се користи на исти начин и у многим другим одговор сет решењима, укључујући ассат, копче, цмодела, гНТ, номоре++ и пбмодели. (длв је изузетак, а синтакса АСП програма написана за ДЛВ је нешто другачија.)

АнсПролог програм се састоји од правила у облику

<head> :- <body> .

Симбол :- ("ако") је пао ако <тело> је празна; таква правила називају чињенице. Најједноставнији тип Лпарсе правила су правила са ограничењима.

Још једна корисна конструкција укључена у том језику је избор. На пример, правило избора.

{p,q,r}.

каже: одаберите произвољно који од атома p,q,r ће се укључити у стабилан модел. Лпарсе програм који садржи овај избор правила и нема других правила има 8 стабилни модела-произвољних подскупова {p,q,r}. Дефиниција стабилног модела је генерализована на програмима са избором правила.^[11] Цхоице правила могу се третирати као скраћеница за пропозицијски формула под стабилним моделима семантике.^[12] На пример, избор правило изнад може се посматрати као скраћеница за повезаност три "искључен средњи" формула:

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

Језик лпарсе нам омогућава и да пише "приморавају" Избор правила, као што су

1{p,q,r}2.

Ово правило каже: изабрати најмање 1 од атома p,q,r, али не више од 2. Смисао овог правила под стабилним моделима семантике се представљају пропозиционалном формулом

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

Кардиналност границе се могу користити у телу правила, као на пример:

:- 2{p,q,r}.

Додавање овог ограничења на Лпарсе програм елиминише стабилне моделе који садрже најмање 2 атома p,q,r. Смисао овог правила може бити представљен пропозиционалном формулом

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

Променљиве (ВЕЛИКИМ СЛОВИМА, као у Пролог) се користи у Лпарсе да скрате колекције правила која следе исти образац, као и да скрате збирке атома у истом правилу. На пример, Лпарсе програм

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

има исто значење као

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

Програм

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

је скраћеница за

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

низ је облика:

<Predicate>(start..end)

где су почетак и крај стални цењени аритметички изрази. Распон је систем знакова пречица која се углавном користи за дефинисање нумеричких домена у компатибилном начин. На пример, чињеница

a(1..3).

је пречица за

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

Распон се такође може користити у органима правилника са истом семантиком.

Условно буквално има облик:

p(X):q(X)

Уколико продужење q је {к (а1); к (а2); ...; q (aN)}, горе услов је семантички еквивалент писању p (а1), p(А2), ..., p(aN) на месту стања. На пример

q(1..2).
a :- 1 {p(X):q(X)}.

је скраћеница за

q(1). q(2).
a :- 1 {p(1), p(2)}.

Стварање стабилних модела

Да бисте пронашли стабилан модел Лпарсе програма који се налазе у датотеци<имефајла> користимо команду

% lparse <filename> | smodels

Опција 0 налаже смоделсу да пронађе све стабилне моделе програма. На пример, ако датотека теста садржи правила

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

онда команда

% lparse test | smodels 0

производи излаз

Одговор: 1
Stable Model: q p Одговор: 2
Stable Model: p Одговор: 3
Stable Model: r p Одговор: 4
Stable Model: q s Одговор: 5
Stable Model: r s Одговор: 6
Stable Model: r q s

Примери АСП програма

Графикон бојења

Н-бојење графикона Г је функција боја \ из свог сета темена до {1,...,n} таква да боје (х) ≠ боје(у) за сваки пар суседних темена x, y . Желимо да користимо АСП да пронађу н-боју датог графа (или утврди да не постоји).

Ово се може остварити коришћењем следећи програм Лпарсе:

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

Линија 1 дефинише бројеве 1,..., n да буду боје. Према правилу избора у линији 2, јединствене боје требало би да буде додељен сваком темену x. Ограничење у реду 3 забрањује додељивање исте боје теменима x и у ако постоји нешто што их повезује.

Ако комбинујемо ову слику са дефиницијом G, као што су

v(1..100). % 1,...,100 are vertices
e(1,55). % there is an edge from 1 to 55
. . .

и имају смоделс на њему, са нумеричким вредностима n наведеног на командној линији, онда су атоми облика боје (...,...) у излазу смоделс ће представљати n-бојење $G$ .

Програм у овом примеру илуструје "генерише-и-тест" организацију која се често налази у једноставним АСП програмима. Правило избора описује скуп "могућих решења" - једноставно надскуп скупа решења датог проблема претраге. Након тога следи ограничење, које елиминише сва потенцијална решења која нису прихватљива. Међутим, процес претрага запослен смоделс и други одговор постављених решења се не заснива на суђењу и грешкама.

Велика клика

Клика у графу је скуп парова суседних темена. Следећи лпарсе програм проналази клику величину ≥ n у датом графику, или утврди да не постоји:

n {in(X) : v(X)}.
:- in(X), in(Y), v(X), v(Y), X!=Y, not e(X,Y), not e(Y,X).

Ово је још један пример који генерише-и-тест организацију. Правило избора у линији 1 "ствара" сви скупови који се састоје од ≥ n темена. Ограничење у линији 2 "Веедс од" сетове који нису клике.

Хамилтонијан циклус

Хамилтонов циклус у режији графика је циклус који пролази кроз свако темене графика тачно једанпут. Следећи Лпарсе програм може да се користи да пронађе Хамилтонов циклус у датом усмереном графику ако постоји; претпостављамо да 0 једна од теменима.

{in(X,Y)} :- e(X,Y).

:- 2 {in(X,Y) : e(X,Y)}, v(X).
:- 2 {in(X,Y) : e(X,Y)}, v(Y).

r(X) :- in(0,X), v(X).
r(Y) :- r(X), in(X,Y), e(X,Y).

:- not r(X), v(X).

Правило избора у линији 1 "генерише" све подскупове скупа ивица. Три ограничења "веед оут" Подскупови које нису Хамилтонов циклус. Последњи од њих користи помоћни предикат r(x)("x је доступан од 0") да забрани темена који не задовољавају овај услов. Овај предикат је рекурзивно дефинисан у редовима 4 и 5.

Овај програм је пример општије "генерисати, дефинишу и тест" организације: укључује дефиницију помоћним предикатима који нам помаже да елиминишемо сва "лоша" потенцијална решења.

Зависност анализе

У обради природних језика, зависност заснована на рашчлањавању може бити формулисана као АСП проблем.^[13] Следећи код парсира латинску реченицу Puella pulchra in villa linguam latinam discit "лепа девојка учи латински у вили". Синтакса дрво је изражена од стране лука предиката који представљају зависност између речи осуде. Израчуната структура је линеарно наредно укорењено стабло.

% ********** input sentence **********
word(1, puella). word(2, pulchra). word(3, in). word(4, villa). word(5, linguam). word(6, latinam). word(7, discit).
% ********** lexicon **********
1{ node(X, attr(pulcher, a, fem, nom, sg));
   node(X, attr(pulcher, a, fem, nom, sg)) }1 :- word(X, pulchra).
node(X, attr(latinus, a, fem, acc, sg)) :- word(X, latinam).
1{ node(X, attr(puella, n, fem, nom, sg));
   node(X, attr(puella, n, fem, abl, sg)) }1 :- word(X, puella).
1{ node(X, attr(villa, n, fem, nom, sg));
   node(X, attr(villa, n, fem, abl, sg)) }1 :- word(X, villa).
node(X, attr(linguam, n, fem, acc, sg)) :- word(X, linguam).
node(X, attr(discere, v, pres, 3, sg)) :- word(X, discit).
node(X, attr(in, p)) :- word(X, in).
% ********** syntactic rules **********
0{ arc(X, Y, subj) }1 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, nom, sg)).
0{ arc(X, Y, dobj) }1 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, acc, sg)).
0{ arc(X, Y, attr) }1 :- node(X, attr(_, n, Gender, Case, Number)), node(Y, attr(_, a, Gender, Case, Number)).
0{ arc(X, Y, prep) }1 :- node(X, attr(_, p)), node(Y, attr(_, n, _, abl, _)), X < Y.
0{ arc(X, Y, adv) }1 :- node(X, attr(_, v, _, _, _)), node(Y, attr(_, p)), not leaf(Y).
% ********** guaranteeing the treeness of the graph **********
1{ root(X):node(X, _) }1.
:- arc(X, Z, _), arc(Y, Z, _), X != Y.
:- arc(X, Y, L1), arc(X, Y, L2), L1 != L2.
path(X, Y) :- arc(X, Y, _).
path(X, Z) :- arc(X, Y, _), path(Y, Z).
:- path(X, X).
:- root(X), node(Y, _), X != Y, not path(X, Y).
leaf(X) :- node(X, _), not arc(X, _, _).

Поређење имплементација

Рани системи, као што су Смоделс, Половни одустајање да пронађу решења. Као теорија и пракси Булов САТ решавача развијао, један број АСП солверс изграђене су на врху САТ решавача, укључујући Ассат и Цмоделс. Ово претворена АСП формулу у САТ пропозицијама, примењено САТ солвер, а затим решења конвертује у АСП форми. Новији системи, као што су копча, користите хибридни приступ, користећи алгоритме сукобом-дривен инспирисане САТ, без пуно претварање у Боолеан логичкој-форми. Ови приступи омогућавају значајно побољшања перформанси, често реда величине, преко раније помацима алгоритама.

Потассцо пројекат делује као кишобран за многе системе испод, укључујући копчу, уземљење система (гринго), постепене системе (ицлинго), ограничења решења (цлингцон), акциони језик до АСП компајлера (цоала), дистрибуирани МПИ имплементације (цласпар) , и многи други.

Већина система подржава варијабле, већ само посредно, тако што би приморало уземљење, помоћу уземљења система као што је Лпарсе или странац као предњи крај. Потреба за уземљење може проузроковати експлозију комбинаторног клаузула; дакле, системи који обављају он-тхе-фли уземљење можда има предност.

Платформа			Функција					Механика
Име	OS	Лиценца	Променљива	Функција симбола	Експлицитни сетови	Експлицитне листе	Дисјунктивна (избор правила) подршка
ASPeRiX Архивирано на сајту Wayback Machine (8. новембар 2016)	Linux	GPL	Да				Не	уземљење у лету
ASSAT	Solaris	Бесплатан софтвер						САТ основа решења
Clasp Answer Set Solver	Linux, Mac OS, Windows	GPL	Да у Цлингу	Да	Не	Не	Да	постепени, САТ решење инспирисан (НоГоод, конфликт-дривен)
Cmodels	Linux, Solaris	GPL	Захтева уземљење				Да	постепени, САТ решење инспирисан (НоГоод, конфликт-дривен)
DLV	Linux, Mac OS, Windows^[14]	free for academic and non-commercial educational use, and for non-profit organizations^[14]	Да	Да	Не	Не	Да	Не компатибилан Лпарс
DLV-Complex	Linux, Mac OS, Windows	Freeware		Да	Да	Да	Да	изграђен на врху ДЛВ - Не компатибилан Лпарс
GnT	Linux	GPL	Захтева уземљење				Да	изграђен на врху смодела
nomore++	Linux	GPL						комбиновани буквално + правилно - основа
Platypus	Linux, Solaris, Windows	GPL						дистрибуира, мулти-тхреадед номоре ++ смоделс
Pbmodels	Linux	?						Псеудо-булово решење на бази
Smodels	Linux, Mac OS, Windows	GPL	Захтева уземљење	Не	Не	Не	Не
Smodels-cc Архивирано на сајту Wayback Machine (15. новембар 2015)	Linux	?	Захтева уземљење					САТ решење засновано; смодела в / конфликтним тачкама
Sup	Linux	?						САТ решење на основи

Види још

Референце

^ Baral 2003.
^ Gelfond, Michael (2008). „Answer sets”. Ур.: van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce. Handbook of Knowledge Representation (PDF). Elsevier. стр. 285—316. ISBN 978-0-08-055702-1. Архивирано из оригинала 03. 03. 2016. г. as PDF
^ Dimopoulos, Y.; Nebel, B.; Köhler, J. (1997). „Encoding planning problems in non-monotonic logic programs”. Ур.: Steel, Sam; Alami, Rachid. Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings. Lecture notes in computer science: Lecture notes in artificial intelligence. 1348. Springer. стр. 273—285. ISBN 978-3-540-63912-1. as Postscript
^ Subrahmanian, V.S.; Zaniolo, C. (1995). „Relating stable models and AI planning domains”. Ур.: Sterling, Leon. Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming. MIT Press. стр. 233—247. ISBN 978-0-262-69177-2. as Postscript
^ Soininen, T.; Niemelä, I. (1998), Formalizing configuration knowledge using rules with choices (Postscript) (TKO-B142), Laboratory of Information Processing Science, Helsinki University of Technology
^ Marek, V.; Truszczyński, M. (1999). „Stable models and an alternative logic programming paradigm”. Ур.: Apt, Krzysztof R. The Logic programming paradigm: a 25-year perspective (PDF). Springer. стр. 169—181. ISBN 978-3-540-65463-6.
^ Niemelä, I. (1999). „Logic programs with stable model semantics as a constraint programming paradigm” (Postscript,gzipped). Annals of Mathematics and Artificial Intelligence. 25: 241—273. doi:10.1023/A:1018930122475.
^ Lifschitz, V. (1999). „Action Languages, Answer Sets, and Planning”. In Apt 1999, стр. 357–374
^ Crick, Tom (2009). Superoptimisation: Provably Optimal Code Generation using Answer Set Programming (PDF) (Ph.D.). University of Bath. Docket 20352. Архивирано из оригинала (PDF) 4. 3. 2016. г. Приступљено 28. 11. 2015.
^ Davila, Rogelio. „AnsProlog, an overview”. Архивирано из оригинала (PowerPoint) 08. 12. 2015. г. Приступљено 28. 11. 2015.
^ Niemelä, I.; Simons, P.; Soinenen, T. (2000). „Stable model semantics of weight constraint rules”. Ур.: Gelfond, Michael; Leone, Nicole; Pfeifer, Gerald. Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings. Lecture notes in computer science: Lecture notes in artificial intelligence. 1730. Springer. стр. 317—331. ISBN 978-3-540-66749-0. as Postscript
^ Ferraris, P.; Lifschitz, V. (2005). „Weight constraints as nested expressions” (PDF). Theory and Practice of Logic Programming. 5 (1-2): 45—74. doi:10.1017/S1471068403001923.
^ „Dependency parsing”. Архивирано из оригинала 15. 4. 2015. г. Приступљено 28. 11. 2015.
^ ^а ^б „DLV System company page”. DLVSYSTEM s.r.l. Приступљено 16. 11. 2011.

Литература

Dimopoulos, Y.; Nebel, B.; Köhler, J. (1997). „Encoding planning problems in non-monotonic logic programs”. Ур.: Steel, Sam; Alami, Rachid. Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings. Lecture notes in computer science: Lecture notes in artificial intelligence. 1348. Springer. стр. 273—285. ISBN 978-3-540-63912-1.
Gelfond, Michael (2008). „Answer sets”. Ур.: van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce. Handbook of Knowledge Representation (PDF). Elsevier. стр. 285—316. ISBN 978-0-08-055702-1. Архивирано из оригинала 03. 03. 2016. г. as PDF
Baral, Chitta (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. ISBN 978-0-521-81802-5.

Спољашње везе

[FOOTNOTEBaral2003-1] Baral 2003.

[2] Gelfond, Michael (2008). „Answer sets”. Ур.: van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce. Handbook of Knowledge Representation (PDF). Elsevier. стр. 285—316. ISBN 978-0-08-055702-1. Архивирано из оригинала 03. 03. 2016. г. as PDF

[3] Dimopoulos, Y.; Nebel, B.; Köhler, J. (1997). „Encoding planning problems in non-monotonic logic programs”. Ур.: Steel, Sam; Alami, Rachid. Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings. Lecture notes in computer science: Lecture notes in artificial intelligence. 1348. Springer. стр. 273—285. ISBN 978-3-540-63912-1. as Postscript

[4] Subrahmanian, V.S.; Zaniolo, C. (1995). „Relating stable models and AI planning domains”. Ур.: Sterling, Leon. Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming. MIT Press. стр. 233—247. ISBN 978-0-262-69177-2. as Postscript

[5] Soininen, T.; Niemelä, I. (1998), Formalizing configuration knowledge using rules with choices (Postscript) (TKO-B142), Laboratory of Information Processing Science, Helsinki University of Technology

[6] Marek, V.; Truszczyński, M. (1999). „Stable models and an alternative logic programming paradigm”. Ур.: Apt, Krzysztof R. The Logic programming paradigm: a 25-year perspective (PDF). Springer. стр. 169—181. ISBN 978-3-540-65463-6.

[7] Niemelä, I. (1999). „Logic programs with stable model semantics as a constraint programming paradigm” (Postscript,gzipped). Annals of Mathematics and Artificial Intelligence. 25: 241—273. doi:10.1023/A:1018930122475.

[8] Lifschitz, V. (1999). „Action Languages, Answer Sets, and Planning”. In Apt 1999, стр. 357–374

[9] Crick, Tom (2009). Superoptimisation: Provably Optimal Code Generation using Answer Set Programming (PDF) (Ph.D.). University of Bath. Docket 20352. Архивирано из оригинала (PDF) 4. 3. 2016. г. Приступљено 28. 11. 2015.

[10] Davila, Rogelio. „AnsProlog, an overview”. Архивирано из оригинала (PowerPoint) 08. 12. 2015. г. Приступљено 28. 11. 2015.

[11] Niemelä, I.; Simons, P.; Soinenen, T. (2000). „Stable model semantics of weight constraint rules”. Ур.: Gelfond, Michael; Leone, Nicole; Pfeifer, Gerald. Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings. Lecture notes in computer science: Lecture notes in artificial intelligence. 1730. Springer. стр. 317—331. ISBN 978-3-540-66749-0. as Postscript

[12] Ferraris, P.; Lifschitz, V. (2005). „Weight constraints as nested expressions” (PDF). Theory and Practice of Logic Programming. 5 (1-2): 45—74. doi:10.1017/S1471068403001923.

[13] „Dependency parsing”. Архивирано из оригинала 15. 4. 2015. г. Приступљено 28. 11. 2015.

[dlvsystem.com-14] а ^б „DLV System company page”. DLVSYSTEM s.r.l. Приступљено 16. 11. 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]