DPLL

Материал из Википедии — свободной энциклопедии
(перенаправлено с «DPLL-алгоритм»)
Перейти к навигации Перейти к поиску

DPLL (алгоритм Дэвиса — Патнема — Логемана — Лавленда) — полный алгоритм поиска с возвратом для решения задачи CNF-SAT — определения выполнимости булевых формул, записанных в конъюнктивной нормальной форме.

Опубликован в 1962 году Мартином Дэвисом, Хилари Патнэмом, Джорджем Логеманом[англ.] и Дональдом Лавлендом[англ.] как усовершенствование более раннего алгоритма Дэвиса — Патнема, основанного на правиле резолюций.

Является высокоэффективным алгоритмом и спустя полвека сохраняет актуальность и используется в большинстве решателей для SAT и системах автоматического доказательства для фрагментов логики первого порядка[1].

Алгоритм поиска с возвратом.

Реализации и приложения

[править | править код]

Задача выполнимости булевых формул важна как с теоретической, так и с практической точек зрения. В теории сложности это первая задача, для которой было доказана принадлежность классу NP-полных задач. Также она может появляться в самых различных практических приложений, например проверка моделей, составление расписаний, диагностика.

Данное направление было и до сих пор является развивающейся областью исследований, ежегодно проводятся соревнования между различными решателями SAT[2]; современные реализации алгоритма DPLL, такие как Chaff[англ.], zChaff[3][4], GRASP и Minisat[5], занимают первые места на таких соревнованиях.

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

Описание алгоритма

[править | править код]

Основной алгоритм с возвратом начинается с выбора переменной, присвоения ей значения «истина», упрощения формулы и затем рекурсивным образом проверки упрощенной формулы на выполнимость; если она выполнима, то исходная формула тоже выполнима; иначе, процедура повторяется, но выбранной переменной задается значение «ложь». Этот подход называется «правилом разбиения», так как он разбивает задачу на две более простые подзадачи. Шаг упрощения заключается в том, что из формулы удаляются все дизъюнкты, которые становятся истинными после присвоения выбранной переменной значения «истина» и удаления из оставшихся дизъюнкт всех вхождений этой переменной, которые становятся ложными.

Алгоритм DPLL позволяет улучшить основной алгоритм с возвратом за счет использования следующих правил на каждом шаге:

Распространение переменной[англ.]
если дизъюнкта содержит ровно одну переменную, которой ещё не задали значение, эта дизъюнкта может принять значение «истина» только в случае присвоения переменной значения, которое сделает её истинной («истина», если переменная входит в дизъюнкту без отрицания, и «ложь», если переменная с отрицанием). Таким образом, не нужно делать выбор на данном шаге. На практике за этим следует каскад присвоений переменным значений, таким образом существенно сокращается количество вариантов перебора.
Исключение «чистых» переменных
если некоторая переменная входит в формулу только с одной «полярностью» (то есть либо только без отрицаний, либо только с отрицаниями), она называется чистой. «Чистым» переменным всегда можно задать значение так, что все содержащие их дизъюнкты станут истинными. Таким образом, эти дизъюнкты не будут влиять на пространство вариантов, и их можно удалить.

Невыполнимость при данных конкретных значениях переменных определяется, когда одна из дизъюнкт становится «пустой», то есть всем её переменным задаются значения таким образом, что их вхождения (с отрицанием или без него) становятся ложными. Выполнимость формулы констатируется или когда всем переменным заданы значения так, что не возникает «пустых» дизъюнкт, или, в современных реализациях, если все дизъюнкты равны истине. Невыполнимость всей формулы может быть установлена только после окончания исчерпывающего перебора.

Алгоритм DPLL может быть выражен с помощью следующего псевдокода, где знаком Φ обозначена формула в конъюнктивной нормальной форме:

  Входные данные: Набор дизъюнкт формулы Φ.
  Выходные данные: Значение истинности
function DPLL(Φ)
   если Φ - это набор выполняющихся дизъюнкт
       тогда return true;
   если Φ содержит пустую дизъюнкту
       then return false;
   для каждой дизъюнкты из одной переменной l в Φ
      Φ  unit-propagate(l, Φ);
   для каждой переменной l которая встречается в чистом виде в Φ
      Φ  pure-literal-assign(l, Φ);
   l  choose-literal(Φ);
   return DPLL(Φ&l) or DPLL(Φ&not(l));

В этом псевдокоде unit-propagate(l, Φ) и pure-literal-assign(l, Φ) — это функции, которые возвращают результат применения к переменной l и формуле Φ распространения переменной и правила исключения «чистой переменной» соответственно. Другими словами, они заменяют каждое вхождение переменной l значением «истина» и каждое вхождение переменной с отрицанием not l значением «ложь» в формуле Φ, а затем упрощают получившуюся формулу. Приведенный псевдокод возвращает только ответ — выполняет ли формулу последний из присвоенных наборов значений. В современных реализациях частичные выполняющие наборы тоже возвращаются в случае успеха.

Алгоритм зависит от выбора «переменной ветвления», то есть переменной, которая выбирается на очередном шаге алгоритма с возвратом. для присвоения ей определённого значения. Таким образом, это не один алгоритм, а целое семейство алгоритмов, по одному на каждый возможный способ выбора «переменных ветвления». Эффективность алгоритма сильно зависит от этого выбора: существуют примеры задач, время работы алгоритма для которых может быть константой или расти экспоненциально, в зависимости от выбора «переменных ветвления». Методы выбора представляют собой эвристические техники и называются также «эвристиками для ветвления» (branching heuristics)[6].

Современные исследования

[править | править код]

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

Более новый алгоритм — метод Сталмарка — известен с 1990 года. Также с 1986 года для решения задачи SAT используются диаграммы решений.

На основе DPLL-алгоритма в середине 1990-х был создан и стал широко применяться CDCL-алгоритм.

Примечания

[править | править код]
  1. Nieuwenhuis, Robert; Oliveras, Albert; Tinelly, Cesar (2004), "Abstract DPLL and Abstract DPLL Modulo Theories" (PDF), Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2004, Proceedings: 36—50, Архивировано (PDF) 17 ноября 2011, Дата обращения: 26 января 2012 {{citation}}: Неизвестный параметр |urltype= игнорируется (справка) Источник. Дата обращения: 26 января 2012. Архивировано 17 ноября 2011 года.
  2. The international SAT Competitions web page, sat! live, Архивировано 12 февраля 2005, Дата обращения: 26 января 2012 {{citation}}: Внешняя ссылка в |publisher= (справка) Источник. Дата обращения: 26 января 2012. Архивировано 12 февраля 2005 года.
  3. zChaff website, Архивировано 19 апреля 2017, Дата обращения: 26 января 2012 Источник. Дата обращения: 26 января 2012. Архивировано 19 апреля 2017 года.
  4. Chaff website, Архивировано 23 февраля 2020, Дата обращения: 26 января 2012 Источник. Дата обращения: 26 января 2012. Архивировано 23 февраля 2020 года.
  5. Minisat website. Архивировано 20 апреля 2012 года.
  6. Marques-silva, Joao. The impact of branching heuristics in propositional satisfiability algorithms (англ.) // In 9th Portuguese Conference on Artificial Intelligence (EPIA) : journal. — 1999. — doi:10.1.1.111.9184. Архивировано 14 апреля 2012 года.

Литература

[править | править код]