これが私の問題の視覚化です：
正方形に保管されている最も価値のある菱形を見つける必要があります。私はこれについて数日間考えていますが、今まで、「forループ」を使用してすべての菱形をチェックする以外に何も見つけることができませんでした. 皆さんはそれについてどう思いますか? それは私がそれを作ることができる唯一の方法ですか？:Pありがとう:)
2 に答える
1
問題がダイヤモンド形の「カーネル」で最大の合計を見つけることである場合、はい、より高速なアルゴリズムがあります。
ペネロペによって提案されたアルゴリズムは良い出発点ですが、菱形のサイズが大きくなると、部分和の入力と出力に必要な数が増えます。これは、値を 2 方向で斜めに積分する 2 次元の最初のパスで回避できます。
[ a b c d] --> integrate a, a+f, a+f+k, a+f+k+p right down
[ e f g h] then integrate the elements in positions c,f,i etc.
[ i j k l]
[ m n o p]
整列された正方形の合計を見つけることと比較した場合のこのアプローチの欠点は、(x+y) が奇数で (x+y) が偶数の対角線の別のセットを計算する必要があることです。結果は、4 ではなく 8 つの積分和をサンプリングすることから得られます。
左から右、上から下を統合する方法（合計面積）が最も理解しやすいと思います
[1 2 0 3] [1 3 3 6] here every cell contains the summed area
[0 0 1 1] [1 3 4 8] of M[I][J] := sigma i=0..I,j=0..J m[i][j]
[1 0 3 1] --> [2 4 8 13]
[0 1 1 1] [2 5 10 16]
area(8..16,100..983) を取得するには、コーナー要素のみにアクセスする必要があります。
Sigma i=8..16,j=100..983 m[i][j] :== M[7][99]+M[16][983]-M[7][983]-M[16][99]
統合する形状を 45 度回転させると、2 組の積分を計算する必要があります。これがチェス盤だったら、白と黒のマスを別々に。次に、各菱形は、一方のマトリックス M_odd からの N*N サイズの合計領域と、もう一方の合計領域マトリックス M_even からの (N-1)*(N-1) サイズの合計領域 (またはその逆) で構成されます。これは、同じ複雑さで任意の菱形サイズにスケーリングします。(そして、N=1 または N=2 の場合に行列 m から要素を加算し、N>2 の正方形に行列 M を使用する最適化の可能性がある)。
コメント: おそらくこれはペネロペが示唆したものと同じですが、5 要素菱形から任意のサイズへの一般化が不足しているため、わかりませんでした。
于 2012-10-10T15:23:45.670 に答える
1
ここに私の考えがあります：
最初の反復では、行列を横断しますが、斜めに横断します。ひし形 (またはひし形の側面) に適合する最も左上の場所から開始し、ひし形のサイズによってカバーされる要素を調べます。
- 要素 (0,1) と (1,0) を調べることから始めます(a)
- 次に (0,2) と (1,1) を調べます(b)
- (1,1)、(2,0) (b)
- (0,3)、(1,2) (c)
- (1,2)、(2,1) (c)
- ...
受験票が届くことを願っています。この要素で行うことは、それらを合計することです: e(0,1) + e(1,0) = 11、e(0,2) + e(1,1) = 3など。同じ行 (上で同じ文字でマークされたもの) の要素を操作している場合、合計を最初から計算し直す必要がないことに注意する必要があります。であるため、2 つの要素のみにアクセスして新しい合計を取得します。
2 回目の反復では、行列を斜めにトラバースしますが、別の側からトラバースします。右上隅から開始し、以前に計算された合計に取り組みます。したがって、調べる最初のペアは(0,3), (1,4) になります。前に行ったのとまったく同じことを行います。合計を再度計算します。
ここで、2 回目の反復の最後に、処理されたすべてのフィールドには、実際には、そのフィールドに上隅があるまばらな菱形の合計が含まれます。3x3 菱形の例を以下の画像に示します。
3 番目のステップ画像から、サイズnの疎菱形が別の疎菱形 (サイズ(n-1)のもの) を「欠落」していることがわかります。反復 1 と 2 は、画像内のサイズnのすべてのまばらな菱形の合計を求める手順とまったく同じです。したがって、3 番目のステップとして、1 回目と 2 回目の反復を再度実行しますが、検索しているサイズ ( n ) ではなく、代わりにサイズ(n-1)を使用します。サイズ 1 の「検索」は入力行列に等しいことに注意してください (たとえば、n=2 の場合、3 番目のステップでは何も計算する必要はありません)。
最後に、一番上の位置 (0,2) にある 3x3 菱形の興味深い合計は、最初の 2 つの反復からの (0,2) での合計と、3 番目のステップからの (1,2) での合計です。 . これら 2 つを一緒に追加できます。位置 (x,y) にある最初の 2 つのパスの結果マトリックスのすべての要素に対して、3 番目のステップの結果マトリックスから位置 (x,y+1) に要素を追加します。次に、最大値を見つけるだけで、菱形の最大値と位置の両方についての答えが得られます。
これをすべて 4 回のパスで実行します (2 回目のパスを計算するときに最大値を追跡できます)。これにより、正方形のサイズがO(4*n^2) = O(n^2)どこにあるかという複雑さが生じます。n
明確であることを願っています。回答を台無しにしてしまった場合は、説明を求めてください。
2x2菱形の例
1 回目のパス
-1 11 3 7 5 * / * * *
-1 9 14 12 3 / * * * *
-1 12 18 4 6 * * * * *
-1 11 3 6 2 * * * * *
-1 -1 -1 -1 -1 * * * * *
2回目のパス
-1 25 15 10 -1 * * * \ *
-1 27 18 18 -1 * * * * \
-1 15 24 6 -1 * * * * *
-1 -1 -1 -1 -1 * * * * *
-1 -1 -1 -1 -1 * * * * *
3番目のステップ
n=1であるため、3 番目のパスでは何も計算する必要がなく、3 番目のパスの出力は入力行列です。
1 2 2 2 2
9 1 5 3 1
8 9 9 2 3
3 9 2 3 1
2 1 3 1 1
ここで、2 番目の反復の出力を 3 番目のステップの出力 (1 桁上にシフト) と合計する必要があります。我々が得る：
-1 26 20 13 -1
-1 36 27 20 -1
-1 24 26 9 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
答え 上隅が (1,1) にあるひし形が最も価値があり、合計は 31 です。
注: -1は菱形の辺が収まらないところです --未定義の和です。プログラムで任意の方法でマークできます (特に、マトリックスに実際に負の値を含めることができる場合)。2 番目のパスでは、未定義の要素を持つ合計をundifinedに設定できます。
注 2:菱形のサイズに関係なく、菱形側をマトリックスにスライドさせると、常に 1 つの数値が入力され、別の数値が合計から出てきます (新しい行を入力する場合を除く)。
注 3 : 2 パス目と 2 パス目の菱形の最初の位置は、/またはで配列にマークされます。\
例 3x3 ひし形
同じ行列で 3x3 菱形を実行して、2x2 菱形だけでなく、一般的な場合 ( は正方形のサイズ) が複雑であることを示しO(n^2)ますn。
z[][]最初のパスf[][]と 2 番目のパスの後の入力行列を呼び出しましょう。s[][]
1 回目のパス
f[0][2] = z[0][2] + z[1][1] + z[2][0] == 11(a)f[0][3] = z[0][3] + z[1][2] + z[2][1] == 16(ロ)f[1][2] = f[0][3] - z[0][3] + z[3][0] == 17(ロ)f[0][4] = z[0][4] + z[1][3] + z[2][2] == 14(c)f[1][3] = f[0][4] - z[0][4] + z[3][1] == 21(c)f[2][2] = f[1][3] - z[1][3] + z[4][0] == 20(c)f[1][4] = z[1][4] + z[2][3] + z[3][2] == 5(ニ)f[2][3] = f[1][4] - z[1][4] + z[4][1] == 5(ニ)f[2][4] = z[2][4] + z[3][3] + z[4][2] == 9(e)
すべての要素に最大 1 回アクセスします。異なる文字でマークされているのは、同じ行の合計です。行の最初の合計では、菱形の側にある要素と同じ数の要素を合計する必要があります。これmをm x m菱形と呼びましょう。行の 1 つおきの合計では、常に正確に 3 つの要素にアクセスする必要があります。前の合計、出て行く要素 (-符号のある要素)、および入る要素 (+符号) です。
-1 -1 11 16 14
-1 -1 17 21 5
-1 -1 20 5 9
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
2回目のパス
次に、2 番目のパスで同様のことを行います (書き出すつもりはありません)。要素が少し少ないだけです。
-1 -1 41 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
3番目のステップ
この手順は、2x2 の例の1 回目と2 回目の反復とまったく同じです。したがって、2x2 のスパース菱形の合計は次のようになります。
-1 25 15 10 -1
-1 27 18 18 -1
-1 15 24 6 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
そして、それを2 回目の反復の出力と合計すると、次のようになります。
-1 -1 59 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
答え行列に収まる 3x3 の菱形は 1 つだけなので、行列に残る要素は 1 つだけです。これは、ちょうど収まる唯一の菱形の合計である 59 です。
于 2012-10-10T12:59:33.747 に答える