最简单的NP-Hard问题
前言
本文介绍了最简单的NP-hard问题——数字分区问题，以及该问题的一个伪多项式解法和两个近似解法。
数字分区问题
讨论这样一个问题：给定一个正整数的多重集合
，能否将
划分为两个子集
和
，使得
中元素的和与
中元素的和相等？在数论和计算机科学中，该问题被称为是数字分区问题，尽管NP完全，但是却存在动态规划的解法能够在伪多项式时间内求解，并且在许多情况下，存在最佳或者是近似的解决方法。因此，这个问题也被称为"最简单的NP-hard问题"。
比如给定多重集合
存在子集
和
，这两个子集划分了
。这个解并不是唯一的。
和
是另外一组解。
并不是所有的多重集合都能找到这个问题的解，比如
。
伪多项式时间算法
在多重集合元素的个数和多重集合元素的和值不是很大时，可以采用动态规划来解决。
假设问题的输入是具有
个正整数的多重集合
设
为
中元素的和值
。那么算法就是找出一个
的子集，其和为
。如果这样的子集存在，那么：
- 如果
是偶数，
中其余元素的和也是
- 如果
是奇数，
中其余元素的和是
，我们将会得到一个近似解。
重叠子问题
用
来表示在
中是否存在子集使得子集元素和为
，如果存在，
为
；如果不存在，
为
。
那么上面的问题就变成了判断
是否为
。为了帮助解决这个问题，我们引入下面的命题：
当且仅当
为
或者
为
时，
为
。
下面来证明这个命题
证明：
- 当
为
时，
使得
成立，
，故
为
;
- 当
为
时，
使得
成立，则必有
使得
成立，
，故
为
;
- 当
为
且
为
时，
使得
成立且
使得
成立，此时明显
使得
成立（反证法可证）。
综上，当且仅当
为
或者
为
时，
为
实现代码
使用Python来简单实现上面的算法:
#!/usr/bin/env python
import numpy as np
def find_partition(s):
n = len(s)
k = sum(s)
p = np.zeros((k / 2 + 1, n + 1), dtype=bool)
p[0] = True
for i in range(1, k/2+1):
for j in range(1, n+1):
p[i][j] = p[i][j-1]
if i >= s[j-1]:
p[i][j] = p[i][j] or p[i-s[j-1]][j-1]
return p[k/2][n]
test_list = [3, 1, 1, 2, 2, 1]
print(find_partition(test_list))程序的输出结果如下
True下面的表格是程序中
的数据
{} | {3} | {3,1} | {3,1,1} | {3,1,1,2} | {3,1,1,2,2} | {3,1,1,2,2,1} | |
|---|---|---|---|---|---|---|---|
0 | True | True | True | True | True | True | True |
1 | False | False | True | True | True | True | True |
2 | False | False | False | True | True | True | True |
3 | False | True | True | True | True | True | True |
4 | False | False | True | True | True | True | True |
5 | False | False | False | True | True | True | True |
复杂度分析
上面算法的时间复杂度为
，其中，
是输入多重集合元素的个数，
是多重集合中所有元素的和。
如果将问题变成将一个多重集合分为
个和相等的子集，算法的空间复杂度将为
，其中
是输入中最大的值。在这样的情况下，即使
也很难应用这样的算法，除非输入的都是一些小数字。
近似求解算法
有一些启发式算法可以用来求这个问题的近似解。
贪心算法
想象一下一群孩子分拨玩游戏的场景，商量好分成几拨后，每次选出一个人，加入到人少的那一拨中，贪心算法的过程类似。在这个问题中，多重集合按降序排列，依次遍历，每次选出一个数添加到和值较小的子多重集合中。这个算法的时间复杂度为
。该算法在实际中能够得到近似解，但是不保证能得到最优解。比如，输入多重集合
，贪心算法会将
分为
和
这两个子多重集合，但是最优解是存在的，比如
和
。
贪心算法能得到最优解法的
近似解；这个意思是说，设最优解中较大多重集合的和为
，贪心算法输出两个多重集合
和
，那么有
。
Python版本的代码如下：
def find_partition(input_list):
a, b = [], []
sum_a, sum_b = 0, 0
for n in sorted(input_list, reverse=True):
if sum_a < sum_b:
a.append(n)
sum_a += n
else:
b.append(n)
sum_b += n
return a, b
test_list = [3, 1, 1, 2, 2, 1]
print(find_partition(test_list))程序结果输出如下
([2, 2, 1], [3, 1, 1])在这个问题中，上面的解法针对的是
的情况，贪心算法还可用于
个分区的情况。对
的情况，算法的时间复杂度是
，能得到最优解法的
近似解。现在，对于数字多重集合划分问题，我们有一个多项式时间近似方案，尽管这不是一个完全多项式时间近似方案。
差分算法
另一种启发式算法是最大差分法，该算法也被称之为Karmarkar-Karp启发式算法。最大差分法分两个阶段运行。算法的第一阶段从输入中取出最大的两个数，用它们的差来替换它们；循环此过程直到只剩下一个数字。替换表示将这两个数字放在不同的集合中，但是不确定具体的集合。在第一阶段结束时，剩下的数字就是两个子集和值的差。第二个阶段构造出真正的解法。
在这个问题中，差分算法比贪心算法效果更好，但对于数字大小和集合大小呈指数关系的情况仍然不适用。
下面的Python代码实现了算法的第一阶段
from queue import PriorityQueue
def karmarkarKarpPartition(input_list):
heap = PriorityQueue()
for n in input_list:
heap.put((-n, n))
while heap.qsize() > 1:
val1 = heap.get()[1]
val2 = heap.get()[1]
sub_ret = val1 - val2
heap.put((-sub_ret, sub_ret))
return heap.get()[1]
test_list = [3, 1, 1, 2, 2, 1]
print(karmarkarKarpPartition(test_list))测试输出为
0