stringtranslate.com

алгоритм DPLL

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

Он был представлен в 1961 году Мартином Дэвисом , Джорджем Логеманом и Дональдом У. Лавлендом и является усовершенствованием более раннего алгоритма Дэвиса–Патнэма , который представляет собой процедуру на основе разрешения, разработанную Дэвисом и Хилари Патнэм в 1960 году. Особенно в старых публикациях алгоритм Дэвиса–Логемана–Лавленда часто называют «методом Дэвиса–Патнэма» или «алгоритмом DP». Другие распространенные названия, которые поддерживают различие, — это DLL и DPLL.

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

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

Таким образом, написание эффективных решателей SAT было темой исследований в течение многих лет. GRASP (1996-1999) был ранней реализацией с использованием DPLL. [1] На международных соревнованиях SAT реализации, основанные на DPLL, такие как zChaff [2] и MiniSat [3], заняли первые места в соревнованиях в 2004 и 2005 годах. [4]

Другим приложением, которое часто использует DPLL, является автоматизированное доказательство теорем или выполнимость теорий по модулю (SMT), представляющая собой задачу SAT, в которой пропозициональные переменные заменяются формулами другой математической теории .

Алгоритм

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

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

Распространение единиц
Если предложение является предложением единицы , т. е. оно содержит только один неназначенный литерал, это предложение может быть удовлетворено только путем назначения необходимого значения, чтобы сделать это литерал истинным. Таким образом, выбор не требуется. Распространение единиц состоит в удалении каждого предложения, содержащего литерал предложения единицы, и в отбрасывании дополнения литерала предложения единицы из каждого предложения, содержащего это дополнение. На практике это часто приводит к детерминированным каскадам единиц, таким образом избегая большой части наивного пространства поиска.
Чистое буквальное устранение
Если пропозициональная переменная встречается только с одной полярностью в формуле, она называется чистой . Чистый литерал всегда можно назначить таким образом, что все содержащие его предложения станут истинными. Таким образом, когда он назначается таким образом, эти предложения больше не ограничивают поиск и могут быть удалены.

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

Алгоритм DPLL можно обобщить в следующем псевдокоде, где Φ — формула CNF :

Алгоритм DPLL Входные данные: набор предложений Φ. Выходные данные: истинностное значение, указывающее, является ли Φ выполнимым.
функция  DPLL (Φ) // распространение единицы: в то время как в Φ есть единичное предложение { l }, делаем Φ ← единичное распространение ( l , Φ); // чисто буквальное исключение: в то время как существует литерал l , который встречается в чистом виде в Φ do Φ ← чистый-литерал-присвоить ( l , Φ); // условия остановки: если Φ пусто, то  вернуть true; если Φ содержит пустое предложение, то  вернуть false; // Процедура DPLL: l ← литерал выбора (Φ); вернуть  DPLL (Φ ∧ {l}) или  DPLL (Φ ∧ {¬l});

В этом псевдокоде unit-propagate(l, Φ)и pure-literal-assign(l, Φ)являются функциями, которые возвращают результат применения единичного распространения и правила чистого литерала соответственно к литералу lи формуле Φ. Другими словами, они заменяют каждое вхождение lна "true" и каждое вхождение not lна "false" в формуле Φи упрощают полученную формулу. Оператор orin в returnвыражении является оператором короткого замыкания . обозначает упрощенный результат замены "true" на in .Φ ∧ {l}lΦ

Алгоритм завершается в одном из двух случаев. Либо формула CNF Φпуста, т. е. не содержит ни одного предложения. Тогда она удовлетворяется любым присваиванием, поскольку все ее предложения являются пустословно истинными. В противном случае, когда формула содержит пустое предложение, предложение является пустословно ложным, поскольку дизъюнкция требует, чтобы хотя бы один член был истинным для того, чтобы весь набор был истинным. В этом случае существование такого предложения подразумевает, что формула (оцениваемая как конъюнкция всех предложений) не может быть оценена как истинная и должна быть невыполнимой.

Функция псевдокода DPLL возвращает только то, удовлетворяет ли окончательное присваивание формуле или нет. В реальной реализации частично удовлетворяющее присваивание обычно также возвращается в случае успеха; это можно вывести, отслеживая литералы ветвления и литеральные присваивания, сделанные во время распространения единиц и чистого устранения литералов.

