通过将矩阵的行和列乘以-1，使整数矩阵中所有元素之和最大化

Question

有一个大小为m，n的整数矩阵M，如何将其转换为使所有元素之和最大的算法？

唯一允许的操作是按列或行乘以-1。可以执行任意多次此类操作。

粗略的总体思路：我的想法是将每个负数的负号移动到值最小的正数上，以使负数对总和的影响最小。

让我们举个例子：

import numpy as np

M = np.matrix([
        [2,2,2,2],
        [2,2,-2,2],
        [2,2,2,2],
        [2,2,2,1],
    ])

def invert_at(M, n, m):
    M[n,:] *= -1
    M[:,m] *= -1

我已经尝试过通过从负数元素到最小数字构建最短路径并沿途 invert_at 每个单元格来实现此目标。

首先包括起始和结束单元格：

invert_at(M, 1, 2)  # start
invert_at(M, 2, 2)
invert_at(M, 3, 2)
invert_at(M, 3, 3)  # end

我最终得到了：

[[ 2  2 -2 -2]
 [-2 -2 -2  2]
 [-2 -2  2  2]
 [ 2  2 -2 -1]]

这看起来很有趣。它将负数推到右下角的-1，但也影响到其他区域。现在，如果我在起始和结束位置再次反转（即-1 * -1 = 1），因此首先略过第一个和最后一个单元格，我最终得到：

[[ 2  2  2  2]
 [ 2  2 -2  2]
 [-2 -2 -2 -2]
 [-2 -2 -2 -1]]

就外观而言，考虑到我的需求，哪个更好？

[[ 2  2  2  2]
 [ 2  2  2  2]
 [ 2  2  2  2]
 [ 2  2  2 -1]]

通过将负数“推向”矩阵的右半部分来解决问题。

谈到“半”，我也曾经尝试过使用矩阵的分区，但是我没有观察到任何可用的模式。

我尝试过的大多数方法都将我带回了原始矩阵，而这种“雪崩效应”让我感到疯狂。

解决这个问题的好方法是什么？

- Flavius

---

我是否误解了问题？乍一看似乎非常简单，如果你只能乘以-1，那么你只需要确定负项是否比正项多，如果是，则*=-1？ - arynaq

是的，看起来我有点明白了。明天考试后我会回头再处理这个问题，看起来很有趣。我会尝试提出一个暴力解法，通常它们会透露出一些模式..通常情况下。 - arynaq

我记得有一个类似的问题：给定一个MxN（M，N> 1）的灯泡网格（最初关闭），每行和每列都有一个开关，确定一种算法，以产生只有一个灯泡打开的网格。我记得有一个聪明的技巧，可以打开和关闭行和列的正确交叉点，以逐个关闭所有灯泡，但它现在想不起来了... - Bakuriu

@Bakuriu：这个问题可以转化为一些模2的线性代数问题。但是在这里，我们需要最大化一个函数，这并不容易。 - tmyklebu

Answer 1

任意n行或m列都可以翻转（-1）或不翻转（1）。

这意味着总可能性的数量为2^(n+m)。这也意味着可以在指数时间内找到解决方案。对于小矩阵，您可以使用暴力搜索所有可能的翻转和未翻转的列和行的组合。

但是，您需要等待所有内容应用完成，否则您将陷入局部最小值中。

在此特定情况下，M已经是最大和（27）。

import numpy as np

def bit_iter(n):
    for i in xrange(2**(n)):
        bits = []
        for j in xrange(n):
            if i & (2**j) != 0:
                bits.append(1)
            else:
                bits.append(0)
        yield bits

def maximal_sum(M):
    Morig = M.copy()
    n, m = M.shape
    best = None
    for bits in bit_iter(n + m):
        nvec = bits[:n]
        mvec = bits[n:]
        assert(len(nvec) + len(mvec) == len(bits))
        M = Morig.copy()
        for i, v in enumerate(nvec):
            if v == 0:
                M[i, :] *= -1
        for i, v in enumerate(mvec):
            if v == 0:
                M[:, i] *= -1
        if best == None or np.sum(M) > np.sum(best):
            best = M
    return best

M = np.matrix([
    [2,2,2,2],
    [2,2,-2,2],
    [2,2,2,2],
    [2,2,2,1],
])
print maximal_sum(M)
M = np.matrix([
        [1,2],[3,-4]
    ])
print maximal_sum(M)
M = np.matrix([
        [2,-2,2,2],
        [2,2,2,2],
        [2,2,-2,2],
        [2,2,2,2],
        [2,2,2,1],
    ])
print maximal_sum(M)

提供：

[[ 2  2  2  2]
 [ 2  2 -2  2]
 [ 2  2  2  2]
 [ 2  2  2  1]]
[[-1  2]
 [ 3  4]]
[[ 2 -2  2  2]
 [ 2  2  2  2]
 [ 2  2 -2  2]
 [ 2  2  2  2]
 [ 2  2  2  1]]

- Andrew Walker

---

@Flavius - 已修复错误。谢谢。 - Andrew Walker

你的方法的一个变体可以在O(2^(min(m,n)) poly(m+n))时间内完成此操作。给定行的签名，您实际上不需要蛮力来找到列的最佳签名。 - tmyklebu

一旦你决定了要翻转的行，你可以通过翻转那些能够提高目标值的列来决定要翻转的列。 - tmyklebu

贪心算法不会接近正确答案。你需要进行彻底的搜索。由于搜索空间巨大，你希望尽早剪枝。我试图在我的回答中概述我认为对于相当大的矩阵进行这种彻底搜索的最有前途的方法。这绝非易事，需要运用许多技巧，但这就是解决此类问题的可行解决方案的本质。 - tmyklebu

@tmyklebu 我已经测试了我的一个想法的版本，它具有通过递归尝试微调解决方案的附加功能。在许多情况下，它可以给出精确的结果和可接受的近似值，但从速度上来看，它正在迅速减慢。即使在某些时候，它会达到25倍的加速。我将思考这个问题并创建不同的替代方案，包括你的方案，以查看它的效果如何。 - Flavius

Answer 2

问题很可能是一个伪布尔函数（PB）优化的NP难题实例。

您可以用布尔变量x_i表示“第i行被否定”的事实，并用布尔变量y_j表示“第j列被否定”的事实。

然后，每个矩阵元素的“翻转符号”可以描述为：

 c(i, j) = 1 - 2*x_i - 2*y_j + 4*x_i*y_j .

因此，鉴于您的矩阵M，您的问题要求最大化PB函数。

 f = sum A[i,j]*c(i, j) .

PB函数的优化被认为是NP难问题，除非这个特定类别的函数有聪明的解决方案，否则智能暴力破解（安德鲁的解决方案）似乎是前进的方式。

在这篇博客文章中有一个非常类似的问题的好的解释。

- Dejan Jovanović

Answer 3

我不确定你的问题是否有多项式时间解决方案。我认为它没有，但我也不知道如何证明它是NP完全的。

一个可能有前途的方法是将其写成一个（非凸）二次规划问题：我们想要找到向量v和w，使得-1 <= v <= 1，-1 <= w <= 1，并且v^T M w尽可能大。这是一种松弛；我不要求v和w只有+/-1条目，但它具有与您的问题相同的最优解。您应该能够找到一个“合理”的凸二次松弛来解决这个问题，然后在其上构建一个分支定界方案。

- tmyklebu