Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с Active Server Pages .
Парадигмы программирования
  • v
  • т
  • е

Программирование набора ответов ( ASP ) - это форма декларативного программирования, ориентированная на сложные (в первую очередь NP-трудные ) задачи поиска . Он основан на семантике стабильной модели (набора ответов) логического программирования . В ASP задачи поиска сводятся к вычислению стабильных моделей, а решатели наборов ответов - программы для создания стабильных моделей - используются для выполнения поиска. Вычислительный процесс, используемый при разработке многих решателей наборов ответов, является усовершенствованием алгоритма DPLL и, в принципе, всегда завершается (в отличие от оценки запроса Prolog , которая может привести к бесконечному циклу).).

В более общем смысле ASP включает все приложения наборов ответов для представления знаний [1] [2] и использование оценки запросов в стиле Пролога для решения проблем, возникающих в этих приложениях.

История [ править ]

Метод планирования, предложенный в 1993 г. Димопулосом, Небелем и Кёлером [3], является ранним примером программирования набора ответов. Их подход основан на соотношении планов и стабильных моделей. [4] Сойнинен и Ниемеля [5] применили то, что сейчас известно как программирование набора ответов, к проблеме конфигурации продукта. Использование решателей наборов ответов для поиска было определено как новая парадигма программирования Мареком и Трушчински в статье, появившейся в 25-летней перспективе парадигмы логического программирования, опубликованной в 1999 г. [6] и в [Niemelä 1999]. [7] Действительно, новая терминология «множество ответов» вместо «стабильной модели» была впервые предложена Лифшицем [8] в статье, вышедшей в том же ретроспективном томе, что и статья Марека-Трущинского.

Набор ответов язык программирования AnsProlog [ править ]

Lparse - это имя программы, которая изначально была создана как инструмент заземления (интерфейс) для смоделей решателя наборов ответов . Язык, который принимает Lparse, теперь обычно называется AnsProlog *, [9] сокращение от Answer Set Programming in Logic . [10] В настоящее время используется таким же образом , и во многих другом наборе ответов решателей, включая Assat , застежку , cmodels , GNT , NOMORE ++ и pbmodels . ( dlv является исключением; синтаксис программ ASP, написанных для dlv, несколько отличается.)

Программа AnsProlog состоит из правил вида

< голова >  : -  < тело >  .

Символ :-(«если») отбрасывается, если <body>он пуст; такие правила называются фактами . Самый простой вид правил Lparse - это правила с ограничениями .

Еще одна полезная конструкция, включенная в этот язык, - это выбор . Например, правило выбора

{ p , q , r }.

говорит: выберите произвольно, какой из атомов включить в стабильную модель. Программа lparse, которая содержит это правило выбора и никаких других правил, имеет 8 стабильных моделей - произвольных подмножеств . Определение стабильной модели было обобщено на программы с правилами выбора. [11] Правила выбора можно рассматривать также как аббревиатуры пропозициональных формул в рамках семантики стабильной модели . [12] Например, приведенное выше правило выбора можно рассматривать как сокращение для объединения трех формул « исключенного среднего »:

Язык lparse позволяет нам также писать "ограниченные" правила выбора, такие как

1 { p , q , r } 2.

Это правило гласит: выберите хотя бы 1 из атомов , но не более 2. Смысл этого правила в семантике стабильной модели представлен пропозициональной формулой

Границы мощности также могут использоваться в теле правила, например:

: -  2 { p , q , r }.

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

Переменные (с заглавной буквы, как в Прологе ) используются в Lparse для сокращения наборов правил, которые следуют одному и тому же шаблону, а также для сокращения наборов атомов в одном правиле. Например, программа Lparse

р ( а ).  р ( б ).  p ( c ). д ( Х )  : -  р ( Х ),  Х ! = а .

имеет то же значение, что и

р ( а ).  р ( б ).  p ( c ). q ( б ).  q ( c ).

Программа

р ( а ).  р ( б ).  p ( c ). { q ( X ): - p ( X )} 2.

сокращение для

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

Диапазон имеет вид:

( начало .. конец )

где начало и конец - арифметические выражения с постоянным значением. Диапазон - это сокращенное обозначение, которое в основном используется для определения числовых доменов совместимым способом. Например, факт

а ( 1..3 ).

это ярлык для

а ( 1 ).  а ( 2 ).  а ( 3 ).

Диапазоны также могут использоваться в телах правил с той же семантикой.

