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

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

(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)))))

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

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

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


lisp subset-sum np-complete
person G.E.M.    schedule 01.03.2010    source источник

Ответы (5)


arrow_upward
5
arrow_downward

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

person Carl Norum    schedule 01.03.2010
comment
Да, мое решение - это, по сути, исчерпывающий поиск всех возможных подмножеств набора до тех пор, пока не будет найдено одно с правильной суммой, поэтому я думаю, что это далеко не эффективный алгоритм. - person G.E.M.; 01.03.2010

arrow_upward
7
arrow_downward

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.

person David Johnstone    schedule 01.03.2010
comment
Это исчерпывающий перебор всех подмножеств, пока не будет найдено одно с правильной суммой. Список подмножеств и сами подмножества - все связанные списки, поэтому они могут быть созданы друг из друга и добавлены к подмножествам за O (1) раз. - person G.E.M.; 01.03.2010
comment
Исправление: если был найден быстрый (полиномиальный) алгоритм для какой-либо NP-полной задачи, то каждая NP-полная задача могла быть решена за полиномиальное время; следует читать, тогда каждая проблема в NP может быть решена за полиномиальное время . - person porges; 22.03.2010
comment
+1 за одну женщину, проводящую аналогию с младенцами O(n), которая помогла объяснить аргумент человеку, не принадлежащему к CS. - person Adam Wuerl; 29.07.2011

arrow_upward
3
arrow_downward

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

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

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

person Vatine    schedule 01.03.2010

arrow_upward
2
arrow_downward

То, что здесь происходит, можно было бы гораздо проще выразить с помощью рекурсии:

(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).

person huaiyuan    schedule 01.03.2010

arrow_upward
0
arrow_downward

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

person Niklas R.    schedule 22.03.2010