arrays - 将数组拆分为 P 个平衡和子数组的算法

Question

我有一个长度为 N 的大数组，假设是这样的:

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

我需要将这个数组拆分成P个子数组(在这个例子中，P=4比较合理)，​​使得每个子数组中的元素之和尽可能接近sigma，是:

sigma=(sum of all elements in original array)/P

在这个例子中，sigma=15。

为了清楚起见，一种可能的结果是:

2 4 6    7 6 3 3   3 4 3 4    4 4 3 3 1
(sums: 12,19,14,15)

我已经编写了一个非常天真的算法，该算法基于我将如何手动进行除法，但我不知道如何施加条件，即总和为 (14,14,14,14,19) 的除法是比 (15,14,16,14,16) 差。

提前谢谢你。

Answer 1

首先，让我们通过为每个可能的解决方案指定输入、输出和度量来形式化您的优化问题(我希望这符合您的兴趣):

Given an array A of positive integers and a positive integer P, separate the array A into P non-overlapping subarrays such that the difference between the sum of each subarray and the perfect sum of the subarrays (sum(A)/P) is minimal.

Input: Array A of positive integers; P is a positive integer.
Output: Array SA of P non-negative integers representing the length of each subarray of A where the sum of these subarray lengths is equal to the length of A.
Measure: abs(sum(sa)-sum(A)/P) is minimal for each sa ∈ {sa | sa = (A_i, …, A_i+‍SAj) for i = (Σ SA_j), j from 0 to P-1}.

输入 和输出 定义了一组有效的解决方案。 measure 定义用于比较多个有效解决方案的度量。由于我们正在寻找与完美解决方案(最小化问题)差异最小的解决方案，因此度量也应该是最小的。

有了这些信息，就很容易实现 measure 函数(这里用 Python):

def measure(a, sa):
    sigma = sum(a)/len(sa)
    diff = 0
    i = 0
    for j in xrange(0, len(sa)):
        diff += abs(sum(a[i:i+sa[j]])-sigma)
        i += sa[j]
    return diff

print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8

现在找到最佳解决方案有点困难。

我们可以使用 Backtracking algorithm用于寻找有效的解决方案并使用测量 功能对其进行评分。我们基本上尝试所有可能的 P 非负整数组合，总和为 length(A) 以表示所有可能的有效解决方案。虽然这确保不会错过有效的解决方案，但它基本上是一种蛮力方法，好处是我们可以省略一些不会比我们最好的解决方案更好的分支。例如。在上面的示例中，如果我们已经有了measure ≤ 38 的解决方案，我们就不需要用 [9,…] (measure> 38) 测试解决方案。

根据维基百科的伪代码模式，我们的 bt 函数如下所示:

def bt(c):
    global P, optimum, optimum_diff
    if reject(P,c):
        return
    if accept(P,c):
        print "%r with %d" % (c, measure(P,c))
        if measure(P,c) < optimum_diff:
            optimum = c
            optimum_diff = measure(P,c)
        return
    s = first(P,c)
    while s is not None:
        bt(list(s))
        s = next(P,s)

全局变量 P、optimum 和 optimum_diff 表示保存 A 值的问题实例， P和sigma，以及最优解及其度量:

class MinimalSumOfSubArraySumsProblem:
    def __init__(self, a, p):
        self.a = a
        self.p = p
        self.sigma = sum(a)/p

接下来我们指定非常简单的 reject 和 accept 函数:

def reject(P,c):
    return optimum_diff < measure(P,c)
def accept(P,c):
    return None not in c

这会简单地拒绝任何其衡量标准已经超过我们尚未优化的解决方案的候选人。我们接受任何有效的解决方案。

由于 c 现在可以包含 None 值，因此 measure 函数也略有变化:

def measure(P, c):
    diff = 0
    i = 0
    for j in xrange(0, P.p):
        if c[j] is None:
            break;
        diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
        i += c[j]
    return diff

剩下的两个函数first和next稍微复杂一点:

def first(P,c):
    t = 0
    is_complete = True
    for i in xrange(0, len(c)):
        if c[i] is None:
            if i+1 < len(c):
                c[i] = 0
            else:
                c[i] = len(P.a) - t
            is_complete = False
            break;
        else:
            t += c[i]
    if is_complete:
        return None
    return c

def next(P,s):
    t = 0
    for i in xrange(0, len(s)):
        t += s[i]
        if i+1 >= len(s) or s[i+1] is None:
            if t+1 > len(P.a):
                return None
            else:
                s[i] += 1
            return s

基本上，first 要么将列表中的下一个 None 值替换为 0(如果它不是列表中的最后一个值)，要么替换为如果它是列表中的最后一个值，则表示有效解决方案的余数(此处略微优化)，或者如果列表中没有 None 值，则返回 None。 next 只是将最右边的整数递增 1 或返回 None(如果递增会超出总数限制)。

现在您需要做的就是创建一个问题实例，初始化全局变量并用根调用bt:

P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)