Примеры задач np-класса.
Задача о выполнимости.
Пусть
х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)
Для этого используется метод уменьшения порядка дизъюнкта
(1
2
…
k)=(1
2
z)
(3
4
…
k
)
Применяя итерационный процесс разложения, можно получить Е*.
Найти алгоритм решения Е* проще, чем функции Е. Но при этом доказав выполнимость Е*, докажем выполнимость исходной функции Е.
Частный случай: при К=2 функция Е входит в Р.
Примерами задач NP-класса могут послужить также задачи на графах:
Определение максимума клик неориентированного графа (NP-трудная задача).
Задача определения полного подграфа (NP-полная задача).
Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).
Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).
Задача определения существования Гамильтонова цикла для графа (NP-полная задача).
Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).
Задача составления расписания (NP-полная задача).
Логическое программирование.
Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.
Самым известным языком логического программирования является Prolog.
Первым языком логического программирования был язык Planner, в котором была заложена возможность автоматического вывода результата из данных и заданных правил перебора вариантов (совокупность которых называлась планом). Planner использовался для того, чтобы понизить требования к вычислительным ресурсам (с помощью метода backtracking) и обеспечить возможность вывода фактов, без активного использования стека. Затем был разработан язык Prolog, который не требовал плана перебора вариантов и был, в этом смысле, упрощением языка Planner.
От языка Planner также произошли логические языки программирования QA-4, Popler, Conniver и QLISP. Языки программирования Mercury, Visual Prolog, Oz и Fril произошли уже от языка Prolog. На базе языка Planner было разработано также несколько альтернативных языков логического программирования, не основанных на методе поиска с возвратами (backtracking), например, Ether.