c - 需要图形路径抽象算法

Question

我有一个数据结构，其中包含如下图所示的图形:

在这棵树中，一个节点可以从它下面的层级中拥有任意数量的唯一子节点。图中的树代表一组路径。其中每条路径都应从级别 1 的节点开始，并以“*”标记的节点结束。所以图中树的路径是:

A then C then G

A then C then G then J

A then D then G

A then D then G the J

A then D then K, and so on...

实际上我的原始树很大(大约 200 万个序列)，每个级别的最大节点数是 61(共 11 个级别)。所以它在我的应用程序(SAMSUNG 的计算机视觉应用程序)中导致了很多内存消耗问题。

我的目标是拥有一个迭代算法，以更紧凑的字符串格式表示这些路径。所以我觉得我们把问题分为如下三个步骤。我已经构建了树数据结构(第 2 步)，但仍然无法推导出在第 3 步中从树中获取输出字符串/序列的迭代算法。

1- 输入字符串:

(A C G) | (A C G J) | (A D G) | (A D G J ) | (AD K) | ....,

其中“|”代表备选方案。

2-构建这些路径的树状数据结构。

3- 要求的输出字符串:

(A (C G [J]) | (D (G [J]) | K)) | (B ....).

哪里哪里“|”代表备选方案，“[]”包含选项。应该优化目标输出字符串，因为没有更多的共同因素可以用来进一步简化它。

Answer 1

您可以使用迭代 DFS 的修改版，它利用堆栈来跟踪未处理的节点。该算法从不会为任何一个节点在堆栈^* 中存储超过 6 个字符，并且堆栈中的节点总是少于 N 个(其中 N 是图中的节点数)。您已经指出 N 最多为 61*11=671，因此堆栈上最多可能有大约 4000 个元素。

在下面的伪代码中，“目标”节点是上面示例中的星号节点，例如G^*.

初始化:

虚拟节点 Φ 被引入，其中一条边从 Φ 到每个“根”节点，例如上面的节点 A 和 B。 Φ 的标记被假定为非打印字符，或者您可以在将其添加到输出字符串之前明确检查。调用函数前节点Φ入栈。

outString := ""
while stack not empty
   pop token
   if token is node
      outString := outString + node(token)  // Line 5 - explanation below
      if node(token) has children
         if node(token) is destination
            outString := outString + "["
            push "]"
         end
         if node(token) has multiple children
            for each child of node(token), from right to left
               push ")"
               push child
               push "("
               push "|"
            end
            pop // remove last "|"
         else
            push child
         end
      end

   else // token is ()[]|
      outString := outString + token
   end
end

此算法对于图的第一部分(A 及其子项)的输出是(为清楚起见添加了额外的空格；这些空格可以轻松添加到代码中):

A (C G [J]) | (D (G [J]) | (K))

您会注意到您的结果与我的结果之间存在偏差:在我的解决方案中，最终节点 K 括在括号中。如果这是不可取的(它可能导致丑陋，如 A[(B​​)|(C)])，您可以通过在从堆栈中弹出节点 token 时执行额外检查来消除它一些额外开销的成本。只需将上面的第 5 行替换为:

if (node(token) has no children
    AND last character of outString is "("
    AND next token on stack is ")")
      remove trailing "(" from outString
      concatenate token to outString
      pop ")" from stack and ignore
else
   outString := outString + node(token) // as above
end

如果您有任何问题或我遗漏了什么，请告诉我。

^* 这将发生在节点被写为 |[(A)] 的情况下(可能极不可能)。大多数节点将在堆栈中占用 4 个或更少的字符。