algorithm - 连接节点以最大化总边缘权重

Question

我正在研究一个可以简化为如下图优化问题的问题。

• 给出一组彩色节点。它们都是未连接的，即图中没有边。

• 要在节点之间插入边。

• 一个节点最多只能有 4 条边。

• 表格提供了边缘利润贡献的规则。

  例如，

  • 连接红色和红色的边:利润为 10

  • 连接红色和蓝色的边:利润为 20

• 节点总数在100左右。

• 颜色的总数通常在 20 到 30 种左右，但也可能高达 50 种。相应地，利润表(边缘)将是一个长列表，但不会列出所有可能的组合。表中未指定的边的利润假定为零。

问题是优化连接(边)，使总利润最大化。

我想知道这个问题，也许以其他方式，是否为人所知。如果是这样，请提供任何可能有帮助的指示。谢谢。

Answer 1

您可以将其转换为寻找最大成本的完美匹配的问题，该问题可以在多项式时间内解决(例如 using a variant of the Blossom algorithm )

转换就是将每个度数为d的节点拆分为d个左节点和d-4个右节点。

对于原图中的每一对顶点u,v，在一个未连接的顶点u左节点和一个未连接的顶点v左节点之间添加一条边，其权重等于连接u和v的利润。

接下来在每对左右节点(对于同一顶点)之间添加额外的边(权重为 0)。

现在在这个新图中构建最大权重完美匹配。

重点是额外的边用完了除了 4 个左节点之外的所有节点。这意味着每个顶点只能从 4 个有利可图的边缘中获利。

例子

假设我们有 7 个彩色节点的问题。我已经绘制了与单个绿色节点和单个红色节点部分对应的扩展图部分。

请注意，左边有 6 个绿色节点，比彩色节点总数少一个。右侧绿色节点有 2 个，比左侧节点数少 4 个。有一个单一的弯曲边连接一个绿色的左节点和一个红色的左节点。如果在完美匹配中选择这条弯曲的边缘，则意味着红色节点应该连接到绿色节点。