Редактирование: 2SAT

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 24: Строка 24:
 
#Построим граф импликаций.  
 
#Построим граф импликаций.  
 
#<i>Найдём в этом графе [[Отношение_связности,_компоненты_связности#Сильная связность | компоненты сильной связности]] за время <tex>O(N + M)</tex></i>, где <tex> N </tex> — количество вершин в графе (удвоенное количество переменных), а <tex> M </tex> — количество ребер графа (удвоенное количество дизъюнктов).
 
#<i>Найдём в этом графе [[Отношение_связности,_компоненты_связности#Сильная связность | компоненты сильной связности]] за время <tex>O(N + M)</tex></i>, где <tex> N </tex> — количество вершин в графе (удвоенное количество переменных), а <tex> M </tex> — количество ребер графа (удвоенное количество дизъюнктов).
#Пусть <tex>comp[v]</tex> — это номер компоненты сильной связности, которой принадлежит вершине <tex>v</tex>. Проверим, что для каждой переменной <tex>x</tex> вершины <tex>x</tex> и <tex>\overline x</tex> лежат в разных компонентах, т.е. <tex>comp[x] \ne comp[\overline x]</tex>. Если это условие не выполняется, то вернуть <i>решение не существует</i>.  
+
#Пусть <tex>comp[v]</tex> — это номер компоненты сильной связности, которой принадлежит вершине <tex>v</tex>. Проверим, что для каждой переменной <tex>x</tex> вершины <tex>x</tex> и <tex>\overline x</tex> лежат в разных компонентах, т.е. <tex>comp[x] \ne comp[\overline x]</tex>. Если это условие не выполняется, то вернуть "решение не существует".  
#Если <tex>comp[x] > comp[\overline x]</tex>, то переменной <tex>x</tex> выбираем значение <tex> \mathtt {true}</tex>, иначе — <tex> \mathtt {false}</tex>.
+
#Если <tex>comp[x] > comp[\overline x]</tex>, то переменной <tex>x</tex> выбираем значение <tex> \mathtt true</tex>, иначе — <tex> \mathtt false</tex>.
  
 
Компоненты сильной связности найдем за <tex>O(N + M)</tex>, затем проверим каждую из <tex>N</tex> переменных за <tex>O(N)</tex>. Следовательно асимптотика <tex>O(N + M)</tex>.
 
Компоненты сильной связности найдем за <tex>O(N + M)</tex>, затем проверим каждую из <tex>N</tex> переменных за <tex>O(N)</tex>. Следовательно асимптотика <tex>O(N + M)</tex>.
Строка 105: Строка 105:
  
 
Решение <tex>\mathrm {2SAT}</tex> может потребоваться в следующих задачах:  
 
Решение <tex>\mathrm {2SAT}</tex> может потребоваться в следующих задачах:  
*латинские квадраты<ref> [https://ru.wikipedia.org/wiki/Латинский_квадрат Википедия — Латинские квадраты] </ref>,  
+
*латинские квадраты<ref> [https://ru.wikipedia.org/wiki/Латинский_квадрат Латинские квадраты] </ref>,  
*квазигруппы<ref>[https://ru.wikipedia.org/wiki/Квазигруппа_(социология) Википедия — Квазигруппы]</ref>,
+
*квазигруппы<ref>[https://ru.wikipedia.org/wiki/Квазигруппа_(социология) Квазигруппы]</ref>,
*числа Рамсея<ref>[https://ru.wikipedia.org/wiki/Теорема_Рамсея#.D0.A7.D0.B8.D1.81.D0.BB.D0.B0_.D0.A0.D0.B0.D0.BC.D1.81.D0.B5.D1.8F Википедия — Числа Рамсея]</ref>,
+
*числа Рамсея<ref>[https://ru.wikipedia.org/wiki/Теорема_Рамсея#.D0.A7.D0.B8.D1.81.D0.BB.D0.B0_.D0.A0.D0.B0.D0.BC.D1.81.D0.B5.D1.8F Числа Рамсея]</ref>,
*система Штейнера<ref>[https://ru.wikipedia.org/wiki/Система_Штейнера Википедия — Система Штейнера]</ref>,
+
*система Штейнера<ref>[https://ru.wikipedia.org/wiki/Система_Штейнера Система Штейнера]</ref>,
 
*проектирование протоколов (пример: для сетевых коммуникаций),
 
*проектирование протоколов (пример: для сетевых коммуникаций),
 
*электронная коммерция (Электронные аукционы и автоматизированные брокеры,
 
*электронная коммерция (Электронные аукционы и автоматизированные брокеры,
Строка 124: Строка 124:
  
 
*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2SAT (2-CNF) ]
 
*[http://e-maxx.ru/algo/2_sat MAXimal :: algo :: Задача 2SAT (2-CNF) ]
*[https://en.wikipedia.org/wiki/2-satisfiability Википедия — 2-satisfiability]
+
*[https://en.wikipedia.org/wiki/2-satisfiability 2-satisfiability — Википедия]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Булевы функции ]]
 
[[Категория: Булевы функции ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: