一般图的最小代价+最大匹配算法

本文关键字：匹配算法 代价 | 更新日期: 2023-09-27 18:17:09

我有一个由节点和边组成的数据集。节点代表人，边代表他们的关系，每个人都有一个用欧几里得距离计算的代价。

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

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

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

我想做的，是找到最大匹配和总体最小成本的解决方案。

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个解决方案，但可能有大量分支边到其他节点)

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

我已经研究了相当多的算法，包括Hungarian, Blossom, Minimal-cost flow，但我不确定哪种算法最适合这种情况。而且，在双偏图中，似乎有很多材料可以解决这类问题，但在这种情况下，情况并非如此。

所以我问你:

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

  2. 你知道有什么好的材料(可能是一些容易理解的伪代码)，为您推荐的算法?我不擅长数学符号。

一般图的最小代价+最大匹配算法

对于(a)，最合适的算法(理论上有更快的算法，但它们更难以理解)将是Edmonds的Blossom算法。不幸的是，它相当复杂，但我将尽我所能解释它的基础。

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

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

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

在二部图中，这是很容易做到的(它可以用DFS来完成)。在一般的图表中，这是更复杂的，这就是Edmonds的Blossom算法。粗略地讲:

  • 建立一个新图，如果你可以先遍历匹配中的边，然后遍历不匹配的边，在两个顶点之间有一条边，从u到v。

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

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

  • 如果walk是一个路径，你有一个交替的路径，完成。

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

深入这(至关重要的)最后一步的细节对于stackoverflow的答案来说有点太多了，但是你可以在维基百科上找到更多的细节，也许有这个高层次的概述可以帮助你理解更多的数学文章。

从头开始实现这个将是相当具有挑战性的。

对于加权版本(具有欧几里得距离)，有一个更复杂的Edmonds算法变体可以处理权重。Kolmogorov提供了一个c++实现和相关论文。这也可以用于未加权的情况，所以使用这个实现可能是一个好主意(即使它不在java中，也应该有一些方法与它接口)。

因为你的权重是基于欧几里得距离的，所以可能会有一个专门的算法来处理这种情况，但我上面提到的更通用的版本也可以工作，并且可以实现它。

相关文章：