Програмування наборами відповідей: відмінності між версіями

[неперевірена версія]

← Попереднє редагування Наступне редагування →

Вилучено вміст Додано вміст

Лінійно

Версія за 15:47, 21 грудня 2016

Програмування наборами відповідей (англ. Answer set programming, ASP) — це форма декларативного програмування, орієнтованого на складні (насамперед NP-складні) задачі пошуку●. Воно засноване на стійкій моделі семантики логічного програмування. В ASP, задача пошуку зводиться до обчислювання стійкої моделі і наборів вирішувачів (answer set solvers) — програм для генерування стійких моделей, що використовуються для пошуку. Обчислювальний процес, включений в конструкцію набору вирішувачів (answer set solvers) — є посиленням DPLL алгоритму●, який завжди є скінченним (на відміну від оцінки запиту в Prolog, що може призвести до нескінченного циклу).

Взагалі, ASP включає всі додатки з наборів відповідей для представлення знань^[1]^[2] та використання оцінки запитів, типу Prolog для вирішення задач, що виникають у цих додатках.

Історія

Планувальний● метод, запропонований в 1993 році Янісом Дімопулосом, Бернардом Небелем^[3] і Джонатаном Кехлером є раннім прикладом програмування наборами відповідей. Їх підхід заснований на взаємозв'язку проекту зі стійкою моделлю. Т.Шойнен та І.Німель застосували те, що зараз відомо як програмування наборами відповідей для розв'язання задачі конфігурації продукту. Використання наборів вирішувачів для пошуку був визначений в якості нової парадигми програмування Віктором Мареком^[4] і Мар'яном Цургувінськи в документі, опублікованому в 1999 році. Дійсно, в новій термінології «набір відповідей», замість «стабільної моделі», був вперше запропонований Ліфшицем, у статті, опублікованій в ретроспективі на роботу Марека-Цургунівськи.

Мова програмування наборів відповідей AnsProlog

Lparse — це назва програми, яка спочатку була створена в якості інструменту заземлення для наборів вирішувачів smodels. Мова, яку приймає Lparse, називається AnsProlog.^[5] На сьогодні, вона використовується так само, і в багатьох інших вирішувачах, таких, як assat, clasp, cmodels, gNt, nomore++ і pbmodels.

Програма на AnsProlog складається з правил:

<head> :- <body> .

Символ :- («if») видаляється, якщо <body> порожній; такі правила називають фактами. Найпростіший вид правил Lparse є правила з обмеженнями. Ще однією корисною конструкцією цієї мови є вибір. Наприклад, правило

{p,q,r}.

каже: вибрати довільно, який з атомів включити до стабільної моделі. У lparse програмі, яка містить це правило вибору і більше ніяких інших правил, є 8 стабільних моделей— довільних підмножин. Визначення стабільних моделей було узагальнено до програм з вибором правил.^[6] Вибір правил може розглядатися також як абревіатура для пропозициональных формул при стійкій моделі семантики.^[7] Наприклад, правило вибір вище можна розглядати як скорочення для сукупності трьох формул «виключеного третього»:

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

Мова lparse дозволяє нам писати «обмеження» правил вибору, такі як

1{p,q,r}2.

Це правило говорить: вибрати принаймні 1 з атомів, але не більше 2. Сенс цього правила в рамках стійкої моделі семантики є пропозиційною формулою:

$(p\lor \thicksim p)\land (q\lor \thicksim q)\land (r\lor \thicksim r)\land (p\lor q\lor r)\land \thicksim (p\land q\land r)$

Границя потужності множини може бути використана в тілі правила, наприклад:

:- 2{p,q,r}.

Додавання цього обмеження в програму Lparse усуває стійкі моделі, які містять щонайменше 2 атоми. Сенс цього правила може бути представлений у вигляді пропозиційної формули

$\thicksim ((p\land q)\lor (p\land r)\lor (q\land r))$ .

