有趣的图遍历优化问题
假设您有一组节点连接成具有一个根节点的树结构，并且任何节点都可以具有任意数量的子节点。
您只能从根节点开始或从当前位置沿着直接连接遍历树。即，不能随机访问特定节点，但图的结构是已知的并且适合内存。
每个节点都有一个必须重新访问的时间，该时间不会向您透露。必须重访时间的计算方式为 [其中 i = 自上次访问以来的时间间隔]：(now + a + i*b + (i< /em>*c)^2)。对于每个节点，参数 a、b 和 c 具有不同的值，但每个参数在不同节点上通常始终处于相同的数量级内。
如果您在必须重新访问时间过后重新访问某个节点，它将重置，以便根据上述公式计算该访问之后的必须重新访问时间为 (now + a)。如果你遍历到一个节点，它会告诉你是否已经过了必须重新访问的时间，但你不会知道它是什么，也不知道 a、b 或 c 的值是什么。
您的目标是选择一种策略，随着时间的推移遍历并重新访问树中的每个节点，以便没有节点超过其必须重新访问的时间，并总体上最小化遍历操作的数量。过早重新访问节点效率低下，但超过必须重新访问时间重新访问节点效率极低。理想情况下，您希望在必须重新访问的时间之前访问每个节点，或者如果需要的话，以便遍历到另一个节点。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我不明白为什么
a、b和c是未知的。如果它们是未知的，那么最好的启发式似乎是旅行商问题，它是 NP 完全问题。所以也许我误解了一些东西。I don't understand why
a,bandcare unknown. If they are unknown then it seems that the best heuristic is the traveling salesman problem, which is NP-Complete. So maybe I'm misunderstanding something.