4

3行x7列の単純な行列があると仮定しましょう。マトリックスには、次のようにゼロ（0）と（1）のみが含まれます。

1 0 1 1 1 0 0
0 0 1 1 0 0 0
0 0 1 0 1 1 0

セナリオ：各行の非ゼロの合計がわかっている場合、

（最初の行は4、2番目の行は2、3番目の行は3です。）（青い線）

さらに、各列の合計がわかっている場合（1、0、3、2、2、1、0）（緑色の線）

また、左上から右下への各対角線の合計（1,0,1,2,3,0,1,1,0）（赤い線）が反時計回りにわかっている場合

そして最後に、左下から右上への各対角線の合計（0,0,2,1,3,2,1,0,0）（黄色の線）がわかります。

ここに画像の説明を入力してください

私の質問は次のとおりです。これらの値を入力（および行列3x7の長さ）として使用すると、

4, 2, 3
1, 0, 3, 2, 2, 1, 0
1, 0, 1, 2, 3, 0, 1, 1, 0
0, 0, 2, 1, 3, 2, 1, 0, 0

最初のマトリックスをどのように描くことができますか？多くのことを考えた結果、これは3x7の未知の値といくつかの方程式を持つ線形方程式システムであるという結論に達しました。右？

これらの方程式を解くために、Cなどでアルゴリズムを作成するにはどうすればよいですか？ガウス方程式のような方法を使用する必要がありますか？

どんな助けでも大歓迎です！

4

4 に答える 4

2

最初の列から始めます。あなたは（赤と黄色のリストの最初の値から）上の値と下の値を知っています。緑のリストの最初からこれら2つの合計を引くと、中間値も得られます。

今、ちょうど右に働きます。

赤いリストの次の値から最初の列の中央の値を引くと、2番目の列の一番上の値が得られます。イエローリストの次の値から同じ中央の値を引くと、2番目の列の一番下の値が得られます。緑のリストの次の値からこれら2つの合計を引くと、2番目の列の中央の値が得られます。

等

これをコーディングする場合、最初の2つの列が特殊なケースであることがわかります。これにより、コードが見苦しくなります。各列の上部、下部、および中央の値を1つの方法で決定できるように、左側にすべてゼロの2つの「ゴースト」列を使用することをお勧めします。

これも簡単に一般化できます。（#rows）-1つのゴースト列を使用する必要があります。

楽しみ。

于 2012-01-29T03:43:25.730 に答える
2

特異値分解を使用して、行列形式の線形同次（および非同次）方程式のシステムに対する非ゼロ最小二乗解を計算できます。

簡単な概要については、以下を参照してください。

http://campar.in.tum.de/twiki/pub/Chair/TeachingWs05ComputerVision/3DCV_svd_000.pdf

最初に、システムをAx = bの形式の行列方程式として書き出す必要があります。ここで、xは列ベクトルとしての21の未知数であり、Aは乗算されたときに線形システムを形成する28x21の行列です。基本的に、線形方程式の行列Aを計算し、Aの特異値分解を計算し、式9.17に示すように結果を方程式に代入する必要があります。

CでSVDを計算するライブラリはたくさんあるので、マトリックスを定式化して9.17で計算を実行するだけで済みます。最も難しい部分は、おそらくすべてがどのように機能するかを理解することです。ライブラリSVD関数を使用すると、必要なコードは比較的少なくなります。

線形連立方程式を作成する方法を始めるために、単純な3x3の場合を考えてみましょう。

私たちのシステムが次の形式の行列であると仮定します

1 0 1
0 1 0
1 0 1

線形システムへの入力は次のようになります。

2 1 2             (sum of rows                 - row)
2 1 2             (sum of colums               - col)
1 0 3 0 1         (sum of first diagonal sets  - t2b)
1 0 3 0 1         (sum of second diagonal sets - b2t)

線形システムの行列を作成します

 A            a1 a2 a3 b1 b2 b3 c1 c2 c3     unknowns (x)    =   result (b)