Змінні (великі літери, як і в Пролозі), використовуються в Lparse для скорочування колекцій правил, які дотримуються тієї ж схеми, а також для скорочення колекцій атомів в одне і те ж правило. Наприклад, Lparse програма:

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 є {q(a1); q(a2); … ; q(aN)}, то вищевказана умова семантично еквівалентна запису: p(a1), p(a2), … , p(aN) на місці умови. Наприклад

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

Це скорочення для

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

Створення стійких моделей

Для знаходження стійкої моделі програми Лапласа, що зберігається у файлі ${filename} використовується команда:

% lparse ${filename} | smodels

Параметр 0 вказує smodels знайти всі стійкі моделі програми. Наприклад, якщо файл test містить правила:

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

тоді команда видасть:

% lparse test | smodels 0
Answer: 1
Stable Model: q p 
Answer: 2
Stable Model: p 
Answer: 3
Stable Model: r p 
Answer: 4
Stable Model: q s 
Answer: 5
Stable Model: r s 
Answer: 6
Stable Model: r q s

Приклади програм ASP

Фарбування графа

n-колір на графі $G=\left\langle V,E\right\rangle$ - це функція $color:V\to \{1,\dots ,n\}$ така, що $color(x)\neq color(y)$ для кожної пари суміжних вершин $(x,y)\in E$ . Ми хотіли б використовувати ASP щоб знайти $n$ -кольорів даного графа (або визначити, що його не існує).

Це можна зробити за допомогою наступної програми Lparse:

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,\dots ,n$ кольорів. В залежності від вибору правил у рядку 2, унікальний колір $i$ повиннен бути призначений для кожної вершини $x$ . Обмеження у рядку 3 забороняє призначати один і той же колір до вершини $x$ і $y$ якщо існує ребро, що з'єднує їх. Якщо поєднати цей файл з визначенням $G$ таким як

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

і запустити smodels на ньому, з числовим значенням $n$ зазначеним в командному рядку, тоді атоми форми $color(\dots ,\dots )$ у вихідних даних smodels будуть представляти собою $n$ -колір $G$ .

Програма в цьому прикладі ілюструє «generate-and-test» організацію, яка часто зустрічається в простих ASP програмах. Правило вибір описує набір «потенційних рішень». Потім слідує обмеження, яке виключає всі можливі рішення, які не прийнятні. Однак, сам процес пошуку, який вживає smodels і інші набори вирішувачів не основані на методі проб і помилок.

Велика кліка

Клікою в графі називають набір попарно суміжних вершин. Наступна lparse-програма знаходить кліку розміру $\geq n$ в даному графі, або визначає, що вона не існує:

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

Це ще один приклад generate-and-test organization. Вибір правил у рядку 1 «створює» всі набори, що складаються з вершин $\geq n$ . Обмеження у рядку 2 «відсіває» ті набори, які не є кліками.

Гамільтонів цикл

Гамільтонів цикл в орієнтованому графі є цикл, який проходить через кожну вершину графа рівно один раз. Наступна Lparse програма може бути використана для пошуку Гамільтонівського циклу в заданому орієнтованому графі, якщо він існує; ми припускаємо, що 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$ is reachable from 0»), щоб заборонити вершини, які не задовільняють цій умові. Цей предикат визначається рекурсивно в рядках 4 та 5.

Ця програма є прикладом більш загального «generate, define and test» організування, яке включає в себе визначення допоміжного предиката, який допомагає нам усунути все «погане» у потенційному рішені.

Синтаксичний аналіз

Обробка природної мови та синтаксичний аналіз можуть бути сформульовані як проблема ASP.^[8] Наступний код аналізує латинську фразу 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, _, _).

Порівняння реалізацій

Ранні системи, такі як Smodels, використовували пошук з поверненням, щоб знайти рішення. З розвитком теорії і практики Boolean SAT solvers, збільшувалася кількість ASP вирішувачів, спроектованих на основі SAT-вирішувачів включно з ASSAT та Cmodels. Вони перетворювали ASP формулу в SAT пропозицію, застосували SAT вирішувач, а потім перетворювали рішення назад до ASP форми. Більш сучасні системи, такі як Clasp, використовують гібридний підхід, використовуючи conflict-driven algorithms без повного перетворення в форму булевої логіки. Ці підходи дозволяють значно поліпшити продуктивність, часто на порядок кращі порівняно з попередніми алгоритмами з поверненням.

