МИНОБРНАУКИ РОССИИ
–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)
––––––––––––––––––––––––––––––––––––––––––
С. А. БЕЛЯЕВ С. В. РОДИОНОВ
ПРОГРАММИРОВАНИЕ НАБОРОВ ОТВЕТОВ
Учебно-методическое пособие
Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ»
2020
УДК 004.432(07) + 510.755(07) ББК З 973.2–018я7 + В 12я7
Б44
Беляев С. А., Родионов С. В.
Б44 Программирование наборов ответов: учеб.-метод. пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2020. 32 с.
ISBN 978-5-7629-2660-7
Представлены материалы по дисциплине «Логическое программирование» по программированию наборов ответов (answer set programming – ASP). Рассматриваются особенности языка программирования и вопросы разработки текста программ и формирования на их основе стабильных моделей из правил и фактов, решающих поставленную задачу. Рассматриваются варианты решения нескольких NP-полных задач. Приводятся основы программирования наборов ответов с использованием ограничений. Описываются механизмы вывода и доказательства, используемые в ASP.
Предназначено для студентов, обучающихся по направлениям «Программная инженерия» и «Прикладная математика и информатика».
УДК 004.432(07) + 510.755(07) ББК З 973.2–018я7 + В 12я7
Рецензент – д-р техн. наук, ведущий специалист Ю. В. Миронов (АО«НИЦСПбЭТУ»).
Утверждено редакционно-издательским советом университета
в качестве учебно-методического пособия
ISBN 978-5-7629-2660-7 |
© СПбГЭТУ «ЛЭТИ», 2020 |
ВВЕДЕНИЕ
Программирование наборов ответов (англ. answer set programming, ASP) – парадигма декларативного программирования, ориентированная на сложные (в основном NP-сложные) задачи поиска. Используется для разработки автономных программных агентов, программирования роботов, формирования расписаний и пр. ASP поддерживает интеграцию с Python, C++, Prolog и др.
Программа на языке ASP основана на семантике логического программирования, анализирует проблему как набор фактов, описывает её с использованием правил и формирует решение в виде стабильной модели (набора ответов). Среда ASP компилирует проблему в виде логической программы и в процессе формирования стабильной модели многократно изменяет получившуюся логическую программу.
В данной работе рассматривается «Potsdam Answer Set Solving Collection» (Potassco) [1] – реализация инструментов ASP в виде программы clingo, включающей в себя граундер gringo [2] и решатель clasp. Программа clingcon будет использоваться для программирования наборов ответов с использованием целочисленных ограничений.
Загрузка и установка
Программы gringo, clasp и clingo производства Potassco разработаны на C++, опубликованы с лицензией MIT и доступны для скачивания на сайте https://potassco.org. Нами использована программа clingo, версия 5.3.0, опубликованная по адресу https://github.com/potassco/clingo/releases.
Доступны реализации для операционных систем Windows, Linux и MacOS. Реализации представлены в виде архивов, после скачивания архивы следует распаковать. Для пробного знакомства и решения небольших задач может использоваться web-версия программы по адресу:
http://potassco.sourceforge.net/clingo.html.
Проверка версии может быть выполнена командой: clingo –version Получение справки по использованию: clingo --help
Также использована программа clingcon, версия 3.3.0, опубликованная по адресу:
https://github.com/potassco/clingcon/releases.
3
1. Язык программирования ASP 1.1. Термы
Логические программы используют термы. В качестве простых термов выступают числа, константы, строки и переменные (в том числе символ «_»). Константы состоят из латинских букв, цифр и символа «_» и могут начинаться только с маленькой латинской буквы или символа «_», за которым обязательно следует маленькая латинская буква (например, const, cOn_St, - c24). Строки записываются в двойных кавычках ("string"). Переменные состоят из латинских букв, цифр и символа «_» и могут начинаться только с большой латинской буквы или символа «_», за которым обязательно следует большая латинская буква (например, V, Variable, _Variable, VaR24). Отдельный символ «_» называется неименованной переменной и обладает дополнительными свойствами.
В качестве составных термов выступают функции и кортежи. Функции имеют имя-константу, за которым в круглых скобках через запятую перечисляются один или более термов (например, time(12, 24, am), d(3), line(point(0,0), point(2, 4)). Кортежи, в отличие от функций, не имеют имени – только скобки, в которых через запятую перечислены один или более термов (например, (abc, 12)).
1.2. Построение простой программы
Программа на языке ASP включает в себя факты, правила и исключения
(ограничения целостности). |
|
|
Факт: |
A. |
|
Правило: |
A :- L1, …, Ln. |
|
Ограничения целостности: |
:- |
L1, …, Ln. |
В качестве «головы» А могут выступать атомы в виде константы или функции. В качестве «тела» правила или ограничения целостности выступают литералы Lj (1 ≤ j ≤ n) вида A или not A, где A – атом, а not обозначает отрицание. Будем называть литерал L позитивным, если он атом A, и негативным, если он атом с отрицанием not A.
Голова факта А должна быть всегда истинна. Если все позитивные литералы в теле правила истинны, а все негативные литералы удовлетворены, то-
4
гда голова А правила истинна. Ограничения целостности при этом выступают в роли фильтра, не должна сложиться ситуация, при которой тело ограничения целостности истинно.
Набор атомов фактов и «голов» каждого правила называется моделью логической программы, если удовлетворены все правила, факты и ограничения целостности с использованием ациклического вывода. Атомы считаются истинными тогда и только тогда, когда они входят в модель. В ASP такой набор атомов называется набором ответов (англ. answer set).
Рассмотрим программу.
a:- b.
b:- a.
Если a и b ложны, то ложны тела обоих правил и ложны их головы. Соответственно, программа истинна при пустом наборе ответов. Если a и b истинны, то тела обоих правил истинны, и истинны головы, но в данном случае нет ациклического вывода результата. Ситуации, когда истинно a, а b ложно или истинно b, а a ложно приводят к противоречию. Вывод: у представленной программы ровно один набор ответов – пустой. Ответ clingo:
Answer: 1
SATISFIABLE
Другая ситуация возникает в следующей программе.
a:- not b.
b:- not a.
В данном случае в набор ответов входит либо a, либо b, пустой набор ответов некорректен, набор ответов, включающий a и b, – некорректен. От-
вет clingo (пример запуска: clingo.exe 0 ab_program.lp):
Answer: 1 b
Answer: 2 a
SATISFIABLE
В дальнейших примерах надпись «SATISFIABLE» приводиться не будет. Рассмотрим программу с фактом, правилами и ограничением целостности.
a:- not b.
b:- not a.
:- c, not b.
5