Условно буквальным имеет вид:

р ( Х ) : д ( Х )

Если расширение q есть {q (a1); q (a2); ...; q (aN)}, указанное выше условие семантически эквивалентно записи p (a1), p (a2), ..., p (aN) вместо условия. Например,

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

это сокращение для

q ( 1 ).  q ( 2 ). а  : -  1  { р ( 1 ),  р ( 2 )}.

Создание стабильных моделей [ править ]

Чтобы найти стабильную модель программы Lparse, хранящуюся в файле, ${filename}мы используем команду

% lparse $ { filename }  | смодели

Вариант 0 дает команду смоделам найти все стабильные модели программы. Например, если файл testсодержит правила

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

тогда команда производит вывод

% lparse test  | smodels 0 Ответ: 1 Стабильная модель: qp Ответ: 2 Стабильная модель: p Ответ: 3 Стабильная модель: rp Ответ: 4 Стабильная модель: qs Ответ: 5 Стабильная модель: RS Ответ: 6 Стабильная модель: rqs

Примеры программ ASP [ править ]

Раскраска графика [ править ]

- раскраска из графа является функцией таким образом, что для каждой пары смежных вершин . Мы хотели бы использовать ASP для поиска раскраски данного графа (или определения того, что он не существует).

Это можно сделать с помощью следующей программы Lparse:

c ( 1 .. n ).  1  { цвет ( X , I )  :  c ( I )}  1  : -  v ( X ).  : -  цвет ( X , I ),  цвет ( Y , I ),  e ( X , Y ),  c ( I ).

Строка 1 определяет числа как цвета. Согласно правилу выбора в строке 2, каждой вершине должен быть присвоен уникальный цвет . Ограничение в строке 3 запрещает назначать один и тот же цвет вершинам и при наличии ребра, соединяющего их.

Если мы объединим этот файл с определением , например,

v ( 1..100 ).  % 1, ..., 100 - вершины e ( 1 , 55 ).  % есть преимущество от 1 до 55 .  .  .

и запустите на нем смодели с числовым значением, указанным в командной строке, тогда атомы формы в выводе смоделей будут представлять собой раскраску .

Программа в этом примере иллюстрирует организацию «генерации и тестирования», которая часто встречается в простых программах ASP. Правило выбора описывает набор «потенциальных решений» - простое надмножество множества решений данной поисковой задачи. За ним следует ограничение, которое устраняет все возможные решения, которые не являются приемлемыми. Однако процесс поиска, используемый смодлами и другими решателями наборов ответов, не основан на методе проб и ошибок .

Большая клика [ править ]

Клика в графе представляет собой набор попарно смежных вершин. Следующая программа lparse находит клику размера в заданном графе или определяет, что она не существует:

n  { in ( X )  :  v ( X )}. : -  в ( X ),  в ( Y ),  v ( X ),  v ( Y ),  X ! = Y , а  не  e ( X , Y ),  не  e ( Y , X ).

Это еще один пример организации «генерировать и тестировать». Правило выбора в строке 1 «генерирует» все множества, состоящие из вершин. Ограничение в строке 2 «отсеивает» множества, не являющиеся кликами.

Гамильтонов цикл [ править ]

Гамильтонов цикл в ориентированном графе представляет собой цикл , который проходит через каждую вершину графа ровно один раз. Следующая программа Lparse может использоваться для поиска гамильтонова цикла в заданном ориентированном графе, если он существует; мы предполагаем, что 0 - одна из вершин.

{ in ( X , Y )}  : -  e ( X , Y ).: -  2  { в ( X , Y )  :  e ( X , Y )},  v ( X ). : -  2  { в ( X , Y )  :  e ( X , Y )},  v ( Y ).r ( X )  : -  в ( 0 , X ),  v ( X ). r ( Y )  : -  r ( X ),  в ( X , Y ),  e ( X , Y ).: -  не  r ( X ),  v ( X ).

Правило выбора в строке 1 «генерирует» все подмножества множества ребер. Эти три ограничения «отсеивают» подмножества, не являющиеся гамильтоновыми циклами. Последний из них использует вспомогательный предикат (« достижимо из 0») для запрета вершин, не удовлетворяющих этому условию. Этот предикат рекурсивно определяется в строках 4 и 5.

Эта программа является примером более общей организации «генерировать, определять и тестировать»: она включает определение вспомогательного предиката, который помогает нам исключить все «плохие» потенциальные решения.

