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

Question

我们从一棵 n-ary 树开始。每个分支代表 "dependence"（即 parent 依赖于 child）。我需要找到相互独立的节点的最大总和。

递归解决方案相当简单：

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

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

现在我很难为此提供非递归解决方案。这将需要 post 顺序遍历。二叉树的迭代 post 顺序已经回答 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);
}

现在用显式堆栈模拟递归调用，一个变量充当"return register,"和goto来模拟call和return执行的跳转指示。为了清楚起见，让伪代码中的一些东西。

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，我们从函数中 return（跳出循环）除非 goto rtn 有循环：

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];

  sp = 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) return rtn_val;
    node = stk[--sp].node;
    i = stk[sp].i + 1;
    child_sum = stk[sp].child_sum + rtn_val;
  }
}

一路上我可能很容易犯错误。我手头没有编译器来做任何测试。但基本想法是合理的，结果应该非常有效。 It compiles to 33 x86 instructions.

完成其中一些操作后，摆脱 goto 的代数技巧就会陷入困境。但是有通用的自动算法可以做同样的事情。构建一个自动执行此转换的工具将相当简单。

现在 goto 已经消失，您可以将其翻译回您选择的语言。

此方法的优点是您无需弄清楚特定算法的操作语义。只需从递归表达式开始并模拟编译器所做的事情，然后用代数进行转换以获得看起来不错的形式。除了愚蠢的错误，它必须有效。

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

Calculating maximum mutually independent set of nodes with iterative approach

algorithm

graph-algorithm