DPLL-Алгоритм
Sign in to saveAlso known as Davis-Putnam-Logemann-Loveland algorithm
algorithm for solving the CNF-SAT problem
Wikidata facts
- Image
- Backtracking-no-backjumping.svg
Show 2 more facts
- inception
- 1962-00-00
- Commons category
- Davis-Putnam-Logemann-Loveland algorithm
Sources (3)
via Wikidata · CC0
Article · Русский
DPLL (алгоритм Дэвиса — Патнема — Логемана — Лавленда) — полный алгоритм поиска с возвратом для решения задачи CNF-SAT — определения выполнимости булевых формул, записанных в конъюнктивной нормальной форме. Опубликован в 1962 году Мартином Дэвисом, Хилари Патнэмом, и как усовершенствование более раннего алгоритма Дэвиса — Патнема, основанного на правиле резолюций. Является высокоэффективным алгоритмом и спустя полвека сохраняет актуальность и используется в большинстве решателей для SAT и системах автоматического доказательства для фрагментов логики первого порядка.
Abstract from DBpedia / Wikipedia · CC BY-SA
Connections
logic
Entity
computer science
Entity
International Standard Book Number
Entity
theory
Entity
digital object identifier
Entity
International Standard Serial Number
Entity
propositional calculus
Entity
Hilary Putnam
Entity
binary tree
Entity
computational complexity theory
Entity
Q22908627
Entity
first-order logic
Entity
search algorithm
Entity
truth value
Entity
NP-complete
Entity
time complexity
Entity
backtracking
Entity
Handle System
Entity
boolean satisfiability problem
Entity
conjunctive normal form
Entity