How to track tree traversal?

Question

I have a tree. It has a flat bottom. We are only interested in the lowest leaves, but that's about how many leaves are below ...

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

Is it ~ 13,107,200,000,000 leaves? Due to the size (the calculation performed on each sheet seems unlikely to be less than one second), I abandoned the idea that it would be possible to visit each sheet.

So, I think that I will create a “smart” leaf finder that first checks the most “likely” nodes (based on the results from those around it). Therefore, it is reasonable to expect that the leaves will be evaluated in the branches / groups of neighbors, but the groups will vary in size and distribution.

What is the smartest way to record which leaves have been visited and which have not?

Answer 1

It seems that you are looking for a fast and efficient (in terms of memory usage) way of conducting a membership test. If so, and if you can handle some false positives, go to the color filter .

Bottom line: use flowering filters in situations where your dataset is really large, and all you need to check is if there is any particular element in the dataset AND a small chance of false positives is acceptable.

Some implementation for Python must exist.

Hope this helps.

Answer 2

You do not give much information, but I would suggest setting up a search algorithm to help you keep track of what it saw. If you had a global way of ranking the leaves by "probability", you would not have a problem, since you could just visit the leaves in descending order of probability. But if I understand you correctly, you are just pretending to climb a hill, right? You can reduce storage requirements by looking for full subtrees (for example, all 1600 x 10 x 4 leaves in a cluster that were selected as "probable") and tracking clusters rather than single leaves.

It looks like your tree geometry is consistent, so depending on how your search works, it should be easy to merge your nodes up ... for example, keep an eye on level 1 nodes whose leaves have all been checked, and when all the children are level 2 node are on your list, drop the kids and keep their parents. It can also be a good way to choose what to explore: if you are exploring three children of level 3 node, then it’s probably worth considering both the fourth and the last.

Finally, the thought: are you really sure that there is no way to exclude some decisions in groups (without examining each individual)? Problems like Sudoku have astronomically large search space, but a good brute force solver eliminates large blocks of opportunity without exploring all the possible 9 x 9 boards. Given the scale of your problem, this would be the most practical way to attack it.

Answer 3

This may be too obvious, but you can save the results in a similar tree. Since your calculations are slow, the result tree should not grow too fast. Then just see if you have results for this node.