5

特定の分岐係数を持つランダム ツリー グラフを何らかの方法で生成できるかどうか知っていますか? 私はそれをk-aryツリーにしたくありません。

また、分岐係数と最大深度の両方を定義できれば素晴らしいと思います。分岐係数と深さが異なる一連の木をランダムに生成したいと考えています。

ランダムな整数入力を持つ TreePlot は、ほとんど私が望むものを返します:

TreePlot[RandomInteger[#] -> # + 1 & /@ Range[0, 100]]

TreePlot の結果

しかし、特定の分岐因子を持つツリーを取得する方法がわかりません。

ありがとう！

4

1 に答える 1

4

少し遅れたと思いますが、質問は好きです。フォームでツリーを作成する代わりに

{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}

次の形式のネストされた呼び出しを使用します。ここで、すべての引数は別のノードを表す子です。

0[1[2, 3, 4], 5]

両方の形式は同等であり、相互に変換できます。

Row[{
  TreeForm[0[1[2, 3, 4], 5]],
  TreePlot[{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}]
  }]

木

アルゴリズムの仕組みは次のとおりです。引数としてf、乱数の子を与える関数が必要で、ノードの作成時に呼び出されます。さらに、d(サブ) ツリーが持つことができる最大の深さを定義する深さがあります。

  1. [分岐を選択]f同様に呼び出すことができf[]、乱数の子を返す分岐関数を定義します。2 つまたは 4 つの子を持つツリーが必要な場合は、たとえば を使用できますf[] := RandomChoice[{2, 4}]。この関数は、ツリーで作成されたノードごとに呼び出されます。

  2. [ツリーの深さを選択] ツリーの最大の深さを選択dします。この時点で、ランダム性をツリーの生成に組み込むことを望んでいるのかわかりません。ここで行うことは、新しいノードが作成されると、その下にあるツリーの深さが、その親の深さから 1 を引いた値と 0 の間でランダムに選択されるということです。

  3. [ID カウンタの作成] 一意のカウンタ変数countを作成し、ゼロに設定します。これにより、ノード ID が増加します。新しいノードを作成すると、1 ずつ増加します。

  4. 【ノードを作成する】countノードIDとして増やして使用します。現在の深度dがゼロの場合は、ID カウントを持つリーフを返します。それ以外の場合fは、ノードが取得する子の数を決定するために呼び出します。新しい子ごとに、そのサブツリーの深さをランダムに選択し、0,...,d-1新しい子ごとに 4. を呼び出します。すべての再帰呼び出しが戻ると、ツリーが構築されます。

幸いなことに、Mathematicaのコードでは、この手順はそれほど冗長ではなく、数行しかありません。上記で説明したことをコードで見つけていただければ幸いです

With[{counter = Unique[]},
 generateTree[f_, d_] := (counter = 0; builder[f, d]);
 builder[f_, d_] := Block[
   {nodeID = counter++, childs = builder[f, #] & /@ RandomInteger[d - 1, f[]]},
   nodeID @@ childs
 ];
 builder[f_, 0] := (counter++);
]

次のようなランダムなツリーを作成できます

branching[] := RandomChoice[{2, 4}];
t = generateTree[branching, 6];
TreeForm[t]

Mathematica グラフィックス

または、次の関数を使用して、ツリーを受け入れられるものに変換することもできます。TreePlot

transformTree[tree_] := Module[{transform},
  transform[(n_Integer)[childs__]] := (Sow[
     n -> # & /@ ({childs} /. h_Integer[__] :> h)]; 
    transform /@ {childs});
  Flatten@Last@Reap[transform[tree]
]

それを使用して、多くのランダムツリーを作成します

trees = Table[generateTree[branching, depth], {depth, 3, 7}, {5}];
GraphicsGrid[Map[TreePlot[transformTree[#]] &, trees, {2}]]

Mathematica グラフィックス

于 2013-12-29T19:31:24.830 に答える