使用迭代方法计算最大相互独立的节点集

Question

我们从一元树开始。每个分支代表“依赖关系”（即，父母依赖于孩子）。我需要找到相互独立的节点的最大和。

递归解决方案很容易：

int calc_max()
{
    int child_max = 0;
    foreach (var n in nodes)
    {
        child_max += n.calc_max();
    }

    return Math.Max(this.value, child_max);
}

现在，我为此很难提供非递归解决方案。这将需要遍历订单。已经回答了二叉树的迭代后继订单here。但是即使有了这种解决方案，我仍然无法从此解决方案中删除递归。

Answer 1

我在SO中展示了几次答案，如何将任何递归算法转换为非递归算法。让我们再做一次。

我将使用C，因为为此目的它更清晰：

int calc_max(NODE *node) {
  int child_sum = 0;
  for (int i = 0; i < node->n_children; ++i) 
    child_sum += calc_max(node->children[i]);
  return MAX(node->value, child_sum);
}

现在使用显式堆栈，用作“返回寄存器”的变量来模拟递归调用，然后使用goto模拟由call指令执行的跳转。为了清楚起见，让一些东西在伪代码中。

int calc_max(NODE *node) {
  int rtn_val; // Simulated register for function return value.
 start:
  int child_sum = 0;
  for (int i = 0; i < node->n_children; ++i) {
    <<save params and locals on frame stack>>
    node = node->children[i];
    goto start;
   rtn:
    child_sum += rtn_val;
  }
  // Simulate using a register to return a result.
  int rtn_val = MAX(node->value, child_sum);
  if (<<frame stack isn't empty>>) {
    <<restore params and locals from frame stack>>
    goto rtn;
  }
  return rtn_val;
}

需要保存的参数和局部变量是node，i和child_sum。这样我们就可以填写伪代码。

typedef struct node {
  struct node *children[8];
  int n_children, value;
} NODE;

#define MAX(A, B) ((A) > (B) ? A : B)

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
 start:
  child_sum = 0;
  for (i = 0; i < node->n_children; ++i) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    goto start;
   rtn:
    child_sum += rtn_val;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    goto rtn;
  }
  return rtn_val;
}

这应该可以正常工作。我还没有测试。 goto并不漂亮，但是如果您愿意，可以使用一些代数将它们转换为while或for循环。步骤如下。

将for循环更改为while，并在rtn之后移动语句以在goto rtn之前执行。然后可以将rtn本身移到while之前：

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
 start:
  i = child_sum = 0;
 rtn:
  while (i < node->n_children) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    goto start;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    child_sum += rtn_val;
    ++i;
    goto rtn;
  }
  return rtn_val;
}

现在通过复制i = child_sum = 0，我们可以将goto start的目标移到rtn。

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
  i = child_sum = 0;
 rtn:
  while (i < node->n_children) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    i = child_sum = 0;
    goto rtn;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    child_sum += rtn_val;
    ++i;
    goto rtn;
  }
  return rtn_val;
}

现在注意，可以删除第一个goto rtn。没有它，while循环会执行相同的操作：

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
  i = child_sum = 0;
 rtn:
  while (i < node->n_children) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    i = child_sum = 0;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    child_sum += rtn_val;
    ++i;
    goto rtn;
  }
  return rtn_val;
}

最后，我们可以用无穷循环代替最后一个goto rtn，除非goto rtn会循环，否则可以中断：

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
  i = child_sum = 0;
  while (1) {
    while (i < node->n_children) {
      stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
      node = node->children[i];
      i = child_sum = 0;
    }
    rtn_val = MAX(node->value, child_sum);
    if (sp <= 0) break;
    --sp;
    node = stk[sp].node;
    i = stk[sp].i + 1;
    child_sum = stk[sp].child_sum + rtn_val;
  }
  return rtn_val;
}

我可能很容易在此过程中犯了一个错误。我没有编译器可以进行任何测试。但是基本思想是合理的，其结果应该非常有效。

关于此方法的好处是，您无需弄清楚操作语义。只需从递归表达式开始并模拟编译器的功能，然后使用代数进行转换即可得到看起来不错的形式。除愚蠢的错误外，它必须有效。