Разбор зависимостей [ править ]

В обработке естественного языка , синтаксический анализ зависимостей на основе может быть сформулирован как проблема ASP. [13] Следующий код анализирует латинское предложение «Puella pulchra in villa linguam latinam discit», «красивая девушка изучает латынь на вилле». Синтаксическое дерево выражается предикатами arc, которые представляют зависимости между словами предложения. Вычисляемая структура представляет собой линейно упорядоченное корневое дерево.

% ********** вводное предложение ********** word ( 1 ,  puella ).  слово ( 2 ,  pulchra ).  слово ( 3 ,  дюйм ).  слово ( 4 ,  вилла ).  слово ( 5 ,  лингвам ).  слово ( 6 ,  латынь ).  слово ( 7 ,  дискит ). % ********** лексикон ********** 1 {  узел ( X ,  attr( pulcher ,  a ,  fem ,  nom ,  sg ));  node ( X ,  attr ( pulcher ,  a ,  fem ,  abl ,  sg ))  } 1  : -  слово ( X ,  pulchra ). node ( X ,  attr ( latinus ,  a ,  fem ,  acc ,  sg ))  : -  слово ( X,  латыни ). 1 {  узел ( X ,  attr ( puella ,  n ,  fem ,  nom ,  sg ));  node ( X ,  attr ( puella ,  n ,  fem ,  abl ,  sg ))  } 1  : -  слово ( X ,  puella ). 1 {  узел ( X ,  attr ( вилла ,  n,  fem ,  nom ,  sg ));  node ( X ,  attr ( вилла ,  n ,  fem ,  abl ,  sg ))  } 1  : -  слово ( X ,  вилла ). node ( X ,  attr ( linguam ,  n ,  fem ,  acc ,  sg ))  : -  слово ( X ,  linguam ). узел( X ,  attr ( discere ,  v ,  pres ,  3 ,  sg ))  : -  слово ( X ,  discit ). node ( X ,  attr ( in ,  p ))  : -  слово ( X ,  in ). % ********** синтаксические правила ********** 0 {  arc ( X ,  Y ,  subj )  } 1  : -  node (X ,  attr ( _ ,  v ,  _ ,  3 ,  sg )),  узел ( Y ,  attr ( _ ,  n ,  _ ,  nom ,  sg )). 0 {  arc ( X ,  Y ,  dobj )  } 1  : -  узел ( X ,  attr ( _ ,  v ,  _ ,  3 ,  sg )), узел ( Y ,  attr ( _ ,  n ,  _ ,  acc ,  sg )). 0 {  arc ( X ,  Y ,  attr )  } 1  : -  узел ( X ,  attr ( _ ,  n ,  Gender ,  Case ,  Number )),  node ( Y ,  attr ( _ ,  a ,  Gender , Корпус ,  номер )). 0 {  arc ( X ,  Y ,  prepare )  } 1  : -  узел ( X ,  attr ( _ ,  p )),  node ( Y ,  attr ( _ ,  n ,  _ ,  abl ,  _ )),  X  <  Y . 0 {  arc ( X ,  Y ,  adv )  }1  : -  узел ( X ,  attr ( _ ,  v ,  _ ,  _ ,  _ )),  узел ( Y ,  attr ( _ ,  p )), а  не  лист ( Y ). % **********, гарантирующий чистоту графа ********** 1 {  root ( X ) : node ( X ,  _ )  } 1 .: -  arc ( X , Z ,  _ ),  дуга ( Y ,  Z ,  _ ),  X  ! =  Y . : -  arc ( X ,  Y ,  L1 ),  arc ( X ,  Y ,  L2 ),  L1  ! =  L2 . путь ( X ,  Y )  : -  arc ( X ,  Y ,  _ ). путь ( X ,  Z)  : -  дуга ( X ,  Y ,  _ ),  путь ( Y ,  Z ). : -  путь ( X ,  X ). : -  корень ( X ),  узел ( Y ,  _ ),  X  ! =  Y , а  не  путь ( X ,  Y ). лист ( X )  : -  узел ( X ,  _ ), а  не дуга ( X ,  _ ,  _ ).

Стандартизация языков и соревнование ASP [ править ]

Рабочая группа по стандартизации ASP разработала стандартную языковую спецификацию, названную ASP-Core-2 [14], к которой стремятся последние системы ASP. ASP-Core-2 - это эталонный язык для соревнований по программированию набора ответов, на котором решатели ASP периодически проверяются по ряду эталонных задач.

