我需要从满足以下属性的所有可能的 DFA 中选择一个确定性有限自动机 (DFA)。必须选择均匀分布的 DFA。
DFA 必须具有以下四个属性:
- DFA 有 N 个节点。
- 每个节点有 2 个传出转换。
- 每个节点都可以从其他每个节点访问。
- DFA 是从所有可能性中以完全一致的随机性选择的。
我不考虑标记节点或转换。如果两个 DFA 具有相同的未标记有向图,则认为它们是相同的。
以下是三种不起作用的算法:
算法#1
- 从一组称为 A 的 N 个节点开始。
- 从 A 中选择一个节点并将其放入集合 B。
虽然集合 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 B
对于 B 中的每个节点 n
- 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
算法#2
- 从一个有 N 个顶点且没有弧的有向图开始。
- 生成 N 个顶点的随机排列以生成随机哈密顿循环,并将其添加到图中。
- 对于每个顶点,向随机选择的顶点添加一个输出弧。
算法#3
- 从一个有 N 个顶点且没有弧的有向图开始。
- 生成一个长度介于 N 和 2N 之间的随机有向循环,并将其添加到图中。
- 对于每个顶点,向随机选择的顶点添加一个输出弧。
我根据算法 #2 创建了算法 #3,但是,我不知道如何选择随机定向循环来创建均匀分布。我什至不知道这是否可能。
任何帮助将不胜感激。