java - 一般图中最小成本+最大匹配的算法

Question

我有一个由节点和边组成的数据集。 节点代表人，边代表人与人之间的关系，每个人都有一个使用欧氏距离计算的成本。

现在我希望通过它们各自的边将这些节点匹配在一起，这里只有一个约束:

• 任何节点只能与其他单个节点匹配。

现在我们知道我正在处理一般图，其中每个节点理论上都可以与数据集中的任何节点匹配，只要它们之间有一条边。

我想做的是找到匹配次数最多且总体成本最低的解决方案。

Node A
Node B
Node C
Node D

- Edge 1:
Start:       End      Cost
Node A       Node B   0.5

- Edge 2:
Start:       End      Cost
Node B       Node C   1

- Edge 3:
Start:       End      Cost
Node C       Node D   0.5

- Edge 2:
Start:       End      Cost
Node D       Node A   1

这个问题的解决方案如下:

• 分配边 1 和边 3，因为这是匹配的最大数量(在这种情况下，显然只有 2 个解决方案，但可能有大量分支边到其他节点)

  <

• 边 1 和边 3 被分配，因为它是具有最大匹配数量和最小总成本的解决方案 (1)

我研究了很多算法，包括 Hungarian、Blossom、Minimal-cost flow，但我不确定哪种算法最适合这种情况。此外，似乎有很多 Material 可以解决二分图中的这类问题，但在这件事上并非如此。

所以我问你:

1. 在这种情况下，哪种算法最适合返回 (a) 最大匹配数量和 (b) 最低总成本。

2. 您是否知道任何适合您推荐的算法的 Material (也许是一些易于理解的伪代码)？我不是数学符号最强的。

Answer 1

对于 (a)，最合适的算法(理论上有更快的算法，但它们更难理解)是 Edmonds 的 Blossom 算法。不幸的是，它非常复杂，但我会尽力解释其基础。

基本思想是进行匹配，并通过进行一些局部更改来不断改进它(增加匹配节点的数量)。关键概念是交替路径:从一个不匹配的节点到另一个不匹配的节点的路径，具有边在匹配中和匹配外交替的属性。

如果您有交替路径，则可以通过翻转交替路径中边的状态(无论它们是否在匹配中)来将匹配的大小增加一。

如果存在交替路径，则匹配不是最大的(因为路径为您提供了增加匹配大小的方法)，相反，您可以证明如果没有交替路径，则匹配是最大限度。因此，要找到最大匹配，您需要做的就是找到一条交替路径。

在二分图中，这很容易做到(可以用 DFS 做到)。在一般的图形中，这更复杂，这就是 Edmonds 的 Blossom 算法出现的原因。粗略地说:

• 构建一个新图，如果您可以通过首先遍历匹配中的边，然后遍历不匹配的边，从 u 到 v，则两个顶点之间有一条边。

• 在此图中，尝试找到从不匹配的顶点到具有不匹配的邻居(即原始图中的邻居)的匹配顶点的路径。

你找到的路径中的每条边对应于原始图的两条边(即匹配中的一条边和匹配中的一条边)，因此路径转换为新图中的交替行走，但这不是必然是一条交替路径(path 和 walk 的区别在于路径只使用每个顶点一次，而 walk 可以多次使用每个顶点)。

• 如果步行是一条路径，则您有一条交替路径并且完成了。

• 如果不是，则步行会多次使用某个顶点。您可以删除两次访问该顶点之间的步行部分，并获得一个新图(删除了部分顶点)。在这个新图中，您必须再次进行整个搜索，如果您在新图中找到交替路径，您可以将其“提升”到原始图的交替路径。

进入这个(关键的)最后一步的细节对于 stackoverflow 的回答来说有点太多了，但你可以在 Wikipedia 上找到更多细节。也许拥有这种高级概述有助于您理解更多数学文章。

从头开始实现将非常具有挑战性。

对于加权版本(使用欧氏距离)，埃德蒙兹算法有一个更复杂的变体可以处理权重。 Kolmogorov提供了 C++ 实现和随附的论文。这也可用于未加权的情况，因此使用此实现可能是个好主意(即使它不是在 Java 中，也应该有某种方式与之交互)。

由于您的权重基于欧几里德距离，因此可能有针对这种情况的专门算法，但我上面提到的更通用的版本也可以使用，并且可以实现。