c++ - グリッドでの効率的なアプローチ

Question

問題:サイズ m*n の 2D グリッドをセット S の文字で埋めて、結果のグリッド内の個別のサブマトリックスの数が特定の数 k に近くなるようにする必要があります。この質問はhttp://www.codechef.com/JULY14/problems/GERALD09
から派生したものです

制限:
1<=n,m<16
1<=k <=m*n*m*n
|S|=4
制限時間=0.1 秒

仮定: 2 つのサブマトリックスは、次元が同じでない場合、または対応する位置の少なくとも 1 組の文字が一致しない場合、区別されます。

私のアプローチ:許容可能な解決策が見つかっている間、ランダムなグリッドとループから開始し、各反復で、現在の状態に応じてランダム性を増減できます (ただし、局所最適状態にとどまる可能性があります)。

しかし、問題は、サブグリッド内の異なるサブマトリックスの数を計算する効率的な方法がわからないことです。かなり高速なカウントのためにハッシュを試みました ( O(n ² m ² ) *生成/検索のコストサブグリッドのハッシュ値)。しかし、このアプローチはハッシュ値の衝突のために正確な答えを与えません.@Vaughn Catoのコメントを使用して修正した後でも、最適な状態を見つけるために15〜25回の反復を実行できますが、それでは十分ではありません.

最近、シミュレーテッド アニーリングを使用して、この種の問題を解決できることを知りました。
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
この最適化問題を解決するための効率的なアプローチを探しています。

前もって感謝します。

Answer 1

彼らはいつか社説を投稿すると思いますが、この特定の問題について考えられるアイデアは次のとおりです。

n特定の および で可能な部分行列のすべての可能な数をローカルで生成しmました。n=m=3私は可能性から抜け出しただけだから11です。可能な値しか得られなかったからです81。さらに、値を生成したとき、最初にすべての可能なオプションを取得しました-可能性のない行列の後、すでにそれらを持っていました。（辞書順に生成しました）n=3,m=4191441926300016M

したがって、考えられる解決策の 1 つは、与えられたとKに対して達成できる の異なる値をできるだけ多く事前計算し、乱数発生器のシードを保存するか、トリプレットごとに文字が必要になるように他の方法で保存することです。特定のテスト ケースでは、隣接する 2 つの値をチェックするだけです。nmO(1)n-m-kk

さらに、可能なK値の数は多くないため、別の方法でそれらを生成できる可能性があります: テーブルのすべての可能な値と適切なテーブルが与えられKたnxm場合、次の行の値をバックトラックすることしかできません。Kforのすべての異なる値を持つすべての可能な行列を取得しようとしますnx(m+1)。