Одговор сет програмирање
Одговор сет програмирање (ОКП) је облик декларативног програмирања оријентисано ка тешким (пре свега НП-тешко) претраживањем проблема. Она се заснива на стабилном моделу (одговор сет) семантичке логике програмирања. У ОКПу, проблеми претраге се своде на рачунарске стабилне моделе, а одговор комплет решење - програми за генерисање стабилних модела се користе за обављање претраге. Рачунарски процес запослен у дизајну који за многе одговоре поставља решење је унапређен у ДПЛЛ алгоритам и, у принципу, увек се завршава (за разлику од Пролог процене упита, што може довести до бесконачне петље).
У општем смислу, ОКП обухвата све апликације одговора комплета представљања знања и коришћење[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] На пример, избор правило изнад може се посматрати као скраћеница за повезаност три "искључен средњи" формула:
Језик лпарсе нам омогућава и да пише "приморавају" Избор правила, као што су
1{p,q,r}2.
Ово правило каже: изабрати најмање 1 од атома p,q,r, али не више од 2. Смисао овог правила под стабилним моделима семантике се представљају пропозиционалном формулом
Кардиналност границе се могу користити у телу правила, као на пример:
:- 2{p,q,r}.
Додавање овог ограничења на Лпарсе програм елиминише стабилне моделе који садрже најмање 2 атома p,q,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-бојење .
Програм у овом примеру илуструје "генерише-и-тест" организацију која се често налази у једноставним АСП програмима. Правило избора описује скуп "могућих решења" - једноставно надскуп скупа решења датог проблема претраге. Након тога следи ограничење, које елиминише сва потенцијална решења која нису прихватљива. Међутим, процес претрага запослен смоделс и други одговор постављених решења се не заснива на суђењу и грешкама.
Велика клика[уреди | уреди извор]
Клика у графу је скуп парова суседних темена. Следећи лпарсе програм проналази клику величину ≥ 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.