9

有一个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]]

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

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

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

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

4

3 回答 3

2

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]]
于 2012-12-20T22:53:13.697 回答
1

作为伪布尔函数(PB) 优化的一个实例，该问题很可能是 NP-hard 。

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

那么，每个矩阵元素的“翻转符号”可以描述为

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

So, given your matrix M, your problem asks to maximize the PB function

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

Optimization of PB functions is known to be NP-hard, so unless this particular class of functions admits a clever solution, smart brute-forcing (Andrew's solutions) seems the way to go.

There is a nice write-up for a very similar problem in this blog post.

于 2012-12-21T05:45:35.440 回答
0

我不确定您的问题是否具有多项式时间解。我不认为是这样，但我也不知道如何证明它是 NP 完全的。

一种可能有前途的方法是将其编写为（非凸）二次程序：我们希望找到向量 v 和 w 使得 -1 <= v <= 1、-1 <= w <= 1 和 v^TM w 尽可能大。这是一种放松；我不要求 v 和 w 仅具有 +/-1 个条目，但它具有与您的问题相同的最佳解决方案。你应该能够为这个问题找到一个“合理的”凸二次松弛，然后在它上面构建一个分支定界方案。

于 2012-12-20T22:10:20.270 回答