4

以下のプロパティを満たすすべての可能な DFA から選択された決定論的有限オートマトン (DFA) を生成する必要があります。DFA は一様分布で選択する必要があります。

DFA には、次の 4 つのプロパティが必要です。

  • DFA には N 個のノードがあります。
  • 各ノードには 2 つの発信トランジションがあります。
  • 各ノードは、他のすべてのノードから到達可能です。
  • DFA は、すべての可能性から完全に均一なランダム性で選択されます。

ノードや遷移のラベル付けは考えていません。2 つの DFA に同じラベルのない有向グラフがある場合、それらは同じと見なされます。

動作しない 3 つのアルゴリズムは次のとおりです。

アルゴリズム #1

  1. A と呼ばれる N 個のノードのセットから始めます。
  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. 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

  1. N 個の頂点とアークのない有向グラフから始めます。
  2. N 個の頂点のランダム順列を生成してランダムなハミルトニアン サイクルを生成し、それをグラフに追加します。
  3. 頂点ごとに、ランダムに選択された頂点に 1 つの出力アークを追加します。

アルゴリズム #3

  1. N 個の頂点とアークのない有向グラフから始めます。
  2. N から 2N の間の長さのランダム有向サイクルを生成し、グラフに追加します。
  3. 頂点ごとに、ランダムに選択された頂点に 1 つの出力アークを追加します。

アルゴリズム #2 に基づいてアルゴリズム #3 を作成しましたが、ランダムな有向サイクルを選択して均一な分布を作成する方法がわかりません。それが可能かどうかさえわかりません。

どんな助けでも大歓迎です。

4

1 に答える 1

1

N が小さい場合 (最初の 2 つの条件を満たすアークの可能なセットが N^(2N) 個あるため、これを乱数ジェネレーターの範囲よりも小さくする必要があります)、ランダムな DFA を生成し、それを破棄することができます。到達条件を満たしていません。

于 2011-04-03T22:41:38.490 に答える