sum of row 1 [ 1  1  1  0  0  0  0  0  0 ]      [a1]                [2]       
sum of row 2 [ 0  0  0  1  1  1  0  0  0 ]      [a2]                [1]
sum of row 3 [ 0  0  0  0  0  0  1  1  1 ]      [a3]                [2]
sum of col 1 [ 1  0  0  1  0  0  1  0  0 ]      [b1]                [2]
sum of col 2 [ 0  1  0  0  1  0  0  1  0 ]      [b2]                [1]
sum of col 3 [ 0  0  1  0  0  1  0  0  1 ]      [b3]                [2]
sum of t2b 1 [ 1  0  0  0  0  0  0  0  0 ]      [c1]                [1]
sum of t2b 2 [ 0  1  0  1  0  0  0  0  0 ]      [c2]                [0]
sum or t2b 3 [ 0  0  1  0  1  0  1  0  0 ]      [c3]                [3]
sum of t2b 4 [ 0  0  0  0  0  1  0  1  0 ]                          [0]
sum of t2b 5 [ 0  0  0  0  0  0  0  0  1 ]                          [1]
sum of b2t 1 [ 0  0  0  0  0  0  1  0  0 ]                          [1]
sum of b2t 2 [ 0  0  0  1  0  0  0  1  0 ]                          [0]
sum of b2t 3 [ 1  0  0  0  1  0  0  0  1 ]                          [3]
sum of b2t 4 [ 0  1  0  0  0  1  0  0  0 ]                          [0]
sum of b2t 5 [ 0  0  1  0  0  0  0  0  0 ]                          [1]

Axを乗算すると、線形連立方程式が得られることがわかります。たとえば、最初の行に不明な列を掛けると、次のようになります。

a1 + a2 + a3 = 2

あなたがしなければならないのは、方程式に現れる列のいずれかに1を入れ、他の場所に0を入れることです。

これで、AのSVDを計算し、その結果を式9.17に代入して、未知数を計算するだけです。

効率的に計算できるSVDをお勧めします。必要に応じて、行列Aを結果ベクトルb（A | b）で拡張し、Aを行階段形に縮小して結果を取得できます。

于 2012-01-30T20:28:36.347 に答える
1

10x15の1と0の配列の場合、値が1または0に制限されていることを無視すると、150の未知数を見つけて、10 + 15 + 2 *（10 + 15-1）=73の方程式を作成しようとします。明らかに、それに基づいて独自のソリューションを持つ線形システムを作成することはできません。

それで、その制約はユニークな解決策を与えるのに十分ですか？

次の合計を持つ4x4行列の場合、2つの解決策があります。

- 1 1 1 1
| 1 1 1 1
\ 0 1 1 0 1 1 0
/ 0 1 1 0 1 1 0

0   0   1   0 
1   0   0   0 
0   0   0   1 
0   1   0   0 

0   1   0   0 
0   0   0   1 
1   0   0   0 
0   0   1   0

したがって、より大きな行列に対して独自の解決策があるとは思いません。同じ対称性が多くの場所に存在します。

- 1 1 0 0 1 1
| 1 1 0 0 1 1
\ 0 1 0 0 1 0 1 0 0 1 0
/ 0 1 0 0 1 0 1 0 0 1 0

0   0   0   0   1   0 
1   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   1 
0   1   0   0   0   0 

0   1   0   0   0   0 
0   0   0   0   0   1 
0   0   0   0   0   0 
0   0   0   0   0   0 
1   0   0   0   0   0 
0   0   0   0   1   0
于 2012-01-31T23:13:01.930 に答える
0

別のバリエーションとしてこれはどうですか

Count the amount of unknown squares each sum passes through   
While there are unsolved cells
   Solve all the cells which are passed through by a sum with only one unknown square
       Cells are solved by simply subtracting off all the known cells from the sum
   Update the amount of unknown squares each sum passes through

境界のケースはありませんが、前の回答と非常によく似ています。これにより、最初にすべてのコーナーが解決され、次にコーナーに隣接するコーナーが解決され、次にそのコーナーからさらに1ステップ内側に解決されます...

編集：また、合計がゼロのパスをゼロにします。これにより、解決可能なパスが解決されます（私は思います）

于 2012-01-30T18:26:22.583 に答える