4

我有一棵树。它有一个平底。我们只对最底部的叶子感兴趣,但这大致是底部有多少叶子......

2×1600×1600×10×4×1600×10×4

那是〜13,107,200,000,000片叶子?由于大小(在每片叶子上执行的计算似乎不太可能优化到不到一秒钟),我已经放弃了访问每片叶子的想法。

所以我想我会构建一个“智能”叶子爬虫,它首先检查最“可能”的节点(基于它周围的结果)。因此,期望叶子在分支/邻居组中进行评估是合理的,但这些组的大小和分布会有所不同。

记录哪些叶子被访问过和哪些没有被访问过的最聪明的方法是什么?

4

3 回答 3

1

您没有提供很多信息,但我建议调整您的搜索算法以帮助您跟踪所看到的内容。如果您有一种按“可能性”对叶子进行排序的全局方法,那么您就不会遇到问题,因为您可以按照可能性的降序访问叶子。但如果我理解正确的话,你只是在爬山,对吧?您可以通过搜索完整的子树(例如,集群中被选为“可能”的所有 1600 x 10 x 4 叶子)并跟踪集群而不是单个叶子来减少存储需求。

听起来您的树几何形状是一致的,因此根据您的搜索工作方式,向上合并节点应该很容易......例如,跟踪所有叶子都已检查的级别 1 节点,以及何时2 级节点在您的列表中,删除子节点并保留其父节点。这也可能是选择检查内容的好方法:如果已经检查了 3 级节点的三个子节点,那么第四个也是最后一个节点可能也值得检查。

最后,一个想法:你真的,真的确定没有办法在组中排除一些解决方案(不检查每个单独的解决方案)吗?像数独这样的问题有一个天文数字般的大搜索空间,但是一个好的蛮力求解器会消除大量的可能性,而不需要检查每一个可能的 9 x 9 棋盘。鉴于您的问题的规模,这将是解决问题的最实用方法。

于 2012-09-01T20:48:45.583 回答
1

您似乎正在寻找一种快速有效(就内存使用而言)的方法来进行成员资格测试。如果是这样,并且如果您可以应对一些误报,请使用布隆过滤器

底线是:在您的数据集非常大并且您所需要的只是检查集合中是否存在特定元素并且误报的可能性很小的情况下使用布隆过滤器。

应该存在一些 Python 实现。

希望这会有所帮助。

于 2012-09-01T08:50:15.750 回答
0

也许这太明显了,但是您可以将结果存储在类似的树中。由于您的计算速度很慢,因此结果树不应过快增长。然后查找是否有给定节点的结果。

于 2012-09-01T09:24:00.020 回答