знайсці матрыцу ў вялікі матрыцы

У мяне ёсць вельмі вялікі п * м матрыца 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 is inside S
  • F2 is not inside S

Кожны элемент у матрыцы з'яўляецца 32-бітнага цэлага ліку. Я магу думаць толькі з дапамогай грубай сілы падыход знайсці Ці 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
Не, ён павінен быць сабраць у матрыцы
дададзена аўтар Jason, крыніца
Матрыца павінна быць бесперапыннай і сабраныя.
дададзена аўтар Jason, крыніца
У нашым прыкладзе, будзе матрыца [1,3; 7,9] (гэта значыць толькі па кутах) лічыцца ўнутры S?
дададзена аўтар Peter de Rivaz, крыніца

9 адказы

Так як вы адзначылі гэта пытанне як C ++ таксама, я забяспечваю гэты код. Гэта грубая сіла тэхнік і, безумоўна, не з'яўляецца ідэальным рашэннем для гэтай задачы. Для S Х Т Галоўны Матрыца і М Х Н Sub Матрыца, часовая складанасць алгарытму Аб (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<<"Match Found in the Main Matrix at starting location "<<(i+1) <<"X"<<(j+1);
            break;
         }
      }
      if(flag==0)
      {
         break;
      }
   }            
   if(flag==0)
   {
      break;
   }
} 
1
дададзена

Яна ўключае ў сябе папярэднюю апрацоўку матрыцы. Гэта будзе цяжка на памяць, але яна павінна быць лепш з пункту гледжання часу вылічэнняў.

  • Праверце, калі памер подматрицы менш, чым у матрыцы, перш чым зрабіць чэк.
  • Пры пабудове матрыцы, пабудаваць канструкцыю, якая адлюстроўвае значэнне ў матрыцы на масіў (х, у) пазіцыі ў матрыцы. Гэта дазволіць вам праверыць існаванне подматрицы, дзе кандыдаты можа існуе. Вы б выкарыстоўваць значэнне ў пункце (0,0) у подматрице і атрымаць магчымыя пазіцыі гэтага значэння ў большай матрыцы. Калі спіс пазіцый пусты, у вас няма кандыдатаў, і такім чынам, суб-матрыца не існуе. Там гэта пачатак (Больш дасведчаныя людзі <�моцны> можа разгледзець гэты наіўны падыход, аднак).
1
дададзена

Так як вы толькі хочаце ведаць, ці з'яўляецца дадзеная матрыца ўнутры іншы вялікі матрыцы. Калі вы ведаеце, як выкарыстоўваць Matlab код з C ++, вы можаце напрамую выкарыстоўваць IsMember з Matlab. Іншы спосаб можа быць паспрабаваць высветліць, як IsMember працуе ў Matlab, а затым рэалізаваць тое ж самае ў C ++.

See Find location of submatrix

1
дададзена
<�Р> Зменены Кодэкс Дып-Бенсон
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
1
дададзена
Прывітанне, у мяне ёсць адна матрыца, як 20 * 20 Іншы 3 * 3, але вынік не так, з дапамогай прыведзенага вышэй кода. Ці магу я ведаць, што ёсць якое-небудзь абмежаванне з кодам?
дададзена аўтар bob90937, крыніца
@ Bob90937 як такой я не адчуваў за вялікую матрыцу парадку, таму я не выйгрыш абмежаванні гэтага кода
дададзена аўтар Singhak, крыніца

Калі вы хочаце запытаць некалькі разоў для адной і той жа вялікай матрыцы і тым жа подматрицы памеру. Ёсць шмат рашэнняў предобработки вялікі матрыцы.

Аналагічны (ці нават той жа) праблема тут.

хуткім спосабу знайсці м й н подматрица ў М х N матрыц

1
дададзена

Калі дадзеныя ў матрыцы не размеркаваны выпадковым чынам, было б карысна, каб запусціць некаторыя статыстычны аналіз на ім. Тады вы маглі б знайсці суб матрыцы шляхам параўнання яе элемента вагаўся іх зваротнай верагоднасцю. Гэта можа быць хутчэй, то просты перабор.

Скажам, у вас ёсць матрыца некаторых нармальна размеркаваных лікаў з гауссовым цэнтрам у 0. І вы хочаце, каб знайсці подматрицы сказаць:

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

Вы павінны пачаць пошук 198, то праверка верхні правы элемент будзе 43, то яго верхняя правая для -12, то любы 3 ці -3 будуць рабіць; і гэтак далей. Гэта дазволіць значна скараціць колькасць параўнанняў у параўнанні з самым жорсткім рашэннем.

0
дададзена

Большая частка адказу залежыць ад таго, што вы робіце паўторна. Тэстуеш кучу велізарных матрыц для той жа подматрицы? Вы тэставанне адзін велізарны матрыцу шукае кучу розных подматрицы?

Ці ёсць якія-небудзь з матрыц маюць паўтараюцца мадэлі, або яны прыгожа і наўскос, ці не можаце рабіць ніякіх здагадак аб дадзеных?

Акрамя таго, не подматрица павінны быць сумежнымі? Ці ўтрымоўвае S

F3 = 1 3
     7 9
0
дададзена
Матрыца павінна быць бесперапыннай і сабрана і іншая інфармацыя ў мяне ёсць дадаць яго ў ніжняй частцы гэтай праблемы.
дададзена аўтар Jason, крыніца

Гэта можна зрабіць у 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) аналагічна слізгальнае сярэдняе.

Другая частка разлічваецца як звычайна ў O (SizeOf (F)), якая менш, чым O (N * M).

Third part is the most interesting. It's convolution which can be calculated in O(N*M*(logN+logM)) using Fast Fourier Transform: http://en.wikipedia.org/wiki/Convolution#Fast_convolution_algorithms

0
дададзена

Мой першапачатковы адказ ніжэй перапынку, думаючы пра гэта ёсць некалькі аптымізацый, гэтыя аптымізацый ставяцца да ганка арыгінальнага адказу.

Для стадыі Б) не шукаць паўнату S : вы можаце абясцэніць усе слупкі і радкі, якія не дазволілі б F , каб адпавядаць. (У прыведзеным ніжэй прыкладзе, пошук толькі верхнюю матрыцу 2х2 налева). У тых выпадках, дзе F значная частка S гэта захаваць бы значнае час.

Калі дыяпазон значэнняў, у межах S даволі нізкі, то стварэнне табліцы пошуку дазволіць значна скараціць час, неабходнае для стадыі Б).


Праца з гэтымі 2-матрыц

findmat2 inside mat1

A) Абярыце адно значэнне з меншага матрыцы:

mat4

B) знайсці яго ў большым

mat3

C) Праверце суседнія ячэйкі, каб убачыць, калі яны супадаюць

mat6 - mat5

0
дададзена
Аднак ён мае справу з матрыцай 500 * 500.
дададзена аўтар Mohamad Ali Baydoun, крыніца