Проект Potassco являє собою «парасольку» для багатьох низькорівнених систем, в тому числі clasp, систему заземлення gringo, та інші.

Більшість систем підтримують змінні, та тільки опосередковано, шляхом примусового заземлення за допомогою заземлюючих систем, таких як Lparse чи gringo. Необхідність заземлення може призвести до комбінаторних вибухів; таким чином, системи які виконують заземлення на льоту мають перевагу.

Платформа			Риси					Механіка
Найменування	Операційна система	Ліцензія	Змінні	Функціональні символи	Явні набори	Явні списки	Правила вибору
ASPeRiX	Linux	GPL	Так				Ні	заземлення «на льоту»
ASSAT	Solaris	Безкоштовна						заснований на SAT-вирішувачі
Clasp Answer Set Solver	Linux, macOS, Windows	GPL	Так	Так	Ні	Ні	Так	інкрементний, надхненний Sat-вирішувачем
Cmodels	Linux, Solaris	GPL	Потребує заземлення				Так	інкрементний, надхненний Sat-вирішувачем
DLV	Linux, macOS, Windows^[9]	безкоштовна для академічного та некомерційного використання в освітніх цілях, а також для некомерційних організацій	Так	Так	Ні	Ні	Так	Не Lparse сумісний
DLV-Complex	Linux, macOS, Windows	GPL		Так	Так	Так	Так	побудований на верині DLV — не Lparse сумісний
GnT	Linux	GPL	Потребує заземлення				Так	побудований на вершині smodels
nomore++	Linux	GPL						комбінований
Platypus	Linux, Solaris, Windows	GPL						розподілений
Pbmodels	Linux	?						заснований на псевдобулевському вирішувачі
Smodels	Linux, macOS, Windows	GPL	Потребує заземлення	Ні	Ні	Ні	Ні
Smodels-cc	Linux	?	Потребує заземлення					заснований на SAT-вирішувачі
Sup	Linux	?						заснований на SAT-вирішувачі

Див. також

Посилання

