Проблема подмножеств суммы и разрешимость NP-полной задачи

Question

я читал о проблеме субпопуляции-суммах, когда я пришел с тем, что, как представляется, универсальный алгоритм для ее решения:

(defun subset-contains-sum (set sum) 
    (let ((subsets) (new-subset) (new-sum)) 
     (dolist (element set) 
      (dolist (subset-sum subsets) 
       (setf new-subset (cons element (car subset-sum))) 
       (setf new-sum (+ element (cdr subset-sum))) 
       (if (= new-sum sum) 
        (return-from subset-contains-sum new-subset)) 
       (setf subsets (cons (cons new-subset new-sum) subsets))) 
      (setf subsets (cons (cons element element) subsets))))) 

«set» - это список, не содержащий дубликатов, а «sum» - сумма для поиска подмножеств. «подмножества» - это список ячеек cons, в которых «автомобиль» представляет собой список подмножеств, а «cdr» - это сумма этого подмножества. Новые подмножества создаются из старых в O (1) раз, просто конспектируя элемент на фронт.

Я не уверен, что это сложность выполнения, но кажется, что с каждым элементом «сумма» растет, размер «подмножеств» удваивается, плюс один, поэтому мне представляется, по крайней мере, квадратичным.

Я публикую это, потому что раньше у меня было впечатление, что проблемы с NP-комплексом, как правило, неразрешимы и что лучшее, на что можно надеяться, это эвристика, но это, похоже, универсальное решение, которое, имеют циклы процессора, всегда дают правильный ответ. Сколько других NP-полных проблем можно решить, как этот?

Answer 1

У всех NP-полных проблем есть решения. Пока вы готовы потратить время на вычисление ответа, то есть. Просто потому, что нет эффективного алгоритма, это не значит, что его нет. Например, вы можете просто перебрать все потенциальные решения, и в конечном итоге вы их получите. Эти проблемы используются повсеместно в реальных вычислениях. Вам просто нужно быть осторожным, как большая проблема, которую вы задаете для себя, если вам понадобится экспоненциальное время (или, что еще хуже!), Чтобы решить эту проблему.

Answer 2

NP-полные проблемы разрешимы, просто не в полиномиальное время (насколько нам известно). То есть NP-полная проблема может иметь алгоритм , который мог бы его решить, но у него не будет, например, алгоритм O(n^3) для его решения.

Интересно, если бы был найден быстрый (многочленный) алгоритм для любой NP-полной задачи, то каждая проблема в NP могла быть решена за полиномиальное время. Это то, о чем говорит P = NP.

Если я правильно понимаю ваш алгоритм (и это больше зависит от ваших комментариев, чем от кода), то это эквивалентно алгоритму O(n*2^n)here. Есть 2^n подмножества, и поскольку вам также необходимо суммировать каждое подмножество, алгоритм составляет O(n*2^n).

Еще одна вещь о сложности - O(whatever) указывает только, насколько хорошо определенный алгоритм масштабируется. Вы не можете сравнить два алгоритма и сказать, что один быстрее, чем другой на основе этого. Нотация Big-O не заботится о деталях и оптимизациях реализации - можно написать две реализации одного и того же алгоритма, причем один из них намного быстрее, чем другой, хотя оба они могут быть как O(n^2). Одна женщина, делающая младенцев, - это операция O(n), но есть вероятность, что это займет намного больше времени, чем у большинства O(n*log(n)) видов, которые вы выполняете. Все, что вы можете сказать, основываясь на этом, заключается в том, что сортировка будет медленнее для очень больших значений на n.

Answer 3

Я не уверен, что во время выполнения сложность этого есть, но, похоже, что с каждым элементом «суммой» растет, то размера «подмножеств» удваивается, плюс один, так мне кажется по меньшей мере, квадратичный.

Если время выполнения удваивается для каждого увеличения N, вы смотрите на алгоритм O (2^N). Это также то, что я ожидал бы от посещения всех подмножеств набора (или всех членов силового набора набора), так как это ровно 2^N членов (если вы включаете пустой набор).

Тот факт, что добавление или добавление элемента во все известные до сих пор множества происходит быстро, не означает, что полная обработка выполняется быстро.

Answer 4

Что происходит здесь можно выразить гораздо проще с помощью рекурсии:

 
(defun subset-sum (set sum &optional subset) 
    (when set 
    (destructuring-bind (head . tail) set 
     (or (and (= head sum) (cons head subset)) 
      (subset-sum tail sum   subset) 
      (subset-sum tail (- sum head) (cons head subset)))))) 

Этих два рекурсивных вызовов в конце ясно показать, что мы обход двоичного дерева глубины N, размера данного набора , Число узлов в двоичном дереве равно O (2^n), как и ожидалось.

Answer 5

Он переносится на полиномиальное время. Уменьшить с помощью Karp до решения проблемы O (nM) с использованием верхних границ кучи или бинарного поиска - log (M * 2^M) = logM + log (2^M) = logM + Mlog2 Ergo Время: O (nM)