3

令 G = (V,E,r) 一个有根有向图，由一组顶点 V 和一组边 E 与指定的根节点 r 定义。该图可能包含循环。任务：给定 V 中的两个顶点 x 和 y，找出从 x 到 y 的所有路径。

由于允许循环，因此路径集显然可能是无限的。因此，我想以正则表达式（Kleene Algebra）的形式找到一组路径。以下是一些示例：示例图表。乘法表示序列，因此路径 abc 表示首先 a，然后是 b，然后是 c。一组路径 a(b+c+d) 表示首先是 a，然后是 b、c 或 d。kleene 星 a* 表示 a 重复零次或多次，a+ 表示 a 重复一次或多次。

现在我正在寻找一种通过算法构造这些表达式的方法。到目前为止我想出了什么：

  • 构造新的表达式树 T。
  • 在结束节点 y 处开始搜索。
  • 找到所有前辈 p 到 y。
  • 对于每个 p：
    • 将 p 作为子节点添加到 T 中的 y。
    • 回溯从 p 到根的树上的路径。如果沿途找到 y，则从 y 到 p 存在一个循环。因此，不仅 p 是 y 的前身，而且 (path)* 也是 p 的前身。因此，将 (path)* 作为子节点添加到 p。
    • 对于所有非循环的前辈，递归调用 y := p 作为新的结束节点。

最后：

  • 反转树，使其以结束节点结束
  • 将表达式树转换为表达式（直截了当）

不确定这是否可行，但是，我猜最坏情况的复杂性也会高于 2^n。有谁知道这个或类似问题的算法？

4

1 回答 1

0

您的算法的总体思路似乎是合理的。但是，我猜想在回溯步骤中可能有很多特殊情况需要您编写代码。特别是，我认为该步骤没有一种简单的方法来解释循环中的循环，即 (path)* 本身包含一个需要 Kleene 星的术语。

不过我有单独的建议。该图可以转换为 NFA，这将允许使用任何众所周知的算法将 NFA 转换为正则表达式。

要将图形转换为 NFA：

  • 将节点 x 设置为起始状态。
  • 将节点 y 设置为唯一的接受状态。
  • 对于每个节点a，标记其所有传入边a。
于 2015-11-03T16:43:05.720 回答