Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно.
Подскажите чего-нибудь.
_____________________________
With respect, Andrew A. Golyakoff
Здравствуйте, golyakov, Вы писали:
G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно. G>Подскажите чего-нибудь.
У рекурсивного алгоритма есть такая особенность: он просматривает одну и ту же клетку несколько раз. Выход из положения: запоминать во вспомогательном массиве уже просмотренные клетки, например, заведем еще таблицу такого же размера, и будем в ее клетках хранить номер группы, к которой относится соответствующая клетка первой таблицы. Изначально заполним всю таблицу -1. А в рекурсивной процедуре смотреть, уже были в клетке (!=-1), или еще не были(==-1).
Re[2]: Поиск связанных областей в двумерном массиве
Здравствуйте, Вадим Никулин, Вы писали:
ВН>Здравствуйте, golyakov, Вы писали:
G>>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно. G>>Подскажите чего-нибудь.
ВН>У рекурсивного алгоритма есть такая особенность: он просматривает одну и ту же клетку несколько раз. Выход из положения: запоминать во вспомогательном массиве уже просмотренные клетки, например, заведем еще таблицу такого же размера, и будем в ее клетках хранить номер группы, к которой относится соответствующая клетка первой таблицы. Изначально заполним всю таблицу -1. А в рекурсивной процедуре смотреть, уже были в клетке (!=-1), или еще не были(==-1).
А мне кажеться что никакой рекурсии не надо. Мое понимание задачи такое:
для двух заданных точек на 2D определить принадлежат ли они одному связному множеству.
Т.е. существует ли путь от одной точки к другой. Но это уже известная задача.
Решается она по моему волновым алгоритмом. Типичное применение — игрушки(когда вы
"посылаете на смерть" юнита в стратегии). И нет там никакой рекурсии.
На счет волнового алгоритма — могу упустить детали,но идея такова.
Из начальной точки начинаем момечать все соседние до тех пор пока не дойдем
до конечной точки или до конца массива.
Re[3]: Поиск связанных областей в двумерном массиве
Здравствуйте, barn_czn, Вы писали:
ВН>>У рекурсивного алгоритма есть такая особенность: он просматривает одну и ту же клетку несколько раз. Выход из положения: запоминать во вспомогательном массиве уже просмотренные клетки, например, заведем еще таблицу такого же размера, и будем в ее клетках хранить номер группы, к которой относится соответствующая клетка первой таблицы. Изначально заполним всю таблицу -1. А в рекурсивной процедуре смотреть, уже были в клетке (!=-1), или еще не были(==-1).
_>А мне кажеться что никакой рекурсии не надо. Мое понимание задачи такое: _>для двух заданных точек на 2D определить принадлежат ли они одному связному множеству. _>Т.е. существует ли путь от одной точки к другой. Но это уже известная задача. _>Решается она по моему волновым алгоритмом. Типичное применение — игрушки(когда вы _>"посылаете на смерть" юнита в стратегии). И нет там никакой рекурсии. _>На счет волнового алгоритма — могу упустить детали,но идея такова. _>Из начальной точки начинаем момечать все соседние до тех пор пока не дойдем _>до конечной точки или до конца массива.
Ну и каким образом ты предлагаешь применять этот алгоритм для поиска связных областей? Перебирать все возможные пары точек и проверять их на принадлежность одному множеству? Ужасно нерационально. Это во-первых.
А во-вторых, волновой алгоритм — рекурсивен. Так что без рекурсии тут все-таки не обойтись.
Здравствуйте, golyakov, Вы писали:
G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно. G>Подскажите чего-нибудь.
Рекурсия по одиночным элементам массива — это очень расточительно. Более разумным вариантом будет построчная рекурсия. В общих чертах: от начальной точки-затравки сразу находится целая связная строка клеток, путем поиска влево и вправо "до упора" (цикл, никакой рекурсии). В процессе такого поиска также выполняется регистрация точек-затравок над и под текущей строкой (по одной точке на связную строку). К этим точкам-затравкам снова рекурсивно применяется тот же алгоритм.
Best regards,
Андрей Тарасевич
Re[2]: Поиск связанных областей в двумерном массиве
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Рекурсия по одиночным элементам массива — это очень расточительно. Более разумным вариантом будет построчная рекурсия. В общих чертах: от начальной точки-затравки сразу находится целая связная строка клеток, путем поиска влево и вправо "до упора" (цикл, никакой рекурсии). В процессе такого поиска также выполняется регистрация точек-затравок над и под текущей строкой (по одной точке на связную строку). К этим точкам-затравкам снова рекурсивно применяется тот же алгоритм.
Я не очень понял про точки-затравки и как их искать сверху и снизу от рассматриваемой строки.
Я это понял так:
Иду по строке. Нахожу нужную точку (очевидно точку-затравку). Затем иду далее вправо (если начинал слева) и нахожу во всей строке строку связанных элементов. Затем иду далее по строке в поисках связанных элементов. В итоге после просмотра строки получаю координаты (одномерные) начал и концов нужных полосочек в данной строке. А как учесть верх и низ — непонятно . Объясните поподробнее.
_____________________________
With respect, Andrew A. Golyakoff
Здравствуйте, golyakov, Вы писали:
G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
G>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно. G>Подскажите чего-нибудь.
Попробуй волновой алгоритм со стеком и пометкой уже просмотренных точек, получается вовсе не рекурсивно.
Примерно так —
1. Берём угловую точку.
2. Если точка ещё не просмотрена довавляем её в стек.
3. если стек пустой, берём следующую точку и к пункту 2
4. берём очередную точку из стека, помечаем как просмотренную, помечаем её область.
5. просматриваем все связные не просмотренные точки вокруг этой точки и добавляем в стек
6. идём к пункту 3
Re[2]: Поиск связанных областей в двумерном массиве
Честно говоря, изложенный алгоритм преставляется странным: зачем так извращаться? Кода больше, а эффект непонятно какой. Достаточно просто вручную реализовать стек.
Re[3]: Поиск связанных областей в двумерном массиве
Здравствуйте, golyakov, Вы писали:
G>Разве этот пункт не подразумевает рекурсии? Если нет, то объясни поподробнее
Стек -- это такая структура данных, совершенно не обязательно реализовывать ее с помощью стека вызовов, достаточно взять обычный массив и хранить указатель на вершину.
То, что тебе объяснили -- это обход в глубину. Если вместо стека применять очередь, то будет обход в ширину, В рамках поставленной задачи потойдет и то и другое, разницы нет.
Re[4]: Поиск связанных областей в двумерном массиве
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 всю эту информацию можно объединить.
Далее можно второй раз (но очень быстро) отсканировать массив и заменить все номера на минимальные эквивалентные.
Re[3]: Поиск связанных областей в двумерном массиве
Здравствуйте, golyakov, Вы писали:
АТ>>Рекурсия по одиночным элементам массива — это очень расточительно. Более разумным вариантом будет построчная рекурсия. В общих чертах: от начальной точки-затравки сразу находится целая связная строка клеток, путем поиска влево и вправо "до упора" (цикл, никакой рекурсии). В процессе такого поиска также выполняется регистрация точек-затравок над и под текущей строкой (по одной точке на связную строку). К этим точкам-затравкам снова рекурсивно применяется тот же алгоритм.
G>Я не очень понял про точки-затравки и как их искать сверху и снизу от рассматриваемой строки. G>Я это понял так: G>Иду по строке. Нахожу нужную точку (очевидно точку-затравку). Затем иду далее вправо (если начинал слева) и нахожу во всей строке строку связанных элементов.
Да, именно так.
G>Затем иду далее по строке в поисках связанных элементов. В итоге после просмотра строки получаю координаты (одномерные) начал и концов нужных полосочек в данной строке.
Нет. Одновременно с тем, как ты шел по текущей строке вправо, ты должен просматривать элементы непосредственно над и под текущим элементом, стараясь при этом найти элементы, которые принадлежат связным строкам над и под текущей строкой (по одному на каждую связную группу). Эти найденные элементы заносятся в очередь и потом обрабатываются тем же самым алгоритмом.
У меня, к сожалению, сейчас не времени описать алгоритм подробнее. Чуть позже приведу пример и объясню детальнее.
Best regards,
Андрей Тарасевич
Re[3]: Поиск связанных областей в двумерном массиве
Здравствуйте, Dimonka, Вы писали:
G>>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
G>>Написал сам через рекурсивную функцию, рассматривающую объекты вокруг себя, но это слишком медленно. G>>Подскажите чего-нибудь.
D>Попробуй волновой алгоритм со стеком и пометкой уже просмотренных точек, получается вовсе не рекурсивно.
D>Примерно так — D>1. Берём угловую точку. D>2. Если точка ещё не просмотрена довавляем её в стек. D>3. если стек пустой, берём следующую точку и к пункту 2 D>4. берём очередную точку из стека, помечаем как просмотренную, помечаем её область. D>5. просматриваем все связные не просмотренные точки вокруг этой точки и добавляем в стек D>6. идём к пункту 3
Где же тут "нерекурсивно"? Пункты 3 и 5 реализуют классическую рекурсию.
Best regards,
Андрей Тарасевич
Re[6]: Поиск связанных областей в двумерном массиве
Здравствуйте, Dimonka, Вы писали:
D>Здравствуйте, Beta, Вы писали:
mab>>>Если вместо стека применять очередь, то будет обход в ширину, В рамках поставленной задачи потойдет и то и другое, разницы нет.
B>>Оба они рекурсивны.
D>
Рекурсия — это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.
D>В нашем варианте ничего подобного не происходит за счёт использования стека.
Это совершенно неверное определение. Это определние синтаксически рекурсивной процедуры или функции на некотором языке программирования, а не определение рекурсивного алгоритма. В алгоритме нет никаких процедур и быть не может.
Рекурсивным алгоритмом, согласно узкому определению, называется реализация стратегии "разделяй и властвуй" (divide & conquer) с наличием обратного хода (т.е., другими словами, в которой в качестве хранилища отложенных задач используется стек). В более широком определении рекурсивным алгоритмом иногда назвают вообще все алгоритмы, реализующие стратегию "разделяй и властвуй".
Проще говоря, если в алгоритме используется какое-то хранилище отложенных задач (стек, очередь, и т.п.), пиковый размер которого не ограничен константой, то это — рекурсивный алгоритм. Приведенные алгоритмы — обход в ширину и глубину — рекурсивны.
Здравствуйте, golyakov, Вы писали:
G>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
Вообще говоря, для того, чтобы рассматривать эту задачу детально, надо сначала выяснить, что же автор задачи имел в виду под словом "найти"? Что именно надо сделать с найденной связной областью? Поместить координаты всех точек в отдельное хранилище? Или просто пометить эти точки некоторым образом в аналогичном двумерном массиве? Или еще что?
Best regards,
Андрей Тарасевич
Re[7]: Поиск связанных областей в двумерном массиве
АТ>Это совершенно неверное определение. Определение на то и определение, что верным может быть разве что синтаксически.
АТ> определние синтаксически рекурсивной процедуры или функции на некотором языке программирования, а не определение рекурсивного алгоритма. В алгоритме нет никаких процедур и быть не может.
А какую вычислительную модель алгоритмом Вы имеете в виду тогда? Видимо, Вас не устраивает, что здесь используется представление в каком-то стандартном языке высокого уровня? Но хорошо, вот дан алгоритм для машины Тьюринга, как понять, рекурсивен ли он?
АТ>Рекурсивным алгоритмом, согласно узкому определению, называется реализация стратегии "разделяй и властвуй" (divide & conquer) с наличием обратного хода (т.е., другими словами, в которой в качестве хранилища отложенных задач используется стек). В более широком определении рекурсивным алгоритмом иногда назвают вообще все алгоритмы, реализующие стратегию "разделяй и властвуй".
Боюсь, что подобным "определением" пользоваться невозможно в виду того, что оно вообще ничего не определяет.
АТ>Проще говоря, если в алгоритме используется какое-то хранилище отложенных задач (стек, очередь, и т.п.), пиковый размер которого не ограничен константой, то это — рекурсивный алгоритм. Приведенные алгоритмы — обход в ширину и глубину — рекурсивны.
Боюсь, что мало кто из людей, профессионально занимаюмающихся theoretical computer science, согласится, что обход в ширину -- рекурсивен.
Re[4]: Поиск связанных областей в двумерном массиве
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Рекрусия по отднльным элементам все равно на практике будет менее эффективной, чем рекурсия по связным строкам.
Это да. Хотя только в предположении, что строки достаточно длинные.
Короче не ясно, чего именно хочет автор вопроса.
Re[4]: Поиск связанных областей в двумерном массиве
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Нет. Одновременно с тем, как ты шел по текущей строке вправо, ты должен просматривать элементы непосредственно над и под текущим элементом, стараясь при этом найти элементы, которые принадлежат связным строкам над и под текущей строкой (по одному на каждую связную группу). Эти найденные элементы заносятся в очередь и потом обрабатываются тем же самым алгоритмом.
АТ>У меня, к сожалению, сейчас не времени описать алгоритм подробнее. Чуть позже приведу пример и объясню детальнее.
ОК. Здесь я приведу пример для вышеописанного построчно-рекурсивного алгоритма поиска области из точки-затравки, а также приведу еще один (уже не рекурсивный) алгоритм поиска областей.
Построчно-рекурсивный алгоритм поиска области
Пусть в нашем массиве присутствует вот такая связная конфигурация
Стоит заметить, что, как и в остальных предложенных здесь на текущий момент алгоритмах, для пометки уже обработанных точек нам понадобится еще один массив такого же размера.
Несложно видеть, что этот алгоритм ничем принципиально не отличается от "поэлементных" рекурсивных алгоритмов поиска в ширину или в глубину. Разница только в том, что рекурсивные шаги делаются для связных строк элементов, а не для отдельных элементов. Такой подход на практике зачастую существенно более эффективен в силу ряда причин. В частности, такой алгоритм часто применяется в качестве алгоритма заливки области на экране. При этом используется тот факт, что благодаря построчной организации видеопамяти, закраска строки пикселов "оптом" является существенно более эффективной операцией, чем закраска той же строки попиксельно. Аналогично в твоем случае, если твой массив хранится в памяти построчно, то этот алгоритм предоставляет соответствующие возможности для оптимизации (в зависимости от того, что именно тебе надо сделать с найденными элементами).
Сканирующий алгоритм поиска области
Предыдущий алгоритм более приспособлен для решения единичной задачи — найти одну связную область, содержащую данный элемент. Для решения массовой задачи, т.е. именно как сказано у тебя в условии -"найти все связные области" — больше подойдет алгоритм, основанный на применении метода сканирования. Это алгоритм сам по себе нерекурсивен.
1. Сначала находим в самой нижней строке массива (строка номер 0) все связные горизонтальные последовательности элементов. Считаем, что каждая связная последовательность является "началом" отдельной связной области
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]
Для нашего примера алгоритм продложит свою работу следующим образом
Детали реализации этого алгоритма несколько зависят от того, что же ты конкретно имел в виду под "нахождением" связной области (от этого, в частности, зависит сложность слияния двух областей). На эту тему я задал тебе отдельный вопрос в этой ветке.
Best regards,
Андрей Тарасевич
Re[8]: Поиск связанных областей в двумерном массиве
Здравствуйте, mab, Вы писали:
АТ>> определние синтаксически рекурсивной процедуры или функции на некотором языке программирования, а не определение рекурсивного алгоритма. В алгоритме нет никаких процедур и быть не может. mab>А какую вычислительную модель алгоритмом Вы имеете в виду тогда? Видимо, Вас не устраивает, что здесь используется представление в каком-то стандартном языке высокого уровня? Но хорошо, вот дан алгоритм для машины Тьюринга, как понять, рекурсивен ли он?
Ты попадаешь в ловушку, аналогичную той, в которую попал предыдущий автор. Он застрял в "процедурном" образе мышления. Ты же ушел в другую степь — машины Тьюринга. Не бывает алгоритмов "для машины Тьюринга". "Алгоритм", сформулированный в виде последовательности команд машины Тьюринга — это уже программа.
АТ>>Рекурсивным алгоритмом, согласно узкому определению, называется реализация стратегии "разделяй и властвуй" (divide & conquer) с наличием обратного хода (т.е., другими словами, в которой в качестве хранилища отложенных задач используется стек). В более широком определении рекурсивным алгоритмом иногда назвают вообще все алгоритмы, реализующие стратегию "разделяй и властвуй". mab>Боюсь, что подобным "определением" пользоваться невозможно в виду того, что оно вообще ничего не определяет.
Определяет. И определяет долстаточно хорошо. В принипе, сказанное мною, это не более чем немного расширенная цитата из Cormen и др. "Intoduction to algorithms".
АТ>>Проще говоря, если в алгоритме используется какое-то хранилище отложенных задач (стек, очередь, и т.п.), пиковый размер которого не ограничен константой, то это — рекурсивный алгоритм. Приведенные алгоритмы — обход в ширину и глубину — рекурсивны.
mab>Боюсь, что мало кто из людей, профессионально занимаюмающихся theoretical computer science, согласится, что обход в ширину -- рекурсивен.
Тут не модет быть никакого "согласится" или "не согласится". Это фопос выбора определения. Да, теоретики "по умолчанию" исползуют вышеупомянутое узкое определние реурсивного алгоритма, которое требует наличия обратного хода рекурсии. Или другими словами, отложенные задачи в рекурсивном алгоритме должны обрабатываться в порядке, обратном порядку из возникновения. В такой ситуации естественным является то, что в рекурсивном алгоритме в качестве хранилища отложенных задач используется именно стек. С точки зрения узкого определения поиск в ширину действительно нерекурсивен.
С практической точки зрения одной из основных проблем рекурсивных алгоритмов является именно само наличие характерного для стратегии 'divide & conquer' неограниченного сверху хранилища отложенных задач, котрое, во-первых, потребляет память и, во-вторых, требует накладных расходов на помещение/извлечение задачи. Является ли это хранилище стеком, очередью или чем-то еще — не играет никакой роли. Когда на практике возникает задача избавления от рекурсии, имеется в виду именно избавление от такого хранилища отложенных задач, т.е. избавление от стратегии 'divide & conquer', ибо задача избавления от рекурсии в узком определении никакой практической ценности не имеет). 'Divide & conquer' — это и есть рекурсия в более широком ее определении. Можешь считать это определение неформальным, если тебе так больше нравится.
Best regards,
Андрей Тарасевич
Re[9]: Поиск связанных областей в двумерном массиве
По-первых, спасибо за ответ.
АТ>Ты попадаешь в ловушку, аналогичную той, в которую попал предыдущий автор. Он застрял в "процедурном" образе мышления. Ты же ушел в другую степь — машины Тьюринга. Не бывает алгоритмов "для машины Тьюринга". "Алгоритм", сформулированный в виде последовательности команд машины Тьюринга — это уже программа.
Чего-то я не понял Вроде "программа для МТ" -- это как раз и определение самого понятия "алгоритм" (одно из многочисленных эквивалентных, и, в силу тезиса Черча, в некотором смысле единственное разумое).
АТ>Определяет. И определяет долстаточно хорошо. В принипе, сказанное мною, это не более чем немного расширенная цитата из Cormen и др. "Intoduction to algorithms".
Действительно, сам для себя с удивлением обнанаружил п.1.3.1. Надо будет сказать Шеню, чтобы в следующем переводе, если такой состоится, как-нибудь пояснить это место.
Вообще же не стоит зацикливаться на этой книге: она по-своему хороша (там, например, неплохо разобраны алгоритмы на графах), но по ряду аспектов содержит весьма "занятную" информацию.
АТ>>>Проще говоря, если в алгоритме используется какое-то хранилище отложенных задач (стек, очередь, и т.п.), пиковый размер которого не ограничен константой, то это — рекурсивный алгоритм. Приведенные алгоритмы — обход в ширину и глубину — рекурсивны.
Ну ты, конечно, и сам понимаешь, что и это определение так себе Потому что получается, что рекурсивен любой алгоритм, у которого объем дополнительной памяти не есть O(1). По крайней мере так это можно формализовать.
АТ>Тут не модет быть никакого "согласится" или "не согласится". Это фопос выбора определения.
Это верно.
АТ>ибо задача избавления от рекурсии в узком определении никакой практической ценности не имеет).
Не согласен: как раз таки имеет, поскольку реализация стека вручную дает выигрыш в производительности. Кроме того, размер стека вызовов вообще зависит от платформы, что нехорошо.
АТ>'Divide & conquer' — это и есть рекурсия в более широком ее определении. Можешь считать это определение неформальным, если тебе так больше нравится.
Андрей, я ни в коей мере не хочу затевать дискуссию о терминах. Мне лишь хочется, чтобы мы поняли мысль друг друга.
АТ>Сорри за опечатки. На клаве нет русских букв.
Нет проблем.
Re[5]: Поиск связанных областей в двумерном массиве
Здравствуйте, mab, Вы писали:
mab>Короче не ясно, чего именно хочет автор вопроса.
Суть задачи в следующем:
Есть ч/б картинка (в двумерном массиве). Необходимо найти размеры и координаты всех связанных "белых" (для конкретики — единиц) областей.
mab>Это да. Хотя только в предположении, что строки достаточно длинные
Нет это картинка, причем небольшая (400х300 — это максимум).
with respect, Golyakov Andrew A.
_____________________________
With respect, Andrew A. Golyakoff
Re[2]: Поиск связанных областей в двумерном массиве
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Здравствуйте, golyakov, Вы писали:
G>>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
АТ>Вообще говоря, для того, чтобы рассматривать эту задачу детально, надо сначала выяснить, что же автор задачи имел в виду под словом "найти"? Что именно надо сделать с найденной связной областью? Поместить координаты всех точек в отдельное хранилище? Или просто пометить эти точки некоторым образом в аналогичном двумерном массиве? Или еще что?
Результатом данного поиска является прямоугольная область "включающая в себя" все связанные области, количество точек в которой превышает какой-то постоянный порог iCount.
_____________________________
With respect, Andrew A. Golyakoff
Re[3]: Поиск связанных областей в двумерном массиве
Здравствуйте, golyakov, Вы писали:
G>>>Есть двумерный массив булевых элементов. Необходимо найти все связанные области (координаты их прямоугольных областей, количество элементов в связаной области). Связанными считаются элементы, расположенные слева, справа, снизу и сверху вплотную друг к другу.
АТ>>Вообще говоря, для того, чтобы рассматривать эту задачу детально, надо сначала выяснить, что же автор задачи имел в виду под словом "найти"? Что именно надо сделать с найденной связной областью? Поместить координаты всех точек в отдельное хранилище? Или просто пометить эти точки некоторым образом в аналогичном двумерном массиве? Или еще что?
G>Результатом данного поиска является прямоугольная область "включающая в себя" все связанные области, количество точек в которой превышает какой-то постоянный порог iCount.
В таком случае предложенный мною алгоритм, основанный на методе построчного сканирования, подходит для решения данной задачи идеально.
Best regards,
Андрей Тарасевич
Re[4]: Поиск связанных областей в двумерном массиве
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>В таком случае предложенный мною алгоритм, основанный на методе построчного сканирования, подходит для решения данной задачи идеально.
Благодарю за подробное изложение алгоритма.
_____________________________
With respect, Andrew A. Golyakoff
Re[5]: Поиск связанных областей в двумерном массиве
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Построчно-рекурсивный алгоритм поиска области
АТ>Сканирующий алгоритм поиска области
Спасибо за алгоритмы,
будем знать красивые решения в лицо
А как учесть верх и низ — непонятно 
. Объясните поподробнее.
Определение на то и определение, что верным может быть разве что синтаксически.
за подробное изложение алгоритма. 
