我有一個非常大的n*m矩陣S。我想要有效地確定在S內是否存在子文件F。大矩陣S的尺寸可以大到500*500。在大矩陣中找到矩陣
爲了澄清，考慮以下幾點：
S = 1 2 3
4 5 6
7 8 9
F1 = 2 3
5 6
F2 = 1 2
4 6
在這種情況下：
F1是內部SF2不是內部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%.
如果您想查詢多次對同一個大矩陣，相同大小的子陣。有很多解決方案來預處理大矩陣。
一個類似的（或者甚至是相同的）問題在這裏。
它包括預處理矩陣。這會對內存造成很大影響，但在計算時間方面應該更好。
由於您只想知道給定的矩陣是否在另一個大矩陣內。如果你知道如何使用C++的Matlab代碼，你可以直接使用Matlab的ismember。另一種方法可能會試圖找出ismember如何在Matlab中工作，然後在C++中實現相同的功能。
我原來的答覆是跌破，想着它有幾個的優化，這些優化技術指的是原來的答案的步驟。
對於步驟B）不要搜索整個S：您可以折扣所有不允許F適合的列和行。 （在下面的例子中，只搜索左上方的2x2矩陣）。在F是S的重要比例的情況下，這將節省相當多的時間。
如果S範圍內的值非常低，那麼創建一個查找表將大大減少步驟B）所需的時間。
與這些2點矩陣工作
找到
內部
A）選擇從較小的矩陣的一個值：
B）內的較大的定位它
C）檢查相鄰單元，看看它們是否匹配
- 
但他正在處理500 * 500的矩陣。 –
既然你已經標記了一個問題，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;
}
}
很多答案取決於你在做什麼重複。你在爲同一個子矩陣測試一堆巨大的矩陣嗎？你在測試一個巨大的矩陣尋找一堆不同的子矩陣嗎？
是否有任何矩陣具有重複模式，或者它們是否漂亮隨機，或者您可以不對數據做任何假設？
另外，子矩陣必須是連續的嗎？ S是否包含
F3 = 1 3
7 9
該矩陣應該是連續的並且聚集在一起，並且我已經將其他信息添加到問題的底部。 –
如果矩陣中的數據不是隨機分佈的，對它進行一些統計分析將會有所幫助。然後你可以通過比較它的元素和他們的逆概率來找到子矩陣。它可能會更快，然後是一個普通的暴力。
說，你有在0高斯中心一些正態分佈整數的矩陣，你想找到小矩陣說：
1 3 -12
-3 43 -1
198 2 2
你必須開始尋找198，然後檢查右上元素爲43，那麼它的右上角爲-12，那麼任何3或-3都可以;等等。與最殘酷的解決方案相比，這將大大減少比較的次數。
有可能在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 *（10即+ 10gm的））使用快速傅立葉卷積：http://en.wikipedia.org/wiki/Convolution#Fast_convolution_algorithms
修改的代碼迪普 - 本森
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;
}
}
在你的榜樣，會矩陣[1,3; 7,9]（也就是角落）被認爲是在S內部？ –
不，它必須被收集在矩陣中 –
矩陣應該連續並聚集。 –