Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Посоветуйте алгоритм / 4 сообщений из 4, страница 1 из 1
01.02.2009, 10:17:24
    #35790066
Begem0t!k
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посоветуйте алгоритм
Есть матрица вида
0001
1001
0011
Необходимо найти эту матрицу и все ее включения в матрицу
00011100000
11100011111
.....
Притом размер этой матрицы много больше искомой матрицы.
Вот вообщем то и все. Если искать полны перебором получается очень медленно. Подскажите есть ли какойнить мат алгоритм типа градиентного спуска
...
Рейтинг: 0 / 0
01.02.2009, 14:30:54
    #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
01.02.2009, 18:41:38
    #35790387
Begem0t!k
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Посоветуйте алгоритм
VxS_,
Размеры матрицы впринципе подходят! Посмотрю ваш алгоритм ! Спасибо!
...
Рейтинг: 0 / 0
02.02.2009, 22:15:54
    #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]