寻找最大权重子图

Question

寻找最大权重子图

algorithmcluster-analysisgraph-theorygraph-algorithmsubgraph

5

我有一个城市区域（假设它是一张街道图），其中所有的街道都有与之相关联的权重和长度。我想要做的是找到一个连通的街道集，其位于其他街道附近，其最大（或接近最大）总权重为W，而我的最大子图只能包含最多N条街道。

我特别不感兴趣的是跨越整个图形的子图，而是只有一个小的街道簇，具有最大或接近最大的组合权重，并且所有街道都“靠近”彼此，其中“靠近”被定义为没有任何街道距离簇中心超过X米。生成的子图必须是连通的。

有人知道这个算法的名称吗？如果存在的话。

同时也对任何解决方案，精确或近似，感兴趣。

为了更形象地展示，假设我的图表是下面图片中所有街道段（交叉口到交叉口）。因此，单个街道不是Avenue A，而是在10th和11th之间的Avenue A等等。街道将具有1或0的权重。假设具有最大权重的街道集合位于所选多边形内 - 我想做的是找到这个多边形。

- kozyr

1

我建议使用一个简单的算法，选择每个节点作为中心，并使用最短路径搜索“附近街道”，返回权重最高的聚类。我猜测节点数量不会太多，可能最多只有10000个？对于这个数据大小，结果应该在几秒钟内就可以得到。你觉得呢？另外，“附近”可以定义为没有街道距离聚类中心超过X米。 - Petar Petrovic

1

假设街道在平面上是曲线，那么两条街道之间的“距离”是什么？例如，它是第一条街道上任意一点和第二条街道上任意一点之间的最小距离吗？我想你会说“是的”，那么下一个问题是：街道A和B足够“接近”，街道B和C也足够“接近”，但街道A和C却不足够“接近”，这种情况是否可行？您是否要求每对街道都足够“接近”？另外，我们可以假设当这些街道相交时，两个街道顶点之间存在一条边吗？ - j_random_hacker

@PetarPetrovic，那应该可以工作，但实际上我需要更实时的，像毫秒级别的。你有什么好的近似值吗？ - kozyr

@j_random_hacker 这里的街道是普通的城市街道。因此，如果街道很长，足够接近的距离为100米，那么A可能靠近B，B可能靠近C，但A不一定靠近C，因此它不会跨越多条街道。度量标准不是街道之间的“足够接近”，而是距离聚类中心的“足够接近”。这里的所有交叉口都将成为顶点——我所说的街道是两个交叉口之间的边缘。为简单起见，我们可以假设没有死胡同街道。 - kozyr

@kozyr：我错过了标准是“足够接近中心”的事实，抱歉，但问题仍然存在，即一堆曲线段（即您的街道）的“中心”实际上是什么。（另一方面，如果您使用交叉口等多个点的中心来定义事物，则“中心”的含义就是明确的。）同样，我仍然想知道“两条街道A和B之间的距离”是否意味着“A上任何一点与B上任何一点之间的最小距离”。 - j_random_hacker

显示剩余6条评论

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gene · Answer 1

这里有一个提议。将节点图中的每个顶点视为您定义的“中心”。对于每个中心C[i]，使用C[i]作为起点执行Dijkstra算法以构建最短路径树。当树包含距离中心超过允许的最大值的顶点时停止构建树。

然后，让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|））。

我可以想到一些可能的优化方案来提高运行时间，但是我想确认这是否解决了你所关心的问题。

- Tryer · Answer 2

这是一个整数规划的精确公式，假设您有有限数量的总街道S，并且群集的“中心”可以是有限数量的街道S之一。如果您正在查看连续欧几里得空间中的群集中心，那将带我们进入Weber Problem的领域。这仍然是可行的，但我们必须查看列生成公式。

目标函数最大化由索引为j的选定街道的权重。约束条件（1）指定选择一个中心。约束条件（2）指定对于任何潜在中心i，只选择N条街道作为邻居。约束条件（3）规定只有当相应的中心被选择时，才选择某个街道作为某个邻域的一部分。其余是二进制整数约束。

如果选择的街道作为中心计入N条街道之一，可以通过指定y_{ii} = x_i来轻松实现。

注意：如果上述公式正确或准确地捕捉到了问题，则[MIP]可以在确定N_i集合后轻松解决。

依次考虑每个i。从N_i中按权重降序选择前N个相邻街道。这是您的现有解。在遍历i时发现更好的解决方案时，请更新现有解。