Сравнение реализаций [ править ]

Ранние системы, такие как Smodels, использовали откат для поиска решений. По мере развития теории и практики логических решателей SAT , ряд решателей ASP был построен на основе решателей SAT, включая ASSAT и Cmodels. Они преобразовали формулу ASP в предложения SAT, применили решатель SAT, а затем преобразовали решения обратно в форму ASP. Более современные системы, такие как Clasp, используют гибридный подход, используя алгоритмы, основанные на конфликтах, вдохновленные SAT, без полного преобразования в форму логической логики. Эти подходы позволяют значительно улучшить производительность, часто на порядок, по сравнению с более ранними алгоритмами поиска с возвратом.

Проект Potassco выступает в качестве зонтика для многих из перечисленных ниже систем, включая зажимы , системы заземления ( gringo ), инкрементные системы ( iclingo ), решатели ограничений ( clingcon ), язык действий для компиляторов ASP ( coala ), распределенные реализации MPI ( claspar ). , и много других.

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

Реализации программирования наборов ответов на основе запросов, такие как система Galliwasp, [15] s (ASP) [16] и s (CASP) [17], полностью избегают заземления за счет использования комбинации разрешения и коиндукции .



ПлатформаФункцииМеханика
ИмяОперационные системыЛицензияПеременныеФункциональные символыЯвные множестваЯвные спискиДизъюнктивная (правила выбора) поддержка
ASPeRiXLinuxGPLдаНетзаземление на лету
АССАТСолярисБесплатное ПОНа основе SAT-решателя
Решатель набора ответов застежкиLinux , macOS , WindowsЛицензия MITДа, в ClingoдаНетНетдаинкрементальный, вдохновленный SAT-решателем (неэффективный, управляемый конфликтами)
CmodelsLinux , SolarisGPLТребуется заземлениедаинкрементальный, вдохновленный SAT-решателем (неэффективный, управляемый конфликтами)
diff-SATLinux , macOS , Windows ( виртуальная машина Java )Лицензия MITТребуется заземлениедаВдохновленный SAT-решателем (нет, конфликтный). Поддерживает решение вероятностных задач и выборку наборов ответов
DLVLinux , macOS , Windows [18]бесплатно для академических и некоммерческих образовательных целей, а также для некоммерческих организаций [18]дадаНетНетдане совместим с Lparse
DLV-КомплексLinux , macOS , WindowsGPLдадададапостроен на основе DLV - несовместим с Lparse
GnTLinuxGPLТребуется заземлениедапостроен на смоделах
JekejekeLinux , macOS , Windows ( виртуальная машина Java )ПроприетарныйдададаВариант DPLL через безопасную прямую цепочку
nomore ++LinuxGPLкомбинированный литерал + основанный на правилах
УтконосLinux , Solaris , WindowsGPLраспределенный, многопоточный nomore ++, смодели
PbmodelsLinux?псевдобулевой решатель на основе
СмоделыLinux , macOS , WindowsGPLТребуется заземлениеНетНетНетНет
Смодельс-CCLinux?Требуется заземлениеНа базе SAT-решателя; смодели с оговорками о конфликте
Как делаLinux?На основе SAT-решателя

См. Также [ править ]

  • Логика по умолчанию
  • Логическое программирование
  • Немонотонная логика
  • Пролог
  • Семантика стабильной модели

