Основные понятия и определения дисциплины


Download 0.68 Mb.
bet15/28
Sana04.05.2023
Hajmi0.68 Mb.
#1426224
1   ...   11   12   13   14   15   16   17   18   ...   28
Bog'liq
ответы

К-выполнимость.
К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*2), содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.
E*(x1, x2,…, xn)E*(xi)
Для этого используется метод уменьшения порядка дизъюнкта
(1  2 … k)=(1  2  z)  (3  4 … k  )
Применяя итерационный процесс разложения, можно получить Е*.
Найти алгоритм решения Е* проще, чем функции Е. Но при этом доказав выполнимость Е*, докажем выполнимость исходной функции Е.
Частный случай: при К=2 функция Е входит в Р.
Примерами задач NP-класса могут послужить также задачи на графах:

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

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

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

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

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

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

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


  1. Download 0.68 Mb.

    Do'stlaringiz bilan baham:
1   ...   11   12   13   14   15   16   17   18   ...   28




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling