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++，因此我提供了此代码。这是一种蛮力技术，绝对不是这个问题的理想解决方案。对于一个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 回答
1

因为您只想知道给定矩阵是否在另一个大矩阵内。如果您知道如何在 C++ 中使用 Matlab 代码，您可以直接使用 Matlab中的代码ismember。另一种方法可能是尝试弄清楚 ismember 在 Matlab 中是如何工作的，然后在 C++ 中实现相同的东西。

请参阅查找子矩阵的位置

于 2013-05-25T15:17:07.087 回答
1

如果要多次查询相同的大矩阵和相同大小的子矩阵。预处理大矩阵有很多解决方案。

这里有一个类似（甚至相同）的问题。

在 MXN 矩阵中查找 amxn 子矩阵的最快方法

于 2013-05-25T14:59:15.393 回答
1

deepu-benson的修改代码

int Ma[][5]= {
        {0, 0, 1, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {1, 1, 1, 1, 0}
    };


    int Su[][3]= {
        {1, 0, 0},
        {1, 0, 0},


    };

    int S = 5;// Size of main matrix row
    int T = 5;//Size of main matrix column
    int M = 2; // size of desire matrix row
    int N = 3; // Size of desire matrix column

int flag, i,j,p,q;

for(i=0; i<=(S-M); i++)
{
   for(j=0; j<=(T-N); j++)
   {
      flag=0;
      for(p=0; p<M; p++)
      {
         for(int q=0; q<N; q++)
         {
            if(Ma[i+p][j+q] != Su[p][q])
            {
               flag=1;

               break;
            }
         }
      }
      if(flag==0)
      {
           printf("Match Found in the Main Matrix at starting location %d, %d",(i+1) ,(j+1));
         break;
      }
   }
   if(flag==0)
   {
        printf("Match Found in the Main Matrix at starting location %d, %d",(i+1) ,(j+1));
      break;
   }
}
于 2015-05-19T10:11:46.820 回答
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) 计算第一部分。

第二部分像往常一样在 O(sizeof(F)) 中计算，小于 O(N*M)。

第三部分是最有趣的。它是卷积，可以使用快速傅里叶变换在 O(N*M*(logN+logM)) 中计算：http ://en.wikipedia.org/wiki/Convolution#Fast_convolution_algorithms

于 2013-05-25T18:23:34.397 回答
0

如果矩阵中的数据不是随机分布的，那么对其进行一些统计分析会很有帮助。然后，您可以通过比较其逆概率范围内的元素来找到子矩阵。它可能会更快，然后是普通的蛮力。

说，你有一些正态分布整数的矩阵，高斯中心在 0。你想找到子矩阵说：

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

您必须开始搜索 198，然后检查右上角的元素为 43，然后检查右上角的 -12，然​​后任何 3 或 -3 都可以；等等。与最残酷的解决方案相比，这将大大减少比较次数。

于 2013-05-25T17:46:25.920 回答
0

我原来的答案在break下面，想想有几个优化，这些优化指的是原来答案的步骤。

对于步骤 B)，不要搜索全部S：您可以折扣所有不允许F适合的列和行。（在下面的例子中，只搜索左上角的 2x2 矩阵）。在其中F很大一部分的情况下，S这将节省大量时间。

如果其中的值范围S非常小，则创建查找表将大大减少步骤 B) 所需的时间。

使用这两个矩阵

找到垫子2里面 垫子1

A) 从较小的矩阵中选择一个值：

mat4

B) 将其定位在较大的范围内

mat3

C) 检查相邻单元格是否匹配

mat6-mat5

于 2013-05-25T15:43:22.627 回答
0

大部分答案取决于你重复做的事情。您是否正在为同一个子矩阵测试一堆巨大的矩阵？您是否正在测试一个巨大的矩阵来寻找一堆不同的子矩阵？

是否有任何矩阵具有重复模式，或者它们是否很好且随机，或者您可以不对数据做出任何假设？

另外，子矩阵是否必须是连续的？S 是否包含

F3 = 1 3
     7 9
于 2013-05-25T15:45:02.383 回答