6

私は非常に大きなn*m行列を持っていSます。Fの中に部分行列が存在するかどうかを効率的に判断したいS。大きな行列Sのサイズは まで500*500です。

明確にするために、次のことを考慮してください。

S = 1 2 3 
    4 5 6
    7 8 9

F1 = 2 3 
     5 6

F2 = 1 2 
     4 6

このような場合には：

  • F1内側にありますS
  • F2中にありませんS

行列の各要素は32-bit整数です。Fが の部分行列であるかどうかを見つけるために、ブルート フォース アプローチを使用することしか考えられませんS。効果的なアルゴリズムを見つけるためにグーグルで検索しましたが、何も見つかりません。

それをより速く行うためのアルゴリズムまたは原則はありますか? (または、ブルート フォース アプローチを最適化する方法はあるのでしょうか?)

PS 統計データ

A total of 8 S
On average, each S will be matched against about 44 F.
The probability of success match (i.e. F appears in a S) is 
19%.
4

9 に答える 9

2

これには、行列の前処理が含まれます。これはメモリに負担がかかりますが、計算時間の点では優れているはずです。

  • チェックを行う前に、サブマトリックスのサイズがマトリックスのサイズよりも小さいかどうかを確認してください。
  • 行列を作成するときに、行列の値を行列の (x,y) 位置の配列にマップする構成を作成します。これにより、候補が存在する可能性のあるサブマトリックスの存在を確認できます。サブマトリックスで (0,0) の値を使用し、より大きなマトリックスでこの値の可能な位置を取得します。ポジションのリストが空の場合、候補者はいないため、サブマトリックスは存在しません。開始点があります (ただし、経験豊富な人はこれを素朴なアプローチと考えるかもしれません)。
于 2013-05-25T15:05:22.223 に答える
1

特定の行列が別の大きな行列の中にあるかどうかだけを知りたいからです。C++ から Matlab コードを使用する方法を知っている場合はismember、Matlab から直接使用できます。もう 1 つの方法は、ismember が Matlab でどのように機能するかを理解しようとしてから、同じことを C++ で実装することです。

サブマトリックスの位置を見つけるを参照してください

于 2013-05-25T15:17:07.087 に答える
1

質問にC++もタグを付けたので、このコードを提供します。これは強引な手法であり、この問題の理想的な解決策ではありません。S X Tメイン マトリックスとM X Nサブ マトリックスの場合、アルゴリズムの時間計算量はですO(STMN)。

cout<<"\nEnter the order of the Main Matrix";
cin>>S>>T;
cout<<"\nEnter the order of the Sub Matrix";
cin>>M>>N;

// Read the Main Matrix into MAT[S][T]

// Read the Sub Matrix into SUB[M][N]

for(i=0; i<(S-M); i++)
{
   for(j=0; j<(T-N); j++)
   {
      flag=0;
      for(p=0; p<M; p++)
      {
         for(q=0; q<N; q++)
         {
            if(MAT[i+p][j+q] != SUB[p][q])
            {
               flag=1;
               break; 
            }
         }
         if(flag==0)
         {
            cout<<"Match Found in the Main Matrix at starting location "<<(i+1) <<"X"<<(j+1);
            break;
         }
      }
      if(flag==0)
      {
         break;
      }
   }            
   if(flag==0)
   {
      break;
   }
}
于 2013-05-25T15:44:07.223 に答える
0

で可能ですO(N*M*(logN+logM))。

等しいことは、差の二乗和が 0 であると表すことができます。

sum[i,j](square(S(n+i,m+j)-F(i,j)))=0
sum[i,j]square(S(n+i,m+j))+sum[i,j](square(F(i,j))-2*sum[i,j](S(n+i,m+j)*F(i,j))=0

最初の部分は、移動平均と同様に、O(N*M) のすべての (n,m) に対して計算できます。

2 番目の部分は、O(N*M) より小さい O(sizeof(F)) で通常どおり計算されます。

第三部が一番面白い。高速フーリエ変換を使用して O(N*M*(logN+logM)) で計算できる畳み込みです: http://en.wikipedia.org/wiki/Convolution#Fast_convolution_algorithms

于 2013-05-25T18:23:34.397 に答える
0

私の元の答えは休憩の下にあり、いくつかの最適化があると考えています。これらの最適化は元の答えのステップを参照しています。

ステップ B) では、全体を検索しないでください。収まらSないすべての列と行を割り引くことができますF。(以下の例では、左上の 2x2 マトリックスのみを検索します)。Fこれがかなりの割合である場合は、Sかなりの時間を節約できます。

値の範囲Sが非常に狭い場合は、ルックアップ テーブルを作成すると、手順 B) に必要な時間が大幅に短縮されます。

これらの 2 つのマトリックスの操作

マット2中 を見つけるマット1

A) より小さい行列から 1 つの値を選択します。

マット4

B）より大きな範囲内に配置します

マット3

C）隣接するセルをチェックして、それらが一致するかどうかを確認します

mat6-マット5

于 2013-05-25T15:43:22.627 に答える
0

答えの多くは、繰り返し行っていることによって異なります。同じサブマトリックスに対して多数の巨大なマトリックスをテストしていますか? 多数の異なる部分行列を探して、1 つの巨大な行列をテストしていますか?

行列の中に繰り返しパターンがあるものはありますか?それとも適切でランダムなものですか?それともデータについて何も仮定できないでしょうか?

また、部分行列は連続している必要がありますか? Sは含まれていますか

F3 = 1 3
     7 9
于 2013-05-25T15:45:02.383 に答える
0

マトリックス内のデータがランダムに分散されていない場合は、統計分析を実行すると役立ちます。次に、その要素の範囲を逆確率で比較することにより、サブマトリックスを見つけることができます。単純なブルートフォースよりも高速である可能性があります。

たとえば、ガウス中心が 0 の正規分布整数の行列があるとします。そして、部分行列を見つけたいとします。

1 3 -12
-3 43 -1
198 2 2

198 の検索を開始し、右上の要素が 43 であることを確認し、次にその右上の要素が -12 であることを確認する必要があります。その後、任意の 3 または -3 で十分です。等々。これにより、最も残忍なソリューションと比較して、比較の数が大幅に削減されます。

于 2013-05-25T17:46:25.920 に答える