4

以下の問題に対して効率的なアルゴリズムを発明しようとしていましたが、失敗したと思います。異なる数と整数k（k <= n）を持つボードn * nが与えられます。ボード内に含まれる平方k * kを見つける必要があります。ここで、異なる数の量が最大になります。それらの例の場合：

n = 4 k = 3
10 9 8 1
7 6 5 7
5 3 0 2
3 4 1 3

n = 4 k = 2
1 2 1 2
2 1 2 1
1 2 1 2
2 1 3 4

答えは次のとおりです。

9 8 1
6 5 7
3 0 2

1 2
3 4

この問題（C ++）の私の解決策は、左上隅の最初の正方形k * kを選択し、数値（キー）をその出現頻度（値）にリンクするマップを作成することに基づいています。次に、マップ内の正方形の最初の列を削除し、次の列を追加して、正方形をさらに1列移動します。右側に着いたら、1列下に移動して境界線まで左に移動します。次に、一歩下がって、国境まで右に進みます。そして、私が最後に到達するまで、以下同様です。答えは、特定の瞬間のマップの最大サイズに基づいています。このソリューションの発明は非常に不十分であると思います（ただし、ブルートフォースよりも優れている可能性があります）。提案をいただければ幸いです。この問題は、修正された最大長方形の問題に何らかの形で単純化できますか？（http://www.drdobbs.com/database/184410529）



ダニエレの提案に従って編集（追加の詳細）

最初に、私のアルゴリズムは最初のk * kの正方形、つまり10 98|を分析します。7 6 5 | 5 30。各要素が分析されると、適切なデータがマップに書き込まれます。したがって、最初はペア（10-> 1）（10番が1回出現）があり、次に（9-> 1）、（8-> 1）、（7-> 1）、（6-> 1）、 （5-> 1）。次に、次の5に会うので、その発生を2に変更します（5-> 2）。そして最後に（3-> 1）、（0-> 1）を追加します。実際、私のマップには8つの要素が含まれています（前述のように、5つは2回発生したため）。この正方形の座標と地図のサイズを覚えています。k*kの正方形を1列右に移動します。したがって、マップの最初の列から要素の外観を減らします。そこで、ペア（10-> 1）と（7-> 1）を削除し、（5-> 2）を（5-> 1）に変更します。そして最後の列を追加します：（1-> 1）、（7-> 1）および（2-> 1）（すべての数字が新しいため）。ここで、マップのサイズが以前よりも大きくなっていることに注意してください（9> 8）。そのため、現在の座標を古い座標の上に保存します。実際、ここでアルゴリズムを終了します（追加の条件：if（map.size（）== k * k）end;）が、それ以外の場合は、境界線まで左よりも1行下に「移動」します。可能なすべてのk*k二乗の分析を終了しました。

実際、私のソリューションはテストシステムによって拒否されたため、時間の消費という点でより良いソリューションを探しています（制限時間を超えています）。各正方形を1つずつ分析しないので、ブルートフォースよりも優れていると思いますが、間違っている可能性があります。とにかく、それはまだ十分ではありません。

簡単になる場合に備えてC++コードを添付することもできますが、役立つとは思えません。アルゴリズムの提案を探しています。

4

1 に答える 1

1

O(n * n * k * log k)あなたのアルゴリズムは、時間計算量とO(k * k)メモリを備えて、かなり良い音に聞こえます。log k値が小さい整数であることがわかっている場合は、マップを配列に置き換えることで、を取り除くことができます。そうしないと、アルゴリズムを実装するコードが非効率になる可能性があります。変化に応じてコードのタイミングを調整nしk、時間が期待どおりに長くなるかどうかを確認してください。

別の可能な方向として、動的計画法スタイルのソリューションを試すことができます。に固定されたx長方形f(x, y, a, b)の一意の値のセット（場合によってはビットマップ）を計算する関数を定義します。次に、問題はの最大値を見つけることです。は、約x次元の4つ以上の小さい長方形セットの和集合として計算されます。小さい長方形のセットがキャッシュされている場合は、それらを再計算し続ける必要はありません。キャッシュには多くのメモリが必要ですが、2サイズの累乗を使用するように分解を調整することで、キャッシュを制限できます。例えば、ab(x, y)|f(x, y, k, k)|f(x, y, a, b)a/2b/2

  f(x, y, 21, 21) = f(x, y, 16, 16)
                    union f(x + 16, y, 4, 16)
                    union f(x + 20, y, 1, 16)
                    union f(x, y + 16, 16, 4)
                    union f(x, y + 20, 16, 1)
                    union f(x + 16, y + 16, 4, 4)
                    union f(x + 20, y + 16, 1, 4)
                    union f(x + 16, y + 20, 4, 1)
                    union f(x + 20, y + 20, 1, 1)

kこのアプローチはO（n * n * log k * log k）に似ているので、1000より大きいなどの大きな値に対してのみ効果があると思います。

于 2012-06-16T03:36:34.760 に答える