SAT / CNF оптимизация - PullRequest
Новая
       17

SAT / CNF оптимизация

5 голосов
/ 17 января 2012

Задача

Я смотрю на специальную часть задачи оптимизации SAT. Для тех, кто не знаком с SAT и смежными темами, вот связанная статья Wikipedia . 

TRUE=(a OR b OR c OR d) AND (a OR f) AND ...

Нет НЕ, и это в соединительной нормальной форме. Это легко решаемо. Однако я пытаюсь минимизировать количество истинных назначений , чтобы сделать все утверждение верным. Я не мог найти способ решить эту проблему.

Возможные решения

Я нашел следующие способы ее решения:

  1. Преобразование в ориентированный граф и поиск минимального остовного дерева, охватывающего только подмножество вершин. Есть алгоритм Эдмонда, но он дает MST для полного графа вместо подмножества вершин.
    • Может быть, существует версия алгоритма Эдмонда, которая решает проблему для подмножества вершин?
    • Может быть, есть способ построить график из исходной задачи, который можно решить с помощью других алгоритмов?
  2. Используйте SAT-решатель, LIP-решатель или исчерпывающий поиск. Меня не интересуют эти решения, так как я пытаюсь использовать эту проблему в качестве лекционного материала.

Вопрос

У вас есть идеи / комментарии? Можете ли вы придумать другие подходы, которые могут работать?

1 Ответ

9 голосов
/ 17 января 2012

Эта проблема также NP-Hard .

Можно показать уменьшение на восток с Набор ударов :

УдарЗадача о множестве : для заданных множеств S1,S2,...,Sn и числа k: выбрано множество S размера k, такое, что для каждого Si существует элемент s в S, такой что s находится в Si.[альтернативное определение: пересечение между Si и S не пусто.]

Сокращение :
для экземпляра (S1,...,Sn,k) набора удара, создайте экземплярвашей проблемы: (S'1 AND S'2 And ... S'n,k), где S'i - все элементы в Si, с ИЛИ.Эти элементы в S'i являются переменными в формуле.

proof:
Удар по множеству -> Эта проблема : если есть экземпляр набора совпадений, S затем, присваивая всем элементам S значение true, формула удовлетворяется элементами k, поскольку для каждого S'i существует некоторая переменная v, которая находится в S и Si и, следовательно, также в S'i.
Эта проблема -> Удар по набору : сборка S со всеми элементами, для которых задано истинное значение [та же идея, что и к Удару по множеству-> Эта проблема].

Поскольку вы ищетеЗадача оптимизации для этого тоже NP-Hard, и если вы ищете точное решение - вы должны попробовать экспоненциальный алгоритм

...