3

colSum と rowSum という 2 つの 10 進数の変数があり、これらの合計に基づいてバイナリ値のマトリックスを作成したいものを使用します。rowSum 配列変数は、各行のすべての 1 を追加した結果です。

だから、あなたが持っているなら

rowSum = [0,1,2]
colSum = [1,1,1]

次の配列を適切に構築する必要があります

matrix = [
 [0,0,0],
 [0,0,1],
 [1,1,0]
]

私は PHP でこのメソッドを使用しています。これは 3x3 マトリックスでは機能しますが、8x8 などのより大きなマトリックスでは機能しません。まず、rowSum 値を使用して行のすべての 1 を埋めます。次に、2 つの列の間違った合計値を見つけようとします。ピボットを使用して、colSum の正しい値を取得するまで、同じ行でそれらを交換します (1 つは cero 値)。しかし、2 つの列の同じ行で 1 と 0 を変更するには、基準をある程度制御する必要があるため、機能しません...

これは私が使用している方法です。

この行列があるとしましょう (N=3 -> NxN):

0  0  0
0  0  1
1  1  0

次に、次の配列があります

R0 = {0,1,2} //--> result of sums of each rows: ( 0+0+0, 0+0+1 , 1+1+0 )
C0 = {1,1,1} // ->sums of each columns

ステップ1

各行に R0(i) と同じ数の 1 を使用して、NxN 配列を作成して塗りつぶします。

0  0  0
1  0  0
1  1  0

この新しい行列の合計を計算します: R1 = {0,1,2} C1 = {2,1,0}

ステップ2

作成した行列の列和のすべての要素が C0 (原点) と同じ値を持っているかどうかを確認します

for ( i=0, N-1) do

 if C0(i)!=C1(i) then
   ReplaceColumn(i)
 end

end

列を置き換えるには、条件を掘り下げる必要があります。C0(0) = 1 != C1(0) = 2 最初の列の合計は、replace を呼び出す条件を満たしているので、

ステップ 3

分岐限定法を適用するための条件を選択し、グローバル条件 (すべての列の合計) を満たす列を変更するのに最適な行を見つけます。

列の合計の差の変化量は次のとおりです。

|C0(i)-C1(i)|

この例では |C0(0)-C1(0)| = 1 回の変更。変更によって列の合計の差が大きくなる場合は、戻る条件にする必要があります。

Σi,N(|C0(i)-C1(i)|)

では、この方法は本当に機能するのでしょうか?

4

1 に答える 1

1

行と列の合計を満たす行列を作成することが目標ですか、それともそれらを満たす行列を作成することですか? 質問からは分かりませんが、前者（「the」の場合）ならあり得ません。

この方法で任意の m × m 行列のビットを一意に表現できる場合を考えてみましょう。次に、次の仮想圧縮アルゴリズムを検討してください。

  • 2 2nビットのデータを取る
  • 2 n × 2 nビットとして扱う
  • データを記述するには、2 × 2 n行と列の合計を使用します。それぞれ最大で log 2 (2 n ) = n ビットを使用します。
  • データは 2 × n × 2 nビットに圧縮されます

2 × n × 2 n << 2 2nであり、このプロセスが繰り返される可能性があるため、ビットの任意の m × m 行列をその行と列の和だけで一意に表現できるという仮定は誤りです。

于 2015-01-20T20:12:36.177 に答える