子集和问题与 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)))))
“set”是一个不包含重复项的列表，“sum”是搜索子集的总和。 “subsets”是 cons 单元的列表，其中“car”是子集列表，“cdr”是该子集的总和。只需将元素放在前面，即可在 O(1) 时间内从旧子集创建新子集。
我不确定它的运行时复杂性是多少，但似乎随着每个元素“总和”的增长，“子集”的大小加倍，再加一，所以在我看来至少是二次的。
我发布此文章是因为我之前的印象是 NP 完全问题往往很棘手，并且通常可以期望的最好的方法是启发式，但这似乎是一种通用解决方案，假设您有 CPU 周期，永远给你正确的答案。还有多少其他 NP 完全问题可以像这个问题一样得到解决？
I was reading about the subset-sums problem when I came up with what appears to be a general-purpose algorithm for solving it:
(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" is a list not containing duplicates and "sum" is the sum to search subsets for. "subsets" is a list of cons cells where the "car" is a subset list and the "cdr" is the sum of that subset. New subsets are created from old ones in O(1) time by just cons'ing the element to the front.
I am not sure what the runtime complexity of it is, but appears that with each element "sum" grows by, the size of "subsets" doubles, plus one, so it appears to me to at least be quadratic.
I am posting this because my impression before was that NP-complete problems tend to be intractable and that the best one can usually hope for is a heuristic, but this appears to be a general-purpose solution that will, assuming you have the CPU cycles, always give you the correct answer. How many other NP-complete problems can be solved like this one?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
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 上非常大的值，排序会变慢。NP-complete problems are solvable, just not in polynomial time (as far as we know). That is, an NP-complete problem may have an
O(n*2^n)algorithm that could solve it, but it won't have, for example, anO(n^3)algorithm to solve it.Interestingly, if a quick (polynomial) algorithm was found for any NP-complete problem, then every problem in NP could be solved in polynomial time. This is what P=NP is about.
If I understand your algorithm correctly (and this is based more on your comments than on the code), then it is equivalent to the
O(n*2^n)algorithm here. There are2^nsubsets, and since you also need to sum each subset, the algorithm isO(n*2^n).One more thing about complexity - the
O(whatever)only indicates how well a particular algorithm scales. You cannot compare two algorithms and say that one is faster than the other based on this. Big-O notation doesn't care about implementation details and optimisations - it is possible to write two implementations of the same algorithm with one being much faster than the other, even though they might both beO(n^2). One woman making babies is anO(n)operation, but the chances are that this is going to take a lot longer than mostO(n*log(n))sorts you perform. All you can say based on this is that sorting will be slower for very large values on n.所有 NP 完全问题都有解。只要您愿意花时间来计算答案，那就是。仅仅因为没有一种高效算法，并不意味着不存在。例如，您可以迭代每个潜在的解决方案，最终会得到一个。这些问题在现实世界的计算中随处可见。如果你需要指数时间（或更糟！）来解决它，你只需要小心你为自己设置的问题有多大。
All of the NP-complete problems have solutions. As long as you're willing to spend the time to compute the answer, that is. Just because there's not an efficient algorithm, doesn't mean there isn't one. For example, you could just iterate over every potential solution, and you'll eventually get one. These problems are used all over the place in real-world computing. You just need to be careful about how a big a problem you set for yourself if you're going to need exponential time (or worse!) to solve it.
如果 N 每增加一次，运行时间就会加倍，那么您正在寻找 O(2^N) 算法。这也是我期望访问一个集合的所有子集（或一个集合的幂集的所有成员），因为这正是 2^N 个成员（如果包含空集）。
向迄今为止所有集合添加或不添加元素的速度很快这一事实并不意味着总处理速度很快。
If the run-time doubles for each increase in N, you're looking at an O(2^N) algorithm. That's also what I'd expect from visiting all subsets of a set (or all members of the powerset of a set), as that's exactly 2^N members (if you include rhe empty set).
The fact that adding or not adding an element to all hitherto-seen sets is fast doesn't mean that the total processing is fast.
这里发生的事情可以用递归更简单地表达：
(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)。
What is going on here could be expressed much more simply using recursion:
(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))))))The two recursive calls at the end clearly show we are traversing a binary tree of depth n, the size of the given set. The number of nodes in the binary tree is O(2^n), as expected.
它可以被推导为多项式时间。使用堆或二分搜索通过 Karp 简化为决策问题 O(nM)，上限为 log(M*2^M)=logM+log(2^M)=logM+Mlog2 Ergo 时间：O(nM)
It's karpreducible to polynomial time. Reduce with Karp reduction to a decision problem O(nM) using a heap or binary search upper bounds is log(M*2^M)=logM+log(2^M)=logM+Mlog2 Ergo Time:O(nM)