如何生成均匀分布的随机 DFA？
我需要生成一个确定性有限自动机 (DFA)，从满足以下属性的所有可能的 DFA 中选择。 DFA 必须选择均匀分布的。
DFA 必须具有以下四个属性：
- DFA 有 N 个节点。
- 每个节点有 2 个传出转换。
- 每个节点都可以从其他每个节点访问。
- DFA 是从所有可能性中以完全一致的随机性选择的。
我不考虑节点或转换的标签。如果两个 DFA 具有相同的未标记有向图，则它们被认为是相同的。
以下是三种不起作用的算法：
算法#1
- 从称为 A 的 N 个节点集合开始。
- 从 A 中选择一个节点并将其放入集合 B 中。
当集合 A 中还剩下节点时
- 3.1 从集合A中选择一个节点x - 3.2 从集合 B 中选择一个少于两个外出转移的节点 y。 - 3.3 从集合B中选择一个节点z - 3.4 添加从 y 到 x 的转换。 - 3.5 添加从 x 到 z 的过渡 - 3.6 将x移动到集合B对于 B 中的每个节点 n
- 4.1 当 n 的传出转换少于两个时 - 4.2 在B中选择一个节点m - 4.3 添加从n到m的转换
对于 B算法 #2
- 从具有 N 个顶点且没有弧的有向图开始。
- 生成 N 个顶点的随机排列以产生随机哈密顿循环，并将其添加到图中。
- 对于每个顶点，将一个传出弧添加到随机选择的顶点。
算法#3
- 从具有 N 个顶点且没有弧的有向图开始。
- 生成一个长度在 N 到 2N 之间的随机有向循环并将其添加到图中。
- 对于每个顶点，将一个传出弧添加到随机选择的顶点。
我根据算法#2 创建了算法#3，但是，我不知道如何选择随机定向循环来创建均匀分布。我什至不知道这是否可能。
任何帮助将不胜感激。
I need to generate a Deterministic Finite Automata (DFA), selected from all possible DFAs that satisfy the properties below. The DFA must be selected with uniform distribution.
The DFA must have the following four properties:
- The DFA has N nodes.
- Each node has 2 outgoing transitions.
- Each node is reachable from every other node.
- The DFA is chosen with perfectly uniform randomness from all possibilities.
I am not considering labeling of nodes or transitions. If two DFAs have the same unlabeled directed graph they are considered the same.
Here are three algorithms that don't work:
Algorithm #1
- Start with a set of N nodes called A.
- Choose a node from A and put it in set B.
While there are nodes left in set A
- 3.1 Choose a node x from set A - 3.2 Choose a node y from set B with less than two outgoing transitions. - 3.3 Choose a node z from set B - 3.4 Add a transition from y to x. - 3.5 Add a transition from x to z - 3.6 Move x to set BFor each node n in B
- 4.1 While n has less than two outgoing transitions - 4.2 Choose a node m in B - 4.3 Add a transition from n to m
Algorithm #2
- Start with a directed graph with N vertices and no arcs.
- Generate a random permutation of the N vertices to produce a random Hamiltonian cycle, and add it to the graph.
- For each vertex add one outgoing arc to a randomly chosen vertex.
Algorithm #3
- Start with a directed graph with N vertices and no arcs.
- Generate a random directed cycle of some length between N and 2N and add it to the graph.
- For each vertex add one outgoing arc to a randomly chosen vertex.
I created algorithm #3 based off of algorithm #2, however, I don't know how to select the random directed cycle to create a uniform distribution. I don't even know if it's possible.
Any help would be greatly appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果 N 很小（有 N^(2N) 可能的弧集满足前两个条件，因此您希望它小于随机数生成器的范围），您可以生成随机 DFA 并丢弃那些不满足可达性条件。
If N is small (there are N^(2N) possible sets of arcs that meet the first two conditions, so you would want this to be less than the range of your random number generator) you can generate random DFAs and discard the ones that don't satisfy the reachability condition.