私はかなり典型的な問題を抱えていると思います。ここに同様のトピックがあったことは知っていますが、私が初心者であり、この問題の異なるバージョンを区別していないことを理解してください。テキストとアルゴリズムのわずかな違いが完全に異なる場合があります。問題は次のとおりです。
For a given 2<=a,b<=1000 and 1<=c<=Min(a,b) find in matrix a x b square c x c
with the largest sum of elements. The elements in matrix are from -1000 to 1000.
行列全体を実行し、すべての点 (x,y) で平方 (x,y)、(x+c,y)、(x,y+c)、(x+ c,y+c)。それから私は最大の合計を選びました。これらの制約により、かなり高速になると思いますが、より高速なアルゴリズムはありますか? アルゴリズムの複雑さを数えるのは苦手ですが、O(a*b*c*c) のようです。そして、最悪の場合、私が間違っていなければ止まらないかもしれません..
これにアプローチする正しい方法は、最初に積分変換を行うことだと思います。元の行列 M の各要素 (i,j) について、積分変換行列 を計算しI(i,j) = sum[0..i, 0..j](M)ます。行方向と列方向の両方で合計を実行すると、O(a*b) 時間でこれを実行できます。
積分変換を取得したら、サブブロックの合計を一定時間で次のように計算できます。
sum[i0..i1, j0..j1](M) = I(i1,j1) - I(i0 - 1, j1) - I(i1, j0 - 1) + I(i0 - 1, j0 - 1)
そのため、合計 O(a*b) について、一定時間で各 cxc 平方和を計算して比較できます。
ここで述べたスライド アプローチを使用すると、複雑さが軽減されると思います。あなたの場合、a、b、cは各最適化問題で一定であると仮定します（つまり、cは最適化変数ではありません）。
1) 左上隅から開始、O(c*c)
2) 左端の列を削除し、右端の列を追加した後、右にスライド O(c)
3) (2) を (ac) 回繰り返すので、O(c*(ac))
4) (1)-(3) O(c*c + c*(ac)) 程度のコスト
5) 下にスライドして、他の (bc) 行についてもこれを行う必要があります。それぞれの行は、下にスライドするのに O(c)、行を完成させるのに O(c*a) かかり、合計で O( c* c + c*(ac) (bc) + c (ac) + c*(bc) )
6) a,b>>c と仮定すると、O(b*c*a) に単純化できます。
何か問題がある場合はお知らせください。
あなたのソリューションは機能し、時間の複雑さについては正しいです。実際、それは a*b*c*c です。少し高速化する 1 つの方法は、c*c ウィンドウをスライドさせたときに、すべてを再計算するのではなく、ウィンドウの外に出ているものだけを差し引き、中に入っているものを足すことです。窓。これは x 方向と y 方向の両方で実行できるため、将来のルックアップのために列 (または行) のすべての c*c 平方の合計を覚えておくとよいでしょう。