итерационная версия простого рекурсивного алгоритма

Question

У меня довольно простой вопрос, я думаю. У меня есть эта проблема, которую очень легко решить с помощью рекурсивной функции, но которую я не смог решить итеративно.

Предположим, у вас есть логическая матрица, например:

M

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

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

Я хочу создать функцию, которая получает эту матрицу и точку, в которой хранится ноль, и которая преобразует каждый ноль в той же области в 2 (предположим, что матрица может хранить любое целое число, даже если оно изначально логическое)

(так же, как при рисовании зоны в Paint или любом графическом редакторе)

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

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

Ну, мой вопрос, как сделать это итеративно ... надеюсь, я не слишком испортил это

Заранее спасибо!

Manuel

ps: Буду признателен, если бы вы могли показать функцию в C, S, Python или псевдокоде, пожалуйста: D

Answer 1

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

Рекурсивная версия этого кода будет выглядеть (псевдокод - без проверки границ):

paint(cells, i, j) {
   if(cells[i][j] == 0) {
      cells[i][j] = 2;
      paint(cells, i+1, j);
      paint(cells, i-1, j);
      paint(cells, i, j+1);
      paint(cells, i, j-1);
   }
}

Это не просто хвостовая рекурсия (более одного рекурсивного вызова), поэтому вы должны добавить некую структуру стека для обработки промежуточной памяти. Одна версия выглядела бы так (псевдокод, java-esque, опять же, без проверки границ):

paint(cells, i, j) {
    Stack todo = new Stack();
    todo.push((i,j))
    while(!todo.isEmpty()) {
       (r, c) = todo.pop();
       if(cells[r][c] == 0) {
          cells[r][c] = 2;
          todo.push((r+1, c));
          todo.push((r-1, c));
          todo.push((r, c+1));
          todo.push((r, c-1));              
       }          
    }
}

Answer 2

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

Пример:

Рекурсивный:

listsum: N* -> N
listsum(n) ==
  if n=[] then 0 
          else hd n + listsum(tl n)

Итерация:

listsum: N* -> N
listsum(n) ==
  res = 0;
  forall i in n do
    res = res + i
  return res

Рекурсия:

treesum: Tree -> N
treesum(t) ==
  if t=nil then 0
  else let (left, node, right) = t in
    treesum(left) + node + treesum(right)

Частичная итерация (попытка):

treesum: Tree -> N
treesum(t) ==
  res = 0
  while t<>nil 
    let (left, node, right) = t in
      res = res + node + treesum(right)
      t = left
  return res

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

Итерация (со стеком):

treesum: Tree -> N
treesum(t) ==
  res = 0

  stack.push(t)
  while not stack.isempty()
    t = stack.pop()
    while t<>nil 
      let (left, node, right) = t in
        stack.pop(right)
        res = res + node + treesum(right)
        t = left

  return res

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

Answer 3

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

Псевдокод:

var s = new Stack();

s.Push( /*upper right point*/ );

while not s.Empty:

    var p = s.Pop()        
    m[ p.x ][ p.y ] = 2

    s.Push ( /*all surrounding 0 pixels*/ )

Answer 4

Для этого я бы использовал объект Stack ou Queue. Это мой псевдокод (похожий на python):

stack.push(p0)
while stack.size() > 0:
    p = stack.pop()
    matrix[p] = 2
    for each point in Arround(p):
       if matrix[point]==0:
          stack.push(point)

Answer 5

Псевдо-код:

Input: Startpoint (x,y), Array[w][h], Fillcolor f

Array[x][y] = f
bool hasChanged = false;
repeat
  for every Array[x][y] with value f:
    check if the surrounding pixels are 0, if so:
      Change them from 0 to f
      hasChanged = true
until (not hasChanged)

Answer 6

Простой способ сделать это итеративно - использовать очередь.

1. вставить начальную точку в очередь
2. получить первый элемент из очереди
3. установлен на 2
4. поставить всех соседей, которые по-прежнему 0, в очередь
5. если очередь не пуста, переходите к 2.

Answer 7

Если делать это итеративно важнее, чем производительность, я бы использовал следующий алгоритм:

1. Установить начальные 2
2. Сканирование матрицы для нахождения 0 рядом с 2
3. Если такой 0 найден, измените его на 2 и перезапустите сканирование на шаге 2.

Это легко понять и не требует стека, но занимает очень много времени.