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 个级别)。因此，它在我的应用程序(三星的计算机视觉应用程序)中导致了许多内存消耗问题。

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

1-输入字符串:

(AC G) | (A C G J)| (AD G) | (ADGJ) | (阿德克)| ....,

哪里“|”代表替代方案。

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 个或更少的字符。