Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.

Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
Подскажите чего-нибудь.

Здравствуйте, golyakov, Вы писали:

G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
G>Подскажите чего-нибудь.

У рекурсивного алгоритма есть такая особенность: он просматривает одну и ту же клетку несколько раз. Выход из положения: запоминать во вспомогательном массиве уже просмотренные клетки, например, заведем еще таблицу такого же размера, и будем в ее клетках хранить номер группы, к которой относится соответствующая клетка первой таблицы. Изначально заполним всю таблицу -1. А в рекурсивной процедуре смотреть, уже были в клетке (!=-1), или еще не были(==-1).

Здравствуйте, Вадим Никулин, Вы писали:

ВН>Здравствуйте, golyakov, Вы писали:

G>>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
G>>Подскажите чего-нибудь.

ВН>У рекурсивного алгоритма есть такая особенность: он просматривает одну и ту же клетку несколько раз. Выход из положения: запоминать во вспомогательном массиве уже просмотренные клетки, например, заведем еще таблицу такого же размера, и будем в ее клетках хранить номер группы, к которой относится соответствующая клетка первой таблицы. Изначально заполним всю таблицу -1. А в рекурсивной процедуре смотреть, уже были в клетке (!=-1), или еще не были(==-1).


А мне кажеться что никакой рекурсии не надо. Мое понимание задачи такое:
для двух заданных точек на 2D определить принадлежат ли они одному связному множеству.
Т.е. существует ли путь от одной точки к другой. Но это уже известная задача.
Решается она по моему волновым алгоритмом. Типичное применение — игрушки(когда вы
"посылаете на смерть" юнита в стратегии). И нет там никакой рекурсии.
На счет волнового алгоритма — могу упустить детали,но идея такова.
Из начальной точки начинаем момечать все соседние до тех пор пока не дойдем
до конечной точки или до конца массива.

Здравствуйте, barn_czn, Вы писали:

ВН>>У рекурсивного алгоритма есть такая особенность: он просматривает одну и ту же клетку несколько раз. Выход из положения: запоминать во вспомогательном массиве уже просмотренные клетки, например, заведем еще таблицу такого же размера, и будем в ее клетках хранить номер группы, к которой относится соответствующая клетка первой таблицы. Изначально заполним всю таблицу -1. А в рекурсивной процедуре смотреть, уже были в клетке (!=-1), или еще не были(==-1).


_>А мне кажеться что никакой рекурсии не надо. Мое понимание задачи такое:
_>для двух заданных точек на 2D определить принадлежат ли они одному связному множеству.
_>Т.е. существует ли путь от одной точки к другой. Но это уже известная задача.
_>Решается она по моему волновым алгоритмом. Типичное применение — игрушки(когда вы
_>"посылаете на смерть" юнита в стратегии). И нет там никакой рекурсии.
_>На счет волнового алгоритма — могу упустить детали,но идея такова.
_>Из начальной точки начинаем момечать все соседние до тех пор пока не дойдем
_>до конечной точки или до конца массива.

Ну и каким образом ты предлагаешь применять этот алгоритм для поиска связных областей? Перебирать все возможные пары точек и проверять их на принадлежность одному множеству? Ужасно нерационально. Это во-первых.

А во-вторых, волновой алгоритм — рекурсивен. Так что без рекурсии тут все-таки не обойтись.

Здравствуйте, golyakov, Вы писали:

G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.

G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
G>Подскажите чего-нибудь.

Рекурсия по одиночным элементам массива — это очень расточительно. Более разумным вариантом будет построчная рекурсия. В общих чертах: от начальной точки-затравки сразу находится целая связная строка клеток, путем поиска влево и вправо "до упора" (цикл, никакой рекурсии). В процессе такого поиска также выполняется регистрация точек-затравок над и под текущей строкой (по одной точке на связную строку). К этим точкам-затравкам снова рекурсивно применяется тот же алгоритм.

Здравствуйте, Вадим Никулин, Вы писали:

ВН> ...А в рекурсивной процедуре...

А можно как-нибудь без рекурсии?

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Рекурсия по одиночным элементам массива — это очень расточительно. Более разумным вариантом будет построчная рекурсия. В общих чертах: от начальной точки-затравки сразу находится целая связная строка клеток, путем поиска влево и вправо "до упора" (цикл, никакой рекурсии). В процессе такого поиска также выполняется регистрация точек-затравок над и под текущей строкой (по одной точке на связную строку). К этим точкам-затравкам снова рекурсивно применяется тот же алгоритм.

Я не очень понял про точки-затравки и как их искать сверху и снизу от рассматриваемой строки.
Я это понял так:
Иду по строке. Нахожу нужную точку (очевидно точку-затравку). Затем иду далее вправо (если начинал слева) и нахожу во всей строке строку связанных элементов. Затем иду далее по строке в поисках связанных элементов. В итоге после просмотра строки получаю координаты (одномерные) начал и концов нужных полосочек в данной строке. А как учесть верх и низ — непонятно . Объясните поподробнее.

