嗯,这是一个非常好的问题,但是你可以在那里做一些非常好的技巧。您可以将图形呈现为方阵0
,1
其中行数和列数是顶点数。每个都1
表示从行中的顶点到列中的顶点的边缘。那么每个可能的图都是一个具有 N^2 位的大二进制数,即有 2^(N^2) 个由 N 个顶点组成的可能图。现在您可以将您的问题分为两部分。
- 从中生成所有可能的图
S
- 每个图只是一个 N^2 位数。
- 然后对于每个此图,您按行和列扩展矩阵,并通过组合乘以每行和列
V
中恰好是一个的可能性。1
V
我需要你澄清一件事。你写了......并且每个顶点S
都可以有任意数量的入边和出边0 是否包含在任意数量中?然后我不明白结果应该包含来自V
和来自S
Constrain to 的所有顶点S
没有意义,因为每个S
顶点都包含在每个解决方案中,作为具有零进出边的顶点。否则,它不是所有 N^2 位数字,而是只有那些1
在每行和每列中至少有一个的数字,然后你不能将你的问题分成两部分,你必须一起S
解决V
。那么首先满足V
行和列可能会更容易(确切地说是一个1
在行和列中),然后将每个此解决方案乘以S
xS
矩阵解决方案,S
当您必须1
在行和列中至少有一个时满足约束。
您可以尝试使用各种表示作为少量顶点的列表列表。您可以array
在计算索引时尝试模块,R+C*N
或者您可以尝试数组数组。对于更大数量的顶点,使用二进制数组是可行的。你甚至可以digraph
在这里尝试模块。类似的方法很适合在 perl 中生成完整的闭包图,其中使用二进制操作很vec
糟糕。但这里似乎不是这样,因为这是一个非常不同的问题。您可能会发现一些更好的优化演示文稿,但我怀疑 Erlang 是否是非常有效地进行此类计算的最佳工具。无论如何,这里的可能性数量增长得非常快 O(2^(N^2)) 所以你不必担心大矩阵的有效存储;-)
编辑:
从这个角度看问题。V
如果您有 10 个顶点并假设它S
是空的。然后有10!
可能的图表,即 3628800。如果有的话S
,大约有2^100
1.2677e+30 个图表(如果每秒生成 1e+09 个图表,则为 4.0197e+13 年)。这意味着对于任何数量大于极少数的顶点,您都有大量可能的图。所以这里最大的问题是,你将如何处理它们。您不能存储它们,但如果是,那么您必须非常有效地存储它们。二进制字段是存储由S
. V
您可以为带顶点的边找到更有效的方法。我会将其存储为数组或列表,其中位置是边缘所在的顶点,值是边缘所在的顶点。
因此,您的解决方案在很大程度上取决于您将如何处理结果。我认为你会以某种方式过滤掉结果,因为我无法想象你会用这么多的图表做什么;-) 我的建议是在图表生成过程中尽早过滤掉有意义的图表。这意味着您的方法应根据目的确定,以使您的结果过滤参与生成算法。
关于这个问题的 Erlang 效率,如果你处理如此大量的实体(可能的图表),你必须非常小心地管理你的内存和 CPU 使用率。您可以使用 Erlang,但对于某些时间关键部分,您应该在 NIF 中使用 C。您还应该使用对内存更友好的数据结构作为二进制文件或 bignums,而不是列表或元组。您还可以找到其他一些语言,如 C、C++、OCaml、Haskell ......更适合这种内存和计算密集型任务。