поиск "островов" на графе

[Euler7]

С точки зрения сложности оба поиска идентичны и по скорости и по памяти. Но на практике рекурсия почти всегда уступает по обоим пунктам, поскольку стек функции часто содержит много лишней информации и самой функции требуется чуть больше времени, чтобы понять продолжать вызовы или нет.
P.S. Кстати, можно и без рекурсии обход в глубину реализовать и с рекурсией в ширину :) .

[Alexu007]

Ну если вам миллиарды клеток перелопатить нада - тогда возможно и алгоритм пошустрее потребуется.

[Skeptic]

Alexu007
Программа целиком может и работает, но вытащенный фрагмент работать не будет.

Допустим, корабль начинается в ячейке (0,0). Чему будет равно х1 в этом фрагменте.

 void Detect_One_Ship_01(int x, int y)
  {
  int x1, y1;
.........................
for (int i = -1; i < 2; i++)
    {
    x1 = x + i;
...............................

Даже если допустить, что фрагмент работает, то как в приведённом фрагменте передаются координаты первой палубы? У вас просмотр всегда начинается только с ячейки $(0,0)$, и поэтому всегда будет находится только первый корабль.

Alexu007, прежде чем советовать программы всегда проверяйте их работоспособность.

[Alexu007]

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

Используется синтаксис C++

  for (int i = 0; i < Rz; i++)
     for (int j = 0; j < Rz; j++)

       if (pole_Homo[i][j] == 1)
         {
         Cx_Palube = 0;
         // вызов функции
         Detect_One_Ship_01(i, j);
         ...
         ...
         }

[arseniiv]

Skeptic в сообщении #962980 писал(а):

как может Alexu007 понять недостатки поиска в глубину, если на его просьбу объяснить это никто не откликнулся? Может быть вы поясните что такое поиск в глубину, а заодно, и в ширину?

Я же откликнулся, послал в гугл. Все ключевые слова в правильном порядке, всё ищется.

Skeptic в сообщении #962980 писал(а):

Зачем без нужды применять рекурсию? Для усложнения программы или наукообразия?

Бритва Хэнлона же.

[Alexu007]

Ну почему без нужды? Программа на сколько упрощается? Представьте сложную фигуру со множеством ответвлений. Без рекурсии нужно будет все эти места ветвлений запоминать, чтобы к ним возвращаться и продолжать обход сложной фигуры. А тут всё делается само. Цена вопроса - некоторое ухудшение быстродействия, и большая прожорливость, и то не факт. Без рекурсии потребуются дополнительные вычисления и выделение динамической памяти, что может и скушать быстродействие.

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

[arseniiv]

Alexu007 в сообщении #963503 писал(а):

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

Так они и с рекурсией запоминаются. В стеке вызовов. И, если вдруг захочется с этими запомненными что-то сделать, вы их из стека запросто не достанете. А из «явного» стека — достанете. Это раз. Упрощение обработки ошибок — это два. Этого должно хватить, ей-богу.

[Pavia]

Alexu007

Alexu007 в сообщении #963503 писал(а):

Ну почему без нужды? Программа на сколько упрощается?

Потому что это прописные истины. Достаточно знать что такое рекурсия. И что любую рекурсию можно заменить циклом со стеком. А некоторую и без стека.
Если научиться читать и понимать рекурсию, то она упрощает запись. Она скрывает часть реализации, что упрощает текст делая его более красивым.

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

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

[Null]

Pavia в сообщении #963685 писал(а):

Что касается изменения асимптотики, то известны алгоритмы с линейной сложностью.

А какой тут алгоритм можно предложить не линейной сложности от площади?

[Skeptic]

' Рекурсивная функция  перебора ячеек области и их перекраска.

' Map(n,m) - карта с областями
' old      - существующий цвет области
' new      - новый цвет области
' i, j     - точка ветвления просмотра области
' k        - количество просмотренных ячеек области

Function Region(i1,j1,old,new)                                                ' перебор ячеек области и их перекраска

   i = i1 
   j = j1   
   k = 0
    Map(i,j) = new                                                            ' перекраска ячейки
    if Map(i-1,j) = old  theh k = 1 + Region(i-1,j,old,new)   end if          ' вверх
    if Map(i,j+1) = old  theh k = 1 + Region(i,j+1,old,new)   end if          ' вправо
    if Map(i+1,j) = old  theh k = 1 + Region(i+1,j,old,new)   end if          ' вниз
    if Map(i,j-1) = old  theh k = 1 + Region(i,j-1,old,new)   end if          ' влево
    Region = k + 1                                                             ' площадь области

End Function

' Это черновик функции, требующий ограничений на значения переменных i и j.

[Alexu007]

Написал я тестовую программу на Qt C++. Размер массива 1000х1000. Посередине "паук" в виде креста, для простоты. "Паук" измеряется дважды:
1. Тупо считаются все ячейки с 1 и в них записываются 2
2. Находится первая ячейка с 1 и дальше работает рекурсия.

Время работы примерно одинаковое. При увеличении "площади паука" = количеству вызовов рекурсивной функции программа начинает аварийно вылетать, где-то свыше 43000 вызовов.

[_Ivana]

Как начинающий функциональщик, хочу отметить пару вещей:
1) как любая рекурсия разворачивается в цикл, так и любые циклы реализуются в виде рекурсии
2) рекурсию можно делать "тупо в лоб" - и тогда будет экспоненциальный расход памяти и времени -
как fib n = fib (n-1) + fib (n-2)
, а можно по уму через хвостовую рекурсию изменения некоторого объекта -
fib (a,b) = fib (b,a+b), а можно через экспоненциальные алгоритмы, увеличивающие скорость на порядки.
Так же и в этой задаче - она мне напомнила мой (изобрел давно изобретенный велосипед) алгоритм заливки контура - каждый раз переопределяем новый контейнер переменной длины (список или вектор), в который помещаем все соседние незалитые точки. Начинаем с одной точки в контейнере, потом в процессе работы алгоритма их количество сначала растет а потом уменьшается до нуля - все пиксели залили. И имеем хвостовую рекурсию или цикл, и никаких экспоненциальных рекурсивных вызовов и переполнения стека.