Задача о сумме подмножеств и разрешимости 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, где "car" - это список подмножеств, а "cdr" - сумма этого подмножества.Новые подмножества создаются из старых за O (1) раз, просто перемещая элемент вперед.

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

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

Answer 1

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

Answer 2

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

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

Если я правильно понимаю ваш алгоритм (а это основано больше на ваших комментариях, чем на коде), то он эквивалентен O(n*2^n) алгоритм здесь.Есть 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

Это можно свести к полиномиальному времени.Сведение с помощью Карпа к проблеме решения O(nM) с использованием верхних границ кучи или двоичного поиска равно log(M*2^M)=logM+log(2^M)=logM+Mlog2 Ergo Time:O(nM)