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

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

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

Answer 1

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 2

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

Answer 3

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

Если время выполнения удваивается при каждом увеличении N, вы смотрите на алгоритм O (2 ^ N). Это также то, что я ожидал бы от посещения всех подмножеств набора (или всех членов powerset набора), так как это ровно 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

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