Как я могу создать случайный DFA с равномерным распределением?

Question

Мне нужно сгенерировать детерминированные конечные автоматы (DFA), выбранные из всех возможных DFA, которые удовлетворяют приведенным ниже свойствам. DFA должен быть выбран с равномерным распределением.

DFA должен иметь следующие четыре свойства:

• DFA имеет N узлов.
• Каждый узел имеет 2 исходящих перехода.
• Каждый узел доступен из любого другого узла.
• DFA выбирается с абсолютно одинаковой случайностью из всех возможных.

Я не рассматриваю маркировку узлов или переходов. Если два DFA имеют одинаковый немеченый ориентированный граф, они считаются одинаковыми.

Вот три алгоритма, которые не работают:

Алгоритм # 1

1. Начните с набора из N узлов, называемых A.
2. Выберите узел из A и поместите его в набор B.

3. Пока в наборе 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
   

4. Для каждого узла n в 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
   

Алгоритм № 2

1. Начните с ориентированного графа с N вершинами и без дуг.
2. Создайте случайную перестановку из N вершин, чтобы получить случайный гамильтонов цикл, и добавьте ее в граф.
3. Для каждой вершины добавьте одну исходящую дугу к случайно выбранной вершине.

Алгоритм № 3

1. Начните с ориентированного графа с N вершинами и без дуг.
2. Создайте произвольно направленный цикл некоторой длины между N и 2N и добавьте его в график.
3. Для каждой вершины добавьте одну исходящую дугу к случайно выбранной вершине.

Я создал алгоритм № 3 на основе алгоритма № 2, однако я не знаю, как выбрать случайный направленный цикл для создания равномерного распределения. Я даже не знаю, возможно ли это.

Любая помощь будет принята с благодарностью.

Answer 1

Если N мало (есть N ^ (2N) возможных наборов дуг, которые соответствуют первым двум условиям, поэтому вы хотите, чтобы это было меньше, чем диапазон вашего генератора случайных чисел), вы можете генерировать случайные DFA и отбрасывать те, которые не удовлетворяют условию достижимости.