Здравствуйте, golyakov, Вы писали:

G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.

G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
G>Подскажите чего-нибудь.

Попробуй волновой алгоритм со стеком и пометкой уже просмотренных точек, получается вовсе не рекурсивно.

Примерно так —
1. Берём угловую точку.
2. Если точка ещё не просмотрена довавляем её в стек.
3. если стек пустой, берём следующую точку и к пункту 2
4. берём очередную точку из стека, помечаем как просмотренную, помечаем её область.
5. просматриваем все связные не просмотренные точки вокруг этой точки и добавляем в стек
6. идём к пункту 3

Здравствуйте, Dimonka, Вы писали:

D>5. просматриваем все связные не просмотренные точки вокруг этой точки и добавляем в стек

Разве этот пункт не подразумевает рекурсии? Если нет, то объясни поподробнее

Здравствуйте, Андрей Тарасевич, Вы писали:

Честно говоря, изложенный алгоритм преставляется странным: зачем так извращаться? Кода больше, а эффект непонятно какой. Достаточно просто вручную реализовать стек.

Здравствуйте, golyakov, Вы писали:

G>Разве этот пункт не подразумевает рекурсии? Если нет, то объясни поподробнее

Стек -- это такая структура данных, совершенно не обязательно реализовывать ее с помощью стека вызовов, достаточно взять обычный массив и хранить указатель на вершину.

То, что тебе объяснили -- это обход в глубину. Если вместо стека применять очередь, то будет обход в ширину, В рамках поставленной задачи потойдет и то и другое, разницы нет.

mab>Если вместо стека применять очередь, то будет обход в ширину, В рамках поставленной задачи потойдет и то и другое, разницы нет.

Оба они рекурсивны.

Здравствуйте, Beta, Вы писали:


mab>>Если вместо стека применять очередь, то будет обход в ширину, В рамках поставленной задачи потойдет и то и другое, разницы нет.

B>Оба они рекурсивны.

Рекурсия — это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.

В нашем варианте ничего подобного не происходит за счёт использования стека.

Здравствуйте, golyakov, Вы писали:

G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.

G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
G>Подскажите чего-нибудь.

Развивая идею Вадима Никулина, предложу следующий алгоритм:

Создадим массив int-ов с нулевыми значениями той же размерности , что и исходный и массив эквивалентных номеров областей aEq, в котором, если aEq[i]==j, то это означает, что области с номерами i и j эквивалентны, причем должно соблюдаться правило i>=j.
Ввведем функцию minEq(i), которая пробегается по цепочке эквивалентных областей, пока aEq[i]!=i и возвращает минимальную эквивалентную область.

Сканируем построчно исходный массив и для каждого элемента у которого в исходном массиве 1 делаем следующее:

Пусть left — номер области из дополнительного массива для левого соседа (его проще сохранить с предыдущего шага, чем брать непосредственно из массива) и up = minEq(номер области из дополнительного массива для верхнего соседа). Для left этого делать не надо, т.к. по алгоритму нам гарантировано, что к нам приходит minEq.

1. Если up и left 0 — присваиваем новый номер области (для примера i), а в aEq[i] заносим число i. Это же число заносим в дополнительный массив.
2. Если из up и left один 0, а другой не 0 (i) — запоминаем в дополнительном массиве ненулевй элемент.
3. Если up и left совпадают — запоминаем в дополнительном массиве этот номер.
4. Если up и left не 0 и не совпадают. Пусть минимальный из них будет i, а оставшийся j — запоминаем в дополнительном массиве i, а в aEq[j] заносим число i.

В процессе сканирования в массиве aEq можно собирать дополнительную информацию о количестве элементов и объемлющем прямоуголнике.

В конце за один проход по массиву aEq всю эту информацию можно объединить.

Далее можно второй раз (но очень быстро) отсканировать массив и заменить все номера на минимальные эквивалентные.

Здравствуйте, golyakov, Вы писали:

АТ>>Рекурсия по одиночным элементам массива — это очень расточительно. Более разумным вариантом будет построчная рекурсия. В общих чертах: от начальной точки-затравки сразу находится целая связная строка клеток, путем поиска влево и вправо "до упора" (цикл, никакой рекурсии). В процессе такого поиска также выполняется регистрация точек-затравок над и под текущей строкой (по одной точке на связную строку). К этим точкам-затравкам снова рекурсивно применяется тот же алгоритм.

G>Я не очень понял про точки-затравки и как их искать сверху и снизу от рассматриваемой строки.
G>Я это понял так:
G>Иду по строке. Нахожу нужную точку (очевидно точку-затравку). Затем иду далее вправо (если начинал слева) и нахожу во всей строке строку связанных элементов.

Да, именно так.

