我需要一个数据结构来存储有限确定性自动机的节点，以便快速找到满足特定条件的节点(对数)。 有问题的条件如下:
I have a node
p, and I have to find a nodeq, such that:(p ∈ F ≡ q ∈ F) & (∀ a : a ∈ Σ : δ(p,a) = δ(q,a)). That is,pandqare either both final or both are not, and they have transitions to the same nodes.
我不想遍历所有节点，因为那样会很慢。显然，如果 q 具有转换的字母字符集与 p 具有转换的字符集不同，则 q 是这不是我正在寻找的节点。
此外，如果 p 和 q 有不同的转换次数，q 又不是我想要的节点。所以我在考虑一种数据结构，根据节点的最终性和转换次数对节点进行排序，这样我就不必查看所有节点，只需查看具有相同最终性和相同转换次数的节点。但这仍然不是对数的。任何想法。
我正在使用 C++。
最佳答案
节点q有两种类型的信息:
- bool 信息
(q ∈ F) (a,n)对列表使得 δ(q,a)==n(即从 q 可达的字符/目标节点对列表)
这两条信息( bool 值和对列表)可以表示为单个序列，您可以为该序列计算哈希键。
这将能够根据您感兴趣的属性对节点进行哈希处理。为给定节点 p 搜索候选节点 q 将接近 O(1) .
(对于您在评论中提到的最小化算法，这意味着您需要在每次迭代后重建此散列，因为配对中的目标节点指针将因迭代期间执行的操作而发生变化。)
关于c++ - 存储 DFA 节点的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17398928/