无向无环图中资源收集器最低运行成本求解

我们有一个无向无环图，任意两个相连节点之间仅有唯一路径，示例图如下：

图片说明 #

• 黑色数字：节点ID（每个节点都配备一个资源收集器）
• 资源收集器：每个收集器可收集相邻边上的资源（例如节点0的收集器无法触及节点1之外的资源点）。收集器运行需要燃料，燃料消耗量与其范围直接相关——范围决定了它在允许的边上能到达的最远资源点（收集器的范围对应图中部分节点的蓝色圆圈）。燃料消耗量计算公式为：fuel = radius of the circle（示例中节点0消耗1单位燃料，节点1和3各消耗2单位燃料，所有资源点均被覆盖，总燃料需求为5，节点2、5、4的半径为0，不消耗燃料）。
• 黑色线条：图的边
• 红点：资源点，我们仅知晓每条边上的资源点数量，且所有资源点在对应边上均匀分布。

任务目标 #

找到资源收集器的最优配置（即确定收集器的半径，实现覆盖所有资源点且燃料消耗最低）。

已尝试的解决方案 #

• 起初尝试定位图的“中心”节点，通过BFS遍历，同时检查下一个节点并确定燃料量，这种方法对部分图有效，但在更复杂的图中不稳定。
• 之后尝试了类似方法，但以叶子节点作为起始点，结果同样不够理想。

内容的提问来源于stack exchange，提问作者John Smith