<<
>>

Задачи соблюдения ограничений

Наконец, в этой главе рассматривались основные задачи соблюдения ограничений, включая задачу выполнимости булевой схемы, SAT и 3-SAT. Среди них для пла- нирования сведений более полезной была задача 3-SAT.

3-SAT: для заданного множества условий C1, ..., Ck , каждое из которых имеет длину 3, по множеству переменных X = {x1, ..., xn}, существует ли выполняющее логическое присваивание?

Из-за своей выразительности и гибкости задача 3-SAT часто становится по- лезной отправной точкой для сведений, в которых ни одна из предшествующих пяти категорий не находит естественного соответствия с рассматриваемой задачей. При проектировании сверток 3-SAT будет полезно вспомнить совет, приведенный в доказательстве (8.8) о том, что экземпляр 3-SAT может рассматриваться с двух разных точек зрения: (a) как поиск по вариантам присваивания переменным с учетом ограничения, что все условия должны быть выполнены, и (b) как поиск по вариантам выбора одного литерала из каждого условия с учетом ограничения о невозможности выбора конфликтующих литералов из разных условий. Каждое из этих представлений 3-SAT полезно, и каждое формирует ключевую идею для целого класса сведений.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задачи соблюдения ограничений:

  1. § 4. Ограничения патентных прав: Общие положения. Ограничения по территории и кругу лиц (п. 1624-1627)
  2. § 2. Соблюдение Конституции и законов
  3. § 57 Общие понятия об ограничении собственности с положительной и с отрицательной стороны. – Государственные ограничения. – Ограничения по сущности вотчинного права. – Реальное их свойство. – Право в чужой вещи. – Эмфитеозис. – Суперфиция. – Сервитут. – Виды и закон сервитутов. – Поземельные повинности германского права. – Сервитуты по местным законам прибалтийских губерний
  4. § 6. Соблюдение и охрана конституции
  5. 4.1. НАДЗОР И КОНТРОЛЬ НАД СОБЛЮДЕНИЕМ ЗАКОНОДАТЕЛЬСТВА О ТРУДЕ
  6. § 6. Контроль за соблюдением законности в государственном управлении
  7. § 6. Контроль за соблюдением законности в государственном управлении
  8. § 4. Контроль за соблюдением законности в государственном управлении
  9. Соблюдение законов и норм формальной логики.
  10. Статья 687. Проверка соблюдения продавцом условий договора купли-продажи
  11. Необходимость соблюдения такта при «получении» любовного послания
  12. 1. Права и обязанности, связанные с соблюдением условий о предмете и качестве работы.
  13. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  14. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  15. Статья 203. Общие требования, соблюдение которых является необходимым для действительности сделки