logo标签列表

生成随机确定有限自动机的算法是什么？

algorithmrandomfinite-automatadfastate-machine
4
DFA必须具备以下四个属性：

  • DFA有N个节点

  • 每个节点有2个出边。

  • 每个节点可以从任何其他节点到达。

  • DFA是从所有可能性中完全随机选择的。

这是我目前为止的翻译：
  1. 从N个节点的集合开始。
  2. 选择一个尚未被选择的节点。
  3. 将其输出连接到另外两个随机选择的节点上。
  4. 标记一个转换为1，另一个转换为0。
  5. 除非所有节点都已被选择，否则回到第2步。
  6. 确定是否存在没有入边连接的节点。
  7. 如果有，则从具有多于1个入边连接的节点中窃取一个入边连接。
  8. 否则，进入第6步，直到没有没有入边连接的节点。
然而，该算法不正确。考虑一个图，其中节点1的两个连接连接到节点2（反之亦然），而节点3的两个连接连接到节点4（反之亦然）。这类似于：

1 <==> 2

3 <==> 4

在此处，<==> 表示双向出边（总共4条边）。这似乎形成了2个团，这意味着并非每个状态都可以从任何其他状态到达。
有人知道如何完成该算法吗？或者，有人知道另一个算法吗？我似乎模糊地记得二叉树可以用来构造这个，但我不确定。
您确定要使每个节点都可以从每个节点到达吗？从起始节点到所有节点可达会更简单。 - Null Set
是的，我确定我需要所有节点都可以从每个节点访问。 - Jeff B.
一个随机构建的确定性有限自动机 (DFA)。该DFA是确定性的。它是随机选择的，从所有具有N个节点的可能DFA中完全均匀地分布。 - Jeff B.
也就是说，它是从具有我在问题中提到的四个属性的所有DFA中随机选择的。 - Jeff B.
你觉得这真的是一个图问题吗？既然下面有一个或两个图解，如果这些方法行不通，我只是好奇是否在数学社区更适合提问。 - jcolebrand
7个回答
4
强连通性是一个困难的约束条件。让我们生成均匀随机的满射转移函数，然后使用例如Tarjan的线性时间SCC算法测试它们，直到我们得到一个强连通的函数。这个过程具有正确的分布，但并不清楚它是否高效；我的研究员直觉认为，强连通性的极限概率小于1但大于0，这意味着期望只需要O(1)次迭代。
生成满射转移函数本身就很不容易。不幸的是，如果没有这个约束条件，每个状态都有一个传入转移的指数级概率。使用在这个问题的答案中描述的算法，对{(1, a), (1, b), (2, a), (2, b), …, (N, a), (N, b)}进行均匀随机划分。随机排列节点并将其分配给部分。
例如，令N = 3，并假设随机划分为：
{{(1, a), (2, a), (3, b)}, {(2, b)}, {(1, b), (3, a)}}.

我们选择了一个随机排列2，3，1，并得出了一个转移函数。
(1, a) |-> 2
(1, b) |-> 1
(2, a) |-> 2
(2, b) |-> 3
(3, a) |-> 1
(3, b) |-> 2
1
请注意，这是假设状态可区分的情况。对于不可区分的状态，请使用Brendan McKay的nauty计算自同构数量A，然后如果它是强连通的，则以1/A的概率接受该图。请注意，A几乎总是1，因此这仍然是有效的，并且在分布上与可区分状态没有太大差异。 - qrqwe
请注意，尽管Jeremiah Willcock的算法是指数时间复杂度的，但现在的计算机速度非常快，所以在你确定N太大之前，应该避免强制使用满射性。 - qrqwe
我指的是无法区分的状态。那么，你说我需要接受哪个概率为1/A的图形？是你上面给出的算法产生的图形吗？ - Jeff B.
@Jeff B. 我怀疑这一点，因为链接的算法确实需要最多k个部分的分区数量，这会破坏对称性。如果你正在使用nauty，那么nauty很可能是瓶颈。如果你放弃nauty，那么可能有更好的采样算法（但这可能最好单独提出一个问题）。 - qrqwe
@Jeff B 如果是这样，我期望有一个Boltzmann采样器可以在o(n^2)的时间内运行分区。如果速度仍然不够快，而你愿意接受更多的近似，你可以尝试MCMC。 - qrqwe
显示剩余2条评论
1
在接下来的内容中，我将使用图论的基本术语。
你可以：
  1. 从N个顶点和没有弧的有向图开始。
  2. 生成N个顶点的随机排列以产生一个随机哈密顿回路，并将其添加到图中。
  3. 对于每个顶点，添加一条指向随机选择的顶点的出弧。
