views:

136

answers:

0

Suppose you have a set of nodes connected into a tree structure with one root node and any node may have any number of child nodes.

You can only traverse the tree starting at the root node or from your current position along direct connections. I.e., no random access to a specific node, but the structure of the graph is already known and fits in memory.

Each node has a must-revisit time which is not revealed to you. The must-revisit time is calculated [where i = time interval since last visit] as (now + a + i*b + (i*c)^2). The parameters a, b and c have different values for each node but each will always generally be within the same order of magnitude across different nodes.

If you revisit a node past after its must-revisit time has passed it will reset so that the must-revisit time after that visit is calculated as (now + a) per the formula above. If you traverse to a node it will be revealed to you whether you have past the must-revisit time or not, but you will not know what it was or what the values or a, b or c are.

Your goal is to choose a strategy to traverse to and revisit each node in the tree over time so that no node is past its must-revisit time and minimize the number of traversal operations overall. Revisiting a node too early is inefficient, but revisiting a node past its must-revisit time is highly inefficient. Ideally you want to hit each node just before its must-revisit time or if you need to in order to traverse to another node.