Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Задача о выполнимости. Пусть х1, х2, , хn – множество логических переменных; – их отрицания или дополнения.






Пусть х1, х2, …, хn – множество логических переменных; – их отрицания или дополнения.

if xi = true then = false

Ú - И; Ù - ИЛИ.

Дизъюнкция: х1 Ú х5 Ú Ú …

Конъюнкция: х4 Ù х3 Ù Ù …

Конъюнктивная нормальная форма:

E*(x1, …, xn) = (x1 Ú x2 Ú x3) Ù (x1 Ú Ú ) Ù ( Ú x4) Ù () (*)

Задача о выполнимости заключается в определении, является ли булевская функция, записанная в КНФ, выполнимой.

Любая булевская функция может быть представлена в КНФ по правилу Де Моргана:

АÚ (ВÙ С)=(АÚ В)Ù (АÚ С)

Говорят, что булевская функция выполнима, если существует некоторое присваивание переменным true или false, при этом функция должна быть равна true.

Для функции (*) она будет выполнима, если ввести следующие присваивания:

(*)

Например:

Функция

f2(xi)=(x1 Ú x2)Ù ()Ù ( )

не является выполнимой, т. к. при любых xi f2(xi)=false.

Теорема:

Задача о выполнимости является NP-полной.

for i=1 to N do

xi выбор (true, false)

if E(x1, x2, …, xN) then успех

else неудача

Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.

К-выполнимость.

К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*2), содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.

E*(x1, x2, …, xn)®E*(xi)

Для этого используется метод уменьшения порядка дизъюнкта

(a1 Ú a2 Ú …Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú …Ú ak Ú )

Применяя итерационный процесс разложения, можно получить Е*.

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

Частный случай: при К=2 функция Е входит в Р.

Примерами задач NP-класса могут послужить также задачи на графах:

1) Определение максимума клик неориентированного графа (NP-трудная задача).

2) Задача определения полного подграфа (NP-полная задача).

3) Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).

4) Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).

5) Задача определения существования Гамильтонова цикла для графа (NP-полная задача).

6) Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).

7) Задача составления расписания (NP-полная задача).


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал