4

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

  • DFAにはN個のノードがあります

  • 各ノードには2つの発信遷移があります。

  • 各ノードは、他のすべてのノードから到達可能です。

  • DFAは、あらゆる可能性から完全に均一なランダム性で選択されます

これは私がこれまでに持っているものです：

  1. N個のノードのコレクションから始めます。
  2. まだ選択されていないノードを選択します。
  3. その出力を他の2つのランダムに選択されたノードに接続します
  4. 一方の遷移1ともう一方の遷移0にラベルを付けます。
  5. すべてのノードが選択されていない限り、2に進みます。
  6. 着信接続のないノードがあるかどうかを確認します。
  7. その場合、複数の着信接続があるノードから着信接続を盗みます。
  8. 着信接続のないノードがない場合を除いて、6に進みます

ただし、これはアルゴリズムが正しくありません。ノード1の2つの接続がノード2（およびその逆）に接続され、ノード3の2つの接続がノード4（およびその逆）に接続されているグラフを考えてみます。それは次のようなものです：

1 <==> 2

3 <==> 4

ここで、<==>とは、双方向の2つの発信接続を意味します（つまり、合計4つの接続）。これは2つのクリークを形成しているように見えます。つまり、すべての州が他のすべての州から到達できるわけではありません。

誰かがアルゴリズムを完了する方法を知っていますか？または、誰かが別のアルゴリズムを知っていますか？二分木を使ってこれを構築できることを漠然と思い出しているようですが、それについてはよくわかりません。

4

7 に答える 7

4

強力な接続は難しい制約です。均一なランダム全射遷移関数を生成してから、強く接続されているものが得られるまで、たとえばタージャンの線形時間SCCアルゴリズムでそれらをテストしてみましょう。このプロセスには適切な配分がありますが、それが効率的であるかどうかは明らかではありません。私の研究者の直感では、強力な接続の制限確率は1未満ですが、0を超えています。これは、期待にO（1）回の反復のみが必要であることを意味します。

全射遷移関数を生成すること自体は重要です。残念ながら、その制約がなければ、すべての状態に着信遷移がある可能性は指数関数的に低くなります。この質問への回答で説明されているアルゴリズムを使用して、{（1、a）、（1、b）、（2、a）、（2、b）、…、（N、a）、 （N、b）}N個のパーツ。ノードをランダムに並べ替えて、パーツに割り当てます。

たとえば、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
于 2011-04-03T19:20:22.653 に答える
1

以下では、グラフ理論の基本的な用語を使用します。

あなたは出来る：

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

結果は、3つの要件すべてを満たします。

于 2011-04-02T20:43:53.457 に答える
1

予想される実行時間O（n ^ {3/2}）アルゴリズムがあります。

各頂点にk個のラベル付きアウトアーク（k-outダイグラフ）が含まれるように、m個の頂点を持つ均一なランダム有向グラフを生成する場合、この有向グラフの最大のSCC（強連結成分）のサイズはc_km前後である可能性が高くなります。ここで、c_kはkに依存する定数です。実際には、このSCCのサイズが正確にc_k m（整数に丸められる）である確率は約1 / \sqrt{m}です。

したがって、サイズn / c_kの均一なランダム2アウト有向グラフを生成し、最大のSCCのサイズを確認できます。サイズが正確にnでない場合は、成功するまで再試行してください。必要な試行の予想数は\sqrt{n}です。また、各有向グラフの生成はO（n）時間で実行する必要があります。したがって、合計すると、アルゴリズムは実行時間O（n ^ {3/2}）を予測しました。詳細については、このペーパーを参照してください。

于 2015-04-24T14:20:53.957 に答える
0

私が考えることができる最も簡単な方法は、Nノードとノードごとに2つの出力エッジを持つランダムDFAを（均一に）生成し、他の制約を無視して、強く接続されていないものを破棄することです（強く使用してテストするのは簡単です）連結成分アルゴリズム）。均一なDFAの生成は、到達可能性の制約なしに簡単である必要があります。パフォーマンスの面で問題となる可能性があるのは、到達可能性プロパティを持つDFAを見つける前にスキップする必要があるDFAの数です。ただし、最初にこのアルゴリズムを試して、許容可能なDFAを生成するのにかかる時間を確認する必要があります。

于 2011-04-03T19:15:24.203 に答える
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のノードに到達できる限り、セットに追加できます。

于 2011-04-02T20:48:21.570 に答える
0

Nと2Nの間のランダムな数の状態N1から始めることができます。

初期状態を状態番号1と想定します。各状態について、入力アルファベットの各文字に対して、ランダムな遷移（1とN1の間）を生成します。

connexオートマトンを初期状態から取得します。状態の数を確認し、数回試行した後、N個の状態を持つ状態を取得します。

最小限のオートマトンも必要な場合は、最終状態の割り当てのみが残りますが、ランダム割り当てでも最小限のオートマトンが取得される可能性が高くなります。

于 2012-03-30T16:03:42.297 に答える
0

次の参照はあなたの質問に関連しているようです：

F. Bassino、J。David、C。Nicaud、不完全な決定性オートマトンの列挙とランダム生成、純粋数学とアプリケーション 19（2-3）（2009）1-16。

F.バッシーノとC.ニコー。アクセス可能なオートマトンの列挙とランダム生成。理論。コンプ。Sc。。381（2007）86-104

于 2013-08-24T08:51:46.183 に答える