时间戳

首页 > 解决方案 > 相邻边对的最小生成树

algorithm - 相邻边对的最小生成树

问题描述

对于某些图，每对相邻边都有相关的成本。我希望找到一个子图，使得每个点都连接起来并且成本最小化（最小生成树）。

图，边为 AB、BC、CD 和 DA。 ABC 成本 15，BCD 成本 13，CDA 成本 63，DAB 成本 81

对于上面的例子，解决方案将包括边 AB、BC 和 CD，但不包括 DA，避免了昂贵的 CDA 和 DAB 三元组，并获得 28 分（ABC + BCD 的权重）。

为了激发这个问题，让我们想象一下，我们正在设计一个地点之间的道路网络，每当汽车在急转弯处转弯时，它就会减速。创建具有少量急弯的理想网络可能会受益于我们将节点三元组考虑在内。

我打算应用此算法的图将具有 5,000 到 20,000 个节点和 15,000 到 80,000 条边。据推测，该功能将是这种类型或类似的：

(
  nodes: [T],
  edges: [(int, int)],
  distance: (a: T, b: T, c: T) => float
) => [(int, int)]

Whereb与 和 都连接a，c但a与c不一定连接。

什么算法解决了这个问题？

感谢您提供的任何帮助。

标签： algorithmoptimizationdynamic-programminggraph-theoryminimum-spanning-tree

解决方案

二次目标似乎有足够的余地来构建用于降低 NP 硬度的小工具，尽管我目前没有证据。

由于您的图表很稀疏，我希望最大度数很小，特别是考虑到您对道路网络的评论。我建议使用以下整数编程公式：

  • 变量：对于每条边 {v, w}，有一个 0-1 变量 x(v, w) 如果 {v, w} 属于生成树则为 1，否则为 0。此外，对于每个顶点 v 和每个与 e 关联的边的非空子集 S，假设存在一个 0-1 变量 y(v, S)，如果树中与 e 关联的边的子集为 S，则该变量为 1，否则为 0 .

  • Objective: 最小化 ∑<sub>v,S ∑<sub>{u,w}⊆S distance(u, v, w) y(v, S)。

  • 初始约束：我们要求 ∑<sub>v,S y(v, S) = 1，也就是说，每个顶点都必须在树中恰好选择一个邻域。我们还要求对于每条边{v, w}满足∑<sub>v,S∋wy(v, S) = x(v, w)，即v选择的邻域必须与边是否一致存在。

  • 连通性约束：现在没有任何东西迫使求解器选择任何边。可以静态地制定连接约束，但我建议采用以下方法。到目前为止，使用约束运行求解器并计算其连通分量。如果只有一个组件，那很好，这是最佳解决方案。否则，对于每个分量 C，要求 ∑<sub>{v,w}∈E(C,V∖C) x(v, w) ≥ 1 - 也就是说，树至少包含一条边，其中一个端点位于C 和一个不在 C 中的端点——然后再试一次。

我通常使用OR-Tools，因为它是我工作的首选库，但您有很多选择。

推荐阅读