Проблема суммы подмножеств и разрешимость полных 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)))))
"набор" является списком, не содержащим дубликаты, и "сумма" является суммой для поиска подмножеств. "подмножества" являются списком ячеек недостатков, где "автомобиль" является списком подмножества, и "CDR" является суммой того подмножества. Новые подмножества создаются из старых в O (1) время просто cons'ing элемент к передней стороне.
Я не уверен, какова сложность во время выполнения его, но появляется, что с каждым элементом "сумма" растет, размер "подмножеств" удваивается плюс одно, таким образом, это, кажется мне, по крайней мере, квадратично.
Я отправляю это, потому что мое впечатление прежде было то, что полные NP проблемы имеют тенденцию быть тяжелыми и что лучший может обычно надеяться на, эвристика, но это, кажется, решение общего назначения, которое будет, предполагая, что Вы имеете циклы ЦП, всегда даете Вам корректный ответ. Сколько другие полные NP проблемы могут быть решены как этот?
5 ответов
Все NP-полные проблемы имеют решения. До тех пор, пока вы готовы потратить время на вычисление ответа, то есть. Если не существует эффективного алгоритма, это не значит, что его нет. Например, вы можете просто перебрать все потенциальные решения, и в конце концов получите одно. Такие задачи повсеместно используются в реальных вычислениях. Вам просто нужно быть осторожным с тем, насколько большую задачу вы ставите перед собой, если вам потребуется экспоненциальное время (или еще хуже!) для ее решения.
То, что здесь происходит, можно было бы гораздо проще выразить с помощью рекурсии:
(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).
Я не уверен, какова его сложность во время выполнения , но похоже, что с каждым элементом "сумма" растет по, размер "подмножеств" удваивается плюс один, , так что мне кажется, по крайней мере, квадратичным.
Если время выполнения удваивается при каждом увеличении N, перед вами алгоритм O (2 ^ N). Это также то, что я ожидал бы от посещения всех подмножеств набора (или всех членов powerset набора), поскольку это ровно 2 ^ N членов (если вы включаете пустой набор).
Тот факт, что добавление или не добавление элемента ко всем ранее известным наборам происходит быстро, не означает, что вся обработка выполняется быстро.
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.
Это karприводится к полиномиальному времени. Свести с редукцией Карпа к задаче решения O (nM) с использованием кучи или двоичного поиска. Верхние границы: log (M * 2 ^ M) = logM + log (2 ^ M) = logM + Mlog2 Ergo Time: O (nM)