大規模な (~ 300k 頂点) ランダム平面グラフ (ここでの「ランダム」は均一に分散されていることを意味します) を生成する最も効率的な方法は何ですか?
11083 次
5 に答える
7
別の可能性は、座標をランダムに選択してから、平面グラフである Delaunay Triangulation を計算することです (見た目も良い)。http://en.wikipedia.org/wiki/Delaunay_triangulationを参照してください。このような三角形分割を計算する O(n log(n)) アルゴリズムがあります。
于 2013-01-15T10:41:34.217 に答える
3
他の要件がなければ、ランダムな迷路の生成を調べると思います。グラフにサイクルが必要な場合は、単純な迷路からいくつかの壁をランダムに削除します。迷路の交点がグラフのノードになり、削除された壁がエッジになります。つまり、迷路のサイズを選択することで、ノードの数を選択できます。
迷路は通常、ある点から別の点への最大 4 つの接続を備えた 2D グリッドで行われますが、ヘックス タイルで迷路を行うことを妨げるものは何もありません。
于 2011-01-19T16:36:59.253 に答える
2
均一とは、空間に均一に分布することを意味する場合、これは、空間生態学的/進化シミュレーターの平面グラフを生成するために開発した非常に高速なアルゴリズムです。指定した予想される次数でランダムな平面グラフを生成しますが、もちろんその周りにいくつかのバリエーションがあります。代わりに、平面グラフで均一なランダム度が必要な場合は、均一な乱数に基づいて期待される次数を選択するように拡張できます。
https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py
于 2011-04-03T14:52:37.077 に答える
1
1 つの方法は、平面グラフと同様の制約 (たとえば、エッジ <= 3*頂点 - 6) を満たすランダム グラフを試行して生成し、Tarjan の平面性テスト アルゴリズムを使用して O(n) 時間で平面であるかどうかを確認することです。 . 平面でない場合は、再度生成します。ただし、これが 300K の頂点に対してどれほど効率的かはわかりません! (または、均一な確率でグラフが得られるかどうか)。
平面グラフの生成に関する文献がいくつかありますが、ここで 1 つの論文を見つけることができます:明らかに O(n^4) の実行時間を期待していたラベル付き平面グラフの生成であり、その価値もないかもしれません。おそらく、そこにある参照は、役立つ可能性のあるものを追跡するのに役立ちます.
幸運を！
于 2010-07-12T21:25:51.810 に答える