powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Посоветуйте алгоритм
4 сообщений из 4, страница 1 из 1
Посоветуйте алгоритм
    #35790066
Begem0t!k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть матрица вида
0001
1001
0011
Необходимо найти эту матрицу и все ее включения в матрицу
00011100000
11100011111
.....
Притом размер этой матрицы много больше искомой матрицы.
Вот вообщем то и все. Если искать полны перебором получается очень медленно. Подскажите есть ли какойнить мат алгоритм типа градиентного спуска
...
Рейтинг: 0 / 0
Посоветуйте алгоритм
    #35790207
VxS_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Begem0t!kмного больше искомой матрицы.

На сколько больше? Размеры массивов уточните (а то большой массив понятие растяжимое). Вот пример перебора, аналогия полного, только проверка заканчивается при первом несоответствии:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
//---------------------------------------------------------------------------

#include <vcl.h>
#include <windows.h>
#include <iostream.h>
#include <math.h>
#pragma hdrstop

#include <tchar.h>
//---------------------------------------------------------------------------

#pragma argsused

typedef byte ChildLine[ 4 ];
ChildLine Child[]={	{ 0 , 0 , 0 , 1 },
					{ 1 , 0 , 0 , 1 },
					{ 0 , 0 , 1 , 1 }	};


typedef byte ParentLine[ 440 ];
ParentLine Parent[]={ /* Тут большой константный массив */	};
int _tmain(int argc, _TCHAR* argv[])
{
	int A=GetTickCount();
	int Parent_j=sizeof(ParentLine);
	int Parent_i=(int)(sizeof(Parent)/Parent_j);
	int Child_j=sizeof(ChildLine);
	int Child_i=(int)(sizeof(Child)/Child_j);
	for (int i= 0 ;i<Parent_i-Child_i+ 1 ;i++)
		for (int j= 0 ;j<Parent_j-Child_j+ 1 ;j++)
		{
			for (int k= 0 ;k<Child_i;k++)
			{
				bool is_this=false;
				for (int m= 0 ;m<Child_j;m++)
				{
					if (Parent[i+k][j+m]==Child[k][m])
					{
						if ((m==(Child_j- 1 ))&&(k==(Child_i- 1 )))
						{
							cout<<"Find: Coordinate: ["<<(int)i<<"]["<<(int)j<<"]"<<endl;
						} else
						if (m==(Child_j- 1 ))
						{
							is_this=true;
						}
					} else
						break;
				}
				if (!is_this)
					break;
			}
		}
	int B=GetTickCount();
	cout<<"Time for search: "<<B-A<<" ms"<<endl;
	return  0 ;
}

Процессор: Intel Pentium Dual-Core T2370 1,73 GHz
Операционная система: Windows Vista Ultimate
Размерность большого массива: 440x292
Размерность малого массива: 4x3
Скорость обработки вне отладчика порядка 10-40 ms (может и больше, все зависит от количества вхождений, чем их больше, тем дольше проверки)

Не подходит?
...
Рейтинг: 0 / 0
Посоветуйте алгоритм
    #35790387
Begem0t!k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VxS_,
Размеры матрицы впринципе подходят! Посмотрю ваш алгоритм ! Спасибо!
...
Рейтинг: 0 / 0
Посоветуйте алгоритм
    #35792575
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Begem0t!kПодскажите есть ли какойнить мат алгоритм типа градиентного спуска
:)

Если матрицы байтовые (n-байтовые), то искать "угол" командами типа REP SCASB и дальше проверять остальное.

Если матрицы битовые, то, видимо, заготовить набор масок, соответствующих всем возможным смещениям образца относительно границы байта/слова/... чтобы проверять по условиям (Value and Mask) == Template.
...
Рейтинг: 0 / 0
4 сообщений из 4, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Посоветуйте алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]