Ссылки [ править ]

  1. ^ Baral, Читта (2003). Представление знаний, рассуждение и декларативное решение проблем . Издательство Кембриджского университета. ISBN 978-0-521-81802-5.
  2. ^ Гельфонд, Майкл (2008). «Наборы ответов» . В ван Хармелен, Франк; Лифшиц, Владимир; Портер, Брюс (ред.). Справочник по представлению знаний . Эльзевир. С. 285–316. ISBN 978-0-08-055702-1. как PDF, Архивировано 3 марта 2016 г. в Wayback Machine.
  3. ^ Dimopoulos, Y .; Небель, Б .; Кёлер, Дж. (1997). «Задачи планирования кодирования в немонотонных логических программах». «Сталь», Сэм; Алами, Рашид (ред.). Последние достижения в планировании искусственного интеллекта: 4-я Европейская конференция по планированию, ECP'97, Тулуза, Франция, 24–26 сентября 1997 г., Материалы . Конспект лекций по информатике: конспект лекций по искусственному интеллекту. 1348 . Springer. С. 273–285. ISBN 978-3-540-63912-1. как постскриптум
  4. ^ Subrahmanian, VS; Заниоло, К. (1995). «Связь стабильных моделей и областей планирования ИИ» . В Стерлинге, Леон (ред.). Логическое программирование: Материалы Двенадцатой Международной конференции по логическому программированию . MIT Press. С. 233–247. ISBN 978-0-262-69177-2. как постскриптум
  5. ^ Сойнинен, Т .; Ниемеля, И. (1998), Формализация знаний о конфигурации с помощью правил с выбором (Postscript) , Лаборатория науки обработки информации, Хельсинкский технологический университет
  6. ^ Марек, В .; Трушчинский, М. (1999). «Стабильные модели и альтернативная парадигма логического программирования». В Apt, Кшиштоф Р. (ред.). Парадигма логического программирования: 25-летняя перспектива (PDF) . Springer. С. 169–181. arXiv : cs / 9809032 . ISBN  978-3-540-65463-6.
  7. ^ Niemelä, I. (1999). «Логические программы со стабильной семантикой модели как парадигма программирования с ограничениями» (Postscript, gzip) . Анналы математики и искусственного интеллекта . 25 (3/4): 241–273. DOI : 10,1023 / A: 1018930122475 .
  8. ^ Лифшиц, В. (1999). «Языки действий, наборы ответов и планирование». Cite journal requires |journal= (help)In Apt 1999 , стр. 357–374.
  9. ^ Крик, Том (2009). Супероптимизация: создание оптимального кода с использованием программирования набора ответов (PDF) (доктор философии). Университет Бата. Документ 20352. Архивировано из оригинального (PDF) 04 марта 2016 года . Проверено 27 мая 2011 .
  10. ↑ Рохелио Давила. «Анспролог, обзор» (PowerPoint) .
  11. ^ Niemelä, I .; Simons, P .; Сойненен, Т. (2000). «Стабильная модельная семантика правил весовых ограничений» . В Гельфонде, Михаил; Леоне, Николь; Пфайфер, Джеральд (ред.). Логическое программирование и немонотонное мышление: 5-я международная конференция, LPNMR '99, Эль-Пасо, Техас, США, 2–4 декабря 1999 г. Материалы . Конспект лекций по информатике: конспект лекций по искусственному интеллекту. 1730 . Springer. С. 317–331. ISBN 978-3-540-66749-0. как постскриптум
  12. ^ Ferraris, P .; Лифшиц, В. (январь 2005 г.). «Ограничения веса как вложенные выражения». Теория и практика логического программирования . 5 (1–2): 45–74. arXiv : cs / 0312045 . DOI : 10.1017 / S1471068403001923 . как постскриптум
  13. ^ "Анализ зависимостей" . Архивировано из оригинала на 2015-04-15 . Проверено 15 апреля 2015 .
  14. ^ «Спецификация языка ввода ASP-Core-2» (PDF) . Проверено 14 мая 2018 .
  15. ^ Марпл, Кайл .; Гупта, Гопал. (2012). "Galliwasp: Решающий набор ответов, ориентированный на цель". В Альберте, Эльвире (ред.). Синтез и преобразование программ на основе логики, 22-й Международный симпозиум, LOPSTR 2012, Лёвен, Бельгия, 18-20 сентября 2012 г., Пересмотренные избранные доклады . Springer. С. 122–136.
  16. ^ Марпл, К .; Salazar, E .; Гупта, Г. (2017). «Вычисление устойчивых моделей нормальных логических программ без заземления». CoRR . абс / 1709.00501. [1]
  17. ^ Ариас, Дж .; Карро, М .; Salazar, E .; Марпл, К .; Гупта, Г. (2018). «Программирование набора ответов по ограничению без заземления». Теория и практика логического программирования . 18 (3–4): 337–354.
  18. ^ a b "Страница компании DLV System" . DLVSYSTEM srl . Проверено 16 ноября 2011 года .

Внешние ссылки [ править ]

  • Спецификация языка ввода ASP-Core-2 2.03c
  • Первый конкурс систем ASP
  • Второй конкурс ASP
  • Третий конкурс ASP
  • Четвертый конкурс ASP
  • Утконос
  • Разнообразные решатели наборов ответов для Debian / Ubuntu
  • Решатель набора ответов застежки