假设您有一组节点连接成一个具有一个根节点的树结构,并且任何节点都可以有任意数量的子节点。
您只能从根节点开始或沿着直接连接从当前位置开始遍历树。即,没有对特定节点的随机访问,但是图的结构是已知的并且适合内存。
每个节点都有一个必须重访的时间,这个时间不会透露给你。必须重访时间计算 [其中i = 自上次访问以来的时间间隔] 为(now + a + i *b + ( i *c)^2)。对于每个节点,参数 a、b 和 c 具有不同的值,但每个节点通常总是在不同节点的相同数量级内。
如果您在必须重访时间过去后重新访问一个节点,它将重置,以便根据上述公式计算该访问后的必须重访时间为 (now + a)。如果您遍历一个节点,它将向您显示您是否已经过了必须重访的时间,但您将不知道它是什么或值或 a、b 或 c 是什么。
您的目标是选择一种策略来遍历并随着时间的推移重新访问树中的每个节点,以便没有节点超过其必须重新访问的时间,并最大限度地减少整体遍历操作的数量。过早重访节点是低效的,但是在超过其必须重访时间后重访节点是非常低效的。理想情况下,您希望在其必须重访时间之前或如果您需要遍历每个节点以遍历另一个节点。