子集和问题与 NP 完全问题的可解性

StackOverflow https://stackoverflow.com/questions/2353497

  •  23-09-2019
  •  | 
  •  

题

当我想出一个似乎是解决它的通用算法时，我正在阅读有关子集和问题的文章：

(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 完全问题可以像这个问题一样得到解决？

有帮助吗？

解决方案

的NP完全问题的所有有解决方案。只要你愿意花钱来计算的答案时，那是。只是因为没有一个的有效的算法，并不意味着没有一个。例如，你可以只遍历每一个潜在的解决方案，最终你会得到一个。这些问题都用遍了在现实世界计算的地方。你只需要小心你为自己设定，如果你将需要指数时间一个大问题（或更糟！）如何解决它。

其他提示

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 上非常大的值，排序会更慢。

  

我不知道运行什么   它的复杂性，但看来，   与每个元素“总和”生长通过，该   的“子集”双打大小，加一，   所以在我看来，至少是   二次的。

如果对于N中的每个增加的运行时间加倍，你正在寻找的O（2 ^ N）的算法。这也是我想从访问一组（或一组的幂的所有成员）的所有子集期望，因为这正是2 ^ N的成员（如果包括RHE空集）。

，添加或不添加的元素的所有迄今看到套的事实快速并不意味着总的处理速度快。

这是怎么回事就可以更简单地使用递归表示：

(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），如所预期。

这是karpreducible到多项式时间。与卡普减少到使用堆或二进制搜索上限决策问题O（nm）的减小是log（M * 2 ^ M）= 10gm的+日志（2 ^ M）= 10gm的+ Mlog2埃尔戈时间：O（nm）的

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top