如何跟踪树遍历的进度？

Question

我有一棵树。它有一个平底。我们只对最下面的叶子感兴趣，但这大概是底部有多少片叶子。。。在

2 x 1600 x 1600 x 10 x 4 x 1600 x 10 x 4

大约13107200000000片树叶？因为它的大小（对每个叶子执行的计算似乎不太可能优化到只需要不到一秒钟的时间），我已经放弃了访问每个叶子的可能性。在

所以我在想我将构建一个“智能”叶爬虫，它首先检查最“可能”的节点（基于它周围节点的结果）。因此，我们有理由期望在相邻的分支/组中对叶子进行评估，但是组的大小和分布会有所不同。在

什么是最聪明的方法来记录哪些叶子被访问过，哪些没有访问过？在

Answer 1

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

Answer 2

你没有给出太多的信息，但我建议调整你的搜索算法，以帮助你跟踪它所看到的内容。如果你有一个按“可能性”对树叶进行全球排序的方法，你就不会有问题，因为你可以按照可能性的降序来访问树叶。但如果我没听错的话，你只是在爬山，对吧？您可以通过搜索完整的子树（例如，选择为“可能”的群集中的所有1600 x 10 x 4叶子）并跟踪群集而不是单个树叶，从而减少存储需求。在

听起来你的树几何结构是一致的，所以根据你的搜索工作方式，它应该很容易合并你的节点向上。。。e、 g.跟踪所有叶子都被检查过的1级节点，当一个2级节点的所有子节点都在您的列表中时，删除这些子节点并保留它们的父节点。这也可能是选择要检查的内容的好方法：如果已经检查了级别3节点的三个子节点，那么第四个也是最后一个节点可能也值得检查。在

最后，想一想：你真的，真的确定没有办法将某些解决方案排除在小组中（不检查每个单独的解决方案）？像数独这样的问题有一个天文般大的搜索空间，但一个好的暴力解决方案消除了大量的可能性，而没有检查每一个可能的9×9棋盘。考虑到问题的严重性，这将是最实际的解决方法。在

Answer 3

似乎您正在寻找一种快速有效（在内存使用方面）的方法来进行成员资格测试。如果是这样，如果你能处理一些误报，那就去bloom filter。在

底线是：在数据集非常大的情况下使用bloom过滤器，所有需要做的就是检查集合中是否存在特定的元素，误报的可能性很小。在

应该存在一些Python实现。在

希望这会有帮助。在