G>Затем иду далее по строке в поисках связанных элементов. В итоге после просмотра строки получаю координаты (одномерные) начал и концов нужных полосочек в данной строке.

Нет. Одновременно с тем, как ты шел по текущей строке вправо, ты должен просматривать элементы непосредственно над и под текущим элементом, стараясь при этом найти элементы, которые принадлежат связным строкам над и под текущей строкой (по одному на каждую связную группу). Эти найденные элементы заносятся в очередь и потом обрабатываются тем же самым алгоритмом.

У меня, к сожалению, сейчас не времени описать алгоритм подробнее. Чуть позже приведу пример и объясню детальнее.

Здравствуйте, mab, Вы писали:

mab>Честно говоря, изложенный алгоритм преставляется странным: зачем так извращаться?

Это классический алгоритм построчной заливки.

mab>Кода больше, а эффект непонятно какой. Достаточно просто вручную реализовать стек.

Рекрусия по отднльным элементам все равно на практике будет менее эффективной, чем рекурсия по связным строкам.

Здравствуйте, Dimonka, Вы писали:

G>>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.

G>>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
G>>Подскажите чего-нибудь.

D>Попробуй волновой алгоритм со стеком и пометкой уже просмотренных точек, получается вовсе не рекурсивно.

D>Примерно так —
D>1. Берём угловую точку.
D>2. Если точка ещё не просмотрена довавляем её в стек.
D>3. если стек пустой, берём следующую точку и к пункту 2
D>4. берём очередную точку из стека, помечаем как просмотренную, помечаем её область.
D>5. просматриваем все связные не просмотренные точки вокруг этой точки и добавляем в стек
D>6. идём к пункту 3

Где же тут "нерекурсивно"? Пункты 3 и 5 реализуют классическую рекурсию.

Здравствуйте, Dimonka, Вы писали:

D>Здравствуйте, Beta, Вы писали:


mab>>>Если вместо стека применять очередь, то будет обход в ширину, В рамках поставленной задачи потойдет и то и другое, разницы нет.

B>>Оба они рекурсивны.

D>

Рекурсия — это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.

D>В нашем варианте ничего подобного не происходит за счёт использования стека.

Это совершенно неверное определение. Это определние синтаксически рекурсивной процедуры или функции на некотором языке программирования, а не определение рекурсивного алгоритма. В алгоритме нет никаких процедур и быть не может.

Рекурсивным алгоритмом, согласно узкому определению, называется реализация стратегии "разделяй и властвуй" (divide & conquer) с наличием обратного хода (т.е., другими словами, в которой в качестве хранилища отложенных задач используется стек). В более широком определении рекурсивным алгоритмом иногда назвают вообще все алгоритмы, реализующие стратегию "разделяй и властвуй".

Проще говоря, если в алгоритме используется какое-то хранилище отложенных задач (стек, очередь, и т.п.), пиковый размер которого не ограничен константой, то это — рекурсивный алгоритм. Приведенные алгоритмы — обход в ширину и глубину — рекурсивны.

Здравствуйте, golyakov, Вы писали:

G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.

Вообще говоря, для того, чтобы рассматривать эту задачу детально, надо сначала выяснить, что же автор задачи имел в виду под словом "найти"? Что именно надо сделать с найденной связной областью? Поместить координаты всех точек в отдельное хранилище? Или просто пометить эти точки некоторым образом в аналогичном двумерном массиве? Или еще что?

АТ>Это совершенно неверное определение.
Определение на то и определение, что верным может быть разве что синтаксически.

АТ> определние синтаксически рекурсивной процедуры или функции на некотором языке программирования, а не определение рекурсивного алгоритма. В алгоритме нет никаких процедур и быть не может.
А какую вычислительную модель алгоритмом Вы имеете в виду тогда? Видимо, Вас не устраивает, что здесь используется представление в каком-то стандартном языке высокого уровня? Но хорошо, вот дан алгоритм для машины Тьюринга, как понять, рекурсивен ли он?

АТ>Рекурсивным алгоритмом, согласно узкому определению, называется реализация стратегии "разделяй и властвуй" (divide & conquer) с наличием обратного хода (т.е., другими словами, в которой в качестве хранилища отложенных задач используется стек). В более широком определении рекурсивным алгоритмом иногда назвают вообще все алгоритмы, реализующие стратегию "разделяй и властвуй".
Боюсь, что подобным "определением" пользоваться невозможно в виду того, что оно вообще ничего не определяет.

АТ>Проще говоря, если в алгоритме используется какое-то хранилище отложенных задач (стек, очередь, и т.п.), пиковый размер которого не ограничен константой, то это — рекурсивный алгоритм. Приведенные алгоритмы — обход в ширину и глубину — рекурсивны.

Боюсь, что мало кто из людей, профессионально занимаюмающихся theoretical computer science, согласится, что обход в ширину -- рекурсивен.