Библиотека, читать онлайн, скачать книги txt

БОЛЬШАЯ БИБЛИОТЕКА

МЕЧТА ЛЮБОГО


Схема анализа конфликта

Алгоритм CDCL conflict-driven clause learning — «управляемое конфликтами обучение дизъюнктам» — основанный на эффективный решатель SAT-решатель. Основная структура данных в CDCL-решателях — импликационный граф, фиксирующий назначения переменным, а другой особенностью является использование нехронологического возврата и запоминание в ходе анализа конфликта. Алгоритм был предложен и Karem Sakallah в 1996 году и независимо Roberto Bayardo и Robert Schrag в 1997 году. В случае, когда встречается конфликт, то есть, полученная формула является невыполнимой, включается механизм возврата бэктрекингапри котором отменяются ветвления, в которых для переменной были опробованы оба значения. Если поиск возвращается к ветвлению первого уровня, вся формула объявляется невыполнимой. Такой возврат, свойственный алгоритму DPLL, называется хронологическим. Одной из важнейших составляющих SAT-решателей является правило единичного дизъюнкта, при котором выбор переменной и её значения однозначен. Следует напомнить, что в дизъюнкт входят как переменные, так и. В дополнение к DPLL и его механизму поиска с возвратом, CDCL использует некоторые другие приёмы : запоминание новых дизъюнктов в ходе поиска с возвратом. Для ещё неназначенных переменных и переменных, по которым было принято решение, имеет значение None. NotAllVariablesAssigned проверяет, есть ли ещё неназначенные переменные. PickBranchingVariable выбирает переменную и назначаемое значение 1 или 0. ConflictAnalysis анализирует возникший конфликт, запоминает новый дизъюнкт и даёт уровень решения, к которому необходимо вернуться. Backtrack производит возврат к уровню, вычисленному в ходе анализа конфликта. Процедура анализа конфликта является центральной для CDCL алгоритма. Основной структурой данных, используемой в CDCL-решателях, является импликационный граф implication graphфиксирующий назначения переменным как в результате решений, так и применением правила единичного дизъюнктав котором вершины соответствуют литералам формулы, а дуги фиксируют структуру импликаций. Процедура начинает с узла импликационного графа, в котором обнаружен конфликт, и охватывает уровни решения с меньшими номерами, переходя назад по импликациям пока не встречает самую свежую назначенную в результате решения переменную. Запомненные дизъюнкты применяются в нехронологическом возврате non-chronological backtracking — ещё одном характерном для CDCL-решателей приёме. Для сравнения: CDCL: запоминание дизъюнктов в результате анализа конфликтов и нехронологический возврат Идея использования структуры импликаций, приведших к конфликту, была развита в сторону применения UIP Unit Implication Points — «точки единичной импликации». UIP — это импликационного графа, который у этого вида графа можно вычислить за линейное время. UIP представляет собой альтернативный вариант назначения переменных и дизъюнкт, запомненный в первой такой точке, гарантированно имеет наименьший размер и обеспечивает наибольшее уменьшение уровня решения. В связи с применением эффективных ленивых структур данных, авторы многих SAT-решателей, например, Chaff, применяют метод первого UIP для запоминания дизъюнктов first UIP clause learning. Так, запоминание дизъюнктов не влияет на полноту и корректность, так как каждый запомненный дизъюнкт может быть выведен из начальных дизъюнктов и других запомненных дизъюнктов. Изменённый механизм возврата также не влияет на полноту и корректность, так как информация о возврате сохраняется в запомненном дизъюнкте. Серый кружок — принудительное назначение. Получаемый граф и есть импликационный граф. GRASP: A new search algorithm for satisfiability. In International Conference on Computer-Aided Design, pages 220—227, November 1996. Using CSP look-back techniques to solve real-world SAT instances. Madigan; Ying Zhao; Lintao Zhang; Sharad Malik 2001. Annual ACM IEEE Design Automation Conference: 530-535. Combinatorial Search: From Algorithms to Systems. Audemard, Gilles; Bordeaux, Lucas; Hamadi, Youssef; Jabbour, Saïd; Sais, Lakhdar 2008. Theory and Applications of Satisfiability Testing. Последнее изменение этой страницы: 18:04, 16 декабря 2015. Текст доступен по ; в отдельных случаях могут действовать дополнительные условия. Wikipedia® — зарегистрированный товарный знак некоммерческой организации.



copyright © e-lx.net