algorithm - 寻找最大重量的子图

Question

我有一个城市区域(让我们把它想象成街道图)，其中所有街道都有一些与之相关的重量和长度。我想要做的是找到一组连接的街道，位于其他街道附近，具有最大(或接近最大)总权重 W，因为我的最大子图最多只能包含 N 条街道。

我对跨越整个图表的子图特别不感兴趣，而只对一小群具有最大或接近最大组合权重且所有街道彼此“靠近”的街道感兴趣，其中“near” 将被定义为距离集群中心不超过 X 米的街道。必须连接生成的子图。

有谁知道这个算法的名称是否存在？

也对任何解、精确解或近似解感兴趣。

为了直观地显示这一点，假设我的图表是下图中的所有街道段(十字路口到十字路口)。所以个别街道不是 A 大道，而是 10 号和 11 号之间的 A 大道，依此类推。街道的权重为 1 或 0。假设具有最大权重的一组街道位于选定的多边形中 - 我想要做的是找到这个多边形。

Answer 1

这是一个建议。将节点图中的每个顶点视为您定义的“中心”。对于每个中心C[i]，执行Dijkstra's algorithm to construct a shortest path tree以 C[i] 为原点。当树包含的顶点超过中心允许的最大值时，停止构建树。

然后令 A[i] 是与以 V[i] 为中心的树中的顶点关联的所有边的集合。结果将是具有最大权重的集合 A[i]。

Dijkstra 算法一次执行的运行时间为 O(|E[i]| + |V[i]| log |V[i]|) 对于 i第中心。这里的集合大小受距中心的最大距离限制。总成本为 sum_(i in 1..|V|) O(|E[i]| + |V[i]| log |V[i]|)。在最大允许权重允许从每个中心包含整个图的退化情况下，成本将为 O(|V| (|E| + |V| log |V|))。

我可以想到一些可能的优化来改善运行时间，但想验证这是否能解决您想到的问题。