↑ Baral, Chitta (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. ISBN 978-0-521-81802-5.
↑ Gelfond, Michael (2008). Answer sets. У van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce (ред.). Handbook of Knowledge Representation. Elsevier. с. 285—316. ISBN 978-0-08-055702-1.
↑ 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
↑ Victor W. Marek. Wikipedia (англ.). 13 грудня 2016. Процитовано 19 грудня 2016.
↑ (Дипломна робота). {{cite thesis}}: Пропущений або порожній |title= (довідка)
↑ Niemelä, I.; Simons, P.; Soinenen, T. (2000). Stable model semantics of weight constraint rules. У 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. {{cite book}}: |editor-first= з пропущеним |editor-last= (довідка)
↑ Ferraris, P.; Lifschitz, V. (January 2005). Weight constraints as nested expressions (PDF). Theory and Practice of Logic Programming. 5 (1-2): 45—74. doi:10.1017/S1471068403001923.
↑ Dependency parsing
↑ DLV System company page. DLVSYSTEM s.r.l. Процитовано 16 November 2011.

[1] Baral, Chitta (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. ISBN 978-0-521-81802-5.

[2] Gelfond, Michael (2008). Answer sets. У van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce (ред.). Handbook of Knowledge Representation. Elsevier. с. 285—316. ISBN 978-0-08-055702-1.

[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] Victor W. Marek. Wikipedia (англ.). 13 грудня 2016. Процитовано 19 грудня 2016.

[5] (Дипломна робота). {{cite thesis}}: Пропущений або порожній |title= (довідка)

[6] Niemelä, I.; Simons, P.; Soinenen, T. (2000). Stable model semantics of weight constraint rules. У 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. {{cite book}}: |editor-first= з пропущеним |editor-last= (довідка)

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

[8] Dependency parsing

[dlvsystem.com-9] DLV System company page. DLVSYSTEM s.r.l. Процитовано 16 November 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Рядок 6: / Рядок 6: @@
 == Історія ==
-{{Нп|Автоматизована система планування і складання розкладів|Планувальний||Automated planning and scheduling}} метод, запропонований в 1993 році [[Янісом Дімопулосом]], [[Бернардом Небелем]]<ref>{{Cite news|url=https://en.wikipedia.org/w/index.php?title=Bernhard_Nebel&oldid=747127750|title=Bernhard Nebel|date=2016-10-31|language=en|work=Wikipedia|accessdate=2016-12-19}}</ref> і [[Джонатаном Кехлерем|Джонатаном Кехлером]] є раннім прикладом програмування наборами відповідей. Їх підхід заснований на взаємозв'язку проекту зі стійкою моделлю. Т.Шойнен та І.Німель застосували те, що зараз відомо як ''програмування наборами відповідей'' для розв'язання задачі конфігурації продукту. Використання наборів вирішувачів для пошуку був визначений в якості нової парадигми програмування  [[В.Мареком|Віктором Мареком]]<ref>{{Cite news|url=https://en.wikipedia.org/w/index.php?title=Victor_W._Marek&oldid=754625380|title=Victor W. Marek|date=2016-12-13|language=en|work=Wikipedia|accessdate=2016-12-19}}</ref> і [[Мар'яном Цургувінськи]] в документі, опублікованому в 1999 році. Дійсно, в новій термінології «набір відповідей», замість «стабільної моделі», був вперше запропонований Ліфшицем, у статті, опублікованій в ретроспективі на роботу Марека-Цургунівськи.
+{{Нп|Автоматизована система планування і складання розкладів|Планувальний||Automated planning and scheduling}} метод, запропонований в 1993 році Янісом Дімопулосом, Бернардом Небелем<ref>
+{{cite book |first1=Y. |last1=Dimopoulos |author2link=Bernhard Nebel |first2=B. |last2=Nebel |first3=J. |last3=Köhler |chapter=Encoding planning problems in non-monotonic logic programs |pages=273–285 |editor1-first=Sam |editor1-last=Steel |editor2-first=Rachid |editor2-last=Alami |title=Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings |url=https://books.google.com/books?id=QSBoQgAACAAJ |year=1997 |publisher=Springer |isbn=978-3-540-63912-1 |volume=1348 |series=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> і [[Джонатаном Кехлерем|Джонатаном Кехлером]] є раннім прикладом програмування наборами відповідей. Їх підхід заснований на взаємозв'язку проекту зі стійкою моделлю. Т.Шойнен та І.Німель застосували те, що зараз відомо як ''програмування наборами відповідей'' для розв'язання задачі конфігурації продукту. Використання наборів вирішувачів для пошуку був визначений в якості нової парадигми програмування  [[В.Мареком|Віктором Мареком]]<ref>{{Cite news|url=https://en.wikipedia.org/w/index.php?title=Victor_W._Marek&oldid=754625380|title=Victor W. Marek|date=2016-12-13|language=en|work=Wikipedia|accessdate=2016-12-19}}</ref> і [[Мар'яном Цургувінськи]] в документі, опублікованому в 1999 році. Дійсно, в новій термінології «набір відповідей», замість «стабільної моделі», був вперше запропонований Ліфшицем, у статті, опублікованій в ретроспективі на роботу Марека-Цургунівськи.
 == Мова програмування наборів відповідей AnsProlog ==

Програмування наборами відповідей: відмінності між версіями

Версія за 15:47, 21 грудня 2016

Зміст

Історія

Мова програмування наборів відповідей AnsProlog

Створення стійких моделей

Приклади програм ASP

Фарбування графа

Велика кліка

Гамільтонів цикл

Синтаксичний аналіз

Порівняння реалізацій

Див. також

Посилання

Навігаційне меню

Програмування наборами відповідей: відмінності між версіями

Версія за 15:47, 21 грудня 2016

Історія

Мова програмування наборів відповідей AnsProlog

Створення стійких моделей

Приклади програм ASP

Фарбування графа

Велика кліка

Гамільтонів цикл

Синтаксичний аналіз

Порівняння реалізацій

Див. також

Посилання

Навігаційне меню

Пошук