由于允许循环,所以路径的集合显然可能是无限的.因此,我想以正则表达式(Kleene Algebra)的形式找到路径集.以下是一些示例:示例图.乘法表示序列,因此路径abc首先表示a,然后是b,然后是c.一组路径a(b + c + d)首先表示a,然后表示b,c或d.亚星号a *表示a重复零次或多次,a +重复一次或多次.
现在,我正在寻找一种通过算法构造这些表达式的方法.到目前为止,我想出了什么:
- 构造新的表达式树T.
- 从结束节点y开始搜索.
- 找到所有前任p到y.
- 每个p:
- 将p作为子节点添加到T中的y.
- 从p到根向后追溯树的路径.如果在此过程中找到y,则存在一个从y到p的循环.因此,p不仅是y的前身,而且 (路径)*也是p的前身.因此,请将(path)*作为p的子节点.
- 对于所有非循环前辈,以y:= p作为新的结束节点进行递归调用.
最后:
- 反转树,使其以结束节点结尾
- 将表达式树转换为表达式(直接)
不确定这是否行得通,但是,我想最坏情况下的复杂度也将超过2 ^ n.有人知道解决此问题或类似问题的算法吗?
解决方案您的算法的总体思路似乎不错.但是,我猜想在该回溯步骤中可能会有很多特殊情况需要编写代码.尤其是,我看不出该步骤在周期内解释周期的简单方法,即(path)*本身包含一个需要Kleene星的术语.
不过我有另外的建议.可以将图形转换为NFA,这将允许使用任何众所周知的算法来转换NFA变成一个正则表达式
要将图形转换为NFA:
- 将节点x设置为开始状态.
- 将节点y设置为唯一接受状态.
- 对于每个节点 a ,标记其所有传入边 a .
Let G = (V,E,r) a rooted directed graph, defined by a set of vertices V and a set of edges E with a designated root node r. The graph may contain cycles. The task: Given two vertices x and y from V, find all paths from x to y.
Since cycles are allowed, the set of paths may obviously be infinite. Therefore, I want to find the set of paths in the form of a regular expression (Kleene Algebra). Here are a few examples: Examples graphs. Multiplication means sequence, so a path abc means first a, then b, then c. A set of paths a(b+c+d) means first a, then either b, c, or d. The kleene star a* means that a is repeated zero or more, a+ that a repeated one or more times.
Now I am looking for a way to construct these expressions algorithmically. What I have come up with so far:
- Construct new expression tree T.
- Start search at end node y.
- Find all predecessors p to y.
- for each p:
- Add p as a child node to y in T.
- Backtrack the path up the tree from p towards the root. If y is found along the way, then there is a cycle from y to p. Therefore, not only is p is a predecessor to y, but (path)* is also a predecessor to p. Therefore, add (path)* as a child node to p.
- For all non-looping predecessors, recursive call with y := p as the new end node.
And finally:
- Invert tree so it ends with the end node
- Convert expression tree to expression (straightforward)
Not sure whether this will work, however, also worst case complexity will be somewhere above 2^n I guess. Does anyone know an algorithm for this or a similar problem?
解决方案The general idea of your algorithm seems sound. However, I'm guessing that there may be many special cases in that back-tracking step that you'll have to code for. In particular, I don't see an easy way for that step to account for cycles within cycles, i.e. (path)* itself contains a term that needs a Kleene star.
I have separate suggestion though. The graph could be converted to an NFA, which would allow use of any of the well known algorithms to convert the NFA into a regular expression.
To convert the graph to an NFA:
- Set node x as the start state.
- Set node y as the only accept state.
- For every node a, label all its incoming edges a.
更多推荐
在有向循环图中找到所有路径作为正则表达式
发布评论