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負の要素から最小の数までの最短経路の 1 つと、そこにある各セルを作成することで、これを試しました。

まず、開始セルと終了セルを含めます。

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 困難である可能性が最も高いです。

ブール変数 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 困難であることが知られているため、この特定のクラスの関数が巧妙な解決策を認めない限り、賢いブルート フォーシング (Andrew の解決策) が適しているようです。

このブログ投稿には、非常によく似た問題に関する優れた記事があります。

于 2012-12-21T05:45:35.440 に答える
0

あなたの問題に多項式時間の解があるかどうかはわかりません。そうではないと思いますが、NP完全であることを証明する方法もわかりません。

有望なアプローチの 1 つは、(非凸) 二次プログラムとして記述することです。-1 <= v <= 1、-1 <= w <= 1、および v^TM となるようなベクトル v と w を見つけたいと考えています。 w はできるだけ大きくします。これはリラクゼーションです。v と w に +/-1 エントリのみを要求しているわけではありませんが、問題と同じ最適解があります。この問題に対する「合理的な」凸二次緩和を見つけ、その上に分枝限定スキームを構築できるはずです。

于 2012-12-20T22:10:20.270 に答える