结果将满足所有三个要求。
是的，我考虑过这个问题，但如果我添加一个哈密顿回路，它真的是随机的吗？我需要从所有可能性中完全均匀地选择它。 - Jeff B.
这是一个非常严格的要求。如果这确实是您需要的，您应该在问题中明确说明。 - NPE
有满足要求但没有哈密顿路径的确定有限状态自动机。考虑边为{ab,ba,bc,cb,aa,cc}的图形。 - Null Set
对于您提供的这个，一个可能性是：（ab，bc，cb，ba） - Jeff B.
特别是对于长度为N的有向环，有N^2种可能的图形（对于每个节点，我们随机选择另一个节点将其连接）。然而，对于长度为N+1的有向环，我认为结果是(N-1)*N种可能的图形（因为1个节点必须已经有2个出站连接）。 - Jeff B.
显示剩余2条评论
1
有一个预期运行时间为 O(n^{3/2}) 的算法。
如果您生成一个具有 m 个顶点的均匀随机有向图，使得每个顶点都有 k 个标记出弧（一个 k-出度有向图），则很可能在此有向图中最大的 SCC（强连通分量）的大小约为 c_k m，其中 c_k 是取决于 k 的常数。实际上，这个 SCC 的大小恰好为 c_k m（四舍五入到整数）的概率约为 1/\sqrt{m}。
因此，您可以生成一个大小为 n/c_k 的均匀随机二出度有向图，并检查最大 SCC 的大小。如果它的大小不是 n，只需重试直至成功。需要尝试的次数的期望值为 \sqrt{n}。而且，每个有向图的生成应该在 O(n) 时间内完成。因此，总体算法的预期运行时间为 O(n^{3/2})。更多详情请参见 this paper。
0

只需不断增加一组可达节点。一旦它们都可达，就填补空白。

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
    Choose a node x from set A
    Choose a node y from set B with less than two outgoing transitions.
    Choose a node z from set B
    Add a transition from y to x.
    Add a transition from x to z
    Move x to set B
For each node n in B
    While n has less than two outgoing transitions
         Choose a node m in B
         Add a transition from n to m
Choose a node to be the start node.
Choose some number of nodes to be accepting nodes.

集合B中的每个节点都可以到达集合B中的任何节点。只要一个节点可以从集合B中的一个节点到达，并且该节点可以到达集合B中的一个节点，它就可以被添加到该集合中。

@Jeff：最近添加的节点始终只有一个外向转换，因此是的，总会有y的候选项。 - Null Set
1
@templatetypedef：在我开始尝试证明之前，我们需要对什么是“不同的确定有限状态自动机”有一个清晰的定义。 - Null Set
@Jeff 图中的对称性可能会使节点的排列相等。 - Null Set
现在我想起来了，我对原始结构并不是那么确定。通过将节点强制放入集合B中，似乎进入B的第一个节点往往会有更多的连接。因此，连接的分布不会像你期望的那样近似均匀。 - Jeff B.
是的，我认为这个算法有严重的缺陷。不过，考虑到我提到的更改，aix的算法似乎几乎正确。 - Jeff B.
显示剩余6条评论
0
我能想到的最简单的方法是（均匀地）生成一个具有N个节点和每个节点两个出边的随机DFA，忽略其他约束条件，然后丢弃任何不是强连通的DFA（可以使用强连通分量算法轻松测试）。生成均匀的DFA应该很容易，没有可达性约束。唯一可能在性能方面有问题的是，在找到具有可达性属性的DFA之前需要跳过多少个DFA。不过，你应该先尝试这个算法，看看生成一个可接受的DFA需要多长时间。
0
以下参考资料似乎与您的问题相关：
F. Bassino, J. David 和 C. Nicaud，《可能不完全确定自动机的枚举和随机生成》，《纯数学与应用》19 (2-3) (2009) 1-16。
F. Bassino 和 C. Nicaud，《可访问自动机的枚举和随机生成》，《理论计算机科学》381 (2007) 86-104。
0

我们可以从N和2N之间的随机状态N1开始。

假设初始状态为状态编号1。 对于每个状态，对于输入字母表中的每个字符，我们生成一个随机转换（在1和N1之间）。

我们从初始状态开始获取连通自动机。我们检查状态数，并经过几次尝试后得到一个具有N个状态的自动机。

如果我们也希望获得最小自动机，则仅保留最终状态的分配，但是随机分配也有很大机会得到最小自动机。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接