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

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

Это да. Хотя только в предположении, что строки достаточно длинные.
Короче не ясно, чего именно хочет автор вопроса.

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

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

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

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

Построчно-рекурсивный алгоритм поиска области

Пусть в нашем массиве присутствует вот такая связная конфигурация

---*******----
*******--**---
--******----**
****1**---***-
-***********--
--****--**-***

И пусть в качестве точки-затравки мы используем точку '1'.

Рекурсивный шаг заключается в следующем:

1. Находим всю строку элементов, содержащую текущую точку-затравку.

---*******----
*******--**--- 
--******----**
XXXX1XX---***-
-***********--
--****--**-***

2. Находим точки-затравки строго над и под найденной строкой (по одной на каждую связную строку сверху и снизу)

---*******----
*******--**--- 
--2*****----**
XXXX1XX---***-
-3**********--
--****--**-***

3. Берем очередную из найденных точек-затравок (пока они есть) и переходим к шагу 1.

Шаги 1 и 2 можно запросто совместить.

Для нашего примера алгоритм продложит свою работу следующим образом

---*******----  ---*******----  ---*******----  ---9******----
**4****--**---  **4****--**---  **4****--**---  XX4XXXX--**---
--2XXXXX----**  --2XXXXX----**  --2XXXXX----**  --2XXXXX----**
XXXX1XX---***-  XXXX1XX---***-  XXXX1XX---7**-  XXXX1XX---7**-
-3**********--  -3**********--  -3XXXXXXXXXX--  -3XXXXXXXXXX--
--****--**-***  --****--**-***  --5***--6*-8**  --5***--6*-8**

И так далее...

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

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

Сканирующий алгоритм поиска области

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

Рассмотрим его работу на таком примере

---*******----
*******--**---
--******--****
*******----**-
-*********-**-
--****--**----

Алгоритм

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

---*******----
*******--**---
--******--****
*******----**-
-*********-**-
--1111--22----

(Каждой области соответсвует своя цифра)

2. В цикле для остальных строк массива от снизу вверх (i = 1...n-1) выполняется следующее (шаги 3-4)

3. Находим все связные горизонтальные последовательности элементов в строке i

     ---*******----
     *******--**---
     --******--****
     *******----**-
     -XXXXXXXXX-XX- (i = 1)
     --1111--22----

4. Анализируем перекрытия найденных в строке i последовательностей (i-последовательностей) с последовательностями из строки i — 1 (i-1-последовательностями).

— Если найденная i-последователность прекрывается с i-1-последовательностью, принадлежащей области k, то приписываем найденную i-последовательность к области k.

— Если окажется, что какая, то из найденных i-последовательностей перекрывается c двумя (или более) i-1-последовательностями, принадлежащими различным областям k и m, то приписываем нашу i-последовательность к области k, и всю уже найденную область m тоже приписываем к области k.

— Если окажется, что какая, то из найденных i-последовательностей не перекрывается ни с одной из i-1-последовательностей, то считаем ее началом новой области

— Если окажется, что ни одна из i-1-последовательностей, принадлежащих области k, не перекрывается ни с одной из i-последовательностей, то это означает, что формирование области k завершено.

     ---*******----
     *******--**---
     --******--****
     *******----**-
     -111111111-33- (i = 1)
     --1111--11----

(Обрати внимание на слияние области 2 с областью 1 и зарождение новой области 3)

[/code]

Для нашего примера алгоритм продложит свою работу следующим образом

---*******----  ---*******----  ---*******----  ---1111111----
*******--**---  *******--**---  1111111--33---  1111111--11---
--******--****  --111111--3333  --111111--3333  --111111--1111
1111111----33-  1111111----33-  1111111----33-  1111111----11-
-111111111-33-  -111111111-33-  -111111111-33-  -111111111-11-
--1111--11----  --1111--11----  --1111--11----  --1111--11----

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

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

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

Ты попадаешь в ловушку, аналогичную той, в которую попал предыдущий автор. Он застрял в "процедурном" образе мышления. Ты же ушел в другую степь — машины Тьюринга. Не бывает алгоритмов "для машины Тьюринга". "Алгоритм", сформулированный в виде последовательности команд машины Тьюринга — это уже программа.

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

Определяет. И определяет долстаточно хорошо. В принипе, сказанное мною, это не более чем немного расширенная цитата из Cormen и др. "Intoduction to algorithms".

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

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

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

С практической точки зрения одной из основных проблем рекурсивных алгоритмов является именно само наличие характерного для стратегии 'divide & conquer' неограниченного сверху хранилища отложенных задач, котрое, во-первых, потребляет память и, во-вторых, требует накладных расходов на помещение/извлечение задачи. Является ли это хранилище стеком, очередью или чем-то еще — не играет никакой роли. Когда на практике возникает задача избавления от рекурсии, имеется в виду именно избавление от такого хранилища отложенных задач, т.е. избавление от стратегии 'divide & conquer', ибо задача избавления от рекурсии в узком определении никакой практической ценности не имеет). 'Divide & conquer' — это и есть рекурсия в более широком ее определении. Можешь считать это определение неформальным, если тебе так больше нравится.

АТ>Тут не модет быть никакого "согласится" или "не согласится". Это фопос выбора определения. Да, теоретики "по

Сорри за опечатки. На клаве нет русских букв.

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

По-первых, спасибо за ответ.

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

АТ>Определяет. И определяет долстаточно хорошо. В принипе, сказанное мною, это не более чем немного расширенная цитата из Cormen и др. "Intoduction to algorithms".
Действительно, сам для себя с удивлением обнанаружил п.1.3.1. Надо будет сказать Шеню, чтобы в следующем переводе, если такой состоится, как-нибудь пояснить это место.

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

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

АТ>Тут не модет быть никакого "согласится" или "не согласится". Это фопос выбора определения.
Это верно.

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

АТ>'Divide & conquer' — это и есть рекурсия в более широком ее определении. Можешь считать это определение неформальным, если тебе так больше нравится.

Андрей, я ни в коей мере не хочу затевать дискуссию о терминах. Мне лишь хочется, чтобы мы поняли мысль друг друга.

АТ>Сорри за опечатки. На клаве нет русских букв.
Нет проблем.

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

mab>Короче не ясно, чего именно хочет автор вопроса.

Суть задачи в следующем:
Есть ч/б картинка (в двумерном массиве). Необходимо найти размеры и координаты всех связанных "белых" (для конкретики — единиц) областей.

mab>Это да. Хотя только в предположении, что строки достаточно длинные

Нет это картинка, причем небольшая (400х300 — это максимум).

with respect, Golyakov Andrew A.

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

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

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

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

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

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

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

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

G>Результатом данного поиска является прямоугольная область "включающая в себя" все связанные области, количество точек в которой превышает какой-то постоянный порог iCount.

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

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

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

Благодарю за подробное изложение алгоритма.

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

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

АТ>Построчно-рекурсивный алгоритм поиска области

АТ>Сканирующий алгоритм поиска области

Спасибо за алгоритмы,
будем знать красивые решения в лицо