最简单的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

原文发布于微信公众号 - 派森公园(demon-hsy)

原文发表时间:2018-05-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件测试经验与教训

Python学习笔记(九)--函数

33610
来自专栏技术专栏

基本排序算法

● 基础 ● 编码简单,易于实现,是一些简单情景的首选 ● 在一些特殊情况下,简单的排序算法更有效 ● 简单的排序算法思想衍生出复杂的排序算法 ● 作为...

612
来自专栏Python中文社区

Python数组中求和问题

本专题主要介绍哈希表和指针两种方法来解决该类问题,从两个数之和引申到三个数之和,再从四个数之和的问题上思考如何构建出一种通用的代码(可以解决N个数之和)。本文主...

820
来自专栏C/C++基础

多益网络2016春季实习校招笔试回顾(C++游戏后台开发)

2016.04.16晚中山大学大学城校区(东校区)参加了多益网络的C++游戏后台开发的笔试。有几道笔试题还是值得斟酌和记录的,特记录如下。比较可惜,因为回老家了...

662
来自专栏开源优测

[快学Python3]二分查找[策略优化版本]

概述 在上文《二分查找》中,我们了解了二分查找基本实现原理和具体的实现算法。 但大家有没有发现,如果目标查找值,如果在查找序列中存在多个,则查找返回的索引值,会...

1916
来自专栏Fred Liang

Numpy

对数组运算相当于对数组每一个元素进行运算 a = np.arange(24).reshape((2,3,4))

772
来自专栏深度学习之tensorflow实战篇

python 中numpy基本方法总结可以类推tensorflow

一、数组方法 创建数组:arange()创建一维数组;array()创建一维或多维数组,其参数是类似于数组的对象,如列表等 反过来转换则可以使用numpy.n...

4375
来自专栏武培轩的专栏

剑指Offer-连续子数组的最大和

题目描述 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边...

2602
来自专栏ACM算法日常

基础算法|4 简单选择排序

我们之前已经了解了三种基础算法,分别为二分查找算法,冒泡排序算法,以及直接插入排序算法。俗话说得好,温故而知新,所以现在就让我们简单回顾一下之前的三种算法吧。...

953
来自专栏小樱的经验随笔

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !! time limit per test:1 second memory limit per test:64 meg...

2483

扫码关注云+社区