Алгоритм Дэвиса–Логеманна–Лавленда зависит от выбора литерала ветвления , который является литералом, рассматриваемым на шаге возврата. В результате это не совсем алгоритм, а скорее семейство алгоритмов, по одному для каждого возможного способа выбора литерала ветвления. Эффективность сильно зависит от выбора литерала ветвления: существуют экземпляры, для которых время выполнения является постоянным или экспоненциальным в зависимости от выбора литералов ветвления. Такие функции выбора также называются эвристическими функциями или эвристиками ветвления. [5]

Визуализация

Этот алгоритм разработали Дэвис, Логеманн, Лавленд (1961). Некоторые свойства этого оригинального алгоритма:

Пример визуализации алгоритма DPLL с хронологическим возвратом:

Связанные алгоритмы

С 1986 года (упрощенно упорядоченные) бинарные диаграммы решений также использовались для решения SAT. [ необходима ссылка ]

В 1989-1990 годах был представлен и запатентован метод Столмарка для проверки формул. Он нашел некоторое применение в промышленных приложениях. [6]

DPLL был расширен для автоматизированного доказательства теорем для фрагментов логики первого порядка с помощью алгоритма DPLL(T) . [1]

В десятилетии 2010-2019 годов работа по улучшению алгоритма нашла лучшие политики для выбора литералов ветвления и новых структур данных, чтобы сделать алгоритм быстрее, особенно часть распространения единиц . Однако главным улучшением стал более мощный алгоритм, Conflict-Driven Clause Learning (CDCL), который похож на DPLL, но после достижения конфликта «изучает» первопричины (назначения переменным) конфликта и использует эту информацию для выполнения нехронологического возврата (также известного как backjumping ), чтобы избежать повторного достижения того же конфликта. Большинство современных решателей SAT основаны на фреймворке CDCL по состоянию на 2019 год. [7]

Отношение к другим понятиям

Запуски алгоритмов на основе DPLL на невыполнимых примерах соответствуют доказательствам опровержения разрешения дерева . [8]

Смотрите также

Ссылки

На Викискладе есть медиафайлы по теме «Алгоритм Дэвиса-Патнэма-Логемана-Лавленда» .

Общий

Специфический

  1. ^ ab Nieuwenhuis, Robert; Oliveras, Albert; Tinelli, Cesar (2004), «Абстрактные DPLL и абстрактные теории DPLL Modulo» (PDF) , Труды Международной конференции по логике для программирования, искусственного интеллекта и рассуждений , LPAR 2004 , стр. 36–50
  2. ^ Сайт zChaff
  3. ^ "Сайт Minisat".
  4. ^ Веб-страница международных соревнований SAT, sat! live
  5. ^ Маркес-Сильва, Жоао П. (1999). «Влияние эвристики ветвления на алгоритмы пропозициональной выполнимости». В Бараоне Педро; Альферес, Хосе Дж. (ред.). Прогресс в области искусственного интеллекта: 9-я португальская конференция по искусственному интеллекту, EPIA '99, Эвора, Португалия, 21–24 сентября 1999 г., материалы . ЛНКС . Том. 1695. стр. 62–63. дои : 10.1007/3-540-48159-1_5. ISBN 978-3-540-66548-9.
  6. ^ Стольмарк, Г.; Сэфлунд, М. (октябрь 1990 г.). «Моделирование и проверка систем и программного обеспечения в пропозициональной логике». Труды IFAC, тома . 23 (6): 31–36. doi :10.1016/S1474-6670(17)52173-4.
  7. ^ Möhle, Sibylle; Biere, Armin (2019). "Обратный откат". Теория и применение тестирования выполнимости – SAT 2019 (PDF) . Конспект лекций по информатике. Том 11628. С. 250–266. doi :10.1007/978-3-030-24258-9_18. ISBN 978-3-030-24257-2. S2CID  195755607.
  8. ^ Ван Бик, Питер (2006). "Алгоритмы поиска с возвратом". В Росси, Франческа; Ван Бик, Питер; Уолш, Тоби (ред.). Справочник по программированию ограничений . Elsevier. стр. 122. ISBN 978-0-444-52726-4.

Дальнейшее чтение