gpt4 book ai didi

algorithm - 寻找最大重量的子图

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:02:28 27 4
gpt4 key购买 nike

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

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

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

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

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

最佳答案

这是一个建议。将节点图中的每个顶点视为您定义的“中心”。对于每个中心C[i],执行Dijkstra's algorithm to construct a shortest path treeC[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|))

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

关于algorithm - 寻找最大重量的子图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46882984/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com