python - 通过将行和列乘以 -1 使矩阵中的整数和最大

Question

有一个矩阵 M尺寸m, n对于整数，什么是将其转换为所有元素之和最大的好算法？

唯一允许的运算是乘以 -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]]

通过将减号“推”到矩阵的右“一半”。

谈到“一半”，我也玩过(很多)使用矩阵分区的想法，但我无法观察到任何可用的模式。

我尝试过的大多数事情都让我回到了最初的矩阵，我们可以观察到的这种“雪崩效应”让我发疯。

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

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]]