21

生成大型（约 300k 个顶点）随机平面图（这里的“随机”表示均匀分布）的最有效方法是什么？

4

5 回答 5

7

另一种可能性是随机选择坐标，然后计算 Delaunay 三角剖分，这是一个平面图（看起来也不错）。请参阅http://en.wikipedia.org/wiki/Delaunay_triangulation有 O(n log(n)) 算法来计算这样的三角剖分。

于 2013-01-15T10:41:34.217 回答
6

你看过玻尔兹曼抽样吗？请参阅 Eric Fusy 的论文“线性时间内平面图的均匀随机抽样”。该论文和实现可在他的主页上找到，该论文称可以在几秒钟内生成大小为 100K 的实例。

于 2013-05-08T08:23:54.160 回答
3

没有任何其他要求，我会说查找随机迷宫生成。如果您想要图中的循环，请从简单的迷宫中随机移除一些墙壁。迷宫中的交叉点成为图表中的节点，移除的墙壁是边缘。这意味着您可以通过选择迷宫的大小来选择节点的数量。

迷宫通常在 2d 网格上完成，从一个点到另一个点最多有 4 个连接，但没有什么能阻止你在六角瓷砖或其他东西上做迷宫。

于 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

一种方法是尝试生成一个满足与平面图类似的约束的随机图（例如，边 <= 3*vertices - 6），并使用 Tarjan 的平面性测试算法在 O(n) 时间内检查它是否是平面的. 如果不是平面，则再次生成。不过，不确定这对于 300K 顶点的效率有多高！（或者它是否甚至会为您提供具有统一概率的图形）。

有一些关于生成平面图的文献，我可以在这里找到一篇论文：Generating Labeled Planar Graphs这显然已经预期了 O(n^4) 的运行时间，并且可能也不值得。也许那里的参考资料会帮助您找到可能有帮助的东西。

祝你好运！

于 2010-07-12T21:25:51.810 回答