Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Локальный минимум

Автор: X 9.12.2005, 01:40

Всем привет! Опять нужна ваша помощь, не могу разобраться. Имеется матрица размером m на n. Надо найти количество локальных минимумов матрицы. Локальный минимум, это элемент, который меньше все соседних элементов, его окружающих.

Автор: blackofe 9.12.2005, 02:17

навскидку. Код const int MAX_X = 3; const int MAX_Y = 4; int a[MAX_X][MAX_Y] = {     {    1,    3,    12,    -9 },     {    5,    24,    0,    54 },     {    -1,    10,    4,    -4 } }; // check x+x_offset row const bool checkXrow(const int x, const int y, const int x_offset) {     // y-1 col     if(y > 0 && a[x+x_offset][y-1] < a[x][y])         return true;     // y col     if(a[x+x_offset][y] < a[x][y])         return true;     // y+1 col     if(y < MAX_Y-1 && a[x+x_offset][y+1] < a[x][y])         return true;     return false; } // if any around more, than the element(x, y), return false const bool IsLocalMin(const int x, const int y) {     // x-1 row     if(x > 0 && checkXrow(x, y, -1))         return false;     // x row     if(checkXrow(x, y, 0))         return false;     // x+1 row     if(x < MAX_X-1 && checkXrow(x, y, 1))         return false;     return true; } int main(int argc, char* argv[]) {     // print matrix     for(int i = 0; i < MAX_X; ++i) {         for(int j = 0; j < MAX_Y; ++j)             cout << a[i][j] << "\t";         cout << endl;     }     // calculate number of local minimums     int count = 0;     for(int i = 0; i < MAX_X; ++i)         for(int j = 0; j < MAX_Y; ++j)             if(IsLocalMin(i, j))                 count++;     // print number of local minimums     cout << "number of local minimums: " << count << endl;     return 0; } идея простая: перебрать все элементы и каждый проверить на вшивость - является ли он локальным минимумом (по ходу дела проверяя выход за границы массива). результат работы программы: Код 1       3       12      -9 5       24      0       54 -1      10      4       -4 number of local minimums: 4 Press any key to continue не отрицаю наличия более красивого решения. очень спешил .

Автор: sergejzr 9.12.2005, 02:25

Грубо говоря у нас 8 соседей (исключения - значения на границах) Код /*    111    101    111 */ bool isLocalMinimum(int *matrix, int y, int i, int maxX, int maxY) {   int value=matrix[x][y];  /*Проверка границы,      затем проверка соседа*/   if(x>0            &&  value>matrix[x-1][y]  ) return false;   if(y>0            &&  value>matrix[x]  [y-1]) return false;   if(x<maxX         &&  value>matrix[x+1][y]  ) return false;   if(y<maxY         &&  value>matrix[x]  [y+1]) return false;   if(y>0            &&  value>matrix[x-1][y-1]) return false;   if(x>0&&y<maxY    &&  value>matrix[x-1][y+1]) return false;   if(x<maxX&&y<maxY &&  value>matrix[x+1][y+1]) return false;   if(x<maxX&&y>0    &&  value>matrix[x+1][y-1]) return false; } Тут код можно упростить в некоторых местах, где проверки частично совпадают, но это для ярых оптимизаторов

Автор: X 9.12.2005, 02:28

Спасибо большое буду разбираться!!!

Автор: sergejzr 9.12.2005, 02:31

Вот, товарищ опередил Это конечно не алгоритм, а перебор. Если у тебя массив представляет собой двумерную функцию, существуют более "быстрые" алгоритмы поиска локальных минимумов. Почти все представляют собой спуск в обратном направлении градиента. Разница в основном в нахождении оптимальной ширины шага. Добавлено @ 02:35 Хммм. ещё можно отбрасывать "проверенные" элементы, которые точно не могут быть локальным минимумом типа как игра в "кораблики". Нашёл минимум, закрасил всех его соседей идт.

Автор: X 9.12.2005, 04:35

sergej.z мне необходимо только это: Код bool isLocalMinimum(int *matrix, int y, int i, int maxX, int maxY) {   int value=matrix[x][y];  /*Проверка границы,      затем проверка соседа*/   if(x>0            &&  value>matrix[x-1][y]  ) return false;   if(y>0            &&  value>matrix[x]  [y-1]) return false;   if(x<maxX         &&  value>matrix[x+1][y]  ) return false;   if(y<maxY         &&  value>matrix[x]  [y+1]) return false; } проверили границы и соседей, а потом что? Как найти кол-во лок. минимумов? Объясни поподробнее плиз

Автор: sergejzr 9.12.2005, 14:08

Дальше разбирать не буду. И так уже достаточно подробно. Код void findAll(int *matrix, int maxX, int maxY) {  int count=0;   for(int x=0;x<=maxX;x++)     for(int y=0;y<=maxY;y++)       if(isLocalMinimum(matrix, x, y, maxX, maxY))         {          cout<<"Local minimum "<<matrix[x][y]<<" at ("<<x<<","<<y<<")"<<endl;          count++;         }    cout<<"There are "<<count<<" local minimas in the matrix"<<endl; }

Автор: blackofe 9.12.2005, 18:59

sergej.z мой первоначальный вариант именно таким и был, просто я все это выстроил по вертикали, и мне не очень понравилось, как это выглядит. вот я и вывел проверку по горизонтали в отдельную функцию. правда из-за этого у меня получилось 9 проверок (включая проверку на себя) - заломало проверять. про "закрашивание" мысль хорошая. усложнило бы алгоритм (это ж их запоминать надо, или делать "слепок" матрицы с "закрасками"), но повысило бы эффективность.

Автор: sergejzr 9.12.2005, 19:10

Если построчно проверять, то конечно "прошедшие" уже не надо проверять будет. то есть проверка только один раз каждого квадрата. Кстати, есть алгоритм для игры в "кораблики"? ИМХО - сюда бы точно подошёл ) Конечно при случайно разбросанных кораблях - тяжело, но кое какие оптимизации при закрашивании можно сделать..

Автор: blackofe 9.12.2005, 19:24

sergej.z прошедшие проверять на "локальную минимумость" было бы не нужно, но возникла бы необходимость проверять на "прошедшесть" . т.е. "прошел? - значит на локальный минимум не проверяем". и понятно, что проверка на "прошедшесть" более быстра, чем на локальный минимум.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)